Analysis of TSP Heuristics for Fuel-Constrained UAS Path Planning applied to Polar Research Missions
Aaron T. Blevins, Shawn Keshmiri, Daksh Shukla, Grant Godfrey · AIAA Scitech 2020 Forum · 2020
In this work, various traveling salesman problem (TSP) heuristics are utilized for the path planning of fixed-wing unmanned aircraft performing polar research missions, and these heuristics are then subjected to aircraft fuel-constraints to achieve an efficient route through flight lines while ensuring operational feasibility. These heuristics include a forward-greedy method, a global-greedy method, and ant colony optimization. Path planning between mission flight lines are dynamically constrained by the minimum turning radius of the aircraft through distance-optimal Dubins paths. The performance and computational expense for each heuristic is assessed for Earth Science mission scenarios along the Helheim Glacier, a key area of interest to the scientific community. Realistic fuel constraints are applied for preliminary mission planning for an upcoming UAS research deployment to the area.