Conflict-Based Search for Explainable Multi-Agent Path Finding Conference Proceeding uri icon



  • The goal of the Multi-Agent Path Finding (MAPF) problem is to find non-colliding paths for agents in an environment, such that each agent reaches its goal from its initial location.; In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free. To this end, a recent work introduces a notion of explainability for MAPF based on a visualization of the plan as a short sequence of images representing time segments, where in each time segment the trajectories of the agents are disjoint.; Then, the problem of Explainable MAPF via Segmentation asks for a set of non-colliding paths that admit a short-enough explanation. Explainable MAPF adds a new difficulty to MAPF, in that it is NP-hard with respect to the size of the environment, and not just the number of agents. Thus, traditional MAPF algorithms are not equipped to directly handle Explainable MAPF. In this work, we adapt Conflict Based Search (CBS), a well-studied algorithm for MAPF, to handle Explainable MAPF. We show how to add explainability constraints on top of the standard CBS tree and its underlying A* search. We examine the usefulness of this approach and, in particular, the trade-off between planning time and explainability.

publication date

  • June 11, 2022

has restriction

  • bronze

Date in CU Experts

  • February 1, 2023 10:43 AM

Full Author List

  • Kottinger J; Almagor S; Lahijanian M

author count

  • 3

Other Profiles

International Standard Serial Number (ISSN)

  • 2334-0835

Electronic International Standard Serial Number (EISSN)

  • 2334-0843

Additional Document Info

start page

  • 692

end page

  • 700


  • 32