Организация навигация группы агентов

На основе модуля автономной навигации одиночного агента может быть построена система навигации группы агентов. Как было описано выше, модуль одиночного агента может быть встроен в систему управления одиночным роботом и, таким образом, вся необходимая для работы системы навигации информация будет поступать от других компонентов робототехнической системы (от подсистемы коммуникации или датчиков робота), а рассчитанная скорость будет передаваться исполнительной системе робота. Помимо модуля навигации одиночного агента был реализован набор модулей, позволяющих запустить работу системы в централизованном режиме, что позволило проверить работоспособность модуля одиночного агента. Помимо этого, такая система позволяет осуществлять централизованную навигацию группы агентов, используя преимущество децентрализованного подхода в возможностях параллельного вычисления траекторий агентов. Также, исходный код системы может быть использован в качестве примера применения модуля навигации одиночного агента.

Далее будут описаны основные компоненты системы и механизмы их взаимодействия. Каждый отдельный модуль представляет из себя ROS узел. Центральный модуль (ROSMission) отвечает за хранение, обновление и передачу данных о состоянии всей системы целиком. Набор промежуточных модулей (ROSSimActor), которые отвечают за взаимодействие между центральным модулем и модулем навигации одиночного агента. Набор модулей навигации одиночного агента (ROSAgent). Помимо этого, система использует стандартный узел, предоставляющий по запросу информацию об окружающей среде в формате графа регулярной декомпозиции (map_server). Иллюстрация узлов системы для 5 агентов представлена на рис. 32.

Рис. 32. Иллюстрация ROS узлов системы навигации группы из 3 агентов. Стрелками обозначены связи и направления передачи информации между узлами.

На начальном этапе работы центральный модуль считывает информацию о количестве агентов, их параметрах, начальных и конечных позициях, а также данные о статических препятствиях из XML-файла, аналогичному тому, что требуется для работы прототипа системы, путь к которому указывается в формате приватного параметра ROS. После этого производится регистрация агентов в центральном модуле. Центральный модуль создает сервис инициализации и ожидает необходимое число запросов (равное числу агентов), в ответ каждому запросу передается идентификатор нового зарегистрированного участника системы, данные о начальном и конечном положении нового агента, параметры агента и данные о статической среде. Когда нужное число агентов было зарегистрировано центральный модуль создает тему, куда публикуются состояния всех агентов в дискретные моменты времени. Помимо этого, центральный модуль подписывается на тему, куда публикуются результаты расчета новых скоростей каждого агента. После окончания подготовительных операций запускается циклический процесс, состоящий из публикации состояний агентов, получения скоростей, обновления состояния агентов. Период работы одной итерации цикла постоянен, т.е. запуски новых итераций производится через равные промежутки времени.

Во время подготовительного этапа промежуточные модули производят запрос к центральному модулю для регистрации нового участника системы и получения необходимых входных данных для конкретного агента. После чего аналогичным образом производится инициализация модуля навигации одиночного агента (промежуточный модуль создает сервис, ожидающий запрос от модуля навигации). Модуль навигации также запрашивает информацию о статических препятствиях в формате графа регулярной декомпозиции у узла map_server. Промежуточный модуль подписывается на тему, содержащую состояния всех агентов, и регистрируется в качестве издателя в теме, принимающей все рассчитанные скорости агентов. Помимо этого, устанавливается двусторонняя связь с использованием тем между промежуточным модулем и модулем навигации одиночного агента. После окончания подготовительного этапа промежуточный модуль ожидает публикации данных о текущем состоянии всех агентов, после получения которой производит отбор соседей текущего агента. Формируется сообщение входных данных для модуля навигации одиночного агента. Модуль одиночного агента принимает входные данные, производит расчет скорости и передает ее обратно промежуточному модулю. Промежуточный модуль создает сообщение, содержащие идентификатор промежуточного модуля и новую скорость и отправляет его центральному модулю с использованием темы всех скоростей агентов. Иллюстрация узлов с темами ROS для системы из 3 агентов представлена на рис. 33.

Рис. 33. Иллюстрация ROS узлов и тем системы навигации группы из 3 агентов. Прямоугольными фигурами обозначены темы ROS, овальными фигурами обозначены узлы ROS, стрелками обозначены связи и направления передачи информации между узлами.

