Эффективный поиск ограниченно-субоптимальных решений задачи многоагентного планирования

Обложка

Цитировать

Полный текст

Аннотация

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

Об авторах

Антон Андреевич Андрейчук

Российский университет дружбы народов

Автор, ответственный за переписку.
Email: andreychuk@mail.com

ведущий исследователь, ассистент

Россия, Москва

Список литературы

  1. Бухвалов О.Л., Городецкий В.И., Карасев О.В. и др. Производственная логистика: Стратегическое планирование, прогнозирование и управление конфликтами// Известия ЮФУ. 2012. №3. С. 209–218.
  2. Иванов А.М. Разработка системы межобъектного взаимодействия интеллектуальных транспортных средств // Известия ВолгГТУ. Серия «Наземные транспортные системы». Вып. 7: межвуз. сб. науч. ст./ВолгГТУ. Волгоград. 2013. № 21 (124) . C. 74-77.
  3. Ронжин A.Л., Ву Д.К., Нгуен В.В., Соленая О.Я. Концептуальная и алгоритмические модели совместного функционирования роботизированной платформы и набора БЛА при выполнении аграрных операций // IV всероссийский научно-практический семинар «Беспилотные транспортные средства с элементами искусственного интеллекта». Труды семинара. Казань. 2017. С. 183-192.
  4. Мотиенко А.И. Планирование тактической траектории движения автоматизированных робототехнических средств при ликвидации последствий чрезвычайных ситуаций// Научные ведомости Белгородского государственного университета. Серия: Экономика. Информатика. 2016. Т. 37. № 2 (223). С. 139-143.
  5. Erdmann M., Lozano-Pérez T. On multiple moving objects // Algorithmica. Т.2. 1987. P. 1419–1424.
  6. Standley T. Finding optimal solutions to cooperative pathfinding problems //Proceedings of the AAAI Conference on Artificial Intelligence. 2010. Т. 24. №. 1. P.173-178.
  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 4(2). 1968. P. 100–107.
  8. Sharon G., Stern R., Felner A., Sturtevant N.R. Conflictbased search for optimal multi-agent pathfinding // Artificial Intelligence. 2015. №. 219. P. 40–66.
  9. Wagner G., Choset H. M*: A complete multirobot path planning algorithm with performance bounds //2011 IEEE/RSJ international conference on intelligent robots and systems. IEEE. 2011. P. 3260-3267.
  10. Sharon G., Stern R., Goldenberg M., Felner A. The increasing cost tree search for optimal multi-agent pathfinding. // Artificial Intelligence. 2013. Т. 195. P. 470–495.
  11. Boyarski E., Felner A., Stern R., Sharon G., Betzalel O., Tolpin D., Shimony E. ICBS: The improved conflictbased search algorithm for multi-agent pathfinding//Proceedings of the Eighth International Symposium on Combinatorial Search (SoCS-2015). 2015. P. 223-225.
  12. Felner A., Li J., Boyarski E., Ma H., Cohen L., Kumar T.S., Koenig S. Adding heuristics to conflict-based search for multi-agent path finding //Proceedings of the 28th International Conference on Automated Planning and Scheduling. 2018. P.83–87.
  13. Barer M., Sharon G., Stern R., Felner A. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem //Seventh Annual Symposium on Combinatorial Search. 2014.
  14. Li J., Ruml W., Koenig S. EECBS: Bounded-Suboptimal Search for Multi-Agent Path Finding // Proceedings of the 35th AAAI Conference on Artificial Intelligence. 2021. P. 12353–12362.
  15. Yakovlev K., Andreychuk A. Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm //Proceedings International Conference on Automated Planning and Scheduling, ICAPS. 2017. P. 586-593.
  16. Walker T.T., Sturtevant N.R., Felner, A. Extended increasing cost tree search for non-unit cost domains // Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI-2018). 2018. P. 534–540.
  17. Cohen L., Uras T., Kumar T. S., Koenig S. Optimal and bounded-suboptimal multi-agent motion planning. In Proceedings of the 12th Symposium on Combinatorial Search (SoCS 2019). 2019. P. 44-51.
  18. Guy S. J., Karamouzas I. Guide to anticipatory collision avoidance //Game AI Pro 2: Collected Wisdom of Game AI Professional – AK Peters/CRC Press. 2015. Т. 2. P. 195-207.
  19. Phillips M., Likhachev M. SIPP: Safe interval path planning for dynamic environments // 2011 IEEE International Conference on Robotics and Automation. IEEE.2011. P. 5628–5635.
  20. Pearl J., Kim, J. H. Studies in Semi-Admissible Heuristics. //IEEE Transaction on Pattern Analysis and Machine Intelligence. 1982. Т.4. P.392–399.
  21. Thayer J. T., Ruml W. Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates // Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-2011). 2011. P.674–679.
  22. Sturtevant N.R. Benchmarks for grid-based pathfinding // IEEE Transactions on Computational Intelligence and AI in Games 4(2). 2012. P. 144–148.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).