Centralized path planning for multiple robots: Optimal decoupling into sequential plans
Citations Over TimeTop 10% of 2009 papers
Abstract
We develop an algorithm to decouple a multi-robot path planning problem into subproblems whose solutions can be executed sequentially. Given an external path planner for general configuration spaces, our algorithm finds an execution sequence that minimizes the dimension of the highest-dimensional subproblem over all possible execution sequences. If the external planner is complete (at least up to this minimum dimension), then our algorithm is complete because it invokes the external planner only for spaces of dimension at most this minimum. Our algorithm can decouple and solve path planning problems with many robots, even with incomplete external planners. We show scenarios involving 16 to 65 robots, where our algorithm solves planning problems of dimension 32 to 130 using a PRM planner for at most eight dimensions. 1
Related Papers
- → Continuous decoupling of dynamically expanding systems(2009)21 cited
- A Review on Path Planning of Flexible Needle(2011)
- RESEARCH ON PATH PLANNING OF MOBILE ROBOT WITH COVERING-PATH FEATURE(2001)
- → Path planning and the geometry of joint space obstacles(2003)13 cited
- → New improvement of "dynamic repulsive potential factor" on artificial potential field path planning algorithm(2021)