Multi Agent Path Finding under Obstacle Uncertainty


  • Bar Shofer Ben Gurion University
  • Guy Shani Ben Gurion University
  • Roni Stern Ben Gurion University of the Negev



Multi-agent and distributed planning, Uncertainty and stochasticity in planning and scheduling, Partially observable and unobservable domains


In multi-agent path finding (MAPF), several agents must move from their current positions to their target positions without colliding. Prior work on MAPF commonly assumed perfect knowledge of the environment. We consider a MAPF setting where this is not the case, and the planner does not know a-priori whether some positions are blocked or not. To sense whether such a position is traversable, an agent must move close to it and adapt its behavior accordingly. In this work we focus on solving this type of MAPF problem, for cases where planning is centralized but cannot be done during execution. In this setting, a solution can be formulated as a plan tree for each agent, branching on the observations. We propose algorithms for finding such plans trees for two modes of executions: centralized, where the agents share information concerning observed obstacles during execution, a decentralized, where such communication is not allowed. The proposed algorithms are complete and can be configured to optimize solution cost, measured for either the best case or the worst case. We implemented these algorithms and provide experimental results demonstrating how our approach scales with respect to the number of agents and the number of positions we are uncertain about. The results show that our algorithms can solve non-trivial problems, but also highlight that this type of MAPF problems is significantly harder than classical MAPF.




How to Cite

Shofer, B., Shani, G., & Stern, R. (2023). Multi Agent Path Finding under Obstacle Uncertainty. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 402-410.