Dynamic and Partially Observable MAPF
An Extended Evaluation Integrating Informed Path Reuse and Context-Aware Planning
Anıl Doğru (Özyeğin University)
Duru Balpınarlı (Özyeğin University)
Amin Deldari Alamdari (Özyeğin University)
Reyhan Aydoğan (TU Delft - Electrical Engineering, Mathematics and Computer Science, Özyeğin University)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Imagine a delivery robot navigating a crowded warehouse, carefully working between shelves and suddenly appearing in front of workers. Alternatively, think of a drone that must quickly change when unexpected obstacles like birds or wind cross its path. In such environments, machines cannot rely on the prior knowledge of the environment, a full view of the world or follow routes. Instead, they must react to what they can see momentarily and make decisions on the fly. Most traditional path planning systems assume that everything in the environment is known in advance and remains unchanged. However, real life is rarely that simple. To address this gap, our previous study introduced a new version of the MAPF problem, Dynamic and Partially Observable Multi-Agent Pathfinding (DPO-MAPF), where agents operate under uncertainty, limited perception, and dynamic changes [8]. We proposed a multitier approach combining global planning with local, online conflict resolution with Ant Colony Optimization. Since conflicts in DPO-MAPF are unpredictable, uncontrollable, and only partially detectable, agents must maximize information utilization to resolve them efficiently. Thus, this paper extends the previous framework with improved revision strategies. Specifically, agent are enabled to reuse earlier parts of their path after detouring, and to consider nearby areas, not just individual locations, when making movement choices. Additionally, the experimental setup is expanded in both diversity and complexity. In particular, evaluations on synthetic and real-world benchmark maps (e.g., MovingAI [41]) demonstrate that these additions improve coordination and success rates, especially in complex, uncertain environments where centralized control is impractical.
Files
File under embargo until 01-12-2026