Search papers, labs, and topics across Lattice.
This paper tackles the Graph Inspection Planning (GIP) problem, which seeks to find the shortest robot path to inspect points of interest. The authors reformulate the core constraints of GIP as a network flow problem, enabling more effective Mixed Integer Linear Programming (MILP) models. Their specialized Branch-and-Cut solver, exploiting the combinatorial structure of flows, achieves significantly tighter lower bounds (30-50% reduction in optimality gaps) and unprecedented scalability, handling problems with up to 15,000 vertices.
By reframing robot inspection planning as a network flow problem, this work achieves a 30-50% reduction in optimality gaps and scales to instances previously intractable for state-of-the-art methods.
Inspection planning is concerned with computing the shortest robot path to inspect a given set of points of interest (POIs) using the robot's sensors. This problem arises in a wide range of applications from manufacturing to medical robotics. To alleviate the problem's complexity, recent methods rely on sampling-based methods to obtain a more manageable (discrete) graph inspection planning (GIP) problem. Unfortunately, GIP still remains highly difficult to solve at scale as it requires simultaneously satisfying POI-coverage and path-connectivity constraints, giving rise to a challenging optimization problem, particularly at scales encountered in real-world scenarios. In this work, we present highly scalable Mixed Integer Linear Programming (MILP) solutions for GIP that significantly advance the state-of-the-art in both runtime and solution quality. Our key insight is a reformulation of the problem's core constraints as a network flow, which enables effective MILP models and a specialized Branch-and-Cut solver that exploits the combinatorial structure of flows. We evaluate our approach on medical and infrastructure benchmarks alongside large-scale synthetic instances. Across all scenarios, our method produces substantially tighter lower bounds than existing formulations, reducing optimality gaps by 30-50% on large instances. Furthermore, our solver demonstrates unprecedented scalability: it provides non-trivial solutions for problems with up to 15,000 vertices and thousands of POIs, where prior state-of-the-art methods typically exhaust memory or fail to provide any meaningful optimality guarantees.
