论文标题
Cl-MAPF：具有运动和时空约束的类似汽车的机器人的多代理路径查找
CL-MAPF: Multi-Agent Path Finding for Car-Like Robots with Kinematic and Spatiotemporal Constraints
论文作者
论文摘要
在过去的几年中，由于其在机器人技术和AI领域的广泛应用，多代理路径的发现已被广泛研究。但是，以前的求解器依靠几个简化的假设。他们限制了采用非独立汽车代理而不是自动性的众多现实领域中的适用性。在本文中，我们给出了类似汽车的机器人（CL-MAPF）问题的多代理路径发现的数学形式化。我们第一次提出了一种新型的基于层次搜索的求解器，称为基于汽车的冲突搜索，以解决此问题。它应用了一个身体冲突树来解决考虑代理形状的碰撞。我们引入了一种称为时空杂种a*的新算法，作为单格路径计划器，以生成满足运动学和时空约束的路径。为了提高效率，我们还提出了方法的顺序计划版本。我们将我们的方法与包含3000个实例的专用基准测试上的两个基线算法进行比较，并在现实世界中对其进行验证。实验结果给出了明确的证据，表明我们的算法量表很好地尺度到了大量代理，并且能够生成可以直接应用于现实世界中类似汽车的机器人的解决方案。基准和源代码在https://github.com/april-zju/cl-cbs中发布。
Multi-Agent Path Finding has been widely studied in the past few years due to its broad application in the field of robotics and AI. However, previous solvers rely on several simplifying assumptions. They limit their applicability in numerous real-world domains that adopt nonholonomic car-like agents rather than holonomic ones. In this paper, we give a mathematical formalization of Multi-Agent Path Finding for Car-Like robots (CL-MAPF) problem. For the first time, we propose a novel hierarchical search-based solver called Car-like Conflict-Based Search to address this problem. It applies a body conflict tree to address collisions considering shapes of the agents. We introduce a new algorithm called Spatiotemporal Hybrid-State A* as the single-agent path planner to generate path satisfying both kinematic and spatiotemporal constraints. We also present a sequential planning version of our method for the sake of efficiency. We compare our method with two baseline algorithms on a dedicated benchmark containing 3000 instances and validate it in real-world scenarios. The experiment results give clear evidence that our algorithm scales well to a large number of agents and is able to produce solutions that can be directly applied to car-like robots in the real world. The benchmark and source code are released in https://github.com/APRIL-ZJU/CL-CBS.
