Scalable Task and Motion Planning for Multi-Robot Systems in Obstacle-Rich Environments

Motion planning problems have been studied in both the artificial intelligence (AI) and robotics communities. AI solvers can compute plans for hundreds of simple agents in minutes with suboptimality guarantees, while robotics solutions typically include richer kinodynamic models during planning, but are very slow when many robots and obstacles are taken into account. We combine the advantages of the two methods by using a twostep approach. First, we use and extend AI solvers for a simplified coordination problem. The output is a discrete plan that cannot be executed on real robots. Second, we apply a computationally efficient post-processing step that creates a continuous plan, taking kinodynamic constraints into account. We show examples for ground robots in a warehouse domain and quadrotors that are tasked with formation change.