# Multi-Robot Path Deconfliction through Prioritization by Path Prospects

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2019.

## Built on by (most cited first, 8 of 8)

- [A Framework for Real-World Multi-Robot Systems Running Decentralized GNN-Based Policies](https://mlsanity.com/paper/2111.01777/) (2021)
- [Environment Optimization for Multi-Agent Navigation](https://mlsanity.com/paper/2209.11279/) (2022)
- [Constrained Environment Optimization for Prioritized Multi-Agent Navigation](https://mlsanity.com/paper/2305.11260/) (2023)
- [Co-Optimizing Reconfigurable Environments and Policies for Decentralized Multi-Agent Navigation](https://mlsanity.com/paper/2403.14583/) (2024)
- [Effective Integration of Weighted Cost-to-go and Conflict Heuristic within Suboptimal CBS](https://mlsanity.com/paper/2205.11624/) (2022)
- [Learning-guided Prioritized Planning for Lifelong Multi-Agent Path Finding in Warehouse Automation](https://mlsanity.com/paper/2603.23838/) (2026)
- [Local Guidance for Configuration-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2510.19072/) (2025)
- [Simultaneous Computation with Multiple Prioritizations in Multi-Agent Motion Planning](https://mlsanity.com/paper/2501.10781/) (2025)

## Abstract (arXiv)

This work deals with the problem of planning conflict-free paths for mobile robots in cluttered environments. Since centralized, coupled planning algorithms are computationally intractable for large numbers of robots, we consider decoupled planning, in which robots plan their paths sequentially in order of priority. Choosing how to prioritize the robots is a key consideration. State-of-the-art prioritization heuristics, however, do not model the coupling between a robot's mobility and its environment. In this paper, we propose a prioritization rule that can be computed online by each robot independently, and that provides consistent, conflict-free path plans. Our innovation is to formalize a robot's path prospects to reach its goal from its current location. To this end, we consider the number of homology classes of trajectories, and use this as a prioritization rule in our decentralized path planning algorithm, whenever any robots enter negotiation to deconflict path plans. This prioritization rule guarantees a partial ordering over the robot set. We perform simulations that compare our method to five benchmarks, and show that it reaches the highest success rate (w.r.t. completeness), and that it strikes the best balance between makespan and flowtime objectives.