Рис. 34. Окно утилиты rviz с запущенной визуализацией работы системы

Для демонстрации работы системы был реализован модуль визуализации положений агентов через утилиту rviz. Модуль получает данные об состояниях агентов в дискретные модели времени из соответствующей темы центрального модуля и основываясь на полученных данных публикует информацию о маркерах, визуализирующих положение агентов в пространстве, в служебную тему утилиты rviz. Данные о карте статических препятствий утилита rviz получает с использованием узла map_server. Пример запуска визуализации системы приведен на рис. 34.

Запуск систем, состоящих из большого числа узлов совершается с помощью утилиты roslaunch. Для данной утилиты необходимо сформировать входной launch файл формата XML, в котором описан порядок запуск узлов и их параметры. Для этого был реализован скрипт на языке Python, который получает от пользователя параметры запуска системы и формирует launch файл и файл-описание статической среды в формате map_server. Исходный код и описание прототипа системы доступны в открытом репозитоии.

Заключение

В ходе выполнения работы была рассмотрена одна из актуальных задач области искусственного интеллекта: задача навигации группы мобильных агентов. Был выполнен анализ научно-технической литературы в этой области. На основе проведенного анализа были выбраны основные алгоритмы и методы для разработки системы автономной навигации группы мобильных агентов. Выбранные алгоритмы были реализованы, на их основе был разработан прототип системы навигации в виде отдельной программы на языке C++, а также в виде модуля для операционной системы роботов (ROS). Для системы был реализован набор тестовых программ и документация исходного кода. Было проведено экспериментальное исследование прототипа системы. К основным результатам работы относятся программные реализации методов децентрализованной навигации, как в виде независимой программной системы, так и в виде модуля ROS, а также - результаты экспериментального исследования этих методов. Отдельные результаты, полученные в процессе работы над ВКР, были представлены в рамках XVII национальной конференции по искусственному интеллекту “КИИ-2019” и XV международной конференция по электромеханике и робототехнике “Завалишинские чтения - 2020”. Соответствующие доклады были опубликованы в сборниках трудах конференции, индексируемых в РИНЦ.

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

Список используемых источников

1 Андреи?чук А.А., Яковлев К.С. Планирование траектории? для коалиции агентов. Алгоритм MAPP // Труды Второи? молодежнои? научнои? конференции «Задачи современнои? информатики». М.: ФИЦ ИУ РАН, 2015. С. 19-24.

2 Тимофеев А. В., Юсупов Р. М. Принципы построения интегрированных систем мультиагентнои? навигации и интеллектуального управления мехатронными роботами // Information Technologies & Knowledge. 2011. Т. 5. № 3 С. 237-244.

3 Sharon G. et al. Conflict-based search for optimal multi-agent pathfinding // Artificial Intelligence. 2015. V. 219. P. 40-66.

4 Ибp M. et al. Prioritized planning algorithms for trajectory coordination of multiple mobile robots // IEEE transactions on automation science and engineering. 2015. V. 12. N. 3. P. 835-849.

5 Dimarogonas D. V., Kyriakopoulos K. J. Decentralized navigation functions for multiple robotic agents with limited sensing capabilities // Journal of Intelligent and Robotic Systems. 2007. V. 48. N. 3. P. 411-433.

6 Xuan P., Lesser V. Multi-agent policies: from centralized ones to decentralized ones // Proceedings of the first international joint conference on Autonomous agents and multiagent systems: V. 3. 2002. P. 1098-1105.

7 Яковлев К.С., Баскин Е.С., Андреи?чук А.А. Метод автоматического планирования совокупности траектории? для навигации беспилотных транспортных средств // Управление большими системами. М.: ИПУ РАН, 2015. № 58. C. 306-342

8 Masehian E., Amin?Naseri M. R. A voronoi diagram?visibility graph?potential field compound algorithm for robot path planning //Journal of Robotic Systems. 2004. V. 21. N. 6. P. 275-300.

9 Overmars M. H., Welzl E. New methods for computing visibility graphs // Proceedings of the fourth annual symposium on Computational geometry. ACM, 1988. P. 164-171.

10 S?eda, M., Pich, V. Robot Motion Planning Using Generalised Voronoi Diagrams // 8th WSEAS International Conference on Signal Processing, Computational Geometry and Artificial Vision. 2008. V. 1. P. 215-220.

