REU Project

The multi-robot path planning problem (MPP) on the plane has long been studied both as a topic of research interest and because of it's numerous applications in numerous fields. While many effective algorithms and heuristics exist for discrete MPP on a graph, up until there have been very few results for the continuous version on the plane. In this work we provide a complete algorithm that solves the MPP problem on the plane with a guarantee of constant factor optimality in expectation. We hope that our work may be a good first step into exploring this problem extensions of it in special cases that reflect real world applications.