TL;DR
DMAPF is a decentralized and distributed solver designed to tackle the massive scalability challenges of Multi-Agent Path Finding (MAPF). By combining spatial decomposition with the logical power of Answer Set Programming (ASP), it successfully coordinates over 1,800 agents in obstacle-laden environments—outperforming state-of-the-art centralized solvers in large-scale scenarios.
What Problem Does This Paper Address?
Multi-Agent Path Finding (MAPF) is the task of finding collision-free paths for a fleet of robots moving from start locations to goals. While centralized algorithms (like Conflict-Based Search) provide optimal or near-optimal solutions, they hit a "scalability wall" as the number of agents grows. Coordinating more than a thousand agents in real-time remains a significant hurdle for warehouse automation and swarm robotics.
The authors previously developed ros-dmapf, a decentralized solver, but it had two major flaws: it couldn't handle obstacles and it failed frequently in "dense" maps where many agents competed for space. DMAPF (Distributed Multi-Agent Pathfinder) was built to overcome these hurdles, specifically targeting large-scale problems with complex geometry.
Methods
DMAPF utilizes a "divide and conquer" strategy integrated into a distributed architecture:
- Spatial Decomposition: The map is divided into subproblems, each assigned to a dedicated solver (a ROS node). Crucially, DMAPF further divides these subproblems into "areas"—disconnected regions separated by obstacles.
- Hierarchical Planning:
- Abstract Planning: Agents first determine a high-level sequence of "areas" they must visit to reach their goal.
- Movement Planning: Local solvers use Answer Set Programming (ASP) to find specific tile-to-tile movements within their assigned subproblem.
- Migration Protocol: To move from one solver's jurisdiction to another, DMAPF uses a three-phase interaction protocol:
- Negotiation: Solvers propose border crossings for agents.
- Rejection: Solvers check for potential corner collisions or congestion and reject problematic migrations.
- Confirmation: Finalized moves are executed, and agent data is transferred between nodes.
- Technology Stack: The system uses clingo (an ASP solver) for its reasoning capabilities and ROS (Robot Operating System) for asynchronous communication and synchronization between distributed solvers.
Datasets
The authors evaluated DMAPF using grid-based maps of varying sizes and agent densities:
- Map Sizes: $24 \times 24$, $48 \times 48$, and $96 \times 96$.
- Agent Counts: Ranging from 23 agents up to a massive 1,843 agents.
- Baselines: Compared against its predecessor (ros-dmapf) and ECBS (Enhanced Conflict-Based Search), a popular bounded-suboptimal centralized solver.
Key Insights and Ideas
- Areas vs. Subproblems: By recognizing that obstacles can split a solver's territory into disconnected "areas," DMAPF avoids the pathfinding dead-ends that plagued earlier decentralized attempts.
- Interleaved Migration: Unlike previous versions that tried to agree on all migrations upfront, DMAPF interleaves migration negotiation with local movement planning. This allows the system to dynamically adjust if a specific border crossing becomes too congested.
- ASP for Local Complexity: While ASP is often too slow for global pathfinding, it is exceptionally good at solving the "small but complex" combinatorial problems found at the borders between solvers, such as assigning specific entry/exit tiles to multiple agents simultaneously.
Key Results
- Superior Scalability: On a $48 \times 48$ map, the centralized ECBS solver failed to find a solution within the 180-second timeout once the agent count reached 460. DMAPF solved the same problem in just 15.6 seconds.
- Massive Swarms: DMAPF successfully handled 1,843 agents on a $96 \times 96$ map in approximately 175 seconds—a scenario where both the predecessor ros-dmapf and centralized solvers failed completely.
- Solution Quality: While centralized solvers (when they work) produce shorter paths (lower "makespan"), DMAPF's solution quality remained consistent and significantly better than ros-dmapf due to its improved border assignment mechanism.
Limitations and Future Work
- Communication Overhead: The new interaction protocol is more complex than previous iterations, making DMAPF slightly slower than ros-dmapf on very simple, low-density maps.
- Lack of Backtracking: If movement planning fails even after relaxing goal constraints, the system currently terminates without a solution. The authors suggest that implementing a distributed backtracking mechanism could further improve the success rate.
- Density Balancing: The authors noted that performance degrades when agent density is unevenly distributed. Future work may involve mechanisms to balance agent density across different areas to prevent local bottlenecks.
Summary updated