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

Обложка

Цитировать

Полный текст

Аннотация

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

Об авторах

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

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

Автор, ответственный за переписку.
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
Скачать

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

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») на элемент с текстом «Принять и продолжить».