A multi-threaded back-and-forth algorithm for planning unmanned aerial vehicles

Abstract A path being planned for an unmanned aerial vehicle (UAV) or its armed conformation called the unmanned combat aerial vehicle (UCAV) has a critical importance on the flight safety and success of the task including reconnaissance, surveillance, monitoring or destroying. The Back-and-Forth (BaF) algorithm is one of the most recent greedy techniques that executes a heuristic approach for generating two backbone candidates and a combination procedure for bringing advantageous segments of them in order to solve the geometric description of the path planning problem. This study was devoted to a thread-based parallel implementation of the BaF algorithm, also named the multi-threaded BaF (tBaF for short). The threads of the tBaF algorithm increase their search bounds gradually according to the assigned thread indexes and execute the heuristic approach and combination procedure of the BaF for calculating paths. A set of detailed experiments was carried out with the aim of evaluating the performance of the tBaF, and its results were compared with the BaF and 14 other meta-heuristic-based path planners over three battlefield scenarios and their 12 test cases containing the preidentified enemy threats. Comparative studies showed that the different local and global search capabilities of the threads gained with the newly introduced thread-based organisation give a significant contribution to the path planning performance and allow the tBaF to be ranked among the top three planners even though it requires at least from four to eight times less function calls than the tested meta-heuristics.