Анализ вопросов управления работой команды интеллектуальных агентов. Подход к обеспечению работы команды агентов в условиях временных ограничений (в реальном времени), основанный на комбинировании моделей приближенных вычислений и anytime-алгоритмов.
Аннотация к работе
Специфика проблемы заключается в том, что агенты, составляющие команду, обладают общими и частными навыками и собственным поведением, неполными знаниями об окружающей среде и ограниченными ресурсами. Каждый такой агент действует в динамически меняющейся среде, и его действия привязаны ко времени и пространству. (4) более сложные делиберативные архитектуры, основанные на использовании механизмов приближенных вычислений [14], “гибких” вычислений [11], делиберативного планирования вычислений [2], планирования вычислений “проектирование ко времени” [5], планирования вычислений “проектирование по критериям” [19], контрактных anytime-алгоритмов ([20], [21] и др.) и прерываемых anytime-алгоритмов ([9] и др.), которые базируются на инкрементных методах улучшения решения; Основной вопрос при организации командной работы агентов состоит в том, каким образом можно обеспечить работу агентов как единой команды в ситуации, когда каждый из агентов реализует собственные намерения с помощью индивидуальных действий, исполняемых параллельно или последовательно с действиями других агентов. Предполагается, что командная работа агентов организуется (рис.1) с помощью общего (группового) плана действий, особенности которого заключаются в следующем: (1) групповой план действий требует, чтобы команда агентов пришла к согласию выполнять предписание (множество заданных инструкций); (2) агенты должны принять на себя обязательства по отношению не только к своим индивидуальным действиям, но также к действиям других агентов и действиям группы в целом; (3) план групповой деятельности может иметь в качестве компонентов как планы индивидуальных агентов для назначенных действий, так и планы подгрупп; (4) при выполнении командной работы агенты команды должны с помощью коммуникаций прийти к согласию с предписанием, а также согласовать собственные намерения друг с другом (рис.1).Принятие решений о действиях в текущей ситуации такими агентами осуществлялось с помощью системы правил, образующих сложное дерево решений. На уровне физических действий используются модули, вырабатывающие команды управления игроком через актуаторы сервера: библиотека алгоритмов (аппроксимаций); модуль управления планом (MPMR) - для формирования управляющих воздействий на другие модули этого уровня в соответствии с планом, выбранным на среднем уровне; модуль управления движением - для управления игроком с помощью выработки соответствующей последовательности команд turn (поворот) и dash (ускорение); модуль управления ударами и пасами - для координированного управления игроком при выполнении ударов по воротам и пасов, реализуемых с помощью команды kick (удар); модуль обработки сенсорной информации - для получения информации от сервера с помощью команд sense_body (позиция тела), change_view (изменение угла обзора); модуль управления обменом - для координирующего управления приемом и передачей сообщений через канал связи с помощью команд коммуникации say (говорить) и hear (слышать). Этот уровень включает следующие модули: база знаний (БЗ) агента - для накопления и хранения планов и аппроксимаций индивидуального поведения игрока в различных игровых ситуациях; модуль мониторинга и выбора текущего плана (MPMR) - для отслеживания текущей ситуации и генерации плана действий при игре в индивидуальном режиме или выполнении сценария координации при выполнении задания в группе игроков. Сюда включены следующие модули: локальная часть распределенной БЗ - для накопления и хранения определенной для данного игрока, как члена группы, части БЗ, необходимой для выполнения своего задания при реализации сценария (включая аппроксимации); база сценариев - для накопления и хранения набора сценариев координированного поведения игрока в группе при выполнении своего задания; модуль мониторинга и выбора сценария - для отслеживания текущей ситуации и генерации сценария; модуль коммуникации - для передачи и приема сообщений от других игроков своей команды и команды противника. В качестве приближенных алгоритмов принятия решений при выборе параметров пасов (номер партнера и номер точки паса) используются следующие алгоритмы: С уменьшенным числом кандидатов паса - при незначительной потере качества паса может быть отброшено до 30-50% возможных решений, если использовать такие простые критерии выбора кандидатов, как “слишком далеко” (пас невозможен) и (или) “слишком близко” (пас не имеет смысла);В данной работе рассмотрены обобщенные модели реализации командной работы агентов, и предложены дополнительные средства обеспечения принятия решений в реальном времени.
Введение
Командная работа агентов актуальна для множества приложений (программные поисковые агенты в сети Интернет, управление коллективом совместно работающих мобильных объектов, компьютерное моделирование различных форм боевых действий, футбол роботов и т.д.).
Согласно современным представлениям, управление командной работой должно выполняться распределенными иерархическими системами с развитыми функциями координации и управления. Ключевой проблемой в таких системах является координация в реальном времени коллективного поведения членов команды, распределено решающих общую задачу. Специфика проблемы заключается в том, что агенты, составляющие команду, обладают общими и частными навыками и собственным поведением, неполными знаниями об окружающей среде и ограниченными ресурсами. При этом должны быть способны выполнить общую задачу посредством реализации индивидуальных задач и коммуникации. Каждый такой агент действует в динамически меняющейся среде, и его действия привязаны ко времени и пространству. Члены команды при выполнении запланированных операций могут объединяться в подгруппы и подчиняться лидеру (назначенному или выбранному). Они функционируют внутри антагонистической среды, которая может мешать их командным действиям.
Существует несколько подходов к описанию и формализации командной работы агентов [7]. Один их них, известный под названием “Теория общих намерений”, предложенный в работе [3], формулирует, в основном, общие рамки, определяющие командное поведение и характер взаимодействия членов команды. Второй, более формализованный подход, описанный в работе [8], известен под названием “Теория общих планов”. В работе [18] ключевые идеи обоих подходов обобщены, частично объединены и использованы при создании программного инструментария для разработки приложений в области командной работы агентов.
Одним из важнейших требований к командной работе агентов является обеспечение гарантированного решения задач в режиме реального времени (при временных ограничениях). Существующие подходы к решению проблемы обеспечения временных ограничений основываются на применении следующих архитектур: (1) реактивные архитектуры (называемые также рефлективными), в которых элементы вывода построены в виде множества пар “стимул ® реакция” ([1], [4] и др.);
(2) архитектуры, базирующиеся на использовании нескольких асинхронно действующих подсистем ([10], [15] и др.);
(3) простые “делиберативные” архитектуры (например, как в системе PRS [12]), в которой механизмы поиска определенным образом ограничены для обеспечения предсказуемости общего времени реакции (отклика) системы;
(4) более сложные делиберативные архитектуры, основанные на использовании механизмов приближенных вычислений [14], “гибких” вычислений [11], делиберативного планирования вычислений [2], планирования вычислений “проектирование ко времени” [5], планирования вычислений “проектирование по критериям” [19], контрактных anytime-алгоритмов ([20], [21] и др.) и прерываемых anytime-алгоритмов ([9] и др.), которые базируются на инкрементных методах улучшения решения;
(5) комбинированные архитектуры, построенные путем интеграции различных делиберативных механизмов планирования вычислений и других механизмов ([6], [13] и др.).
Целью настоящей статьи является разработка архитектур и моделей принятия решений, которые позволят командам агентов решать сложные поведенческие задачи в реальном времени. В статье рассмотрена обобщенная модель управления командной работой, раскрыт предлагаемый подход к обеспечению командной работы в условиях временных ограничений, представлена реализующая данный подход модель агента-футболиста, обеспечивающая симуляцию командной игры, а также кратко описана модель агента-пилота, которая может обеспечить командную работу группы беспилотных летательных аппаратов.
2. Управление командной работой
Команда агентов должна обеспечивать достижение общих целей в динамической внешней среде в присутствии шума и противодействия со стороны соперника. Командная работа есть нечто большее, чем просто скоординированное множество индивидуальных действий отдельных агентов. Принято говорить, что в командной работе агенты “сотрудничают”. Сотрудничество есть специальный вид скоординированной деятельности агентов, в которой они совместно решают некоторую задачу для достижения общей цели. Основной вопрос при организации командной работы агентов состоит в том, каким образом можно обеспечить работу агентов как единой команды в ситуации, когда каждый из агентов реализует собственные намерения с помощью индивидуальных действий, исполняемых параллельно или последовательно с действиями других агентов.
Настоящая работа базируется на идеях, изложенных в работе [18]. Предполагается, что командная работа агентов организуется (рис.1) с помощью общего (группового) плана действий, особенности которого заключаются в следующем: (1) групповой план действий требует, чтобы команда агентов пришла к согласию выполнять предписание (множество заданных инструкций); (2) агенты должны принять на себя обязательства по отношению не только к своим индивидуальным действиям, но также к действиям других агентов и действиям группы в целом; (3) план групповой деятельности может иметь в качестве компонентов как планы индивидуальных агентов для назначенных действий, так и планы подгрупп; (4) при выполнении командной работы агенты команды должны с помощью коммуникаций прийти к согласию с предписанием, а также согласовать собственные намерения друг с другом (рис.1).
Каждый агент команды должен иметь механизм для принятия решений о том, кто именно будет выполнять отдельные действия (рис.2). Агент может иметь два вида планов: полный общий план и частичный общий план.
Полный общий план детально описывает все аспекты последовательности совместных действий команды агентов, что включает совместные убеждения агентов команды и общее согласие команды выполнять совместные действия согласно некоторому исчерпывающе описанному предписанию. Это предписание содержит в себе описание множества отдельных действий и множества условий их выполнения. Полный общий план должен описывать все множество взаимосвязанных намерений и убеждений агентов, вовлеченных в команду.
Однако на практике команда не имеет полного общего плана, а располагает только частичным общим планом, который представляет собой только некоторый “срез” ментального состояния команды в частной ситуации, возникающей в процессе командной работы.
В рамках общего плана агенты могут иметь план подгруппы, в которой они должны тесно взаимодействовать при выполнении запланированной последовательности действий, а также собственные индивидуальные планы. Коммуникации агентов имеют целью восполнить условия полного общего плана. В процессе коммуникации групповые намерения согласуются с групповыми убеждениями, в результате чего вырабатывается согласие выполнять предписание по планируемой последовательности действий группы агентов. Кроме того, согласуются индивидуальные намерения и убеждения агентов подгрупп, в результате чего вырабатывается согласие выполнять предписанное агенту действие из планируемой последовательности.
Существенное влияние на качество командной работы оказывает тип и архитектура реализуемых агентов. Предполагается, что агенты могут быть гетерогенными и иметь реактивную, делиберативную или когнитивную архитектуру. Реактивные агенты реализуют командную работу в соответствии с набором правил, определяющих текущее взаимодействие агентов по типу “стимул-реакция”. Делиберативные или разумные агенты используют модель мира в символьной форме и принимают координированные решения о действиях на основе формальных рассуждений. Когнитивные агенты являются интеллектуальными агентами, построенными как когнитивные системы, имеющие нервно-системную организацию структур, функций и поведения [16]. Они решают задачи координации и выбора поведения с использованием когнитивных структур, которые способны обучаться и принимать решения ассоциативно.
3. Обеспечение временных ограничений
Каждый агент, входящий в состав команды, должен получать информацию о внешней среде и непосредственно влиять на нее через свои действия, выполняя заданную подцель функционирования. Для адекватного взаимодействия с внешней средой агент должен удовлетворять требованию функционирования в реальном масштабе времени. Это требование подразумевает реализацию агентом процедуры выбора и принятия решений о своих действиях за выделенное время, гарантируя соответствие между скоростями реакции агента и изменений среды при максимально достижимом качестве решений. Выполнению этого требования препятствует то, что агенты обладают ограниченной “рациональностью” и “реактивностью”, так как они имеют ограниченное быстродействие и память.
Управление командной работой в условиях временных ограничений предлагается осуществлять путем интеграции различных делиберативных механизмов планирования вычислений, в том числе полных моделей и алгоритмов решения задач, приближенных вычислений, контрактных и прерываемых anytime-алгоритмов. Приближенные вычисления реализуют модели решения задач и подзадач, различные по времени и качеству. Прерываемые алгоритмы основываются на том, что их выполнение может быть прервано в любой момент, причем к моменту прерывания обеспечивается получение определенного результата, качество которого возрастает с ростом предоставляемого времени. Контрактные алгоритмы обеспечивают получение решения к назначенному времени, а затем могут улучшать решение. Преимущество anytime-алгоритмов заключается в том, что при их использовании агент имеет некоторый вариант решения в любое заданное время после получения первого (грубого) решения.
В соответствии с данным подходом предполагается, что в состав агента кроме компонентов, свойственных соответствующей архитектуре агента, входят также библиотеки {L} алгоритмов решения задач принятия решений, разделенные по уровням и выполняемые агентом, а также модули MPMR планирования, мониторинга и перепланирования процесса принятия решений, также разделенные по уровням.
Библиотеки {L} могут включать полные и приближенные модели решения задач и подзадач, обладающие различной вычислительной сложностью, точностью, определенностью и полнотой учета различных факторов, а также контрактные и прерываемые anytime-алгоритмы.
Каждому алгоритму из {L} ставятся в соответствие так называемые условные профили их выполнения. Эти профили в общем случае задают условие применения алгоритма (выполняемую задачу, ситуацию предметной области и имеющиеся вычислительные ресурсы) и вероятностные (возможностные) показатели качества решений в зависимости от выделенного времени и показателей качества исходных данных.
Общую модель принятия решений агентом с учетом удовлетворения временных ограничений зададим в виде: TC=, где M={mi} - множество задач, реализуемых агентом;
C={cj} - множество выделенных ситуаций предметной области, в которых может находиться агент;
R={rl} - вычислительные ресурсы агента (rl - количество ресурсов l-го типа);
T - временное ограничение на принятие решения;
P={ps} - профили алгоритмов из {L};
A=({(ar, tr, qr)}, p) - структура алгоритмов из {L}, используемых для принятия решений (ar - r-й алгоритм из {L}, tr - время выполнения ar, qr - показатель качества выполнения ar, p - отношение порядка, заданное на структуре алгоритмов);
RA: M?C?R?T?P® max Q A - правила выбора структуры алгоритмов из {L} за заданное время T с наилучшим возможным качеством, реализуемых MPMR, Q - показатель качества принятия решений.
На рис.3 показана обобщенная схема, отражающая процесс реализации предлагаемой техники принятия решений агентом. Здесь модуль MPMR включает три компоненты: планирования МР , мониторинга ММ и перепланирования MR. На общие входы этих компонент приходят значения параметров от блока ограничений на компьютерные ресурсы. Последний получает информацию о текущем состоянии управляемого объекта и среды, формируемую модулем анализа текущей ситуации, который, в свою очередь, перерабатывает информацию, появляющуюся в моделях внутреннего состояния и мира объекта. При появлении новой информации на входах компонента МР формирует на выходе сигналы, определяющие заранее запланированные действия при выборе подходящих алгоритмов принятия решений, и подает их на входы компоненты ММ. Компонента MR может корректировать запланированный выбор алгоритма принятия решения, если это необходимо. Компонента ММ реализует откорректированный выбор алгоритма принятия решения из библиотеки алгоритмов. Выбранный таким образом алгоритм реализуется модулем принятия решений.
Реализация механизмов удовлетворения временных ограничений при принятии решений командой агентов предполагается на трех уровнях: (1) уровне решения общей задачи команды, предписывающей последовательность выполнения отдельных подзадач;
(2) уровне отдельных подзадач, каждая из которых выполняется отдельным агентом и требует реализации последовательности определенных алгоритмов;
(3) уровне реализации агентом конкретных алгоритмов.
Обобщенный алгоритм принятия решений агентом с учетом временных ограничений выполняется в виде непрерывного цикла и состоит из следующих шагов: (1) выбор, генерация и (или) модификация модели (плана) решения задачи;
(2) прогнозирование требуемого времени и параметров качества формируемого решения;
(3) определение, будет ли выполнена задача за отведенное время, и будут ли варианты решений удовлетворять заданным требованиям. Если ответ - отрицательный, выполняется переход на шаг 5;
(4) реализация принятия решений в соответствии с выбранной моделью. Динамическое прогнозирование и отслеживание времени, требуемого для завершения решения задачи и показателей качества формируемого решения (для сравнения текущих и спрогнозированных значений). В случае расхождения значений - переход на шаг 3. Иначе - завершение алгоритма;
(5) идентификация состояния процесса принятия решений и выбор (генерация) наиболее приемлемой Ап модели решения задачи, ее отдельных подзадач и алгоритмов. Переход на шаг 2.
Вывод
В данной работе рассмотрены обобщенные модели реализации командной работы агентов, и предложены дополнительные средства обеспечения принятия решений в реальном времени. Разработанные модели приближенных вычислений, не допускающие потери решений в циклах управления, могут использоваться для разработки команд агентов, функционирующих в различных предметных областях.
Описанные методы управления командной работой агентов-футболистов были применены для создания программного обеспечения агента Era-Polytech, который участвовал в соревнованиях по виртуальному футболу (German Open, April 2002; ROBOCUP02, June 2002). Его исходный и бинарный код размещен на сайте http:\\www.robocup.org. Программный прототип системы моделирования воздушных операций беспилотных летательных аппаратов, управляемых когнитивными агентами-пилотами, находится на стадии разработки.
Список литературы
1. Agre P.E., Chapman D. Pengi: An implementation of a theory of activity // Proceedings of the Sixth National Conference on Artificial Intelligence, Seattle, July 1987.
2. Boddy M., Dean T. Deliberation scheduling for problem solving in timeconstrained environments // Artificial Intelligence, Vol.67, N 2, 1993.
3. Cohen P., Levesque H. Teamwork // Nous, 25, 1991.
4. Firby R.J. An investigation into reactive planning in complex domains // Proceedings of the Sixth National Conference on Artificial Intelligence, Seattle, July 1987.
5. Garvey A., Lesser V. Designtotime realtime scheduling // IEEE Transactions on Systems, Man and Cybernetics, Vol.23, N 6, 1993.
6. Garvey A., Lesser V. A Survey of Research in Deliberative REALTIME Artificial Intelligence // Journal of REALTIME Systems, Vol.6, N 3, 1994.
8. Grosz B., Kraus S. Collaborative plans for complex group actions // Artificial Intelligence, Vol.86, 1996.
9. Hansen E.A., Zilberstein S. Monitoring and control of anytime algorithms: A dynamic programming approach // Artificial Intelligence, Vol.26, N 1-2, 2001.
10. HAYESROTH B., Collinot A. Scalability of realtime reasoning in intelligent agents. Technical Report KSL 9108, Knowledge Systems Laboratory, Stanford University, 1991.
11. Horvitz E.J., Rutledge G. Timedependent utility and action under uncertainty // Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, Los Angeles, CA, July 1991.
12. Ingrand F.F., Georgeff M.P. Managing Deliberation and Reasoning in REALTIME AI Systems // Proceedings of the Workshop Innovative Approaches to Planning, Scheduling, and Control, 1990.
13. Котенко И.В. Модели и алгоритмы обеспечения гарантированного времени решения задач системами, основанными на знаниях // Международная конференция по мягким вычислениям и измерениям. SMC’2000. Сборник докладов. СПБ, 2000.
14. Lesser V.R., Pavlin J., Durfee E. Approximate Processing in REALTIME Problem Solving // AI Magazine, Vol.9, N 1, 1988.
15. Musliner D.J., Durfee E.H., Shin K.G. CIRCA: A cooperative intelligent realtime control architecture // IEEE Trans. on Systems, Man and Cybernetics, Vol.23, N 6, 1993.
16. Stankevitch L.A. A cognitive agent for soccer game // Proceeding of First Workshop of Central and Eastern Europe on Multiagent Systems. CEEMAC"99. S-Petersburg, 1999.
17. Stone P. Layered learning in multiagent systems. A winner approach to Robotic Soccer. The MIT Press, 2000.
18. Tambe M. Towards flexible teamwork // Journal of Artificial Intelligence Research, N 7, 1997.
19. Wagner T., Lesser V. Design-to-Criteria Scheduling: REALTIME Agent Control // Proceedings of AAAI 2000 Spring Symposium on REALTIME Autonomous Systems, Stanford, CA, March, 2000.
20. Zilberstein S., Charpillet F., Chassaing P. REALTIME Problem-Solving with Contract Algorithms // Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. IJCAI 99. Morgan Kaufmann, 1999.
21. Zilberstein S., Charpillet F., Chassaing P. Optimal Sequencing of Contract Algorithms // Annals of Mathematics and Artificial Intelligence, 2001.