Routing for bridge inspecting robots using a metaheuristic genetic algorithm
Abstract
Deteriorating bridge infrastructure accounts for billions per year in inspection costs worldwide and recent advances in robotics and autonomy for bridge inspection can significantly decrease these costs. However, generating optimal tours for inspection robots to cover all members of a bridge truss maps to the well known but NP-hard Min-Max k-Chinese Postman arc-routing problem. We thus attack this problem with a new meta-heuristic genetic algorithm that quickly produces near-optimal balanced tours for k robots. Meta-heuristic genetic algorithm produced tour quality is statistically indistinguishable from best know results on common benchmarks. Scaling up to real-world bridge sizes, our genetic algorithm produces significantly better (15.24%) tours in a fraction of the time (0.05) compared to a prior genetic algorithm approach using a direct encoding. These results show the potential of our new approach for the broad class of arc-routing problems and specifically for quickly generating high-quality tours for robot-assisted real-world bridge inspection tasks.
Department(s)
Computer Science
Document Type
Conference Proceeding
DOI
10.1145/3520304.3529057
Keywords
bridge inspection, combinatorial optimization, genetic algorithms, metaheuristics, routing and layout
Publication Date
7-9-2022
Recommended Citation
Liu, Siming; Dedeurwaerder, Bryan; Louis, Sushil J.; and Harris, Nicholas, "Routing for bridge inspecting robots using a metaheuristic genetic algorithm" (2022). Faculty Scholarship. 745.
https://bearworks.missouristate.edu/articles00/745
Journal Title
Gecco 2022 Companion Proceedings of the 2022 Genetic and Evolutionary Computation Conference
