CLOT: Multi-Robot Motion Planning Via Collaborative Optimal Transport under Signal Temporal Logic Tasks

Abstract

Multi-robot systems often need to navigate through obstacle-cluttered environments while performing complex tasks. To ensure collision-free trajectories among the robots and with the obstacles is essential for the overall safety, along with additional requirements such as dynamic feasibility, relative formation, connectivity maintenance and temporal tasks. Existing work mostly focuses on the design of analytical controllers that encapsulate all these constraints, which often suffer from undesired local minima due to conflicting non-convex objectives. This work proposes a novel motion planning scheme for multi-robot systems under various safety and high-level tasks, specified as signal temporal logic (STL) formulas over collective states such as collision avoidance, relative formation and connectivity maintenance. A gradient-free method called collaborative optimal transport (CLOT) is proposed that optimizes batches of system-wide smooth trajectories over highly nonlinear costs handled through the zero-order Sinkhorn-Knopp step. Via parallel computation on GPUs, it is shown to significantly improve the scalability from a few robots to over 100 robots, with an average planning time of few seconds. Lastly, its applicability is extensively demonstrated both in simulation and hardware, over complex environments and high-level temporal tasks.