  Path planning for multiple robots (MRPP) represents a task of finding
non-colliding paths for robots through which they can navigate from their
initial positions to specified goal positions. The problem is usually modeled
using undirected graphs where robots move between vertices across edges.
Contemporary optimal solving algorithms include dedicated search-based methods,
that solve the problem directly, and compilation-based algorithms that reduce
MRPP to a different formalism for which an efficient solver exists, such as
constraint programming (CP), mixed integer programming (MIP), or Boolean
satisfiability (SAT). In this paper, we enhance existing SAT-based algorithm
for MRPP via spartification of the set of candidate paths for each robot from
which target Boolean encoding is derived. Suggested sparsification of the set
of paths led to smaller target Boolean formulae that can be constructed and
solved faster while optimality guarantees of the approach have been kept.

Robotics;Artificial Intelligence