Введение 3
Постановка задачи 5
Обзор литературы 8
Глава 1. Глобальное планирование пути 9
1.1. Алгоритм А* 9
1.2. Алгоритм волновой трассировки 10
1.3. Практическое сравнение эффективности алгоритма А*
и алгоритма волновой трассировки по быстродействию 10
1.4. Разработка модификации алгоритма волновой трассировки ... 15
1.5. Практическое сравнение эффективности разработанной
модификации и алгоритма волновой трассировки по быстродействию 22
Глава 2. Трассировка пути 26
Глава 3. Моделирование движения агентов в виртуальной среде и предотвращение столкновений при локальном взаимодействии между
агентами 31
3.1. Результаты исследования подходов к предотвращению
столкновений 32
3.2. Разработка подхода к предотвращению столкновений при
локальном взаимодействии между агентами 34
Выводы 40
Заключение 41
Список литературы 42
Приложение А. Структура реализованной мультиагентной системы
управления перемещениями в виртуальной среде 43
Проблемы искусственного интеллекта на протяжении многих лет занимают умы многих ученых. Одной из важнейших составляющих теории искусственного интеллекта являются агенты - сущности, обладающие интеллектом. Системы, которые способны управлять более чем одним агентом, называются мультиагентными. Данные системы имеют обширные области применения, такие как робототехника, системы виртуальной реальности, компьютерные игры, симуляторы толпы, моделирование транспортных потоков. В этих системах агентами могут являться роботы, виртуальные люди, а также транспорт.
Важной и актуальной проблемой разработки мультиагентных систем является управление перемещениями агентов в реальном времени. Моделирование перемещений занимает особое место в создании систем искусственного интеллекта, поскольку множество сложных моделей поведения агентов базируется именно на способности к перемещениям. Агенты, воплощенные в некоторой виртуальной среде, которая может моделироваться по образу реально существующей местности, могут выполнять задачи, связанные с передвижением из одной точки виртуальной среды в другую. При этом, поскольку агенты воплощены в данной среде, они подчиняются ее ограничениям, среди которых можно выделить неподвижные препятствия - непроходимые участки виртуальной среды, а также самих агентов, которые являются динамическими препятствиями друг для друга.
Под мультиагентной системой управления перемещениями в виртуальной среде будем понимать определенный набор средств, обеспечивающий передвижение агентов из одной точки виртуальной среды в другую без столкновения с неподвижными препятствиями и с другими агентами.
Цель работы: разработать мультиагентную систему управления перемещениями в виртуальной среде.
При разработке мультиагентной системы управления перемещениями в первую очередь была проанализирована проблема глобального планирования пути - прокладки маршрута для агента в виртуальной среде без учета присутствия в этой среде других агентов. Это объясняется тем, что при перемещении агента из некоторой начальной точки виртуальной среды в конечную (целевую) агент должен придерживаться кратчайшего пути между начальной и конечной точками с учетом неподвижных препятствий для более быстрого и эффективного выполнения своих задач. При этом планирование кратчайшего пути, которого должен придерживаться агент, не зависит от других агентов по причине того, что долгосрочное прогнозирование столкновений агента с другими агентами требует большого количества вычислительных ресурсов, что неприемлемо при работе системы, в которой одновременно участвует множество агентов в реальном времени. В связи с этим было решено использовать графы, характеризующие проходимые участки виртуальной среды, на которых будет осуществляться поиск кратчайшего пути. Проблема глобального планирования пути рассматривается в главе 1.
После того, как был найден кратчайший путь в качестве результата глобального планирования, возникает проблема трассировки пути - отслеживания возможности передвижения агента из своего текущего местоположения напрямую к каждой вершине графа, составляющей путь (данной проблеме посвящена глава 2), а также проблема предотвращения столкновений при локальном взаимодействии между агентами, о которой говорится в главе 3.
Существует множество способов создания мультиагентных систем, каждый из которых требует досконального изучения. Различные комбинации, составленные из множества методов решения указанных в работе проблем, дают разные результаты, которые в совокупности позволяют найти лучший подход к проектированию мультиагентных систем.
В данной работе в рамках разработки мультиагентной системы управления перемещениями в виртуальной среде были рассмотрены и решены проблемы глобального планирования пути, трассировки пути, а также предотвращения столкновений при локальном взаимодействии между агентами.
Проведено практическое сравнение эффективности алгоритма А* и алгоритма волновой трассировки по быстродействию. Разработана модификация алгоритма волновой трассировки, которая в среднем в два раза превзошла эффективность алгоритма волновой трассировки по быстродействию.
Разработан алгоритм трассировки пути, который для каждого агента успешно определяет возможность сократить путь, полученный на этапе глобального планирования, и двигаться при этом в достаточно свободном пространстве, обеспечивающем выполнение агентом необходимых маневров.
Проанализированы подходы, предназначенные для предотвращения столкновений между агентами. Разработан подход к предотвращению столкновений при локальном взаимодействии между агентами.
В результате выполненной работы получены алгоритмы и подходы, которые в совокупности решили поставленную в данной работе задачу.
