Optimal Multi-Robot Motion Planning in a Planar Polygonal Environment
Benjamin Holmgren, Duke University
Given a geometric object which can move within an environment, the fundamental robot motion planning problem is to produce a path between a desired start and end position that avoids colliding with obstacles, if one exists. With the ubiquitous use of multi-robot systems, we are interested in motion planning for teams of robots. Moreover, rather than producing a feasible plan, we additionally desire an optimal plan with respect to geometric criteria such as path length or makespan. We consider the problem within a planar polygonal environment, modeling robots as convex sets. Algorithmic motion planning has been widely studied in the computational geometry and robotics communities since at least the 1980s, but to date few theoretical guarantees are known with regard to optimal motion planning. When the objective is to minimize the makespan, we show that optimal multi-robot motion planning is NP-Complete by a reduction from the partition problem, even for only two robots. When the objective is instead to minimize the sum of the path lengths, we characterize optimal motion plans for teams of convex robots. We discuss approximation schemes, and ongoing work in combinatorial geometry aimed at efficiently partitioning the configuration space.