# Multi-Robot Reliable Navigation in Uncertain Topological Environments with Graph Attention Networks

arXiv: https://arxiv.org/abs/2411.16134 · HTML: https://mlsanity.com/paper/2411.16134/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for robot navigation and UAV control, one of 15 directions in Deep reinforcement learning methods.
- Builds on 15 of its 38 references that are in the map.
- First posted on arXiv 25 Nov 2024.

## Placed in

- Deep reinforcement learning methods / [RL for robot navigation and UAV control](https://mlsanity.com/deeprl/rl-for-robot-navigation-and-uav-control/)

## Builds on (most cited first, 15 of 15)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Deep Reinforcement Learning for Multi-Agent Systems: A Review of Challenges, Solutions and Applications](https://mlsanity.com/paper/1812.11794/) (2018)
- [Graph Neural Networks for Decentralized Multi-Robot Path Planning](https://mlsanity.com/paper/1912.06095/) (2019)
- [PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong](https://mlsanity.com/paper/2010.08184/) (2020)
- [Message-Aware Graph Attention Networks for Large-Scale Multi-Robot Path Planning](https://mlsanity.com/paper/2011.13219/) (2020)
- [SCRIMP: Scalable Communication for Reinforcement- and Imitation-Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2303.00605/) (2023)
- [Distributed Heuristic Multi-Agent Path Finding with Communication](https://mlsanity.com/paper/2106.11365/) (2021)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [Multi-Agent Path Finding with Delay Probabilities](https://mlsanity.com/paper/1612.05309/) (2016)
- [Multi-Agent Path Finding with Prioritized Communication Learning](https://mlsanity.com/paper/2202.03634/) (2022)
- [ALPHA: Attention-based Long-horizon Pathfinding in Highly-structured Areas](https://mlsanity.com/paper/2310.08350/) (2023)
- [Social Behavior as a Key to Learning-based Multi-Agent Pathfinding Dilemmas](https://mlsanity.com/paper/2408.03063/) (2024)

## Abstract (arXiv)

This paper studies the multi-robot reliable navigation problem in uncertain topological networks, which aims at maximizing the robot team's on-time arrival probabilities in the face of road network uncertainties. The uncertainty in these networks stems from the unknown edge traversability, which is only revealed to the robot upon its arrival at the edge's starting node. Existing approaches often struggle to adapt to real-time network topology changes, making them unsuitable for varying topological environments. To address the challenge, we reformulate the problem into a Partially Observable Markov Decision Process (POMDP) framework and introduce the Dynamic Adaptive Graph Embedding method to capture the evolving nature of the navigation task. We further enhance each robot's policy learning process by integrating deep reinforcement learning with Graph Attention Networks (GATs), leveraging self-attention to focus on critical graph features. The proposed approach, namely Multi-Agent Routing in Variable Environments with Learning (MARVEL) employs the generalized policy gradient algorithm to optimize the robots' real-time decision-making process iteratively. We compare the performance of MARVEL with state-of-the-art reliable navigation algorithms as well as Canadian traveller problem solutions in a range of canonical transportation networks, demonstrating improved adaptability and performance in uncertain topological networks. Additionally, real-world experiments with two robots navigating within a self-constructed indoor environment with uncertain topological structures demonstrate MARVEL's practicality.