Введение 3
Постановка задачи 5
Обзор литературы 8
Глава 1. Глобальное планирование пути 9
Глава 2. Трассировка пути 17
Глава 3. Моделирование движения агентов в виртуальной среде и предотвращение столкновений при локальном взаимодействии между агентами 22
3.1. Разработка подхода к предотвращению столкновений при
локальном взаимодействии между агентами 23
3.2. Экстренная остановка агентов 43
Выводы 47
Заключение 48
Список литературы 49
Приложение А. Структура реализованной мультиагентной системы управления перемещениями в виртуальной среде 50
Проблемы искусственного интеллекта на протяжении многих лет занимают умы многих ученых. Одной из важнейших составляющих теории искусственного интеллекта являются агенты - сущности, обладающие интеллектом. Системы, которые способны управлять более чем одним агентом, называются мультиагентными. Данные системы имеют обширные области применения, такие как робототехника, системы виртуальной реальности, компьютерные игры, симуляторы толпы, моделирование транспортных потоков. В этих системах агентами могут являться роботы, виртуальные люди, а также транспорт.
Важной и актуальной проблемой разработки мультиагентных систем является управление перемещениями агентов в реальном времени. Моделирование перемещений занимает особое место в создании систем искусственного интеллекта, поскольку множество сложных моделей поведения агентов базируется именно на способности к перемещениям. Агенты, воплощенные в некоторой виртуальной среде, которая может моделироваться по образу реально существующей местности, могут выполнять задачи, связанные с передвижением из одной точки виртуальной среды в другую. При этом, поскольку агенты воплощены в данной среде, они подчиняются ее ограничениям, среди которых можно выделить неподвижные препятствия - непроходимые участки виртуальной среды, а также самих агентов, которые являются динамическими препятствиями друг для друга.
Под мультиагентной системой управления перемещениями в виртуальной среде будем понимать определенный набор средств, обеспечивающий передвижение агентов из одной точки виртуальной среды в другую без столкновения с неподвижными препятствиями и с другими агентами.
Цель работы: разработать мультиагентную систему управления перемещениями в виртуальной среде.
При разработке мультиагентной системы управления перемещениями в первую очередь была проанализирована проблема глобального планирования пути - прокладки маршрута для агента в виртуальной среде без учета присутствия в этой среде других агентов. Это объясняется тем, что при перемещении агента из некоторой начальной точки виртуальной среды в конечную (целевую) агент должен придерживаться кратчайшего пути между начальной и конечной точками с учетом неподвижных препятствий для более быстрого и эффективного выполнения своих задач. При этом планирование кратчайшего пути, которого должен придерживаться агент, не зависит от других агентов по причине того, что долгосрочное прогнозирование столкновений агента с другими агентами требует большого количества вычислительных ресурсов, что неприемлемо при работе системы, в которой одновременно участвует множество агентов в реальном времени. В связи с этим было решено использовать графы, характеризующие проходимые участки виртуальной среды, на которых будет осуществляться поиск кратчайшего пути. Проблема глобального планирования пути рассматривается в главе 1.
После того, как был найден кратчайший путь в качестве результата глобального планирования, возникает проблема трассировки пути - отслеживания возможности передвижения агента из своего текущего местоположения напрямую к каждой вершине графа, составляющей путь (данной проблеме посвящена глава 2), а также проблема предотвращения столкновений при локальном взаимодействии между агентами, о которой говорится в главе 3.
Данная работа является продолжением выпускной квалификационной работы бакалавра [1], в которой были решены проблемы глобального планирования пути и трассировки пути. В текущей работе была решена проблема предотвращения столкновений при локальном взаимодействии между агентами, а также были проверены и испытаны алгоритмы, разработанные в выпускной квалификационной работе бакалавра.
Существует множество способов создания мультиагентных систем, каждый из которых требует досконального изучения. Различные комбинации, составленные из множества методов решения указанных в работе проблем, дают разные результаты, которые в совокупности позволяют найти лучший подход к проектированию мультиагентных систем.
В данной работе в рамках разработки мультиагентной системы управления перемещениями в виртуальной среде были рассмотрены и решены проблемы глобального планирования пути, трассировки пути, а также предотвращения столкновений при локальном взаимодействии между агентами.
Подтверждена эффективность разработанной модификации алгоритма волновой трассировки, которая в среднем в два раза превосходит эффективность алгоритма волновой трассировки по быстродействию.
Проверен и испытан разработанный алгоритм трассировки пути, который для каждого агента успешно определяет возможность сократить путь, полученный на этапе глобального планирования, и двигаться при этом в достаточно свободном пространстве, обеспечивающем выполнение агентом необходимых маневров.
Разработан подход к предотвращению столкновений при локальном взаимодействии между агентами.
В результате выполненной работы получены алгоритмы и подходы, которые в совокупности решили поставленную в данной работе задачу.
