Integer Programming as a General Solution Methodology for Path-Based Optimization in Robotics: Principles, Best Practices, and Applications

摘要: Integer programming (IP) has proven to be highly effective in solving many path-based optimization problems robotics. However, the applications of IP are generally done an ad-hoc, problem specific manner. In this work, after examined a wide range problems, we describe solution methodology for these that is both easy apply (in two simple steps) and high-performance terms computation time achieved optimality. We demonstrate generality our approach through application three challenging problems: multi-robot path planning (MPP), minimum constraint removal (MCR), reward collection RCPs). Associated experiments show can efficiently produce (near-)optimal solutions with large state spaces, complex constraints, complicated objective functions. conjunction proposition methodology, introduce new practical robotics (MMCR) (MPP) partial solutions, which quickly effectively solved using proposed pipeline.