Multi Agent Path Finding with Kinematic Constraints
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.
ICAPS