A distributed solver for multi-agent path finding problems
A distributed solver for multi-agent path finding problems
复制标题
多智能体寻路问题的分布式求解器
DOI：
10.1145/3356464.3357702
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Yeoh, W.
中科院分区：
文献类型：
--
作者：
Pianpak, Poom;Son, Trancao;Toups, O. Z;Yeoh, W.
多智能体寻径（MAPF）问题传统上以集中的方式解决。有些工作关注于完整性、最优性、性能，或者它们之间的权衡。然而，基于空间分布的作品却很少。本文介绍了分布式MAPF求解器ros-dmapf。它由多个MAPF子求解器组成，这些子求解器除了解决指定的子问题外，还相互作用以解决给定的MAPF问题。在当前的实现中，子求解器是基于问题的空间分布而创建的多智能体答案集规划系统。ROS -dmapf组件之间的交互由机器人操作系统（ROS）促进。ros-dmapf的亮点在于它的可伸缩性和高度的并行性。我们使用阿司匹林系统的仅移动域对ros-dmapf进行了经验评估，结果表明ros-dmapf可以很好地扩展。例如，ros-dmapf在消费者笔记本电脑上7分钟内给出了一个包含2000个机器人的随机生成100×100无障碍地图的MAPF问题的长度约为600的解决方案——这个问题超出了单个子求解器的能力。我们还将ros-dmapf与其他一些MAPF求解器进行了比较，结果表明该系统性能良好。我们还讨论了未来工作中可能的改进。
Multi-Agent Path Finding(MAPF) problems are traditionally solved in a centralized manner. There are works focusing on completeness, optimality, performance, or a tradeoff between them. However, there are only a few works based on spatial distribution. In this paper, we introduce ros-dmapf, a distributed MAPF solver. It consists of multiple MAPF sub-solvers, which---besides solving their assigned sub-problems---interact with each other to solve a given MAPF problem. In the current implementation, the sub-solvers are answer set planning systems for multiple agents, and are created based on spatial distribution of the problem. Interactions between components of ros-dmapf are facilitated by theRobot Operating System(ROS). The highlights of ros-dmapf are its scalability and a high degree of parallelism. We empirically evaluate ros-dmapf using the move-only domain of theasprilosystem and results suggest that ros-dmapf scales up well. For instance, ros-dmapf gives a solution of length around 600 for a MAPF problem with 2000 robots in randomly generated 100×100 obstacle-free maps---a problem beyond the capability of a single sub-solver---within 7 minutes on a consumer laptop. We also evaluate ros-dmapf against some other MAPF solvers and results show that the system performs well. We also discuss possible improvements for future work.
登录
查看更多内容
基于冲突搜索的多代理路径查找的不相交分裂
影响因子：
5.2
作者：
Jiaoyang Li;Daniel Damir Harabor;Peter James Stuckey;Hang Ma;Sven Koenig
通讯作者：
Sven Koenig
空间分布式多智能体路径规划
DOI：
10.1609/icaps.v24i1.13618
发表时间：
2014
期刊：
Proceedings of the International Conference on Automated Planning and Scheduling
影响因子：
--
作者：
C. Wilt;A. Botea
通讯作者：
A. Botea
影响因子：
1.4
作者：
GEBSER, MARTIN;OBERMEIER, PHILIPP;OTTO, THOMAS;SCHAUB, TORSTEN;SABUNCU, ORKUNT;NGUYEN, VAN;SON, TRAN CAO
通讯作者：
SON, TRAN CAO
单代理和多代理环境中的答案集规划
DOI：
--
发表时间：
2018
期刊：
KI - Künstliche Intelligenz
影响因子：
--
作者：
Tran Cao Son;M. Balduccini
通讯作者：
M. Balduccini
大型代理的多代理路径查找
DOI：
--
发表时间：
2019
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence (AAAI
影响因子：
--
作者：
Li, J.;Surynek, P.;Felner, A.;Ma, H.;Kumar, S.;Koenig, S.
通讯作者：
Koenig, S.