Model predictive path integral for decentralized multi-agent collision avoidance

Stepan Dergachev, Konstantin S. YakovlevPeerJ Comput. Sci 2024 · DOI

TL;DR

This paper introduces a novel decentralized collision avoidance method for multi-agent systems that guarantees safety even with arbitrary affine kinematic constraints. By integrating the Model Predictive Path Integral (MPPI) algorithm with constraints derived from Optimal Reciprocal Collision Avoidance (ORCA), the approach effectively balances safety and efficiency, outperforming existing methods in complex scenarios.

What Problem Does This Paper Address?

Navigating in environments with multiple agents (robots, vehicles, etc.) is a critical challenge, especially when agents must operate independently without constant communication. A key aspect of this is collision avoidance. Existing methods often struggle with:

  • Kinematic Constraints: Many approaches assume agents can change direction instantaneously, which is unrealistic for many real-world systems like cars or drones.
  • Generality: Some methods are tailored to specific types of robots (e.g., car-like) and don't easily extend to others.
  • Safety Guarantees: Even advanced methods might not always guarantee collision-free paths, especially in dense agent configurations.
  • Decentralization: Achieving robust collision avoidance without a central controller, relying only on local information, is difficult.

This paper aims to bridge this gap by proposing a decentralized method that is generalizable to various kinematic models and provides strong safety guarantees.

Methods

The core of the proposed method lies in a novel adaptation of the Model Predictive Path Integral (MPPI) algorithm. MPPI is a powerful sampling-based optimization technique for optimal control. The authors enhance it by:

  • Safe Distribution Construction: Instead of sampling control actions from a standard distribution, they derive a "safe" distribution. This distribution is constructed by incorporating linear constraints derived from Optimal Reciprocal Collision Avoidance (ORCA). ORCA is a well-established method for decentralized collision avoidance that defines safe velocity regions.
  • Convex Optimization for Safe Parameters: The parameters of this safe distribution (mean and covariance) are found by solving a Second-Order Cone Programming (SOCP) problem. This ensures that sampled controls have a high probability of satisfying the safety constraints.
  • Integration with MPPI: The safe distribution is then used within the MPPI framework to sample control sequences. This ensures that the selected control actions are not only optimal in terms of a cost function but also safe.
  • Handling Kinematic Constraints: The method is designed to work with arbitrary affine kinematic motion models, making it applicable to a wide range of agents.

Datasets

The paper does not explicitly mention the use of pre-existing datasets for training. Instead, it focuses on evaluating its proposed method through extensive simulation experiments. These experiments are designed to test the algorithm in various scenarios:

  • Differential-Drive Robot Dynamics:
    • Circle Scenario: Agents start on a circle and move to opposite points, creating potential congestion in the center.
  • Grid Scenario: Agents are placed on a grid and their goals are randomly assigned, testing performance under varying densities.
  • Random Scenario: Agents are placed randomly in an environment, testing general navigation.
  • Car-like Dynamics: Similar scenarios (Circle) are used to test the method with more complex car-like robot dynamics.
  • Learning-Based Method Comparison: A scenario similar to the Circle scenario is used to compare against a learning-based approach.
  • Heterogeneous Agents and Uncertainty: A modified Random scenario is used to test performance with agents of different sizes/speeds and with noisy state information.

Key Insights and Ideas

  • Bridging MPPI and ORCA: The paper successfully combines the strengths of MPPI (optimization, arbitrary cost functions) with ORCA (decentralized safety constraints) to create a robust collision avoidance system.
  • Safety through Distribution Shaping: The core innovation is not just adding constraints, but actively shaping the sampling distribution to guarantee a high probability of safe actions, rather than just filtering out unsafe ones.
  • SOCP for Efficient Safety Parameter Optimization: Reformulating the problem of finding safe distribution parameters into an SOCP problem is crucial for computational tractability and efficiency.
  • Generalizability to Kinematic Models: The method's ability to handle arbitrary affine kinematic models is a significant advantage over many existing approaches.
  • Performance in Dense Scenarios: The proposed method shows particular strength in dense agent configurations, where other methods tend to struggle or deadlock.

Key Results

The proposed MPPI-ORCA method was evaluated against state-of-the-art algorithms like ORCA-DD and B-UAVC, as well as a learning-based method.

  • Success Rate: The method consistently achieved high success rates across various scenarios, often outperforming competitors, especially in dense configurations (e.g., 93% success rate for 16 agents in dense grid vs. 0% for ORCA-DD).
  • Makespan (Solution Duration): MPPI-ORCA generally produced shorter solution durations compared to ORCA-DD and B-UAVC, particularly in complex or dense scenarios. For instance, in the Circle scenario with 10 agents, it was faster than B-UAVC by 80%.
  • Car-like Dynamics: The method successfully handled car-like dynamics, though with slightly longer makespans due to the inherent limitations of turning in place.
  • Learning-Based Comparison: MPPI-ORCA significantly outperformed a learning-based method in terms of success rate, especially when generalization to unseen scenarios was tested.
  • Uncertainty Handling: The method showed robustness to moderate levels of uncertainty in agent states, though high uncertainty required careful parameter tuning or larger safety buffers.

Limitations and Future Work

  • Limitations:
    • Infeasibility: The paper acknowledges that the problem might be infeasible if the set of safe velocities is empty or if no admissible control exists. Solutions like decelerating or relaxing constraints are suggested.
  • Conservative Solutions: High values of the probability guarantee ($\alpha$) can lead to conservative solutions or deadlocks.
  • Visibility Range: Safety guarantees are dependent on the agent's visibility radius covering the maximum movement in one time step.
  • Computational Cost: While SOCP is polynomial, the overall MPPI sampling process can still be computationally intensive, especially with a large number of agents or samples.
  • Future Work:
    • Further explore the incorporation of uncertainties in state and neighbor information, as well as control execution inaccuracies.
  • Implement the approach using ROS and conduct experiments in more advanced simulators (Gazebo) and on real robots.
  • Investigate the impact of different safety buffer strategies and their trade-offs with deadlocks.

Summary updated

BibTeX
@article{dergachev2024model,
  author = {Stepan Dergachev and Konstantin S. Yakovlev},
  title = {{Model predictive path integral for decentralized multi-agent collision avoidance}},
  journal = {PeerJ Comput. Sci.},
  year = {2024},
  doi = {10.7717/peerj-cs.2220},
}
Figure