Summary: Multi-Agent Path Finding with Kinematic Constraints

Summary: Multi-Agent Path Finding with Kinematic Constraints

Wolfgang Hönig, T. K. Satish Kumar, Liron Cohen, Hang Ma, Hong Xu, Nora Ayanian, Sven Koenig

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Best Sister Conferences. Pages 4869-4873. https://doi.org/10.24963/ijcai.2017/684

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 velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST 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, considers kinematic constraints, provides a guaranteed safety distance between robots, and exploits slack to avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.
Keywords:
Artificial Intelligence: multi-agent systems
Artificial Intelligence: robotics
Artificial Intelligence: artificial intelligence