Multi-Goal Feasible Path Planning Using Ant Colony Optimization

Abstract — A new algorithm for solving multi-goal planning problems in the presence of obstacles is introduced. We extend ant colony optimization (ACO) from its well-known application, the traveling salesman problem (TSP), to that of multi-goal feasible path planning for inspection and surveillance appli-cations. Specifically, the ant colony framework is combined with a sampling-based point-to-point planning algorithm; this is compared with two successful sampling-based multi-goal planning algorithms in an obstacle-filled two-dimensional envi-ronment. Total mission time, a function of computational cost and the duration of the planned mission, is used as a basis for comparison. In our application of interest, autonomous undewater inspections, the ACO algorithm is found to be the best-equipped for planning in minimum mission time, offering an interior point in the tradeoff between computational complexity and optimality. I