Biobjective UAV routing for a mission to visit multiple mobile targets

Abstract

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.

Appendices

Appendix

Radar detection threat measure

We use the radar detection threat measure as in Tezcaner Öztürk and Köksalan (2023). Equation A.1 computes the detection threat of a trajectory between two targets located at Cartesian coordinates $({x}_{a},{y}_{a})$ and $({x}_{b},{y}_{b})$. We integrate the detection probabilities along the trajectory of the UAV in order to come up with the detection threat measure.

$$RDT=\underset{({x}_{a},{y}_{a})}{\overset{({x}_{b},{y}_{b}) }{\int }}{pd}_{(x,y)}ds$$

(A.1)

The detection probability is a function of the signal-to-noise ratio, which depends on the characteristics of the radar and the UAV and is inversely proportional to the fourth power of the distance between them. In Equation A.2, ${R}_{(x,y)}$ is the distance between point $(x,y)$ and the radar and all terms except ${R}_{(x,y)}$ are constant. We can thus write this ratio using the term $C=\frac{{P}_{t}{G}_{t}^{2}{\lambda }^{2}\sigma }{{\left(4\pi \right)}^{3}K{T}_{s}{B}_{n}{L}_{s} }.$

$${S/N}_{\left(x,y\right)}=\frac{{P}_{t}{G}_{t}^{2}{\lambda }^{2}\sigma }{{\left(4\pi \right)}^{3}K{T}_{s}{B}_{n}{L}_{s} {{R}_{(x,y)}}^{4}}=\frac{C}{ {{R}_{(x,y)}}^{4}}$$

(A.2)

We then find the detection probability at a point $(x,y)$ using Equation A.3.

$${pd}_{\left(x,y\right)}=\left\{\begin{array}{l}1 \quad \text{if }\,10\,{\mathrm\,{log}}_{10}\left({S/N}_{\left(x,y\right)}\right)>{\mathrm{UB}}_{S/N}\\ \frac{10\,{\mathrm\,{log}}_{10}\left({S/N}_{\left(x,y\right)}\right)-{\mathrm{LB}}_{S/N}}{{\mathrm{UB}}_{S/N}-{\mathrm{LB}}_{S/N}} \quad \text{if}\, {\mathrm{LB}}_{S/N}<10\,{\mathrm\,{log}}_{10}\left({S/N}_{\left(x,y\right)}\right)\le {\mathrm{UB}}_{S/N}\\ 0 \quad \text{if}\, 10\,{\mathrm\,{log}}_{10}\left({S/N}_{\left(x,y\right)}\right)\le {\mathrm{LB}}_{S/N}\end{array}\right.$$

(A.3)

We present an example that shows the signal-to-noise ratios and the detection probabilities of two points, A and B, in the radar’s effective area in Fig. 9.

Fig. 9

Two points (A and B) in the effective regions of the radar

Here, ${R}_{A}=1.4$ and ${R}_{B}=2.6.$ For $C=2270, { \mathrm{LB}}_{S/N}=15, {\mathrm{UB}}_{S/N}=30,$ the signal-to-noise ratios of the two points are ${S/N}_{\left(A\right)}=590.90$ and ${S/N}_{\left(B\right)}=49.67,$ yielding ${\mathrm{pd}}_{\left(A\right)}=0.85$ and ${\mathrm{pd}}_{\left(B\right)}=0.13$.

The radar detection threat measure is not a probability. It is rather the integration of the detection probabilities along the trajectory of the UAV.

If there are multiple radars on the trajectory, the radar that poses the highest risk is considered as effective as in Tezcaner Öztürk and Köksalan (2023).