Wolfgang Hönig, T. K. Satish Kumar, Liron Cohen, Hang Ma, Hong Xu, Nora Ayanian, and Sven Koenig. Multi-agent path finding with kinematic contraints. In the 26th International Conference on Automated Planning and Scheduling (ICAPS), 477–485. 2016. Outstanding paper award in the robotics track. URL: http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13183/12711.
[BibTeX] [full text]

## Abstract

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.

## BibTeX

@inproceedings{honig2016,
author = "Hönig, Wolfgang and Kumar, T. K. Satish and Cohen, Liron and Ma, Hang and Xu, Hong and Ayanian, Nora and Koenig, Sven",
year = "2016",
pages = "477--485",
url = "http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13183/12711",
note = "Outstanding paper award in the robotics track",
booktitle = "the 26th International Conference on Automated Planning and Scheduling ({ICAPS})",
title = "Multi-Agent Path Finding with Kinematic Contraints"
}