Congestion Mitigation Path Planning for Large-Scale Multi-Agent Navigation in Dense Environments
Takuro Kato, Keisuke Okumura,, Yoko Sasaki, Naoya Yokomachi
AI summary
Problem
High-density multi-agent navigation suffers from local congestion and deadlocks when agents operate semi-decentrally, while existing coordination methods lack scalability or rely on rigid structures and pre-training.
Approach
CMPP models environments as sparse graphs and assigns multiplicative penalties to vertices based on incoming agent flows, solved via an exact MINLP solver or a scalable anytime tree-search algorithm to yield congestion-minimizing routes.
Key results
- Formulation of CMPP with a multiplicative vertex congestion cost function
- Development of A-CMTS, a scalable two-layer anytime search algorithm
- ORCA integration raises 400-agent navigation success rate from 83.9% to 99.0%
- PIBT coupling yields up to 58% throughput gain for 1,500 agents in warehouse simulations
Why it matters
Provides a scalable, model-free routing framework that enhances throughput and prevents deadlocks in real-world multi-agent systems like logistics warehouses and autonomous vehicle networks.
Abstract
In high-density environments where numerous au- tonomous agents move simultaneously in a distributed manner, streamlining global flows to mitigate local congestion is crucial to maintain overall navigation efficiency. This paper introduces a novel path-planning problem, congestion mitigation path plan- ning (CMPP), which embeds congestion directly into the cost function, defined by the usage of incoming edges along agents’ paths. CMPP assigns a flow-based multiplicative penalty to each vertex of a sparse graph, which grows steeply where frequently- traversed paths intersect, capturing the intuition that congestion intensifies where many agents enter the same area from different directions. Minimizing the total cost yields a set of coarse-level, time-independent routes that autonomous agents can follow while applying their own local collision avoidance. We formulate the problem and develop two solvers: (i) an exact mixed-integer nonlinear programming solver for small instances, and (ii) a scalable two-layer search algorithm, A-CMTS, which quickly finds suboptimal solutions for large-scale instances and iteratively refines them toward the optimum. Empirical studies show that augmenting state-of-the-art collision-avoidance planners with CMPP significantly reduces local congestion and enhances system throughput in both discrete- and continuous-space scenarios. These results indicate that CMPP improves the performance of multi-agent systems in real-world applications such as logistics and autonomous-vehicle operations.