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

Nicholas Harris
Siming Liu, Missouri State University
Sushil J. Louis
Hung Hung La

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.