Publication

P. Surynek. Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2021.

Abstract: Path planning for multiple robots (MRPP) represents a task of finding non-colliding paths for robots via which they can navigate from their initial positions to specified goal positions. The problem is often modeled using undirected graphs where robots move between vertices across edges while no two robots can simultaneously occupy the same vertex nor can traverse an edge in opposite directions. 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 linear programming (MIP), or Boolean satisfiability (SAT). In this paper, we enhance existing SAT-based algorithm for MRPP via sparsification of the set of candidate paths for each robot from which the target Boolean encoding is derived. Suggested sparsification of the set of paths led to a smaller target Boolean formulae that can be constructed and solved faster while optimality guarantees of the approach have been kept.

Download the paper in pdf.