This paper studies the optimal visibility coverage for autonomous robots in complex 3D environments. When a robot equipped with a range sensor is sent to inspect a 3D region, we want the complete visual coverage on the entire region using smallest number of scans. The practical sensor equipped on the robot usually has a pyramid-shaped visible range with restricted scanning distance and angle. Finding the optimal pyramid visibility coverage of a 3D region is NP hard. In this paper we present an efficient computation algorithm to find a good approximate solution. Our framework allows the user to flexibly specify a coverage rate parameter to balance the percentage of visibility and the required guarding points for the given region. The algorithm is assessed in a simulated 3D pipeline environment for the detection of leak, clog, and deformation.
This paper introduces a hierarchical optimization algorithm to an open NP-hard 3D guarding problem for massive data sets. The proposed hierarchical integer linear programming (HILP) algorithm can find the fewest spots necessary to cover an entire given 3D region. Efficiently solving this problem can greatly benefit autonomous pipeline monitoring and inspections. Unlike most existing pipeline inspection systems that focus on designing mobility and control of the explore robots, this frame- work focuses on planning automatic and thorough inspection in a complex environment. We demonstrate its efficacy on a simulated system built upon scanned pipelines environments using our prototype robots, in which leaks, clogs, and deformation can be thoroughly detected.