A multi-threaded greedy heuristic for geometric path planning of unmanned aerial vehicles

Abstract

The tremendous potential of the unmanned aerial vehicles (UAVs) and their improved variants with the military equipments seen on the surveillance, reconnaissance, monitoring and combat missions collected the researchers’ attentions for solving challenging problems about them. One of these challenging problems about the mentioned vehicles is related to how a flight path is calculated by considering the minimization goals or constraints for the enemy threats, fuel or battery usage and turning maneuvers. The Back-and-Forth (BaF) algorithm has been introduced recently as a solver for the UAV path planning problem and its promising performance against the well-known meta-heuristic based techniques has been validated. In this study, the greedy heuristic of the BaF algorithm was combined with the computational power of a multi-threaded system and subtly designed search bound adjustment strategy and then a new approach called the Parallel Planner for short PPlanner was developed. The capabilities of the PPlanner was investigated in detail by changing the number of concurrent threads and using twelve test cases from three fixed altitude battlefield scenarios. Moreover, the paths calculated with the PPlanner were compared to the paths of the BaF algorithm and fourteen different meta-heuristic guided techniques. Experimental studies showed that while the PPlanner obtains more qualified paths for six of twelve cases than all other competitors, it is ranked as the second or third best path planner for the remaining cases and positioned among the top three methods even though consuming at least three times less function evaluations.