  Integer programming (IP) has proven to be highly effective in solving many
path-based optimization problems in robotics. However, the applications of IP
are generally done in an ad-hoc, problem specific manner. In this work, after
examined a wide range of path-based optimization problems, we describe an IP
solution methodology for these problems that is both easy to apply (in two
simple steps) and high-performance in terms of the computation time and the
achieved optimality. We demonstrate the generality of our approach through the
application to three challenging path-based optimization problems: multi-robot
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: multi-robot minimum constraint removal (MMCR) and multi-robot path
planning (MPP) with partial solutions, which can be quickly and effectively
solved using our proposed IP solution pipeline.
