A genetic algorithm for minmax k-chinese postman problem with applications to bridge inspection

Abstract

Bridge inspections ensure transportation infrastructure safety and save lives but current manual bridge inspections can be slow and costly. Automated bridge inspection research mitigates these problems and we investigate a multirobot approach to automated bridge inspection by mapping the inspection problem to the well known k-Chinese Postman problem and using multiple robots for faster, more cost-effective, and more standardized bridge inspections. We first show that a genetic algorithm quickly approaches the optimal solution to the 1-postman problem corresponding to a single robot inspecting a bridge. Then, we use the same genetic algorithm to efficiently solve the more difficult, multi-robot, NP-hard, MinMax k-postman problem (k > 1). The genetic algorithm s solutions to this problem represent robot paths that traverse (and thus inspect) every truss at least once and that minimize the length of the longest path traversed by any of the k robots-thus minimizing time and distributing the workload. These simulation results from our immersive bridge inspection simulation and training system built with the Unity3D game engine, show that our genetic algorithm quickly and efficiently produces good paths, and in addition, achieves approximately linear speedup for each robot added to the inspection task.

Department(s)

Computer Science

Document Type

Conference Proceeding

Stable URL

https://scholarsmine.mst.edu/inspire-meetings/2019_meeting/robotic_platform/2/

Publication Date

1-1-2019

Journal Title

9th International Conference on Structural Health Monitoring of Intelligent Infrastructure: Transferring Research into Practice, SHMII 2019 - Conference Proceedings

Citation-only

Share

COinS