arXiv (Cornell University) · 2019 · 12 citations · 21 references
EngineeringComputer ScienceRobotics EngineeringMobile RoboticsPath PlanningRoboticsMulti-robot CoordinationRobot Motion PlanningTrajectory GenerationHomologyMulti-robot Path PlanningMulti-robot PlanningMulti-robot Trajectory PlanningPrioritizationPrioritization HeuristicsRobot Path PlanningRobotic Path Planning
This work deals with the problem of planning conflict-free paths for mobile robots in cluttered environments. Since centralized, coupled planning algorithms are computationally intractable for large numbers of robots, we consider decoupled planning, in which robots plan their paths sequentially in order of priority. Choosing how to prioritize the robots is a key consideration. State-of-the-art prioritization heuristics, however, do not model the coupling between a robot's mobility and its environment. In this paper, we propose a prioritization rule that can be computed online by each robot independently, and that provides consistent, conflict-free path plans. Our innovation is to formalize a robot's path prospects to reach its goal from its current location. To this end, we consider the number of homology classes of trajectories, and use this as a prioritization rule in our decentralized path planning algorithm, whenever any robots enter negotiation to deconflict path plans. This prioritization rule guarantees a partial ordering over the robot set. We perform simulations that compare our method to five benchmarks, and show that it reaches the highest success rate (w.r.t. completeness), and that it strikes the best balance between makespan and flowtime objectives.
21
Michael Erdmann, Tomás Lozano‐Pérez · Algorithmica · 1987 · 743 citations
Prioritized motion planning for multiple robots
J.P. van den Berg, M.H. Overmars · 2005 · 324 citations