Linear programming for UAVs search path planning in livestock health monitoring

UAV-Assisted Livestock Monitoring is a highly relevant and essential application. It involves deploying autonomous Unmanned Aerial Vehicles (UAVs) to gather remote information from various sensors and IoT devices attached to the livestock's necks. Such information includes the health status indicators of the cattle like temperature, respiration rate, images or videos of the activity, etc. The practical implementation of this application presents several challenges. One significant obstacle is the lack of accurate cattle position information. Employing the Global Positioning System (GPS) has limitations like the high cost, and the need for a reliable network connection, which may not be available in all rural areas. Even using passive tags like RFID tags is not very practical due to their limited reading distance. Thus, the imperfect knowledge of the cattle location forces the UAV to perform area exploration and cattle searches. The focus of this research work is to design a model that determines the optimal UAV search path to localize cattle.¹ We denote this issue as UAV Cattle Search (UCS) path planning. In a previous work (Benalaya et al., 2022), we addressed the UCS problem assuming a single stationary cattle (denoted UCS-ST problem). We now extend this problem with two new assumptions : (i) a single moving cattle (UCS-SMT problem), and (ii) two moving cattle (UCS-TMT problem). For each of these problems, we elaborate a Mixed-Integer Linear Programming formulation (MILP) where the objective function is the total expected search time. Minimizing the search time is crucial for successful search missions. However, to the best of our knowledge, the literature did not focus on finding the fastest path while guaranteeing the target localization. Thus, in the conducted work, we focused on the time required for a UAV to locate a target and formulated an objective function aiming at reducing this time. We implemented the models using mathematical optimization software. Running different instances, our models find optimal solutions that guarantee accurate cattle localization while minimizing the expected search time for graphs including up to 36 vertices (UCS-ST). We have been inspired by established formulations in the literature addressing related problems such as the Traveling Salesman Problem and Optimal Search path. However, to the best of our knowledge, the exact linear formulations of our specific problems have never been proposed.