en.Wedoany.com Reported - A Chinese research team has proposed a new paradigm called DPCN (Decentralized-Planning-Centralized-Negotiation) to address the Multi-Agent Path Planning (MAPF) problem. This paradigm maintains the scalability of decentralized approaches while effectively handling dynamic conflicts through a centralized negotiation mechanism, achieving performance superior to existing reinforcement learning methods on standard benchmarks.
Multi-Agent Path Planning aims to plan collision-free paths for multiple agents in a shared environment, with wide applications in automated warehousing, service robot scheduling, and airport logistics. Traditional centralized planning strategies perform well on small-scale problems but face a sharp increase in computational complexity when dealing with large-scale agent teams. Decentralized methods based on reinforcement learning offer scalability and environmental adaptability, but are limited by local observation fields, which can easily lead to congestion, collisions, and even deadlocks.
DPCN divides each time step into two phases: in the planning phase, each agent independently generates an action intention based on local observation information o_i^t (with a field of view of 3×3); in the negotiation phase, the system detects all potential conflicts (including vertex conflicts and swap conflicts) and dynamically aggregates the agents involved in conflicts into "super agents." Through a learnable PNSE network (Pointer Network Special Edition), a "winner" is selected from the conflict set based on the environmental state to execute its original intention, while the remaining agents remain stationary or resample new actions.
To address the challenges of inconsistent action sets and dynamic training difficulties for super agents, the PNSE network, inspired by pointer networks, can handle variable-length inputs and inconsistent action spaces. The research team proposed a customized policy gradient reinforcement learning training mechanism, employing a mean-field approximation for fair distribution of global rewards, enabling effective training of dynamic super agents.
Experiments were conducted on standard MAPF benchmarks and random maps, comparing two types of centralized planners (ODrM*, BALANCE) and three cutting-edge RL methods (SCRIMP, DCC, PICO). Random map experiments set map sizes from 30×30 to 100×100, obstacle densities from 0% to 30%, and agent counts from 32 to 256. Each setting was repeated 200 times, reporting success rates and task completion steps. Results show that DPCN consistently maintains high success rates and low task completion times in high obstacle density (30%) and large-scale scenarios, significantly outperforming other RL methods and surpassing centralized planners.
When evaluating generalization ability on structured maps, experiments used three typical map types: a multi-room environment of size 32×32 (room size 3×3), an auditorium environment of 162×141, and a warehouse environment of 170×84 (with shelf aisle width of only 2 cells). Each map contained 25 problem instances. DPCN maintained efficient coordination of large-scale teams in these complex structures.
The research team noted that DPCN, through its innovative architecture of decentralized planning and centralized negotiation, effectively resolves conflict coordination challenges under local observation while maintaining scalability. Future work will explore applications in dynamic obstacles, heterogeneous agents, and real robot platforms.
