Proceedings of the International Conference on Automated Planning and Scheduling · 2016 · 140 citations · 31 references
EngineeringComputer ScienceRobotics EngineeringPath PlanningRobot KinematicsRoboticsKinematic ConstraintsMulti-robot SchedulingRobot Motion PlanningTrajectory GenerationTrajectory OptimizationDifferential Drive RobotsKinematic Constraints In Collision AvoidanceMulti-agent Path PlanningPolynomial-time AlgorithmsReplanningRobot Path PlanningRobotic Path PlanningSafety Distance Calculation
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.
31
Rina Dechter, Itay Meiri, Judea Pearl · Artificial Intelligence · 1991 · 1.8K citations
Conflict-based search for optimal multi-agent pathfinding
Guni Sharon, Roni Stern, Ariel Felner et al. · Artificial Intelligence · 2014 · 1.2K citations