  In multi-agent path finding (MAPF), the task is to find non-conflicting paths
for multiple agents from their initial positions to given individual goal
positions. MAPF represents a classical artificial intelligence problem often
addressed by heuristic-search. An important alternative to search-based
techniques is compilation of MAPF to a different formalism such as Boolean
satisfiability (SAT). Contemporary SAT-based approaches to MAPF regard the SAT
solver as an external tool whose task is to return an assignment of all
decision variables of a Boolean model of input MAPF. We present in this short
paper a novel compilation scheme called DPLL(MAPF) in which the consistency
checking of partial assignments of decision variables with respect to the MAPF
rules is integrated directly into the SAT solver. This scheme allows for far
more automated compilation where the SAT solver and the consistency checking
procedure work together simultaneously to create the Boolean model and to
search for its satisfying assignment.
