Adaptive grid-based decomposition for UAV-based coverage path planning in maritime search and rescue

Today, Search and Rescue (SAR) teams are increasingly leveraging advanced technologies such as artificial intelligence and Unmanned Aerial Vehicles (UAVs) to enhance the efficiency of their operations (Martinez-Alpiste et al., 2021). In this context, UAVs, with their high flight speed and ability to scan areas at night or in low-light conditions, can address one of the challenges in SAR operations: monitoring large or hard-to-reach search areas. In ground SAR operations, additional methods such as employing dogs and volunteers can be used alongside UAVs to expedite target searching. However, in maritime SAR operations, fewer options are available, making UAVs particularly important for enhancing operational efficiency. In this regard, one of the main questions is how UAVs should fly to cover the search area in the shortest possible time, a challenge addressed in the literature under the Coverage Path Planning (CPP) problem. Various objective functions were considered in CPP, including the number of turning maneuvers (Maza & Ollero, 2007), path length (Bouzid et al., 2017), flight time (Forsmo et al., 2013), energy consumption (Di Franco and Buttazzo, 2016), and total coverage time (Kazemdehbashi and Liu, 2025). Additionally, two main types of decomposition are used in the CPP problem: exact cell decomposition and grid-based decomposition. In exact cell decomposition, the search area is divided into smaller sub-areas, whereas in grid-based decomposition, the area is represented as a grid, and each grid's cell must be covered to achieve full coverage. In this paper, we propose an Adaptive Grid-based Decomposition (AGD) algorithm to reduce the number of cells in the grid required to cover the primary search area.