Asymptotically Optimal Path Planning and Surface Reconstruction for Inspection

Book excerpt: Motivated by inspection applications for marine structures, this thesis develops algorithms to enable their autonomous inspection. Two essential parts of the inspection problem are (1) path planning and (2) surface reconstruction. On the first problem, we develop a novel analysis of asymptotic optimality of control-space sampling path planning algorithms. This analysis demonstrated that asymptotically optimal path planning for any Lipschitz continuous dynamical system can be achieved by sampling the control space directly. We also determine theoretical convergence rates for this class of algorithms. These two contributions were also illustrated numerically via extensive simulation. Based on the above analysis, we developed a new inspection planning algorithm, called Random Inspection Tree Algorithm (RITA). Given a perfect model of a structure, sensor specifications, robot dynamics, and an initial configuration of a robot, RITA computes the optimal inspection trajectory that observes all surface points on the structure. This algorithm uses of control-space sampling techniques to find admissible trajectories with decreasing cost. As the number of iterations increases, RITA converges to optimal control trajectories. A rich set of simulation results, motivated by inspection problems for marine structures, illustrate our methods. Data gathered from all different views of the structure are assembled to reconstruct a 3D model of the external surfaces of the structure of interest. Our work also involved field experimentation. We use off-the-shelf sensors and a robotic platform to scan marine structures above and below the waterline. Using such scanned data points, we reconstruct triangulated polyhedral surface models of marine structures based on Poisson techniques. We have tested our system extensively in field experiments at sea. We present results on construction of various 3D surface models of marine structures, such as stationary jetties and slowly moving structures (floating platforms and boats). This work contributes to the autonomous inspection problem for structures and to the optimal path, inspection and task planning problems.