The application of a greedy algorithm to search-and-rescue trajectory planning for UAV systems

This paper presents the application of an improved greedy algorithm to generate locally optimal trajectories of UAV systems used for search and rescue in given conditions, which are represented by score maps of probability to detect missing targets. A minor technique was introduced to help UAVs escape from the 'trapped' situation while searching and enhance performance efficiency. The algorithm was applied to systems with single and multiple UAVs searching over the Gaussian-type and random-type score maps. Based on the obtained results, the validity and efficiency of the algorithm have been demonstrated. The effects of some parameters, such as the grid resolution used to generate trajectories and the maximum flight distance, were investigated in this study. It was found that with a given maximum flight distance, there is a compromise between grid resolution and area coverage. UAVs may enhance local search quality by increasing the grid resolution; however, less global coverage can be obtained. This analysis result is important for the trajectory planning of multiple-UAV systems, in which, each UAV may require its own trajectory parameters to fit its flight characteristics.