UAV Search Path Optimization for Recording Emerging Targets

This paper considers the situation where targets emerge according to a nonhomogeneous space-time Poisson process during the mission. The only provided information is the time-dependent arrival rate function for each cell in the area. Two heuristics are proposed. The first heuristic is based on an approximation of the target recording problem as an orienteering problem with time windows (OPTW), in which the time window settings for each cell are associated with the type of target-emerging condition that it represents. The second heuristic is based on a tabu search method. To analyze the effectiveness of both heu-ristics, target arrivals are simulated across a suitable number of replications and summary statistics are obtained. Further, computational testing is conducted to study the impacts of three factors: sensor-capture radius, unmanned aerial vehicle (UAV) speed, and UAV service time. The factorial analysis shows that sensor-capture radius and UAV service time affect performance significantly. Both heuristics deliver comparable solutions, with the tabu search method consuming less CPU time. In terms of managerial insights, what we find is that cell visitation priorities should be based on a combination of factors that includes its target-emerging conditions, distance from the start and end points, and available mission time.