Model predictive path integral for decentralized multi-agent collision avoidance

Stepan Dergachev

doi:10.7717/peerj-cs.2220

2024-08-21

Stepan Dergachev *

Konstantin Yakovlev

DOI：10.7717/peerj-cs.2220

原文链接

查看原文

摘要

En 中文

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.e., i.e ., they assume that an agent might change the direction of movement instantaneously) or are tailored to specific fi c kinematic motion models (e.g., e.g ., 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 fi ne kinematic motion models, including but not limited to differential-drive robots, car-like robots, quadrotors, etc. . The suggested approach is based on the seminal sampling-based model predictive control algorithm, i.e ., MPPI, , that originally solves a single-agent problem. We enhance it by introducing safe distributions for the multi-agent setting that are derived from the Optimal Reciprocal Collision Avoidance (ORCA) linear constraints, an established approach from the multi-agent navigation domain. We rigorously show that such distributions can be found by solving a specific fi c convex optimization problem. We also provide a theoretical justification fi cation that the resultant algorithm guarantees safety, i.e ., 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 fi nd that in many cases, the suggested approach outperforms competitors and allows solving problem instances that the other methods cannot successfully solve.

Keyword:

Collision avoidance

Kinematic constraints

Decentralized multi-agent systems

Model predictive path integral

Decentralized multi-agent navigation

Multi-robot systems

Sampling-based optimzation