DMAPF: A Decentralized and Distributed Solver for Multi-Agent Path Finding Problem with Obstacles

Poom Pianpak, Tran Cao Son

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:

  1. 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.
  2. Hierarchical Planning:
    • Abstract Planning: Agents first determine a high-level sequence of "areas" they must visit to reach their goal.
  3. Movement Planning: Local solvers use Answer Set Programming (ASP) to find specific tile-to-tile movements within their assigned subproblem.
  4. Migration Protocol: To move from one solver's jurisdiction to another, DMAPF uses a three-phase interaction protocol:
  5. Negotiation: Solvers propose border crossings for agents.
  6. Rejection: Solvers check for potential corner collisions or congestion and reject problematic migrations.
  7. Confirmation: Finalized moves are executed, and agent data is transferred between nodes.
  8. 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

Abstract

Multi-Agent Path Finding (MAPF) is a problem of finding a sequence of movements for agents to reach their assigned location without collision. Centralized algorithms usually give optimal solutions, but have difficulties to scale without employing various techniques - usually with a sacrifice of optimality; but solving MAPF problems with the number of agents greater than a thousand remains a challenge nevertheless. To tackle the scalability issue, we present DMAPF - a decentralized and distributed MAPF solver, which is a continuation of our recently published work, ros-dmapf. We address the issues of ros-dmapf where it (i) only works in maps without obstacles; and (ii) has a low success rate with dense maps. Given a MAPF problem, both ros-dmapf and DMAPF divide the map spatially into subproblems, but the latter further divides each subproblem into disconnected regions called areas. Each subproblem is assigned to a distributed solver, which then individually creates an abstract plan - a sequence of areas that an agent needs to visit - for each agent in it, and interleaves agent migration with movement planning. Answer Set Programming, which is known for its performance in small but complex problems, is used in many parts including problem division, abstract planning, border assignment for the migration, and movement planning. Robot Operating System is used to facilitate communication between the solvers and to enable the opportunity to integrate with robotic systems. DMAPF introduces a new interaction protocol between the solvers, and mechanisms that together result in a higher success rate and better solution quality without sacrificing much of the performance. We implement and experimentally validate DMAPF by comparing it with other state-of-the-art MAPF solvers and the results show that our system achieves better scalability.
BibTeX
@inproceedings{pianpak2021dmapf,
  author = {Poom Pianpak and Tran Cao Son},
  title = {{DMAPF: A Decentralized and Distributed Solver for Multi-Agent Path Finding Problem with Obstacles}},
  booktitle = {ICLP Technical Communications},
  year = {2021},
  url = {https://openreview.net/forum?id=ycMOqg_QjE5},
}

Loading related content...

Figure