Recursive Feasibility and Deadlock Resolution in MPC-based Multi-robot Trajectory Generation

Collision-free trajectory generation within a shared workspace is fundamental for most multi-robot applications. However, despite of their versatility, many widely-used methods based on model predictive control (MPC) lack theoretical guarantees on the feasibility of underlying optimization. Furthermore, when applied in a distributed manner, deadlocks often occur where several robots block each other indefinitely without resolution. Towards this end, we propose a systematic method called infinite-horizon model predictive control with deadlock resolution (IMPC-DR). It can provably ensure recursive feasibility and effectively resolve deadlocks online in addition to the handling of input and model constraints. The method is based on formulating a convex optimization over the proposed modified buffered Voronoi cells in each planning horizon. Moreover, it is fully distributed and requires only local inter-robot communication. Comprehensive simulation and experiment studies are conducted over large-scale multi-robot systems. Significant improvements of both feasibility and success rate are shown, in comparison with other state-of-the-art methods and especially in crowded and high-speed scenarios.