Heuristically Guided Compilation for Multi-Agent Path Finding
This work addresses a specific bottleneck in MAPF solvers for robotics or logistics, but it is incremental as it builds on existing compilation methods.
The paper tackles the challenge of integrating domain-specific heuristics into compilation-based solvers for multi-agent path finding (MAPF) by constructing SAT encodings only for candidate paths, which outperforms vanilla SAT-based solvers in experiments.
Multi-agent path finding (MAPF) is a task of finding non-conflicting paths connecting agents' specified initial and goal positions in a shared environment. We focus on compilation-based solvers in which the MAPF problem is expressed in a different well established formalism such as mixed-integer linear programming (MILP), Boolean satisfiability (SAT), or constraint programming (CP). As the target solvers for these formalisms act as black-boxes it is challenging to integrate MAPF specific heuristics in the MAPF compilation-based solvers. We show in this work how the build a MAPF encoding for the target SAT solver in which domain specific heuristic knowledge is reflected. The heuristic knowledge is transferred to the SAT solver by selecting candidate paths for each agent and by constructing the encoding only for these candidate paths instead of constructing the encoding for all possible paths for an agent. The conducted experiments show that heuristically guided compilation outperforms the vanilla variants of the SAT-based MAPF solver.