Main /
PublicationJ. Kottinger, S. Almagor and M. Lahijanian. ConflictBased Search for Explainable MultiAgent Path Finding. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pages (in print), 2022. Abstract: In the MultiAgent Path Finding (MAPF) problem, the goal is to find noncolliding paths for agents in an environment, such that each agent reaches its goal from its initial location. In safetycritical applications, a human supervisor may want to verify that the plan is indeed collisionfree. 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 explainable MAPF problem asks for a set of noncolliding paths that admits a shortenough explanation. Explainable MAPF adds a new difficulty to MAPF, in that it is NPhard 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 explainableMAPF. In this work, we adapt Conflict Based Search (CBS), a wellstudied 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 tradeoff between planning time and explainability.
