On Tightly Bounding the Dubins Traveling Salesman’s Optimum  Satyanarayana Manyam ∗ ,   Sivakumar Rathinam †  Abstract  The Dubins Traveling Salesman Problem (DTSP) has generated significant interest over the last decade due to its occurrence in several civil and military surveillance applications. Currently, there is no algorithm that can find an optimal solution to the problem. In addition, relaxing the motion constraints and solving the resulting Euclidean TSP (ETSP) provides the only lower bound available for the problem. However, in many problem instances, the lower bound computed by solving the ETSP is far below the cost of the feasible solutions obtained by some well-known algorithms for the DTSP. This article addresses this fundamental issue and presents the first systematic procedure for developing tight lower bounds for the DTSP.  1. Introduction  Given a set of targets on a plane and a constant   ρ   ≥   0, the Dubins Traveling Salesman Problem (DTSP) aims to find a path such that each target is visited at least once, the radius of curvature of any point in the path is at least equal to   ρ , and the length of the path is minimal. This problem is a generalization of the Euclidean TSP (ETSP) and is NP-hard [1, 2].   The DTSP belongs to a class of task allocation and path planning problems envisioned for a team of unmanned aerial vehicles in [3].   The DTSP has received significant attention in the literature [1, 2, 4–14], mainly due to its importance in unmanned vehicle applications, the simplicity of the problem statement, and its status as a hard problem to solve because it inherits features from both optimal control and combinatorial optimization. Currently, there is no procedure for finding an optimal solution for the DTSP. Therefore, heuristics and approximation algorithms have been developed over the last decade to find feasible solutions.   Tang and Ozguner [11] present gradient-based heuristics for both single and multiple vehicle variants of the DTSP. Savla et al. [12] use an optimal solution to the ETSP to find a feasible solution for the DTSP, and they bound the cost of the feasible solution with respect to the optimal cost of the ETSP. Rathinam et al. [1] develop an approximation algorithm for the DTSP in cases where the distance between any two targets is at least equal to 2 ρ . Ny et al. [2] develop an approximation algorithm for the DTSP in which the approximation guarantee is inversely proportional to the minimum distance between any two targets. The weakness of the approximation guarantees of these algorithms for the DTSP is due to the lack of a good lower bound, as all these algorithms essentially use the Euclidean distances between the targets to bound the cost of a feasible solution. Other heuristics have been used for solving the DTSP. A receding horizon approach that involves finding an optimal Dubins path through three consecutive targets is used to generate feasible solutions in [14]. The heuristic in [4] finds a feasible solution by minimizing the sum of the distances travelled by the vehicle and  ∗ National Research Council Fellow, Air Force Research Laboratory, Dayton-Ohio, 45433.  † Associate Professor, Mechanical Engineering, Texas A & M University, College Station, TX-77843,   corresponding author : srathinam@tamu.edu  arXiv:1506.08752v3 [math.OC] 10 Feb 2016
the sum of the changes in the heading angles at each of the targets. Macharet et al. [5,7] first obtain a tour by solving the ETSP and then select the heading angle at each target using an orientation-assignment heuristic. A multiple lookahead approach is used to find feasible solutions in [8, 15]. Meta-heuristics have also been developed to find feasible solutions for the DTSP in [9, 10].  Figure 1. There are four possible headings at each target. A feasible solution for the DTSP can be obtained by choosing a heading at each target and finding a corresponding optimal TSP path.  Another common approach [13,16] involves discretizing the heading angle at each target and posing the resulting problem as a one-in-a-set TSP (Fig. 1). The greater the number of discretizations, the closer an optimal one-in-a-set TSP solution gets to the optimal DTSP solution. This approach provides a natural way to find a good, feasible solution to the problem [16]. However, this also requires us to solve a large one-in- a-set TSP, which is combinatorially hard. Nevertheless, this approach provides an upper bound [13] for the optimal cost of the DTSP, and simulation results indicate that the cost of the solutions start to converge with more than 15 discretizations at each target. The fundamental question with regard to all the above heuristics and approximation algorithms is how close a feasible solution   actually is   to the optimum. For example, Fig. 2 shows the cost of the feasible solutions obtained by solving the one-in-a-set TSP and the ETSP for 25 instances with 20 targets in each instance. Even with 32 discretizations of the possible angles at each target, the cost of the feasible solution is at least 30% greater than the corresponding optimal ETSP cost for several of these instances. As the optimal cost is not known for the DTSP, identifying a tight lower bound is crucial for determining the quality of the solutions that have been provided as well as for developing constant factor approximation algorithms. This fundamental question was the motivation for the bounding algorithms in [17–20]. In these algo- rithms, the requirement that the arrival and departure angles must be equal at each target is removed, and instead there is a penalty in the objective function whenever the requirement is violated. This results in a max-min problem where the minimization problem is an asymmetric TSP (ATSP) and the cost of travel- ing between any two targets requires solving a new optimal control problem. In terms of lower bounding, the difficulty with this approach is that we are not currently aware of any algorithm that will guarantee a lower bound for the optimal control problem. Nonetheless, this is a useful approach, and advances in lower bounding optimal control problems will lead to finding lower bounds for the DTSP. In this article, we propose a new approach to finding tight lower bounds for the DTSP. This is the first systematic procedure available for the DTSP and is a natural counterpart to the one-in-a-set TSP approach we discussed above. In this approach, we remove the requirement that the arrival angle and the departure angle at each target must be the same, but we restrain these angles so that they belong to one sector or interval (refer to Fig. 3). The lower bounding problem aims to choose an interval at each target such that the arrival angle and the departure angle at the target belong to the same interval, each target is visited at
0   5   10   15   20   25  3000  3500  4000  4500  5000  5500  6000  Euclidean lower bounds  Instance Number  Cost  Feasible solutions with  32 discretizations Figure 2. A comparison between the cost of the feasible solution (upper bound) obtained by solving the one-in-a-set TSP with 32 discretizations and the optimal cost of the corresponding Euclidean TSP (lower bound) for 25 instances. There are 20 targets in each instance, and the location of each target is sampled from a 1000 × 1000 square. Also, the minimum turning radius of the vehicle is set to 100.  least once, and the sum of the costs of travelling between the targets is minimized. The cost of traveling between two intervals corresponding to two distinct targets now reduces to a new optimal control problem, which we refer to as the   Dubins interval problem . Given two targets and an interval at each target, the problem is to find a Dubins path such that the departure angle at the initial target and the arrival angle at the final target belong to the given intervals and the length of the path is minimal.   The lower bounding problem is a one-in-a-set TSP and can be solved just like the upper bounding problem. If the size of each of the intervals at each target reduces to zero, the lower bounding problem reduces to the DTSP. If there is only one interval of size 2 π   at each target, the result is a Euclidean TSP. As the size of the intervals at the targets becomes smaller, the one-in-a-set TSP becomes combinatorially hard, similar to the upper bounding problem. Nevertheless, this provides a systematic approach to finding lower bounds for the DTSP, provided the Dubins interval problem can be solved. The Dubins interval problem is a new generalization of the standard Dubins problem [25] which has not been formulated or solved 1   in the literature. The difficulty with solving this problem lies in the fact that the length of the shortest Dubins paths between any two targets is a non-linear, discontinuos function of the heading angles of the targets. Therefore, finding the optimal heading angles from the given intervals at the targets that minimizes the length of the Dubins path is non-trivial. In this article, we solve the Dubins interval problem using the monotonicity properties and the extremal values of the length of the Dubins paths. The following are the contributions of this article:  1 We point out that we are also working on a completely different approach which is based on optimal control in [21]. However, the approach in [21] still relies on the results of this paper. Second, unlike the analysis and results in this paper, the work in [21] does not provide information about the rate of change of lengths of the Dubins paths as a function of the heading angles at the targets. This information is critical and very useful in the development of bounds for feasible solutions and approximation algorithms for the DTSP.
Figure 3. There are four intervals at each target. A lower bound for the DTSP can be obtained by choosing an interval and restricting both the arrival and the departure angles to be in the chosen interval at each target, and then finding a corresponding optimal TSP path. The shaded interval at each target shows the chosen interval with the arrival and departure angles in blue.  1. The formulation of the lower bounding problem for the DTSP as a novel one-in-a-set TSP where the cost of traveling between any two targets requires solving a Dubins Interval Problem. This is the first formulation that aims to provide a tight lower bound for the DTSP. 2. The first algorithm to solve the Dubins Interval Problem by exploiting its structure and monotonicity properties. 3. Numerical results to corroborate the performance of the proposed lower bounding approach for the 25 instances shown in figure 2.  2. Lower Bounding Problem Formulation  The set of targets is denoted by   T   =   { 1 ,   2 ,   · · ·   ,   n } , where   n   is the number of targets. The set of avail- able angles   [ 0 ,   2 π ]   at any target   i   is partitioned into a collection of closed intervals denoted by   I i   : =  { [ 0 ,   φ i 1 ] ,   [ φ i 1 ,   φ i 2 ] ,   · · ·   ,   [ φ im i − 1   ,   φ im i   =   2 π ] } , where   m i ( ≥   1 )   denotes the number of intervals at target   i   and the   φ i j   are constants such that 0   ≤   φ i 1   ≤   φ i 2   ≤ · · · ≤   φ im i   =   2 π . Let   ( x i ,   y i )   denote the location of target  i   ∈   T   , and let the arrival angle and the departure angle of the vehicle at target   i   be denoted by   θ ia   and  θ id   , respectively. The configuration of the vehicle leaving target   i   at   θ id   is then denoted by   ( x i ,   y i ,   θ id   ) , and  ( x i ,   y i ,   θ ia )   similarly denotes the vehicle’s arrival configuration. The length of the shortest Dubins path from  ( x i ,   y i ,   θ id   )   to   ( x   j ,   y   j ,   θ   ja )   is denoted by   d i j ( θ id   ,   θ   ja ) . Given an interval   I i   at target   i   and an interval   I j   at target  j , define   d ∗  i j ( I i ,   I j )   : =   min θ id   ∈ I i , θ   ja ∈ I j   d i j ( θ id   ,   θ   ja ) . The objective of the Bounding Problem   (BP)   is to find a sequence of targets   ( s 1 ,   s 2 ,   · · ·   ,   s n ) ,   s i   ∈   T   , to visit and an interval   I s i   ∈   I i   for each target   s i   ∈   T   such that  •   each target is visited at least once, and  •   the cost   ∑ n − 1  i = 1   d ∗  s i s i + 1   ( I s i   ,   I s i + 1   ) +   d ∗  s n s 1   ( I s n   ,   I s 1   )   is minimized. Addressing this   BP   first requires solving min θ id   ∈ I i , θ   ja ∈ I j   d i j ( θ id   ,   θ   ja ) . Once this problem is solved, the  BP   is essentially a one-in-a-set TSP. In this article, we transform the one-in-a-set TSP into an ATSP using the Noon-Bean transformation [22] and then convert the resulting ATSP into a symmetric TSP using the transformation in [23].   The symmetric TSP is solved using the Concorde solver [24] to find an optimal solution. Prior to addressing the Dubins Interval Problem in the next section, we first formally state the lower bounding result in the following proposition.
Proposition 2.1.   The optimal cost to the   BP   is a lower bound to the DTSP. Proof.   Any optimal solution to the DTSP is a feasible solution to the   BP   for any positive number of intervals at each target.   Therefore, the optimal cost of the   BP   must be a lower bound to the optimal cost of the DTSP.  3. Dubins Interval Problem  Without loss of generality, let the Dubins interval problem be denoted as min θ 1 ∈ I 1 , θ 2 ∈ I 2   d 12 ( θ 1 ,   θ 2 ) , where  d 12 ( θ 1 ,   θ 2 )   indicates the shortest path (also referred to as the Dubins path) for traveling from   ( x 1 ,   y 1 ,   θ 1 )  to   ( x 2 ,   y 2 ,   θ 2 )   subject to the minimum turning radius constraint (Fig.   4).   Here the interval   I k   is defined as   [ θ   min k   ,   θ   max k   ]   ⊆   [ 0 ,   2 π ]   for   k   =   1 ,   2.   Given an initial configuration   ( x 1 ,   y 1 ,   θ 1 )   and a final configuration  ( x 2 ,   y 2 ,   θ 2 ) , L.E. Dubins [25] showed that the shortest path for a vehicle to travel between the two configu- rations subject to the minimum turning radius ( ρ ) constraint must consist of at most three segments, where each segment is a circle of radius   ρ   or a straight line. Specifically, if a curved segment of radius   ρ   along which the vehicle travels in a counterclockwise (clockwise) rotational motion is denoted by   L ( R ) , and the segment along which the vehicle travels straight is denoted by   S , then the shortest path is one of   RSR ,   RSL ,  LSR ,   LSL ,   RLR , and   LRL . 1  2  Figure 4. A feasible solution to the Dubins interval problem.  Let   RSL ( θ 1 ,   θ 2 )   denote the length of the   RSL   path from   ( x 1 ,   y 1 ,   θ 1 )   to   ( x 2 ,   y 2 ,   θ 2 ) .   RSL ( θ 1 ,   θ 2 )   is set to   ∞  if the   RSL   path does not exist. Let   RSR ( θ 1 ,   θ 2 ) ,   LSR ( θ 1 ,   θ 2 ) ,   LSL ( θ 1 ,   θ 2 ) ,   RLR ( θ 1 ,   θ 2 ) , and   LRL ( θ 1 ,   θ 2 )   be defined in a similar way. Using these definitions, the Dubins interval problem can be written as follows: min  θ 1 ∈ I 1 , θ 2 ∈ I 2  d 12 ( θ 1 ,   θ 2 ) =   min  θ 1 ∈ I 1 , θ 2 ∈ I 2  { RSR ( θ 1 ,   θ 2 ) ,   RSL ( θ 1 ,   θ 2 ) ,   LSR ( θ 1 ,   θ 2 ) ,   LSL ( θ 1 ,   θ 2 ) ,   RLR ( θ 1 ,   θ 2 ) ,   LRL ( θ 1 ,   θ 2 ) } .  (1)  Remark 3.1.   d 12 ( θ 1 ,   θ 2 )   is a lower semicontinuous function and is minimized over closed and bounded intervals I 1   and I 2 .   Therefore, the Dubins interval problem is well defined, i . e . , there exist   θ   ∗  1   ∈   I 1   and  θ   ∗  2   ∈   I 2   such that d 12 ( θ   ∗  1   ,   θ   ∗  2   ) =   min θ 1 ∈ I 1 , θ 2 ∈ I 2   d 12 ( θ 1 ,   θ 2 ) .  To solve the Dubins interval problem, we also consider shortest paths that contain at most two segments between   ( x 1 ,   y 1 )   and   ( x 2 ,   y 2 ) . For any path   T   ∈ { RS ,   LS ,   SR ,   SL ,   RL ,   LR }   and   θ 1   ∈   I 1 , let   T   1 ( θ 1 )   denote the distance of the shortest path of type   T   that starts at   ( x 1 ,   y 1 )   with a departure angle of   θ 1   and arrives at
( x 2 ,   y 2 )   with an arrival angle in   I 2 . In this case, the arrival angle at   ( x 2 ,   y 2 )   will be a function of   θ 1   and   T   and is denoted as   θ 2 ( T   ,   θ 1 ) .   T   1 ( θ 1 )   is set to   ∞   if a path of type   T   does not exist or if   θ 2 ( T   ,   θ 1 )   / ∈   I 2 . Similarly, let   T   2 ( θ 2 )   denote the distance of the shortest path of type   T   that starts at   ( x 1 ,   y 1 )   with a departure angle in   I 1   and arrives at   ( x 2 ,   y 2 )   with an arrival angle of   θ 2 . In this case, the departure angle at   ( x 1 ,   y 1 )   will be a function of   θ 2   and   T   and is denoted as   θ 1 ( T   ,   θ 2 ) .   T   2 ( θ 2 )   is set to   ∞   if the path of type   T   does not exist or if   θ 1 ( T   ,   θ 2 )   / ∈   I 1 . From the definitions, note that min θ 1 ∈ I 1   T   1 ( θ 1 ) =   min θ 2 ∈ I 2   T   2 ( θ 2 ) . The following theorem provides a way to further simplify equation (1) and solve the Dubins interval problem:  Theorem 3.1.  min  θ 1 ∈ I 1  min  θ 2 ∈ I 2  { d 12 ( θ 1 ,   θ 2 ) }   =   min { d ∗ ,   min  θ 1 ∈ I 1  { RS 1 ( θ 1 ) ,   SR 1 ( θ 1 ) ,   LS 1 ( θ 1 ) ,   SL 1 ( θ 1 ) ,   LR 1 ( θ 1 ) ,   RL 1 ( θ 1 ) }}   (2)  where d ∗   : =   min { d 12 ( θ   min  1   ,   θ   min  2   ) ,   d 12 ( θ   max  1   ,   θ   min  2   ) ,   d 12 ( θ   min  1   ,   θ   max  2   ) ,   d 12 ( θ   max  1   ,   θ   max  2   ) } .  In English, this theorem states that an optimal path to the Dubins interval problem must be one of the following: 1. An optimal Dubins path consisting of at most three segments such that both the arrival and departure angles at each target belong to one of the boundary values of the respective intervals, or 2. An optimal Dubins path consisting of at most two segments such that the angle constraints are satis- fied. After proving this theorem in the next subsection, we will provide algorithms to solve for the optimal Dubins paths with at most two segments (i.e., to solve min θ 1 ∈ I 1   P ( θ 1 )   for any path   P   ∈ { RS 1 ,   SR 1 ,   LS 1 ,   SL 1 ,   LR 1 ,   RL 1 } ). As   d ∗   in the above theorem can already be computed directly using Dubins’s result [25], one can then com- pute the optimal cost for the Dubins interval problem and the corresponding departure and arrival angles.  3.1. Proof of Theorem 3.1  This theorem will be proved in two parts. First, we will first show how to simplify min θ 1 ∈ I 1 , θ 2 ∈ I 2   P ( θ 1 ,   θ 2 )  for any path   P   ∈ { RSR ,   RSL ,   LSR ,   LSL } . Then we will address the   LRL   and the   RLR   paths.  3.1.1. Optimizing RSR, RSL, LSR, and LSL paths.   The following result is known [26] for each of the paths  P   ∈ { RSR ,   RSL ,   LSR ,   LSL }   from   ( x 1 ,   y 1 ,   θ 1 )   to   ( x 2 ,   y 2 ,   θ 2 ) :  Lemma 3.1.   For any   P   ∈ { RSR ,   RSL ,   LSR ,   LSL }   and i   =   1 ,   2 , either   ∂   P ( θ 1 , θ 2 )  ∂ θ i   ≥   0   ∀   θ i   or   ∂   P ( θ 1 , θ 2 )  ∂ θ i   ≤   0  ∀   θ i   when   P   exists and none of its curved segments vanish.  Now let us apply the above lemma to the   RSL   path. The   RSL   path ceases to exist when the segment   S  vanishes, i.e., the   RSL   path reduces to an   RL   path. In addition, when one of the curved segments vanishes, the   RSL   path reduces to either the   RS   or the   SL   path (refer to Fig. 5). Therefore, given   θ 1 , the optimum for min θ 2 ∈ [ θ   min  2   , θ   max  2   ]   RSL ( θ 1 ,   θ 2 )   must be attained when   θ 2   =   θ   min  2   or   θ 2   =   θ   max  2   or when the   RSL   path reduces to an   RL ,   RS , or   SL   path. This can be stated as follows:
θ 2  0   1   2   3   4   5   6   7  200  300  400  500  600  700  800  900  1000  RSL Length  RSL path reduces to RL at these two values of   θ 2 , and   does   not   exist   be- tween these values.  At this   θ 2   value, final turn vanishes in the RSL path and reduces to RS. Figure 5. Given   θ 1 , the length of the RSL path varies monotonically with respect to   θ 2   wherever the path exists and none of its curved segments vanish.  min  θ 2 ∈ I 2  { RSL ( θ 1 ,   θ 2 ) }   : =   min { RSL ( θ 1 ,   θ   min  2   ) ,   RSL ( θ 1 ,   θ   max  2   ) ,   RS 1 ( θ 1 ) ,   SL 1 ( θ 1 ) ,   RL 1 ( θ 1 ) } .   (3) Therefore, min  θ 1 ∈ I 1  min  θ 2 ∈ I 2  { RSL ( θ 1 ,   θ 2 ) }  =   min  θ 1 ∈ I 1  min { RSL ( θ 1 ,   θ   min  2   ) ,   RSL ( θ 1 ,   θ   max  2   ) ,   RS 1 ( θ 1 ) ,   SL 1 ( θ 1 ) ,   RL 1 ( θ 1 ) }  =   min { min  θ 1 ∈ I 1  RSL ( θ 1 ,   θ   min  2   ) ,   min  θ 1 ∈ I 1  RSL ( θ 1 ,   θ   max  2   ) ,   min  θ 1 ∈ I 1  { RS 1 ( θ 1 ) ,   SL 1 ( θ 1 ) ,   RL 1 ( θ 1 ) }} .   (4) Similarly, using Lemma 3.1 again, we get the following: min  θ 1 ∈ I 1  RSL ( θ 1 ,   θ   min  2   ) =   min { RSL ( θ   min  1   ,   θ   min  2   ) ,   RSL ( θ   max  1   ,   θ   min  2   ) ,   RS 2 ( θ   min  2   ) ,   SL 2 ( θ   min  2   ) ,   RL 2 ( θ   min  2   ) } ,   (5) min  θ 1 ∈ I 1  RSL ( θ 1 ,   θ   max  2   ) =   min { RSL ( θ   min  1   ,   θ   max  2   ) ,   RSL ( θ   max  1   ,   θ   max  2   ) ,   RS 2 ( θ   max  2   ) ,   SL 2 ( θ   max  2   ) ,   RL 2 ( θ   max  2   ) } .   (6) Now, one can easily verify the following: For any   T   ∈ { RS ,   SL ,   RL } ,   min  θ 1 ∈ I 1  T   1 ( θ 1 )   ≤   T   2 ( θ   min  2   )   and min  θ 1 ∈ I 1  T   1 ( θ 1 )   ≤   T   2 ( θ   max  2   ) .   (7) Substituting for min θ 1 ∈ I 1   RSL ( θ 1 ,   θ   min  2   )   and min θ 1 ∈ I 1   RSL ( θ 1 ,   θ   max  2   )   in (4) using equations (5) and (6) and simplifying further using (7), we get min  θ 1 ∈ I 1  min  θ 2 ∈ I 2  RSL ( θ 1 ,   θ 2 ) =   min { RSL ∗ ,   min  θ 1 ∈ I 1  { RS 1 ( θ 1 ) ,   SL 1 ( θ 1 ) ,   RL 1 ( θ 1 ) }} ,   (8)
where  RSL ∗   : =   min { RSL ( θ   min  1   ,   θ   min  2   ) ,   RSL ( θ   max  1   ,   θ   min  2   ) ,   RSL ( θ   min  1   ,   θ   max  2   ) ,   RSL ( θ   max  1   ,   θ   max  2   ) } .  As Lemma 3.1 is also applicable to   RSR ,   LSL , and   LSR   paths, one can use the above procedure and sim- plify min θ 1 ∈ I 1 , θ 2 ∈ I 2   RSR ( θ 1 ,   θ 2 ) , min θ 1 ∈ I 1 , θ 2 ∈ I 2   LSL ( θ 1 ,   θ 2 ) , and min θ 1 ∈ I 1 , θ 2 ∈ I 2   LSR ( θ 1 ,   θ 2 )   in a similar way. Combining all these results, we obtain the following: min  θ 1 ∈ I 1  min  θ 2 ∈ I 2  min  P ∈{ RSR , RSL , LSR , LSL }   P ( θ 1 ,   θ 2 ) =   min { P ∗ ,   min  θ 1 ∈ I 1  { RS 1 ( θ 1 ) ,   SR 1 ( θ 1 ) ,   LS 1 ( θ 1 ) ,   SL 1 ( θ 1 ) ,   LR 1 ( θ 1 ) ,   RL 1 ( θ 1 ) }}  (9) where  P ∗   : =   min  P ∈{ RSR , RSL , LSR , LSL }   min { P ( θ   min  1   ,   θ   min  2   ) ,   P ( θ   max  1   ,   θ   min  2   ) ,   P ( θ   min  1   ,   θ   max  2   ) ,   P ( θ   max  1   ,   θ   max  2   ) } .  3.1.2. Optimizing RLR and LRL paths.   Xavier et al. [26] have shown that the   RLR   and   LRL   paths can- not lead to an optimal Dubins path if the distance between the two targets is greater than 4 ρ . Therefore, in this section, we assume that the distance between the two targets is at most 4 ρ .   We will focus on min θ 1 ∈ I 1 , θ 2 ∈ I 2   LRL ( θ 1 ,   θ 2 ) ; min θ 1 ∈ I 1 , θ 2 ∈ I 2   RLR ( θ 1 ,   θ 2 )   can be solved in a similar way. Given   θ 1 , unlike the length of the   RSL   path,   LRL ( θ 1 ,   θ 2 )   is not monotonous with respect to   θ 2   when   LRL   exists. Without loss of generality, we assume that   θ 1   = 0 and first aim to understand   LRL ( 0 ,   θ 2 )   as a function of   θ 2   (refer to Fig. 6). Target 1 is located at the origin and target 2 is located at   (    ̄ x ,    ̄ y ) . The angles   α   and   β   in Fig. 6 are functions of   θ 2 . For brevity, we use   α   and   β   in place of   α ( θ 2 )   and   β   ( θ 2 ) , respectively. Let   LRL ( 0 ,   θ 2 )   be denoted as  D ( θ 2 )   : = ( 2 π   +   2 α   +   2 β   +   θ 2 ) ρ . In the ensuing discussion, we use the fact that the length of the   R   segment in an   LRL   path must be greater than   πρ   (i.e., 0   <   α   +   β   <   π ) for the   LRL   path to be an optimal Dubins path between any two targets [25, 27]. ( ̄ x,    ̄ y )  (0 ,   0)   x -axis  y -axis  α  α   β  β  θ 2  ρ  ρ  Figure 6.   LRL   path for   θ 1   =   0 .  Lemma 3.2.   If the LRL path exists and none of its curved segments vanish, then for any   θ 2   such that  0   <   α ( θ 2 ) +   β   ( θ 2 )   <   π ,   dD  d θ 2   6   =   0   except when   D ( θ 2 )   reaches a maximum, when   θ 2   satisfies   α   +   π / 2   =   θ 2 .
Proof.   Using Fig. 6,   α   and   β   can be obtained in terms of   θ 2   as follows: 2 ρ   sin   α   +   ρ   =   2 ρ   sin   β   +   ρ   cos   θ 2   +    ̄ y ,   (10) 2 ρ   cos   α   +   2 ρ   cos   β   +   ρ   sin   θ 2   =    ̄ x .   (11) Differentiating and simplifying the above equations, we get cos   α   d α  d θ 2  −   cos   β   d β  d θ 2  =   −   sin   θ 2  2   ,   (12) sin   α   d α  d θ 2  +   sin   β   d β  d θ 2  =   cos   θ 2  2   .   (13) Further solving for the derivatives, we get  d β  d θ 2  =   cos ( θ 2   −   α )  2 sin ( α   +   β   )   ,   (14)  d α  d θ 2  =   cos ( θ 2   +   β   )  2 sin ( α   +   β   )   .   (15) Therefore,  d D  d θ 2  =   ρ ( 2   d β  d θ 2  +   2   d α  d θ 2  +   1 )   (16)  =   ρ (   cos ( θ 2   −   α )  sin ( α   +   β   ) +   cos ( θ 2   +   β   )  sin ( α   +   β   ) +   1 ) .   (17) Equation   d D  d θ 2   =   0 yields the following possibilities:   θ 2   =   π  2   +   α   or   θ 2   +   β   =   −   π  2   .   θ 2   +   β   =   −   π  2   corresponds to the case where the second left turn disappears; there is a jump in the length of the   LRL   path at this   θ 2 , and therefore   d D  d θ 2   does not exist.   θ 2   =   π  2   +   α   corresponds to the case where the turn angle in the right turn is equal to the turn angle in the second left turn; one can verify that   D ( θ 2 )   reaches a maximum at this point because   d 2 D  d θ   2 2  =   −   3 ρ  2 1 + cos ( α + β   )  sin ( α + β   )   <   0 (refer to Fig. 7). The derivatives of   LRL ( θ 1 ,   θ 2 )   do not exist when any turn in the path disappears or when the angle in the right turn becomes equal to   π , as shown in Fig. 8. The length of the two paths (Fig. 8) when the   LRL  path just ceases to exist are denoted by   LRL 1  a ( θ 1 )   and   LRL 1  b ( θ 1 ) . Therefore, applying the above lemma to the   LRL   path and following similar steps to those in subsection 3.1.1, we get the following result: min  θ 2 ∈ I 2  { LRL ( θ 1 ,   θ 2 ) }   : =   min { LRL ( θ 1 ,   θ   min  2   ) ,   LRL ( θ 1 ,   θ   max  2   ) ,   LR 1 ( θ 1 ) ,   RL 1 ( θ 1 ) ,   LRL 1  a ( θ 1 ) ,   LRL 1  b ( θ 1 ) } .   (18) Again, as in subsection 3.1.1, one can further simplify the above optimization problem: min  θ 1 ∈ I 1  min  θ 2 ∈ I 2  { LRL ( θ 1 ,   θ 2 ) }   =   min { LRL ∗ ,   min  θ 1 ∈ I 1  { LR 1 ( θ 1 ) ,   RL 1 ( θ 1 ) ,   LRL 1  a ( θ 1 ) ,   LRL 1  b ( θ 1 ) }}   (19) where  LRL ∗   : =   min { LRL ( θ   min  1   ,   θ   min  2   ) ,   LRL ( θ   max  1   ,   θ   min  2   ) ,   LRL ( θ   min  1   ,   θ   max  2   ) ,   LRL ( θ   max  1   ,   θ   max  2   ) } .
θ 2  0   1   2   3   4   5   6   7  400  500  600  700  800  900  1000  1100  1200  LRL Length  θ 2   =   π  2   +   α  LRL path does not exist for the   θ 2   values between these two points.   These points   correspond   to  LRL 1  a ( θ 1 ) and   LRL 1  b   ( θ 1 ). Figure 7. Given   θ 1 , the length of the   LRL   path reaches a maximum when   θ 2   =   π  2   +   α , as shown. This figure also shows the values of   θ 2   where the   LRL   path just ceases to exist.  Note that   LRL 1  a ( θ 1 )   and   LRL 1  b ( θ 1 )   can never result in an optimal Dubins path because the angle in the right turn is equal to   π   [27].   Therefore, once equation (19) is substituted in equation (1), the functions  LRL 1  a ( θ 1 )   and   LRL 1  b ( θ 1 )   will drop out. min θ 1 ∈ I 1   min θ 2 ∈ I 2   { RLR ( θ 1 ,   θ 2 ) }   can be simplified in a similar way. Hence, combining the above results with equation (9), we obtain the result stated in Theorem 3.1.  4. Algorithms for Optimizing Dubins Paths with At Most Two Segments  The only remaining step needed to solve the Dubins interval problem is to show how to optimize min θ 1 ∈ I 1   { RS 1 ( θ 1 ) ,   SR 1 ( θ 1 ) ,   LS 1 ( θ 1 ) ,   SL 1 ( θ 1 ) ,   LR 1 ( θ 1 ) ,   RL 1 ( θ 1 ) } . In this section, we will solve two prob- lems: min θ 1 ∈ I 1   { RS 1 ( θ 1 ) }   and min θ 1 ∈ I 1   { RL 1 ( θ 1 ) } . The remaining paths can be solved using simple transfor- mations (reflections about the   x   or the   y   axis).  4.1. Optimizing the RS path  Without loss of generality, a reference frame can be chosen such that target 1 is at the origin and target 2 lies on the   x -axis as shown in Fig. 9. Here  ̄ x   represents the Euclidean distance between the targets. Given   θ 1 , the existence of the   RS   path as well as its length can be determined using geometry. The length of the   S   path, the angle between the   x -axis and the   S   path, and the final arrival angle at target 2 are also functions of   θ 1  and can be expressed as   L ( θ 1 ) ,   φ   ( θ 1 ) , and   θ 2 ( RS ,   θ 1 ) , respectively. Let the length of the   RS   path be denoted as   D ( θ 1 ) . For brevity, in some places we will use   L ,   φ   ,   θ 2 , and   D   instead of   L ( θ 1 ) ,   φ   ( θ 1 ) ,   θ 2 ( RS ,   θ 1 ) , and  D ( θ 1 ) , respectively. Let   d S   : =    ̄ x   if the angle of the straight line joining the two targets lies in the intervals  I 1   and   I 2 . If the angle constraints are not satisfied,   d S   is set to   ∞ . Similarly, let   d R   denote the length of the shortest circular arc of type   R   that joins the two targets such that the boundary angles of the arc belong to the respective intervals at the targets. If such an arc does not exist,   d R   is set to   ∞ . In the following lemma, we assume that   [ θ   min  1   ,   θ   max  1   ]   ⊆   [ 0 ,   2 π ]   and   [ θ   min  2   ,   θ   max  2   ]   ⊆   [ 0 ,   2 π ] .
θ 1  ( ̄ x,   0)  (0 ,   0)  x -axis  y -axis  LRL   path doesn’t exist  for   θ 2   in this set.  LRL 1  a ( θ 1 )  LRL 1  b   ( θ 1 ) Figure 8. Given   θ 1 , the   LRL   paths when the arc angle in the right turn is   π . This figure shows the angles for   θ 2   when the   LRL   path does not exist.  Lemma 4.1.   min θ 1 ∈ I 1   { RS 1 ( θ 1 ) }   : =   min { d S ,   d R ,   RS 1 ( θ   min  1   ) ,   RS 2 ( θ   min  2   ) ,   RS 2 ( θ   max  2   ) } . Proof.   Refer to the appendix for the proof.  4.2. Optimizing the RL path  We use similar notations as in previous subsections (refer to Fig. 10). The angles   φ   ( θ 1 )   and   θ 2 ( RL ,   θ 1 )  are also written as   φ   and   θ 2 , for brevity. The length of the   RL   path is denoted as   D ( θ 1 )   and is equal to  ρ ( θ 1   +   θ 2   +   2 φ   ) .   RL   paths do not exist when  ̄ x   >   4 ρ . In addition, even when 0   ≤    ̄ x   ≤   4 ρ , there are a subset of angles of   θ 1   for which an   RL   path does not exist. Moreover, given   θ 1 , there are two possible   RL   paths, as either   φ   +   θ 2   ≤   π   or   φ   +   θ 2   >   π . In the following discussion and in Fig. 10, we assume that   φ   +   θ 2   <   π . The other   RL   path can be addressed similarly. We first define some values of   θ 1   where the optimum can occur (these correspond to the extreme values of   D   and   θ 2   for the RL path and will be derived later in the proof). Let   θ   1 ∗   be the solution to the equation  θ 2 ( RL ,   θ 1 ) =   θ 1 . Also, let   θ   2 ∗   and   θ   3 ∗   be the solutions to equation   φ   ( θ 1 ) +   θ 2 ( RL ,   θ 1 ) =   π . Let   d L   denote the length of the shortest circular arc of type   L   that joins the two targets such that the boundary angles of the arc belong to the corresponding intervals at the targets and   φ   +   θ 2   <   π . If such an arc does not exist, then   d L  is set to   ∞ . Let   RL ∗   =   min { RL 1 ( θ   max  1   ) ,   RL 1 ( θ   min  1   ) ,   RL 2 ( θ   min  2   ) ,   RL 2 ( θ   max  2   } .  Lemma 4.2.   If    ̄ x   >   2 ρ ,   min θ 1 ∈ I 1   { RL 1 ( θ 1 ) }   : =   min { RL 1 ( θ   1 ∗ ) ,   RL 1 ( θ   2 ∗ ) ,   RL 1 ( θ   3 ∗ ) ,   RL ∗ } .   If   0   ≤    ̄ x   ≤   2 ρ ,  min θ 1 ∈ I 1   { RL 1 ( θ 1 ) }   : =   min { d L ,   d R ,   RL 1 ( θ   1 ∗ ) ,   RL ∗ ) } . Proof.   Refer to the appendix.  5. Numerical results  Computational results are presented for 25 instances with 20 targets in each instance. The locations of the targets were sampled from a 1000   ×   1000 square. The minimum turning radius of the vehicle was chosen to be 100. The heading angles at each target are discretized into 4, 8, 16, and 32 intervals. We use the Noon- Bean transformation to first convert the one-in-a-set TSP into an ATSP. Then we use a transformation method
θ 1   φ θ 1  φ  L  ( ̄ x,   0) (0 ,   0)  θ 2  ρ  x -axis  y -axis Figure 9.   RS   path  outlined in [23] to convert the ATSP into a symmetric TSP. This method converts an asymmetric instance with   n   nodes into a symmetric instance with 3 n   nodes. We chose this method primarily because unlike other transformations, there is no big- M   constant involved, and therefore we did not have any numerical difficulties such as those faced in [16, 19, 20].   For example, the transformed TSP instance with 32 discretizations at each target has 1920 nodes.   Each of the transformed TSP instances was solved to optimality using the CONCORDE solver [24]. The improvement of the lower bounds as the number of discretizations or intervals increases is shown in Fig. 11. On average, the improvement of the lower bounds with respective to the optimal ETSP cost for 32 intervals was 22.28%. A feasible solution was also obtained by discretizing the angles at each target (32 values) and applying the above transformation procedure.   The comparison of the cost of the feasible solution with respect to the optimal Euclidean TSP cost and the lower bound (corresponding to 32 intervals at each target) for the 25 instances is shown in Fig. 12. The average deviation of the cost of the feasible solution from its corresponding lower bound is 5.2%, while the average deviation of the cost of the feasible solution from its corresponding ETSP cost is 29.2%. In one of the instances, we found the cost of the feasible solution from its corresponding lower bound improved by approximately 44%. These results show that the proposed approach can be used to obtain tight lower bounds for the DTSP. A feasible DTSP solution and an optimal solution corresponding to the lower bound for an instance are shown in Fig. 13.  6. Conclusion  We provide a systematic procedure to find lower bounds for the DTSP. This article provides a new direc- tion for developing approximation algorithms for the DTSP. Currently, the transformation method increases the size of the one-in-a-set TSP by 2 or 3 times, resulting in a large TSP. Computationally, more efficient tools for directly solving the one-in-a-set TSP will be useful in finding tighter lower and upper bounds for the DTSP. Future work can also address the same problem with multiple vehicles and other precedence constraints.
θ 1  φ  θ 1   φ   ( ̄ x,   0) (0 ,   0)  θ 2  ρ  x -axis  y -axis  θ 2  ρ  ρ Figure 10.   RL   path 0   5   10   15   20   25  3000  3500  4000  4500  5000  5500  Instance Number  Cost  Euclidean lower bounds  4 intervals   8 intervals  16 intervals  32 intervals  Figure 11. Lower bounds computed with 4, 8, 16, and 32 intervals at each target for 25 instances.  References  [1]   S. Rathinam, R. Sengupta, and S. Darbha, “A resource allocation algorithm for multivehicle systems with nonholonomic constraints,”   IEEE Transactions Automation Science and Engineering , vol. 4, pp. 98–104, 2007. [2]   J. Le Ny, E. Feron, and E. Frazzoli, “On the dubins traveling salesman problem.”   IEEE Trans. Automat. Contr. , vol. 57, no. 1,
0   5   10   15   20   25  3000  3500  4000  4500  5000  5500  6000  Instance Number  Cost  Euclidean lower bounds  New lower bounds  Upper bounds Figure 12. Comparison between lower bounds and upper bounds for 32 discretizations, along with the optimal Euclidean TSP cost. 0   200   400   600   800   1000  0  200  400  600  800  1000  1200  Feasible Dubins Path  Path obtained by the lower bound  Figure 13. A feasible Dubins path for an instance with 20 targets, and the path obtained from lower bound computation.  pp. 265–270, 2012. [3]   P. Chandler and M. Pachter, “Research issues in autonomous control of tactical uavs,” in   American Control Conference, 1998. Proceedings of the 1998 , vol. 1, Jun 1998, pp. 394–398 vol.1. [4]   A. C. Medeiros and S. Urrutia, “Discrete optimization methods to determine trajectories for dubins’ vehicles,”   Electronic Notes in Discrete Mathematics , vol. 36, pp. 17 – 24, 2010,   { ISCO }   2010 - International Symposium on Combinatorial
Optimization. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1571065310000041 [5]   D. Macharet and M. Campos, “An orientation assignment heuristic to the dubins traveling salesman problem,” in   Advances in Artificial Intelligence – IBERAMIA 2014 , ser. Lecture Notes in Computer Science, A. L. Bazzan and K. Pichara, Eds. Springer International Publishing, 2014, vol. 8864, pp. 457–468. [6]   D. G. Macharet, A. Alves Neto, V. F. da Camara Neto, and M. F. Campos, “Efficient target visiting path planning for multiple vehicles with bounded curvature,” in   Intelligent Robots and Systems (IROS), 2013 IEEE/RSJ International Conference on . IEEE, 2013, pp. 3830–3836. [7]   D. G. Macharet, A. A. Neto, V. F. da Camara Neto, and M. F. Campos, “Data gathering tour optimization for dubins’ vehicles,” in   Evolutionary Computation (CEC), 2012 IEEE Congress on .   IEEE, 2012, pp. 1–8. [8]   P. Sujit, B. Hudzietz, and S. Saripalli, “Route planning for angle constrained terrain mapping using an unmanned aerial vehicle,”   Journal of Intelligent & Robotic Systems , vol. 69, no. 1-4, pp. 273–283, 2013. [9]   R. J. Kenefic, “Finding good dubins tours for uavs using particle swarm optimization,”   Journal of Aerospace Computing, Information, and Communication , vol. 5, no. 2, pp. 47–56, 2008. [10]   D. G. Macharet, A. A. Neto, V. F. da Camara Neto, and M. F. Campos, “Nonholonomic path planning optimization for dubins’ vehicles,” in   Robotics and Automation (ICRA), 2011 IEEE International Conference on .   IEEE, 2011, pp. 4208–4213. [11]   Z. Tang and U. Ozguner, “Motion planning for multitarget surveillance with mobile sensor agents,”   Robotics, IEEE Transac- tions on , vol. 21, no. 5, pp. 898–908, Oct 2005. [12]   K. Savla, E. Frazzoli, and F. Bullo, “Traveling salesperson problems for the dubins vehicle,”   IEEE Transactions on Automatic Control , vol. 53, pp. 1378–1391, 2008. [13]   C. Epstein, I. Cohen, and T. Shima, “On the discretized dubins traveling salesman problem,”   Technical Report , 2014. [14]   X. Ma, D. Casta ̃ n ́ on,   et al. , “Receding horizon planning for dubins traveling salesman problems,” in   Decision and Control, 2006 45th IEEE Conference on .   IEEE, 2006, pp. 5453–5458. [15]   P. Isaiah and T. Shima, “Motion planning algorithms for the dubins travelling salesperson problem,”   Automatica , vol. 53, pp. 247–255, 2015. [16]   P. Oberlin, S. Rathinam, and S. Darbha, “Today’s traveling salesman problem,”   IEEE Robotics and Automation Magazine , vol. 17, no. 4, pp. 70–77, Dec. 2010. [17]   S. G. Manyam, S. Rathinam, S. Darbha, and K. J. Obermeyer, “Lower bounds for a vehicle routing problem with motion constraints,”   International Journal of Robotics and Automation , vol. 30, no. 3, 2015. [18]   S. G. Manyam, S. Rathinam, and S. Darbha, “Computation of lower bounds for a multiple depot, multiple vehicle routing problem with motion constraints,”   Journal of Dynamic Systems, Measurement, and Control , vol. 137, no. 9, p. 094501, 2015. [19]   S. G. Manyam, S. Rathinam, S. Darbha, and K. J. Obermeyer, “Computation of a lower bound for a vehicle routing problem with motion constraints,” in   ASME 2012 5th Annual Dynamic Systems and Control Conference joint with the JSME 2012 11th Motion and Vibration Conference .   American Society of Mechanical Engineers, 2012, pp. 695–701. [20]   S. G. Manyam, S. Rathinam, and S. Darbha, “Computation of lower bounds for a multiple depot, multiple vehicle routing problem with motion constraints,” in   Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on .   IEEE, 2013, pp. 2378–2383. [21]   S. Manyam, S. Rathinam, D. Casbeer, and E. Garcia, “Shortest paths of bounded curvature for the dubins interval problem,”  arXiv preprint arXiv:1507.06980 , 2015. [22]   C. E. Noon and J. C. Bean, “A lagrangian based approach for the asymmetric generalized traveling salesman problem,”  Operations Research , vol. 39, no. 4, pp. 623–632, July 1991. [Online]. Available: http://or.journal.informs.org/content/39/4/ 623 [23]   G. Gutin and A. P. Punnen, Eds.,   The traveling salesman problem and its variations , ser. Combinatorial optimization. Dordrecht, London: Kluwer Academic, 2002. [Online]. Available: http://opac.inria.fr/record=b1120710 [24]   D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook,   The Traveling Salesman Problem: A Computational Study (Prince- ton Series in Applied Mathematics) .   Princeton, NJ, USA: Princeton University Press, 2007. [25]   L.E.Dubins, “On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents,”   American Journal of Mathematics , vol. 79, no. 3, pp. 487–516, 1957. [26]   X.   Goaoc,   H.-S.   Kim,   and   S.   Lazard,   “Bounded-curvature   shortest   paths   through   a   sequence   of   points   using convex   optimization,”   SIAM   Journal   on   Computing ,   vol.   42,   no.   2,   pp.   662–684,   2013.   [Online].   Available: http://dx.doi.org/10.1137/100816079 [27]   J.-D. Boissonnat, A. Crzo, and J. Leblond, “Shortest paths of bounded curvature in the plane,”   Journal of Intelligent and Robotic Systems , vol. 11, no. 1-2, pp. 5–20, 1994. [Online]. Available: http://dx.doi.org/10.1007/BF01258291
θ 1  0   1   2   3   4   5   6   7  200  300  400  500  600  700  800  900  RS Length  θ 1   =   θ ∗ (a)  ̄ x   >   2 ρ θ 1  0   1   2   3   4   5   6   7  0  1  2  3  4  5  6  7  θ 2  θ 1   =   θ ∗   (b)  ̄ x   >   2 ρ θ 1  0   1   2   3   4   5   6   7  100  200  300  400  500  600  700  800  900  RS Length  Paths of type   R  (c)  ̄ x   ≤   2 ρ θ 1  0   1   2   3   4   5   6   7  0  1  2  3  4  5  6  7  θ 2  Paths of type   R   (d)  ̄ x   ≤   2 ρ  Figure 14.   RS   path: examples illustrating   D ( θ 1 )   and   θ 2 ( RS ,   θ 1 ) .
7. Appendix  7.1. Proof of Lemma 4.1  Using Fig. 9, one can relate   L   and   φ   to   θ 1   using the following equations:  ρ   sin   φ   +   L   cos   φ   =    ̄ x   −   ρ   sin   θ 1 ,  ρ   cos   φ   −   L   sin   φ   =   ρ   cos   θ 1 .   (20) The arrival angle   θ 2 ( RS ,   θ 1 )   at target 2 is equal to 2 π   −   φ   . We now consider two different cases:  ̄ x   >   2 ρ   and  ̄ x   ≤   2 ρ   (the   RS   path does not exist for a subset of angles of   θ 1   if  ̄ x   <   2 ρ ).  Case 1:    ̄ x   >   2 ρ . The length of the   RS   path is   D   : = ( θ 1   +   φ   ) ρ   +   L . Therefore,   d D  d θ 1   : = ( 1   +   d φ  d θ 1   ) ρ   +   dL d θ 1   . The derivatives of   φ   and   L   with respect to   θ 1   can be obtained by differentiating (20) as follows:  ( ρ   cos   φ   −   L   sin   φ   )   d φ  d θ 1  +   cos   φ   dL d θ 1  =   − ρ   cos   θ 1 ,   (21)  − ( ρ   sin   φ   +   L   cos   φ   )   d φ  d θ 1  −   sin   φ   dL d θ 1  =   − ρ   sin   θ 1 .   (22) Solving these equations and simplifying further, we obtain the following:  d φ  d θ 1  =    ̄ x L   cos   φ   −   1 ,   (23)  dL d θ 1  =   −   ρ    ̄ x L   cos   θ 1 .   (24) Therefore,  d D  d θ 1  = ( 1   +   d φ  d θ 1  ) ρ   +   dL d θ 1  (25)  =    ̄ x L   ( ρ   cos   φ   −   ρ   cos   θ 1 )   (26)  =    ̄ x   sin   φ   .   (27) For any   θ 1   ∈   [ 0 ,   2 π ] , it is easy to verify geometrically that   φ   ∈   [ 0 ,   π ]   using Fig. 9. Therefore,   ∀ θ 1   ∈   ( 0 ,   2 π ) ,  d D  d θ 1   >   0, i.e., the length of the   RS   path increases monotonically from  ̄ x . When   θ 1   =   2 π , the curved segment in the   RS   path vanishes and the length of the   RS   path returns to the Euclidean distance between the targets (  ̄ x ). Even though the length of the   RS   path increases monotonically for any   θ 1   ∈   [ 0 ,   2 π ) , the arrival angle at target 2,   θ 2   : =   2 π   −   φ   , first decreases with   θ 1 , reaches a minimum at some   θ 1   =   θ   ∗ , and increases to 2 π . This minimum can be computed by solving   d φ  d θ 1   =   0   ⇒    ̄ x L   cos ( φ   ( θ   ∗ ))   −   1   =   0 or cos ( φ   ( θ   ∗ )) =   L   ̄ x   . One can verify that at   θ 1   =   θ   ∗ ,   θ 2   reaches a minimum. Now, the optimum for min θ 1 ∈ I 1   { RS 1 ( θ 1 ) }   must satisfy one of the following conditions: 1.   d D  d θ 1   =   0 or   θ 1   =   0 (   d D  d θ 1   does not exist at this point) or   θ 1   =   θ   min  1   or   θ 1   =   θ   max  1   .   ∀ θ 1   ∈   ( 0 ,   2 π ) ,   d D  d θ 1   6   =   0. As the length of the   RS   path increases monotonically with respect to   θ 1 , we need not consider   θ 1   =   θ   max  1   . Therefore, for this condition, the optimum occurs when   θ 1   =   0 or   θ 1   =   θ   min  1   .
2.   θ 2   =   θ   min  2   or   θ 2   =   θ   max  2   . Therefore, when  ̄ x   >   2 ρ , min θ 1 ∈ I 1   { RS 1 ( θ 1 ) }   : =   min { d S ,   RS 1 ( θ   min  1   ) ,   RS 2 ( θ   min  2   ) ,   RS 2 ( θ   max  2   ) } .  Case 2:    ̄ x   ≤   2 ρ . In this case, the   RS   path is not defined for any   θ 1   ∈   ( sin (    ̄ x  2 ρ   ) ,   π  2   +   cos (    ̄ x  2 ρ   )) .   Moreover, when   θ 1   =  sin (    ̄ x  2 ρ   )   or   θ 1   =   π  2   +   cos (    ̄ x  2 ρ   ) , the   RS   path reduces to just one segment of type   R . Therefore, following the same analysis as in the previous case, min θ 1 ∈ I 1   { RS 1 ( θ 1 ) }   : =   min { d S ,   d R ,   RS 1 ( θ   min  1   ) ,   RS 2 ( θ   min  2   ) ,   RS 2 ( θ   max  2   ) } . Hence this case is proved.  7.2. Proof of Lemma 4.2  We can solve for   φ   and   θ 2   using the following equations (Fig. 10): 2 ρ   cos   φ   −   ρ   cos   θ 2   =   ρ   cos   θ 1 ,  2 ρ   sin   φ   +   ρ   sin   θ 2   =    ̄ x   −   ρ   sin   θ 1 .   (28) Differentiating and simplifying these equations, we get  − 2 sin   φ   d φ  d θ 1  +   sin   θ 2  d θ 2  d θ 1  =   −   sin   θ 1 ,   (29) 2 cos   φ   d φ  d θ 1  +   cos   θ 2  d θ 2  d θ 1  =   −   cos   θ 1 .   (30) Solving further for   d φ  d θ 1   and   d θ 2  d θ 1   , we get  d φ  d θ 1  =   sin ( θ 1   −   θ 2 )  2 sin ( φ   +   θ 2 )   ,   (31)  d θ 2  d θ 1  =   −   sin ( θ 1   +   φ   )  sin ( φ   +   θ 2 )   ,   (32)  d D  d θ 1  =   ρ ( 1   +   d θ 2  d θ 1  +   2   d φ  d θ 1  ) =   ρ ( 1   −   sin ( θ 1   +   φ   )  sin ( φ   +   θ 2 ) +   sin ( θ 1   −   θ 2 )  sin ( φ   +   θ 2 ) ) .   (33) Equating   d D  d θ 1   =   0 and simplifying the equations, we get either   φ   +   θ 1   =   0 or   φ   +   θ 2   =   0 or   θ 1   =   θ 2 .  φ   +   θ 1   =   0 or   φ   +   θ 2   =   0 would imply that one of the circles vanishes; however, this is possible only when  ̄ x   ≤   2 ρ .   When   θ 1   =   θ 2 , we note that   d θ 2  d θ 1   =   − 1 and   d φ  d θ 1   =   0.   Using this, one can verify that  d 2 D  d θ   2 1  =   2 ( 1 − cos ( θ 1 + φ   ))  sin ( θ 1 + φ   )   ⇒   d 2 D  d θ   2 1  >   0. Therefore, the length of the   RL   path reaches a minimum when   θ 1   =   θ 2 .  Case 1:   4 ρ   ≥    ̄ x   ≥   2 ρ . The optimum for min θ 1 ∈ I 1   { RL 1 ( θ 1 ) }   must occur at one of the extreme values of   D ( θ 1 )   or when   θ 1   ∈ { θ   min  1   ,   θ   max  1   }   or   θ 2   ∈ { θ   min  2   ,   θ   max  2   } .   D ( θ 1 )   reaches a local minimum at   θ 1   =   θ   1 ∗   (Fig. 15). Also, the   RL   path just ceases to exist when   θ 1   =   θ   2 ∗   or   θ 1   =   θ   3 ∗ . Specifically, for a small   ε   >   0, the   RL   path does not exist when
θ 1  0   1   2   3   4   5   6  200  300  400  500  600  700  800  900  RL Length  φ   +   θ 2   =   π ,   φ   +   θ 1   < π  θ 2   =   θ 1  φ   +   θ 1   =   π  φ   +   θ 2   =   π ,   φ   +   θ 1   > π  θ 1 ∗  θ 2 ∗   θ 3 ∗ (a)  ̄ x   >   2 ρ θ 1  0   1   2   3   4   5   6  θ 2  1  1.5  2  2.5  3  3.5  φ   +   θ 2   =   π ,   φ   +   θ 1   < π  φ   +   θ 2   =   π ,   φ   +   θ 1   > π  θ 2   =   θ 1  φ   +   θ 1   =   π  θ 1 ∗  θ 2 ∗   θ 3 ∗   (b)  ̄ x   >   2 ρ θ 1  0   1   2   3   4   5   6   7  100  200  300  400  500  600  700  800  900  RL Length  φ   +   θ 1   = 0  θ 2   =   θ 1  φ   +   θ 2   = 0,   φ   +   θ 1   < π  φ   +   θ 2   = 0,   φ   +   θ 1   > π  Path of type   L   Path of type   R  θ 1 ∗  (c)  ̄ x   ≤   2 ρ 0   1   2   3   4   5   6   7  0  0.5  1  1.5  2  2.5  3  3.5  θ 2  θ 1  φ   +   θ 2   = 0,   φ   +   θ 1   > π  φ   +   θ 2   = 0,   φ   +   θ 1   < π  θ 2   =   θ 1  φ   +   θ 1   = 0  Path of type   L  Path of type   R  θ 1 ∗   (d)  ̄ x   ≤   2 ρ  Figure 15.   RL   Path: examples illustrating   D ( θ 1 )   and   θ 2 ( RL ,   θ 1 )   for the case when   0   ≤   φ   +   θ 2   ≤   π .  θ 1   =   θ   2 ∗   −   ε   or   θ 1   =   θ   3 ∗   +   ε . Therefore, min θ 1 ∈ I 1   { RL 1 ( θ 1 ) }   : =   min { RL 1 ( θ   1 ∗ ) ,   RL 1 ( θ   2 ∗ ) ,   RL 1 ( θ   3 ∗ ) ,   RL ∗ } .  Case 2:   2 ρ   ≥    ̄ x   ≥   0. In this case, one of the circles may cease to exist, and therefore the optimum may be equal to   d L   or   d R  if the corresponding angle constraints are met. Following the same arguments as in the previous case, we obtain min θ 1 ∈ I 1   { RL 1 ( θ 1 ) }   : =   min { d L ,   d R ,   RL 1 ( θ   1 ∗ ) ,   RL ∗ ) } . Hence this case is proved.