Boolean Satisfiability Approach to Optimal Multi-agent Path Finding under the Sum of Cost Objective

Abstract

This paper focuses on finding optimal solutions to the multi-agent path finding (MAPF) problem over undirected graphs where the task is to find non-colliding paths for multiple agents, each with a different start and goal position. An encoding of MAPF to Boolean satisfiability (SAT) is already known to the makespan optimal variant of the problem.

Keywords

• Boolean Satisfiability Approach
• Optimal Multi-agent Path Finding
• Sum Cost Objective