On Computing Universal Plans for Partially Observable Multi-Agent Path Finding

Fengming Zhu, Fangzhen Lin

Abstract

Decentralized Multi-Agent Path Finding (MAPF) in partially observable environments presents a significant challenge for autonomous robotics. While centralized solvers are efficient for large-scale static environments, they lack robustness in decentralized settings where agents have limited visibility. This paper introduces an Answer Set Programming (ASP) based approach to compute "universal plans"—decentralized policies that guide agents based on local observations. By leveraging inductive reachability and domain-specific heuristics, the proposed system achieves superior scalability compared to traditional Dec-POMDP solvers, handling state spaces with tens of thousands of states.

Introduction

Multi-Agent Path Finding (MAPF) is a foundational problem in robotics, typically solved via centralized computation. However, in real-world scenarios like home or office environments, robots often operate without a central controller and possess limited sensor ranges (partial observability). In such cases, a fixed path is insufficient; instead, robots require a universal plan—a policy that dictates the optimal action for any given local observation. Presented at ICLP 2025, this research by Fengming Zhu and Fangzhen Lin proposes an Answer Set Programming (ASP) framework to generate these robust decentralized policies.

Methodology: Universal Planning via ASP

The core contribution of this work is the shift from path-finding to policy-finding. A universal plan $\pi$ is a decentralized policy computed offline but executed independently by each agent based on its current observation.

Figure 1: Illustration of a universal plan $\pi$ mapping a grid configuration to decentralized execution scenarios for multiple agents.

To compute these policies, the researchers utilize Answer Set Programming (ASP), a declarative logic programming paradigm. The methodology involves:

  1. Inductive Reachability: Defining global states as "reachable" if the current policy eventually leads all agents to their respective goals.
  2. Traffic Rules and Heuristics: To manage the combinatorial explosion of the search space, the system incorporates "Myopic Preferences" (favoring moves that reduce Manhattan distance) and "Traffic Rules" (shared protocols for conflict resolution in tight spaces, such as yielding in corridors).
  3. Anytime Optimization: The solver can minimize the "sum-of-makespan" across all possible starting configurations, ensuring high-quality policies without exhaustive search.

Evaluation and Results

The system was evaluated against standard Dec-POMDP benchmarks and new scaling benchmarks on 2D grids ranging from 3x3 to 6x6 with up to 5 agents.

Table 1: Comparison of state space complexity between standard Dec-POMDP benchmarks and the cases solved by the proposed ASP framework.

Key Insights

  • Superior Scalability: As shown in the comparison above, the ASP-based system successfully handles instances with over 42,000 states (e.g., Grid6x6 with 3 agents), whereas traditional Dec-POMDP solvers often struggle once the state space exceeds a few hundred.
  • Sensor Range Impact: The study identified a "sweet spot" at Sensor Range 2. While Range 1 often leads to unsolvable deadlocks due to late detection, Range 2 provides enough foresight for feasible decentralized coordination.
  • Efficiency Gains: By incorporating "last-minute coordination" heuristics, the researchers reduced the sum-of-makespan in larger grids significantly (e.g., from ~43,000 to ~11,000 in a 6x6 grid), demonstrating that logical constraints can effectively prune the search space without sacrificing policy quality.

Conclusion

By framing decentralized MAPF as a universal planning problem within an ASP framework, this research provides a robust alternative to probabilistic Dec-POMDP solvers. The resulting policies offer logical guarantees of goal reachability and collision avoidance. Future work aims to integrate these symbolic safety rules with Reinforcement Learning to combine logical rigor with the flexibility of neural planners.

Summary updated

BibTeX
@inproceedings{zhu2026computing,
  author = {Fengming Zhu and Fangzhen Lin},
  title = {{On Computing Universal Plans for Partially Observable Multi-Agent Path Finding}},
  booktitle = {Electronic},
  year = {2026},
  doi = {10.4204/eptcs.439.11},
}
Figure