Multi-Agent Path Finding (MAPF) is a problem of finding a sequence of movements for agents to reach their assigned location without collision. Centralized algorithms usually give optimal solutions, but have difficulties to scale without employing various techniques - usually with a sacrifice of optimality; but solving MAPF problems with the number of agents greater than a thousand remains a challenge nevertheless. To tackle the scalability issue, we present DMAPF - a decentralized and distributed MAPF solver, which is a continuation of our recently published work, ros-dmapf. We address the issues of ros-dmapf where it (i) only works in maps without obstacles; and (ii) has a low success rate with dense maps. Given a MAPF problem, both ros-dmapf and DMAPF divide the map spatially into subproblems, but the latter further divides each subproblem into disconnected regions called areas. Each subproblem is assigned to a distributed solver, which then individually creates an abstract plan - a sequence of areas that an agent needs to visit - for each agent in it, and interleaves agent migration with movement planning. Answer Set Programming, which is known for its performance in small but complex problems, is used in many parts including problem division, abstract planning, border assignment for the migration, and movement planning. Robot Operating System is used to facilitate communication between the solvers and to enable the opportunity to integrate with robotic systems. DMAPF introduces a new interaction protocol between the solvers, and mechanisms that together result in a higher success rate and better solution quality without sacrificing much of the performance. We implement and experimentally validate DMAPF by comparing it with other state-of-the-art MAPF solvers and the results show that our system achieves better scalability.
翻译:多代理路径定位(MAPF) 是一个问题, 要找到代理商在没有碰撞的情况下到达指定地点的移动序列。 中央化算法通常提供最佳的解决方案, 但难以在不使用各种技术的情况下进行规模化 — — 通常是以优化为牺牲; 但是, 解决MAPF问题, 代理商数量超过一千个, 但仍是一个挑战。 要解决可缩缩缩缩缩问题, 我们提出 DMAPF — 分散和分布的MAPF 解答器。 这是我们最近出版的工作( ros- dmapf ) 的继续。 我们处理的是ros- dmapf 的问题, 在那里, 它( 一) 只能用在地图上, 只能用不设障碍的地图; 和 (二) 低成功率与密集的地图; 鉴于MAPF 问题, 罗斯- dmapf 和 D MAPF 将地图在空间上分割成问题, 但后又将每个子相隔开。 每个子问题被指派给一个分布式的解算器, 然后单独创建一个解算算算出一个解决方案- —— 。 在一个小代理服务器需要访问的解算算出一个更小代理的系统之间的领域, 。 和内部的系统, 使用一个更好的运算算出一个更好的运算算出一个更好的运算算法, 。