Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives
Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives
复制标题
同时执行单代理原语的多代理寻路
DOI：
10.1609/socs.v3i1.18243
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kostas E. Bekris
中科院分区：
文献类型：
--
作者：
Qandeel Sajid;Ryan Luna;Kostas E. Bekris
多智能体寻路是一个具有挑战性的组合问题，它涉及多个智能体在图上从一组初始节点移动到一组期望的目标，而没有智能体间的冲突。搜索所有代理的复合空间具有指数复杂性，并且不能很好地扩展。解耦方法更有效，但通常不完整。然而，有多项式时间算法，它利用单一或少数代理原语的完整性保证。这些替代方案的一个局限性是所得到的解决方案是顺序的，其中一次只有一个代理移动。与多个代理可以同时移动的方法相比，这种解决方案的质量较低。这项工作提出了一种算法，多代理寻路，利用类似的单代理原语，但允许所有代理并行移动。本文介绍了该算法及其性质。实验比较表明，所得到的路径是大大优于顺序的，即使经过后处理，并行化步骤，以及解耦合和耦合的替代品返回的解决方案。实验还表明，良好的可扩展性和竞争力的计算性能。
Multi-agent pathfinding is a challenging combinatorial problem that involves multiple agents moving on a graph from a set of initial nodes to a set of desired goals without inter-agent collisions. Searching the composite space of all agents has exponential complexity and does not scale well. Decoupled methods are more efficient but are generally incomplete. There are, however, polynomial time algorithms, which utilize single or few-agents primitives with completeness guarantees. One limitation of these alternatives is that the resulting solution is sequential, where only one agent moves at a time. Such solutions are of low quality when compared to methods where multiple agents can move simultaneously. This work proposes an algorithm for multi-agent pathfinding that utilizes similar single-agent primitives but allows all agents to move in parallel. The paper describes the algorithm and its properties. Experimental comparisons suggest that the resulting paths are considerably better than sequential ones, even after a post-processing, parallelization step, as well as solutions returned by decoupled and coupled alternatives. The experiments also suggest good scalability and competitive computational performance.