# Optimization Dubins Path of Multiple UAVs for Post-Earthquake Rapid-Assessment
## 2 Problem Modeling
### Feasible UAV Path  
Dubins curves are widely used to generate the feasible paths of minimal length for a UAV between any two vertices. Since the length of shortest feasible path between any two vertices is related to the UAV's minimum turning radius, the path length of the heterogeneous UAVs is usually different between the same two points. Reference [20] demonstrated that the sensors on UAVs can capture an area with a width of at least \(2\rho\), so it is a reasonable assumption that any two targets are at least \(2\rho\) apart. There are two kinds of Dubins curves, the first one is with a terminal heading constraint and the other is without any terminal heading constraint [35]. The potential targets studied in this paper have no terminal heading constraints. Therefore, by optimizing the UAV heading angle when accessing each target, the UAV path length can be shortened, resulting in a savings of UAV energy to access more targets and in turn improve the expected profit. Figure 1 shows the heading angle discretization when the UAV accesses a potential target, with the heading angle discretization set defined as  
\[H=\{\theta_{i}:\theta_{i}=\frac{2\pi i}{N_{\theta}},i=0,1,\ldots,N_{\theta}-1\}, \tag{3}\]  
where \(N_{\theta}>0\) is an integer defining the heading angle dispersion rate. For example, for \(N_{\theta}=8\) of Figure 1, the discretization set is \(H=\left\{0^{\circ},45^{\circ},90^{\circ},135^{\circ},180^{\circ},225^{\circ},270 ^{\circ},315^{\circ}\right\}\). The heading angle of the UAV presented in this figure is \(\theta=315^{\circ}\). A feasible path of UAV \(k\) is an ordered set, \(R_{k}\), of at least \(r+2(r\geq 1)\) vertices of the form \(R_{k}=\{q_{D_{k}},q^{k}_{V^{k}_{1}},\cdots,q^{k}_{V^{k}_{l}},\cdots,q^{k}_{V^{k}_ {l}},q_{D_{l}}\}\), where \(V^{k}_{l},l=1,\ldots,r\), corresponds to the index of \(r\) potential targets being accessed in that sequence by UAV \(k\). A feasible multi-UAV rapid-assessment routing scheme is composed of the flight paths of all UAVs, \(\mathit{Scheme}=\{R_{1},\ldots;R_{k};\ldots;R_{k}\},k\in\mathbf{U}\). In the scheme shown in Figure 2, UAV1 starts from \(D_{1}\) at a \(90^{\circ}\) heading angle, first accesses the #1 target at a \(90^{\circ}\) heading angle, then accesses the #4 target at a \(225^{\circ}\) heading angle, and finally returns to \(D_{1}\) at a \(315^{\circ}\) heading angle; UAV2 starts from \(D_{2}\) at a \(315^{\circ}\) heading angle, first accesses the #2 target at a \(315^{\circ}\) heading angle, then accesses the #5 target at a \(225^{\circ}\) heading angle, accesses the #3 target at a \(135^{\circ}\) heading angle, and finally returns to \(D_{2}\) at a \(45^{\circ}\) heading angle. The scheme can be expressed as \(\mathit{Scheme}=\left\{(D_{1},90^{\circ}),(5,90^{\circ}),(4,225^{\circ}),(D_{1}, 315^{\circ});(D_{2},315^{\circ}),(2,315^{\circ}),(5,225^{\circ}),(3,135^{\circ} ),(D_{2},45^{\circ})\right\}\). The #5 target appears twice in \(\mathit{Scheme}\), which means that the #5 target is revisited. According to the research results of [PERSON] [36], the revisiting modes are divided into restricted node revisiting and node revisiting without any restrictions. Considering the actual needs of the task completion time of rapid assessment, this paper adopts the first revisiting method, i.e., to revisit target \(i\), UAV \(k\) has to visit another target before it can return to target \(i\). In this paper, we take the constraint of an overnight stay being forbidden, which refers to the naming of the first revisiting mode in [36], as an important constraint of the MURARP model. The feasible path of UAV \(k\) consists of the following three parts: (i) the path from UAV's configuration at launching depot \(q_{D_{k}}\) to the entry configuration at the first target \(q^{k}_{V^{k}_{1}}\); (ii) all the feasible paths from the exit configuration \(q^{k}_{V^{k}_{1}}\) of current target \(V^{k}_{l}\) to the entry configuration \(q^{k}_{V^{k}_{l+1}}\) of the next  
Figure 1: Sample diagram of heading angle discretization with \(N_{\theta}=8\).