Finding All Optimal Solutions in Multi-Agent Path Finding

Abstract

The Multi-Agent Path Finding problem (MAPF) aims to find conflict-free paths for a group of agents, leading each agent to its respective goal. MAPF is applicable in navigating autonomous robots and vehicles to their destination. In this paper, we study the requirement of finding all optimal solutions in MAPF. We discuss the representation of all optimal solutions, propose four algorithms for finding them, and perform an extensive empirical evaluation of the proposed algorithms.