## 2 Problem Statement  
The kinematics of the UAV can be approximated by the [PERSON] vehicle in the plane. The pose of the [PERSON] vehicle \(X\) can be represented by the triplet \((x,y,\theta)\in SE(2)\), where \((x,y)\in\mathbb{R}^{2}\) define the position of the vehicle in the plane and \(\theta\in\mathbb{S}^{1}\) defines the heading of the vehicle. The vehicle kinematics are then written as,  
\[\begin{bmatrix}\dot{x}\\ \dot{y}\\ \dot{\theta}\end{bmatrix}=\begin{bmatrix}\
u\cos(\theta)\\ \
u\sin(\theta)\\ \frac{\
u}{\rho}u\end{bmatrix} \tag{1}\]  
where \(\
u\) is the forward speed of the vehicle, \(\rho\) is the minimum turning radius, and \(u\in[-1,1]\) is the bounded control input. Let \(\mathcal{L}_{\rho}:SE(2)\times SE(2)\rightarrow\mathbb{R}_{+}\) associate the length \(\mathcal{L}_{\rho}(X_{1},X_{2})\) of the minimum length path from an initial pose \(X_{1}\) of the Dubins vehicle to a final pose \(X_{2}\), subject to the kinematic constraints in Equation (1). Notice that this length depends implicitly on the forward speed of the vehicle and the minimum turning radius through the kinematic constraints in Equation (1). This length, which we will refer to as the Dubins distance from \(X_{1}\) to \(X_{2}\), can be computed in constant time [5].  
Let \(\mathcal{R}=\{\mathcal{R}_{1},\mathcal{R}_{2},...,\mathcal{R}_{n}\}\) be set of \(n\) compact regions in a compact region \(\mathcal{Q}\subset\mathbb{R}^{2}\), and let \(\Sigma=(\sigma_{1},\sigma_{2},\ldots,\sigma_{n})\) be an ordered permutation of \(\{1,\ldots,n\}\). Define a projection from \(SE(2)\) to \(\mathbb{R}^{2}\) as \(\mathcal{P}:SE(2)\rightarrow\mathbb{R}^{2}\), _i.e._, \(\mathcal{P}(X)=[x\;y]^{T}\), and let \(P_{i}\) be an element of \(SE(2)\) whose projection lies in \(\mathcal{R}_{i}\). We denote the vector created by stacking a vehicle configuration \(P_{i}\) for each of the \(n\) regions as \(P\in SE(2)^{n}\).  
The DTSPN involves finding the minimum length tour in which the [PERSON] vehicle visits each region in \(\mathcal{R}\) while obeying the kinematic constraints of Equation (1). This is an optimization over all possible permutations \(\Sigma\) and configurations \(P\). Stated more formally:  
**Problem 2.1** (Dtspn).: \[\underset{\Sigma,P}{\text{minimize}} \mathcal{L}_{\rho}(P_{\sigma_{n}},P_{\sigma_{1}})+\sum_{i=1}^{n-1 }\mathcal{L}_{\rho}(P_{\sigma_{i}},P_{\sigma_{i+1}})\] \[\text{subject to} \mathcal{P}(P_{i})\in\mathcal{R}_{i},\,i=1,\ldots,n\]  
The problem presented in Problem 2.1 is combinatorial in \(\Sigma\), the sequence of regions to visit and infinite dimensional in \(P\), the poses of the vehicle. We present an algorithm to convert this problem to a finite dimensional combinatorial optimization on a graph by first generating a set of \(m\geq n\) sample configurations \(S_{i}\in SE(2)\), \(\mathcal{S}:=\{\mathbf{S}_{1},\ldots,\mathbf{S}_{m}\}\) such that  
\[\mathcal{P}(\mathbf{S}_{k})\in\bigcup_{i=1}^{n}\mathcal{R}_{i},\;k=1,\ldots,m \tag{2}\]  
and \(\forall i\;\exists k\;\text{s.t.}\;\mathcal{P}(\mathbf{S}_{k})\in\mathcal{R}_{i}\). The algorithm then approximates Problem 2.1 by finding the best sample configurations \(P\subseteq\mathcal{S}\) and the order \(\Sigma\) in which to visit them.  
**Problem 2.2** (Sampled DTSPN).: \[\underset{\Sigma,P}{\text{minimize}} \mathcal{L}_{\rho}(P_{\sigma_{n}},P_{\sigma_{1}})+\sum_{i=1}^{n-1 }\mathcal{L}_{\rho}(P_{\sigma_{i}},P_{\sigma_{i+1}})\] \[\text{subject to} \mathbf{P}_{i}\in\mathcal{S}\] \[\mathcal{P}(P_{i})\in\mathcal{R}_{i},\,i=1,\ldots,n\]