Probability-Informed UAV Route Generation in a Search and Rescue Context

Unmanned Aerial Vehicles (UAVs) are a versatile method for quickly providing information for Search and Rescue teams from an aerial perspective. The use of UAVs for Search and Rescue is becoming more prevalent; as such, path planning and route generation must be considered to ensure optimal information gain to support ground-based searchers. Ergodic optimised path planning is one approach; the routes generated are adjusted based on a prior distribution to spend proportionally more time searching in high-likelihood areas than low-likelihood regions. Coverage path planning is another option; a coverage route would typically visit all areas which provide new information before revisiting areas. Some of the benefits of ergodic search address the drawbacks of coverage path planning, and vice versa - hence the need for a method which can utilise both approaches. Ergodic optimised path planning can produce routes where a large portion of time is spent redundantly searching areas which could be covered in a much shorter time, such as flat terrain, whereas coverage planning can lead to routes which may spend disproportionate time searching areas with lower likelihood of detecting a missing person. This paper develops a path planning method combining these two approaches through consideration of systematic and random errors in a custom formulated Travelling Salesman Problem (TSP). The routes produced are assessed against pure coverage searches. The ability of the method to select path planning types is explored, with variation in systematic and random error values used to demonstrate how these impact the optimal solution and the behaviour's shown by the route - ergodic or coverage. Optimising patterns with the new model shows that the combined approach of coverage and ergodic style routing leads to a higher probability of detection within a toy simulation than either approach applied exclusively.