ISSN 2071-8594

Российская академия наук

Главный редактор

Г.С. Осипов

А.А. Андрейчук Алгоритм планирования и согласования совокупности траекторий для группы интеллектуальных агентов

Аннотация.

В работе рассматривается задача планирования совокупности неконфликтных траекторий для группы интеллектуальных агентов. Предлагаемый алгоритм использует приоритизированный подход и работает в два этапа: независимое планирование индивидуальных траекторий агентов и согласование траекторий. Предлагается оригинальный метод согласования траекторий, который работает исключительно за счет добавления временных задержек. Благодаря представлению временной оси в виде последовательности интервалов, а не дискретных моментов времени, алгоритм способен согласовывать траектории, построенные с возможностью перемещения в произвольном направлении. Проведенные модельные экспериментальные исследования продемонстрировали применимость предлагаемого алгоритма и его высокую вычислительную эффективность.

Ключевые слова:

планирование траектории, многоагентные системы, устранение конфликтов, A*, Theta*, МТ-граф.

Стр. 72-85.

DOI 10.14357/20718594180407

Литература

1. Макаров Д.А., Панов А.И., Яковлев К.С. Архитектура многоуровневой интеллектуальной системы управления беспилотными летательными аппаратами // Искусственный интеллект и принятие решений. – 2015. – №3 – C.18-32.
2. Бухвалов О.Л., Городецкий В.И., Карасев О.В. и др. Производственная логистика: Стратегическое планирование, прогнозирование и управление конфликтами // Известия ЮФУ – 2012. – №3. – С. 209–218.
3. Иванов А.М. Разработка системы межобъектного взаимодействия интеллектуальных транспортных средств // Известия ВолгГТУ. Серия «Наземные транспортные системы». Вып. 7: межвуз. сб. науч. ст./ВолгГТУ. – Волгоград, 2013б – № 21 (124) – C. 74-77.
4. Ронжин A.Л., Ву Д.К., Нгуен В.В., Соленая О.Я. Концептуальная и алгоритмические модели совместного функционирования роботизированной платформы и набора БЛА при выполнении аграрных операций // IV всероссийский научно-практический семинар «Беспилотные транспортные средства с элементами искусственного интеллекта». Труды семинара. Казань. – 2017. – С. 183 -192.
5. Мотиенко А.И. Планирование тактической траектории движения автоматизированных робототехнических средств при ликвидации последствий чрезвычайных ситуаций// Научные ведомости Белгородского государственного университета. Серия: Экономика. Информатика. – 2016. – Т. 37. – № 2 (223). – С. 139-143.
6. Van Den Berg J., Guy S., Lin M., Manocha D. Reciprocal n-body collision avoidance //Robotics research. – Springer, Berlin, Heidelberg, 2011. – P. 3-19.
7. Hart P. E., Nilsson N. J., Raphael B. A formal basis for the heuristic determination of minimum cost paths //IEEE transactions on Systems Science and Cybernetics. – 1968. – Т. 4. – №. 2. – P. 100-107.
8. Daniel K., Nash A., Koenig S., Felner A. Theta*: Anyangle path planning on grids //Journal of Artificial Intelligence Research. – 2010. – Т. 39. – P. 533-579.
9. Андрейчук А.А., Яковлев К.С. Методы планирования траектории на плоскости с учетом геометрических ограничений //Известия РАН. Теория и системы управления. – 2017. – № 6, С. 125-140.
10. Standley T.S. Finding Optimal Solutions to Cooperative Pathfinding Problems //Proceedings of The 24th AAAI Conference on Artificial Intelligence (AAAI2010). – 2010. – Т. 1. – P. 28-29.
11. Sharon G., Stern R., Felner A., Sturtevant N.R. Conflictbased search for optimal multi-agent pathfinding //Artificial Intelligence. – 2015. – Т. 219. – P. 40-66.
12. Wagner G., Choset H. M*: A complete multirobot path planning algorithm with performance bounds //Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on. – IEEE, 2011. – P. 3260-3267.
13. Андрейчук А.А., Яковлев К.С. Метод разрешения конфликтов при планировании пространственных траекторий для группы беспилотных летательных аппаратов //Третий Всероссийский научно-практический семинар «Беспилотные транспортные средства с элементами искусственного интеллекта» (БТС-ИИ-2016, 22-23 сентября 2016 г., г. Иннополис, Республика Татарстан, Россия): Труды семинара. – М: Изд-во «Перо», 2016. – 184 с. С. 31-40.
14. Silver D. Cooperative Pathfinding //AIIDE. – 2005. – Т. 1. – P. 117-122.
15. Wang K. H. C., Botea A. MAPP: a scalable multi-agent path planning algorithm with tractability and completeness guarantees //Journal of Artificial Intelligence Research. – 2011. – Т. 42. – P. 55-90.
16. Erdmann M., Lozano-Perez T. On multiple moving objects //Algorithmica, – 1987. – Т. 2, P. 1419–1424
17. Cˇap M., Nov´ak P., Kleiner A., Seleck´y M. Prioritized planning algorithms for trajectory coordination of multiple mobile robots. //IEEE Transactions on Automation Science and Engineering, – 2015. – Т. 12, №3. P. 835–849
18. Harabor D., Grastien A., Oz D., Aksakalli V. Optimal anyangle pathfinding in practice. //Journal of Artificial Intelligence Research, – 2016. – Т. 56. C. 89–118.
19. Yakovlev K., Andreychuk A. Any-angle pathfinding for multiple agents based on sipp algorithm. //Proceedings of The 27th International Conference on Automated Planning and Scheduling (ICAPS2017) – 2017. – P. 586–593.
20. Phillips M., Likhachev M. SIPP: Safe interval path planning for dynamic environments. //Proceedings of The 2011 IEEE International Conference on Robotics and Automation (ICRA-2011) – 2011. – С. 5628–5635.
21. Yap P. Grid-based path-finding //In Proceedings of 15th Conference of the Canadian Society for Computational Studies of Intelligence, Springer: Berlin, Heidelberg – 2002. – P.44-55.
22. Guy S.J., Karamouzas I. Guide to anticipatory collision avoidance. //Game AI Pro 2: Collected Wisdom of Game AI Professionals, S. Rabin, Ed., – 2015. – ch. 19. P. 195–208.