Lazy Compilation of Variants of Multirobot Path Planning with Satisfiability Modulo Theory (SMT) Approach We address variants of multirobot path planning in graphs (MRPP). We assume robots placed in vertices of an undirected graph with at most one robot per vertex. Robots can move across edges while various problem specific constraints must be satisfied. We introduce a general problem formulation that encompasses known types of robot relocation problems such as multirobot path planning (MRPP), token swapping (TSWAP), token rotation (TROT), and token permutation (TPERM). We generalize SMTCBS, a recent solving approach for MRPP based on satisfiability modulo theories (SMT). SMT CBS compiles MRPP lazily within the SMT framework, starting with the basic model that is refined with a collision resolution constraints whenever collisions between robots occur in the current solution. We show modifications the SMTCBS algorithm for variants of MRPP and evaluate them experimentally.

Integer Programming as a General Solution Methodology for PathBased Optimization in Robotics: Principles, Best Practices, and Applications Integer programming (IP) has proven to be highly effective in solving many pathbased optimization problems in robotics. However, the applications of IP are generally done in an adhoc, problemspecific manner. In this work, after examined a wide range of pathbased optimization problems, we describe an IP solution methodology for these problems that is both easy to apply (in two simple steps) and highperformance in terms of the computation time and the achieved optimality. We demonstrate the generality of our approach through the application to three challenging pathbased optimization problems: multirobot path planning(MPP), minimum constraint removal(MCR), and reward collection problems(RCPs). Associated experiments show that the approach can efficiently produce (near)optimal solutions for problems with large state spaces, complex constraints, and complicated objective functions. In conjunction with the proposition of the IP methodology, we introduce two new and practical robotics problems: multirobot minimum constraint removal(MMCR) and multirobot path planning(MPP) with partial solutions, which can be quickly and effectively solved using our proposed IP solution pipeline.