Description

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.

Location

St. Louis, Missouri

Start Date

8-6-2019 1:20 PM

End Date

8-6-2019 1:40 PM

Meeting Name

INSPIRE-UTC 2019 Annual Meeting

Document Type

Article - Conference proceedings

Document Version

Final Version

File Type

text

Language(s)

English

Source Publication Title

Proceedings of the 9th International Conference on Structural Health Monitoring of Intelligent Infrastructure (2019: Aug. 4-7, St. Louis, MO)

Share

COinS
 
Aug 6th, 1:20 PM Aug 6th, 1:40 PM

A Genetic Algorithm for MinMax K-Chinese Postman Problem with Applications to Bridge Inspection

St. Louis, Missouri

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.