Model predictive path integral for decentralized multi-agent collision avoidance

Collision avoidance is a crucial component of any decentralized multi-agent navigation system. Currently, most of the existing multi-agent collision-avoidance methods either do not take into account the kinematic constraints of the agents (<i>i.e</i>., they assume that an agent might change the direction of movement instantaneously) or are tailored to specific kinematic motion models (<i>e.g</i>., car-like robots). In this work, we suggest a novel generalized approach to decentralized multi-agent collision-avoidance that can be applied to agents with arbitrary affine kinematic motion models, including but not limited to differential-drive robots, car-like robots, quadrotors, <i>etc</i>. The suggested approach is based on the seminal sampling-based model predictive control algorithm, <i>i.e</i>., <i>MPPI</i>, that originally solves a single-agent problem. We enhance it by introducing safe distributions for the multi-agent setting that are derived from the <i>Optimal Reciprocal Collision Avoidance (ORCA)</i> linear constraints, an established approach from the multi-agent navigation domain. We rigorously show that such distributions can be found by solving a specific convex optimization problem. We also provide a theoretical justification that the resultant algorithm guarantees safety, <i>i.e</i>., that at each time step the control suggested by our algorithm does not lead to a collision. We empirically evaluate the proposed method in simulation experiments that involve comparison with the state of the art in different setups. We find that in many cases, the suggested approach outperforms competitors and allows solving problem instances that the other methods cannot successfully solve.