Dissertation/Thesis Abstract

Route Optimization for Automated Bridge Inspection with Genetic Algorithm
by Harris, Nicholas, M.S., University of Nevada, Reno, 2019, 51; 27666630
Abstract (Summary)

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.

Indexing (document details)
Advisor: Louis, Sushil J., La, Hung Manh
Commitee: Moustafa, Mohamed A.
School: University of Nevada, Reno
Department: Computer Science
School Location: United States -- Nevada
Source: MAI 81/8(E), Masters Abstracts International
Source Type: DISSERTATION
Subjects: Computer science
Keywords: Arc routing, Bridge inspection, Chinese postman, Genetic algorithm, Robotics, Vehicle routing
Publication Number: 27666630
ISBN: 9781392794746
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest