Presentation description

Industrial robots serve a critical role in modern automation, enhancing fields such as manufacturing, surveillance, surgery, and others. A significant challenge to these applications is inspection planning-the development of a motion plan for efficiently inspecting a set of points of interest (POIs) efficiently. This task is extremely computationally intensive, with the addition of points leading to an exponential growth in the search space.

This project explores practical algorithmic solutions to improve inspection planning by conceptualizing it as a Graph Inspection problem. We model a motion plan in the robot's configuration space as a closed walk in an edge-weighted graph, where POIs are represented as colors associated with the vertices. The goal is to minimize the cost while maximizing the number of inspected POIs. We design several new algorithms, drawing on the problem's similarity to the Travelling Salesperson Problem. Our results prove that the problem can be solved in polynomial time when the number of POIs is bounded, thereby establishing the fixed-parameter tractability of our solvers. Furthermore, we complement our algorithms with several techniques for improving scalability, including principled approaches for reducing the number of POIs, and calculating and then combining several shorter inspection plans that each cover a part of the search space.

We evaluated our approaches against the state-of-the-art in inspection planning algorithm, IRIS-CLI (Fu et al., 2021), on two realistic data sets, one from a bridge inspection task and one from a surgical robotics scenario. The evaluation criteria include solution weight, coverage of points of interest, and computation time. This comparison aims to highlight the efficiency and effectiveness of our proposed solutions in real-world scenarios.