Decentralized Multi-Robot Navigation Based on Deep Reinforcement Learning and Trajectory Optimization

Bi Yi-fei, Jianing Luo, Jiwei Zhu, Junxiu Liu, Wei LiBiomimetics 2025 · DOI

TL;DR

This paper introduces the GNN-RL-APF-Lagrangian algorithm, a novel approach for decentralized multi-robot navigation that combines Graph Neural Networks (GNNs) and Deep Reinforcement Learning (DRL) for path generation with Artificial Potential Fields (APF) and nonlinear optimization for enhanced safety. This method significantly improves collision avoidance and safety in complex environments, achieving high success rates even with up to 30 robots.

What Problem Does This Paper Address?

Coordinating multiple robots to navigate complex environments while avoiding collisions is a significant challenge. While existing decentralized methods are computationally efficient, they often struggle to guarantee safety. This paper tackles the problem of ensuring robust and safe multi-robot navigation, particularly in scenarios with dynamic obstacles and a high density of robots, where traditional approaches can falter. The goal is to achieve reliable navigation without centralized control, mimicking the emergent behaviors seen in biological systems.

Methods

The core of the proposed solution is the GNN-RL-APF-Lagrangian algorithm, which builds upon several key components:

  • Graph Neural Networks (GNNs): Used to aggregate high-dimensional features from neighboring robots, allowing each robot to build a richer understanding of its local environment and the state of its peers. This addresses the challenge of limited information in decentralized systems.
  • Deep Reinforcement Learning (DRL): A policy network, trained using DRL, takes the aggregated GNN features and local observations (laser scans, goal position, other robot positions) to generate an initial path. This is a standard approach for learning complex navigation policies.
  • Artificial Potential Field (APF): To enhance safety, an APF is integrated. It generates repulsive forces from obstacles, which are used to refine the DRL-generated trajectory. This adds a layer of safety by actively pushing robots away from perceived threats.
  • Constrained Nonlinear Optimization (Lagrangian Dual Problem): To further guarantee safety and address potential issues where APF might get stuck in local optima or produce unsafe paths due to inconsistent step sizes, a constrained nonlinear optimization problem is formulated. This problem is transformed into a Lagrangian dual problem, which is then solved to fine-tune the APF-adjusted paths. This is a novel combination, using optimization to refine the RL-generated and APF-adjusted paths.

The overall framework follows a centralized training, decentralized execution scheme, meaning the policy is trained centrally but can be deployed independently on each robot using only local observations.

Datasets

The paper does not explicitly mention using pre-existing datasets for training. Instead, it describes a simulation environment where training maps were randomly generated. Three types of maps were used for policy training: random obstacle layouts, maze-like structures, and a combination of both. For evaluation, experiments were conducted in both obstacle-free maps and complex environments with random static obstacles.

Key Insights and Ideas

  • Synergy of Learning and Optimization: The paper demonstrates that combining the adaptive learning capabilities of DRL with the safety guarantees of APF and nonlinear optimization leads to significantly more robust and safer navigation than using DRL alone.
  • Biomimetic Inspiration: The approach draws inspiration from biological systems (flocking birds, schooling fish) for local information aggregation and repulsive force mechanisms, highlighting the effectiveness of bio-inspired design in robotics.
  • Addressing APF Limitations: By using nonlinear optimization to refine APF-guided paths, the algorithm overcomes the tendency of APF to get stuck in local optima, a common issue in traditional APF-based navigation.
  • Scalability and Decentralization: The GNN-based approach naturally supports decentralized execution and demonstrates impressive scalability, maintaining performance even with a large number of robots (up to 30).

Key Results

  • Improved Success Rate: The GNN-RL-APF-Lagrangian algorithm achieved a success rate of 96.43% in sparse obstacle environments and 89.77% in dense obstacle scenarios. This represents a significant improvement of 59% and 60%, respectively, over baseline GNN-RL approaches.
  • Enhanced Safety: In comparative experiments, the GNN-RL-APF-Lagrangian algorithm consistently achieved a 100% success rate in obstacle-free environments across various robot numbers (2-8 robots), outperforming the GNN-RL algorithm which experienced timeouts and lower success rates.
  • Scalability: The algorithm demonstrated robust scalability, maintaining good performance with up to 30 robots in large-scale obstacle avoidance experiments.
  • Trade-offs: While the GNN-RL-APF-Lagrangian algorithm offers superior safety, it incurs a slightly longer path length (due to detours) and increased computation time compared to simpler methods, especially in dense environments.

Limitations and Future Work

  • Computational Overhead: The addition of nonlinear optimization increases computation time, which might be a concern for applications requiring extremely low latency (sub-10ms). The authors suggest that the GNN-RL-APF variant (without Lagrangian optimization) might be preferable in such cases.
  • Simulation vs. Real-World: The paper notes that time consumption statistics are based on simulations and may be an overestimation compared to real-world scenarios, requiring careful consideration for practical deployment.
  • Future Work: The authors propose several directions:
  • Hardware Implementation: Deploying the system on heterogeneous robot teams (ground vehicles and drones) for applications like warehouse automation and search-and-rescue.
  • Real-time Optimization: Investigating parallel computing architectures and GPU acceleration for sub-millisecond response times.
  • Perception Enhancement: Extending the system to vision-based SLAM and integrating semantic understanding for navigation in human-populated environments.
  • Adaptability: Making the system adaptable to robot teams with varying capabilities, sizes, and kinematic constraints.
  • Theoretical Guarantees: Developing formal safety certificates and convergence guarantees for the combined learning-optimization framework.

Summary updated

Abstract

Multi-robot systems are significant in decision-making capabilities and applications, but avoiding collisions during movement remains a critical challenge. Existing decentralized obstacle avoidance strategies, while low in computational cost, often fail to ensure safety effectively. To address this issue, this paper leverages graph neural networks (GNNs) and deep reinforcement learning (DRL) to aggregate high-dimensional features as inputs for reinforcement learning (RL) to generate paths. Additionally, it introduces safety constraints through an artificial potential field (APF) to optimize these trajectories. Additionally, a constrained nonlinear optimization method further refines the APF-adjusted paths, resulting in the development of the GNN-RL-APF-Lagrangian algorithm. By combining APF and nonlinear optimization techniques, experimental results demonstrate that this method significantly enhances the safety and obstacle avoidance capabilities of multi-robot systems in complex environments. The proposed GNN-RL-APF-Lagrangian algorithm achieves a 96.43% success rate in sparse obstacle environments and 89.77% in dense obstacle scenarios, representing improvements of 59% and 60%, respectively, over baseline GNN-RL approaches. The method maintains scalability up to 30 robots while preserving distributed execution properties.
BibTeX
@inproceedings{yifei2025decentralized,
  author = {BI Yi-fei and Jianing Luo and Jiwei Zhu and Junxiu Liu and Wei Li},
  title = {{Decentralized Multi-Robot Navigation Based on Deep Reinforcement Learning and Trajectory Optimization}},
  booktitle = {Biomimetics},
  year = {2025},
  doi = {10.3390/biomimetics10060366},
}
Figure