Многоагентные системы планирования траектории - одна из развивающихся направлений искусственного интеллекта. Разработки в этой области активно применяются в компьютерных играх, авиации [1] и робототехнике. При разработке систем многоагентного планирования траектории перед разработчиками появляется ряд задач. Одной из таких задач является эффективное планирование траектории для каждого агента от начальной позиции до конечной и координация агентов между собой так, чтобы они не мешали движению других агентов.
Зачастую, агенты не могут знать всю местность заранее, но могут автоматически наблюдать за ней в определенном диапазоне вокруг себя и запоминать ее для использования в будущем. Например, такие ситуации встречаются при разработке навигации для персонажей в компьютерных играх реального времени (таких, как Baldur’s Gate(рис. 1), Total Annihilation, Age of Empires или Dark Reign).
Агенты в нашей задаче могут не знать всю местность заранее и в ходе их движения по местности могут возникнуть большое количество непредвиденных обстоятельств, которые затрудняют поиск. По мере того как агенты перемещаются по местности, они наблюдают за ней все больше, что ускоряет будущие поиски, поскольку уменьшает количество возможных непредвиденных обстоятельств. Также, агенты могут обмениваться между собой какой-то информацией для того, чтобы помогать другим агентам избегать конфликтов с другими агентами или препятствиями. В данной ситуации нахождение оптимального решения - сложно-разрешимая задача и необходимо использовать производительный поисковый подход, который может немного пожертвовать оптимальностью результирующих траекторий ради общей производительности. Результирующие траектории, вероятно, не являются оптимальными, но это часто перевешивается экономией вычислений.
Целью данной дипломной работы является в исследование формальной постановки задачи многоагентного планирования траектории в условиях частичной наблюдаемости, различных постановок данной задачи и разработка системы навигации групп мобильных агентов для решения данной задачи.
В ходе выполнения работы были исследованы задачи многоагентного планирования траектории и планирования траектории в условиях частичной наблюдаемости. Был проведен анализ технической литературы, на его основе были разработаны новые алгоритмы для задачи многоагентного планирования траектории в условиях частичной наблюдаемости, основанные на изученных алгоритмах многоагентного планирования и планирования в условиях частичной наблюдаемости. Данные алгоритмы были реализованы, на их основе был разработан прототип системы планирования движения роботов на языке программирования C++. Было проведено экспериментальное исследование производительности написанных алгоритмов.
К основным результатам работы относится программная реализация алгоритмов и системы планирования движения группы агентов в условиях частичной наблюдаемости и также результаты экспериментального исследования алгоритмов.
На основании экспериментальных исследований можно сделать вывод, что версии, в которых происходил обмен между агентами большим количеством информации, показывают лучшие результаты. Для версии алгоритма с полной децентрализацией лучше всего себя показывает стратегия «Квадрат+», так как в отличие от других стратегий она лишена случаев взаимной блокировки.
В будущих работах планируется разработка стратегий, основанные на субоптимальных алгоритмах основанных на правилах (TASS, Push And Swap), использовать подходы с других алгоритмов частичной наблюдаемости (например как LSS-LRTA*) или других алгоритмов многоагентного планирования траектории.
