Multi-Agent Path Finding with Kinematic Constraints
Multi-Agent Path Finding with Kinematic Constraints
复制标题
DOI：
10.1609/icaps.v26i1.13796
复制
发表时间：
2016-03
期刊：
影响因子：
--
通讯作者：
W. Hönig;T. K. S. Kumar;L. Cohen;Hang Ma;Hong Xu;Nora Ayanian;Sven Koenig
中科院分区：
文献类型：
--
作者：
W. Hönig;T. K. S. Kumar;L. Cohen;Hang Ma;Hong Xu;Nora Ayanian;Sven Koenig
在AI和机器人技术中，对多试路径查找（MAPF）进行了很好的研究。给定一个具有分配起始和目标位置的代理的离散环境，AI的MAPF求解器可为数百名具有用户提供的次级优化保证的代理找到无碰撞路径。但是，他们忽略了实际机器人受运动限制（例如有限的最大速度限制）的约束，并且具有不完美的计划执行能力。因此，我们引入了MAPF-POST，这是一种新颖的方法，它利用一个简单的时间网络在多项式时间内将MAPF求解器的输出进行后处理，以创建可以在机器人上执行的计划执行时间表。该时间表适用于非全面机器人，考虑到最大的翻译和旋转速度，提供了保证的安全距离，并利用Slack吸收不完善的计划执行，并避免在许多情况下进行耗时的重建。我们在模拟和差异驱动机器人中评估MAPF-POST，展示了我们方法的实用性。
Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as finite maximum velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST, a novel approach that makes use of a simple temporal network to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, takes their maximum translational and rotational velocities into account, provides a guaranteed safety distance between them, and exploits slack to absorb imperfect plan executions and avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.