Biobjective UAV routing for a mission to visit multiple mobile targets

We address the route planning problem of an unmanned air vehicle (UAV) that operates in a two-dimensional hostile terrain monitored with radars. In this terrain, there are a number of targets that are planned to be visited to collect intelligence. We consider a setting where a UAV starts from a base, visits the targets, and returns to the base. Targets may move during the UAV’s mission and their movement directions are unpredictable in advance. We consider two objectives: to minimize distance and to minimize radar detection threat. These objectives are conflicting in the regions monitored by radars. The constructed routes comprise the visiting order to the targets and the trajectories used between the visited pairs of targets. There are many efficient trajectories between the target pairs and many efficient visiting orders of the targets due to the two conflicting objectives. As a result, there are many efficient routes that are combinations of efficient trajectories and efficient orders of visits. Due to the dynamic nature of the problem, there is a need to select the route to follow in real time. To respond to these challenges, we develop an algorithm that finds a preferred route of a route planner (RP) quickly. We characterize the efficient trajectories between target pairs approximately and utilize the RP’s preferences to choose the preferred efficient trajectories and to construct a preferred route. During the flight of the UAV, targets keep moving. We update the route every time the UAV reaches a new target. We also develop a heuristic approach in case the problem needs to be solved faster. We demonstrate our algorithms on 5, 9, and 15-target problems.