A genetic algorithm for multi-robot routing in automated bridge inspection

Abstract

We attack the problem of generating balanced and efficient routing for automated inspection by using genetic algorithms to solve the equivalent Min-Max k Windy Chinese Postman Problem. Specifically, we use k robots to collectively inspect every member of a steel truss bridge. Experimental results show that the genetic algorithm produces efficient routes that are well-balanced among the robots. Additionally, we demonstrate that with our novel representation, as the number of robots increases, the generated routes exhibit near-linear speedup in the time needed to complete the inspection task - k robots take k1 th the time needed by one robot. Finally, our genetic algorithm produces similar results on a set of benchmark arc routing problem instances from the literature.

Department(s)

Computer Science

Document Type

Conference Proceeding

DOI

https://doi.org/10.1145/3319619.3321917

Keywords

Arc routing, Bridge inspection, Genetic algorithms, Robot inspection

Publication Date

7-13-2019

Journal Title

GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion

Link to Full Text

Share

COinS