11 Яковлев К. С., Баскин Е. С. Графовые модели в задаче планирования траектории на плоскости // Искусственныи? интеллект и принятие решении?. 2013. № 1. С. 5-12.

12 Dijkstra E. W. A note on two problems in connexion with graphs // Numerische Mathematik. 1959. V. 1. P. 269-271.

13 Hart P., Nillson N., Raphael B. A formal basis for the heuristics determination of minimum costs path. // IEEE Transactions on Systems Science and Cybernetics. 1968. V. 4. N 2. P. 100-107.

14 Korf R.E. Articial Intelligence Search Algorithms // In Algorithms and Theory of Computation Handbook, CRC Press, 1996. P. 40.

15 Stentz A. Optimal and efficient path planning for partially known environments // Intelligent Unmanned Ground Vehicles. Springer, Boston, MA, 1997. P. 203-220.

16 Koenig S., Likhachev M., Furcy D. Lifelong planning A? // Artificial Intelligence. 2004. V. 155. N. 1-2. P. 93-146.

17 Harabor D. D., Grastien A. Online graph pruning for pathfinding on grid maps // Twenty-Fifth AAAI Conference on Artificial Intelligence. 2011.

18 Daniel K. et al. Theta*: Any-angle path planning on grids // Journal of Artificial Intelligence Research. 2010. V. 39. P. 533-579.

19 Van den Berg J., Lin M., Manocha D. Reciprocal velocity obstacles for real-time multi-agent navigation // 2008 IEEE International Conference on Robotics and Automation. IEEE, 2008. P. 1928-1935.

20 Van Den Berg J. et al. Reciprocal n-body collision avoidance // Robotics research. Springer, Berlin, Heidelberg, 2011. P. 3-19.

21 Ma Y., Manocha D., Wang W. Efficient reciprocal collision avoidance between heterogeneous agents using CTMAT // Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 2018. P. 1044-1052.

22 Best A., Narang S., Manocha D. Real-time reciprocal collision avoidance with elliptical agents // 2016 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2016. P. 298-305.

23 Van Den Berg J. et al. LQG-obstacles: Feedback control with collision avoidance for mobile robots with motion and sensing uncertainty // 2012 IEEE International Conference on Robotics and Automation. IEEE, 2012. P. 346-353.

24 Gopalakrishnan B. et al. PRVO: Probabilistic reciprocal velocity obstacle for multi robot navigation under uncertainty // 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2017. P. 1089-1096.

25 Snape J. et al. Smooth coordination and navigation for multiple differential-drive robots // Experimental Robotics. Springer, Berlin, Heidelberg, 2014. P. 601-613.

26 Snape J. et al. Smooth and collision-free navigation for multiple robots under differential-drive constraints // 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2010. P. 4584-4589.

27 Alonso-Mora J. et al. Optimal reciprocal collision avoidance for multiple non-holonomic robots // Distributed Autonomous Robotic Systems. Springer, Berlin, Heidelberg, 2013. P. 203-216.

28 Zhou D. et al. Fast, on-line collision avoidance for dynamic vehicles using buffered voronoi cells // IEEE Robotics and Automation Letters. 2017. V. 2. N. 2. P. 1047-1054.

29 Chen Y. F. et al. Decentralized non-communicating multiagent collision avoidance with deep reinforcement learning // 2017 IEEE international conference on robotics and automation (ICRA). IEEE, 2017. P. 285-292.

30 Long P. et al. Towards optimally decentralized multi-robot collision avoidance via deep reinforcement learning // 2018 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2018. P. 6252-6259.

31 Wu X. An efficient antialiasing technique // Acm Siggraph Computer Graphics. - 1991. V. 25. N. 4. P. 143-152.

32 de Berg M., Cheong O., van Kreveld M., Overmars M. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2008.

33 Prechelt L. An empirical comparison of seven programming languages // Computer. 2000. V. 33. N. 10. P. 23-29.

34 Elkady A., Sobh T. Robotics middleware: A comprehensive literature survey and attribute-based bibliography // Journal of Robotics. 2012. V. 2012.

35 Magyar G., Sinибk P., Krizsбn Z. Comparison study of robotic middleware for robotic applications // Emergent Trends in Robotics and Intelligent Systems. Springer, Cham, 2015. P. 121-128.

Размещено на Allbest.ru