Effective Bounded-Suboptimal Algorithm of Solving Multi-Agent Pathfinding Problem

Capa

Citar

Texto integral

Resumo

The paper considers the problem of finding a combination of collision-free trajectories for a set of agents capable of performing actions of arbitrary duration. To solve this problem, two bounded-suboptimal modifications of the continuous-time conflict-based search algorithm are proposed. The results of the carried out model experimental studies have demonstrated the high computational efficiency of the proposed modifications.

Sobre autores

Anton Andreychuk

Peoples Friendship University of Russia (RUDN University)

Autor responsável pela correspondência
Email: andreychuk@mail.com

Leading researcher, Assistant of the department

Rússia, Moscow

Bibliografia

  1. Bukhvalov, O.L., Gorodetskij, V.I., Karasev, O.V. et al. Proizvodstvennaya logistika: Strategicheskoe planirovanie, prognozirovanie i upravlenie konfliktami [Industrial Logistics: Strategic Planning, Forecasting and Conflict Management] // Izvestiya YUFU [SFU Tidings]. 2012. V. 3. P. 209–218.
  2. Ivanov, A.M. Razrabotka sistemy mezhob"ektnogo vzaimodejstviya intellektual'nykh transportnykh sredstv [Development of a system of interobject interaction of intelligent vehicles] // Izvestiya VolgGTU. Seriya «Nazemnye transportnye sistemy» [VolgSTU Tidings. Series "Land transport systems."]. 2013. V. 7. №. 21(124). P. 74–77.
  3. Ronzhin, A.L., Vu, D.K., Nguen, V.V., Solenaya, O.Ya. Kontseptual'naya i algoritmicheskie modeli sovmestnogo funktsionirovaniya robotizirovannoj platformy i nabora BLА pri vypolnenii agrarnykh operatsij [Conceptual and algorithmic models of the joint operation of a robotic platform and a set of UAVs in the performance of agrarian operations] // IV vserossijskij nauchno-prakticheskij seminar "Bespilotnye transportnye sredstva s elementami iskusstvennogo intellekta". Trudy seminara. Kazan'. [IV All-Russian Scientific and Practical Seminar "Unmanned Vehicles with Artificial Intelligence Elements". Proceedings of the seminar. Kazan]. 2017. P. 183 -192.
  4. Motienko, А.I. Planirovanie takticheskoj traektorii dvizheniya avtomatizirovannykh robototekhnicheskikh sredstv prilikvidatsii posledstvij chrezvychajnykh situatsij [Planning of the tactical trajectory of the movement of automated robotic means during the liquidation of the consequences of emergency situations] // Nauchnye vedomosti Belgorodskogo gosudarstvennogo universiteta. Seriya: EHkonomika. Informatika. [Scientific bulletins of the Belgorod State University. Series: The Economy. Computer science.]. 2016. V. 37. №. 2(223). P.139–143.
  5. Erdmann M., Lozano-Pérez T. On multiple moving objects // Algorithmica. 1987. V. 2. P. 1419–1424.
  6. Standley T. Finding optimal solutions to cooperative pathfinding problems //Proceedings of the AAAI Conference on Artificial Intelligence. 2010. V. 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. V. 195. 2013. 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 multiagent 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 // 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. V. 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. V. 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.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

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