Coverage Motion Planning for Search and Rescue Missions : A Costmap Based Approach for fixed wing UAVs using Simulated Annealing &Cubic Splines

Abstract: The present study proposes a novel approach to Coverage Path Planning for unmanned aerial vehicle (UAV) inspired by the Orienteering Problem. The main goal is to develop an algorithm suitable for Search and Rescue Missions, which can produce a search pattern with dynamical constrains, that is not limited to the traditional back-and-forth motion or spiral patterns. This method leads to a more flexible and diverse coverage of the Area of Interest. In order to generate dynamically correct trajectories, we utilize cubic splines as motion primitives to solve the Orienteering Problem. To accomplish this, we implement and test three different types of cubic splines, namely Catmull-Rom, Freya, and B-splines. To determine the coverage of the search area, the sensor's projection (footprint) is evaluated along the spline trajectory onto a costmap. This method accounts for the footprint's orientation and size, which depend on the UAV's attitude to some extent. This version of the Orienteering Problem using splines for dynamical control and calculating coverage, we call the Mapping Motion Orienteering Problem (MMOP). \\The heuristic method Simulated Annealing is used to address the combinatorial challenges of the MMOP, and two cost functions are tested for optimization. The study shows that the choice of spline has a significant impact on the algorithm's efficacy, and B-splines are the most effective in generating dynamic and adaptable trajectories. However, the study also shows that the Simulated Annealing algorithm with identical settings produced varied resulting paths. Finally, further research is needed to solve the challenges faced with the computational time, which heavily depends on factors such as the sampling rate for the footprint along the path and the resolution of the costmap and footprint itself.