Thesis Defense - Nicholas Harris

Route Optimization for Automated Bridge Inspection with Genetic Algorithm

We develop a Genetic Algorithm (GA) to generate efficient routes for a robotic bridge inspection team. Using robots to automate the process of bridge inspection will improve human safety and reduce time and money allocated to bridge inspections. To do this, we attack the problem of minimizing and balancing routes for a team of robots during a bridge inspection task. In this thesis, we present a GA with a new representation that utilizes Dijkstra’s Algorithm to unfold routes. We apply our GA to this problem to minimize the time needed by a number of robots to cooperatively inspect every member of a steel truss bridge. We also improve this algorithm by incorporating a caching table to store previously computed routes; this results in much faster runtime at the cost of higher memory usage. This task maps well to the NP-Hard Min-Max k-Chinese Postman Problem (MM k-CPP), which is part of the family of Arc Routing Problems (ARPs). These represent a broad class of problems wherein the goal is to traverse every edge of a graph in the most optimal fashion, under some set of constraints. Some variants of this problem, including the MM k-CPP, are NP-hard and therefore optimal solutions for large problems are not tractable to produce in a reasonable amount of time. Results with our new representation demonstrate its ability to produce near-optimal solutions across a wide range of problem instances, under different sets of constraints. The genetic algorithm produces near optimal routes that are equally balanced among the robots, and as the number of inspection robots increases the generated routes produce a linear speedup in the time needed to inspect the entire bridge. We finally develop a methodology to use our GA to produce high-quality inspection routes on real-world bridges within a practical amount of time.

Tuesday, November 26, 2019 at 4:00 pm to 6:00 pm

HREL, 109/110 1664 North Virginia ST, Reno, NV