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.
|Advisor:||Louis, Sushil J., La, Hung Manh|
|Commitee:||Moustafa, Mohamed A.|
|School:||University of Nevada, Reno|
|School Location:||United States -- Nevada|
|Source:||MAI 81/8(E), Masters Abstracts International|
|Keywords:||Arc routing, Bridge inspection, Chinese postman, Genetic algorithm, Robotics, Vehicle routing|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be