Ordering Autonomous Underwater Vehicle Inspection Locations with a Genetic Algorithm

Abstract—This paper describes a genetic algorithm for solving the traveling salesman problem (TSP) for autonomous navigation. The method is applied to autonomous underwater vehicles for efficient path planning during underwater mine inspections, sponsored by the Office of Naval Research. This method is significantly easier to implement and much more extensible to real world variants of TSP, e.g. problems incorporating currents, limited turning radius, limitations in depth changes, etc., than other, more efficient, approaches. A specific case study demonstrates a variation accounting for constant currents. Performance is compared against existing behaviors for path planning implemented in the Mission-Oriented Operating Suite (MOOS). The results show that the genetic algorithm performs significantly better than the approach currently implemented in MOOS and successfully accounts for factors such as currents. I