Shortest Paths of Bounded Curvature for the Dubins Interval Problem  Satyanarayana Manyam 1 , Sivakumar Rathinam 2 , David Casbeer 3   and Eloy Garcia 4  Abstract —The   Dubins   interval   problem   aims   to   find   the shortest path of bounded curvature between two targets such that the departure angle from the first target and the arrival angle at the second target are constrained to two respective intervals. We propose a new and a simple algorithm to this problem based on the minimum principle of Pontryagin.  I. I NTRODUCTION  Path planning problems involving Dubins vehicles have received significant attention in the literature due to their applications involving unmanned vehicles [1]–[13]. A Dubins vehicle [14] is a vehicle that travels at a constant speed and has a lower bound on the radius of curvature at any point along its path. The basic problem of finding a shortest path for a vehicle from a point at   ( x 1 , y 1 )   with heading   θ 1   to a point at   ( x 2 , y 2 )  with heading   θ 2   was solved by Dubins in [14], and later by authors in [15], [16] using Pontryagin’s minimum principle [17]. This article considers a generalization of this standard problem called the Dubins Interval Problem and is stated as follows: Given two targets located at   ( x 1 , y 1 )   and   ( x 2 , y 2 ) , respectively, on a plane, a closed interval   Θ 1   of departure angles from target 1, and a closed interval   Θ 2   of arrival angles at target 2, find a departure angle   θ 1   ∈   Θ 1 , an arrival angle  θ 2   ∈   Θ 2   and a path from   ( x 1 , y 1 , θ 1 )   to   ( x 2 , y 2 , θ 2 )   such that the radius of curvature at any point in the path is lower bounded by   ρ   and the length of the path is a minimum (refer to Fig. 1). ( x 1 , y 1 )  ( x 2 , y 2 )  Fig. 1.   A feasible solution to the Dubins Interval Problem.  1 National   Research   Council   Fellow,   Air   Force   Research   Laboratory, Dayton-OH, 45433,  2 Assistant Professor, Mechanical Engineering, Texas A & M University, College Station, TX-77843,  3 Research Scientist, Air Force Research Laboratory, Dayton-OH, 45433,  4 Research Scientist, Infoscitex Corp., Dayton-Ohio, 45431.  Variants of the Dubins interval problem arise in search and attack problems [18], [19] where a vehicle must reach a target such that the arrival angle of the vehicle at the target must be within given bounds. The Dubins interval problem also arises while lower bounding Traveling Salesman Problems (TSPs) involving Dubins vehicles [20]. In [20], the lower bounding problem was posed as a generalized TSP where the cost of traveling between any two nodes requires one to solve the Dubins interval problem. The Dubins interval problem was solved using calculus and some monotonicity properties of the optimal paths in [20]. In this article, we give a simple and a direct algorithm using Pontryagin’s minimum principle [17]. The application of the minimum principle leads to an additional set of complementary slackness conditions corresponding to the angle constraints at the targets. The key contribution of this article lies in interpreting these conditions and characterizing an optimal solution to the Dubins interval problem. Similar to solving the standard Dubins problem, an optimal solution to the Dubins interval problem can be obtained by simply comparing the length of few candidate solutions. After proving the main result for the Dubins interval problem, we also solve the special case of the Dubins interval problem where the departure angle is given at target 1 while a closed interval of angles is given at target 2. In this special case, the objective is to find an optimal Dubins path and the corresponding arrival angle at target 2. II. N OTATIONS  The two targets lie on a ground plane and the motion of the vehicle also occurs on the same plane. As commonly assumed, any angle measured with respect to the   x -axis in the counterclockwise direction is positive. The interval   Θ k  at target   k   is defined as   Θ k   = [ θ min k   , θ max k   ]   ⊆   [0 ,   2 π ]   with  θ min k   < θ max k   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 [14] showed that the shortest path for a vehicle to travel be- tween the two configurations 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. In particular, 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   or a degenerate form of these paths. For example, the degenerate forms of   RSL   are   S ,   L ,   R ,   RS ,   SL   and   RL . We also subscript a curved segment in some places ( L ψ   or   R ψ   ) to indicate the angle of turn ( ψ ) in the curved segment. In the results stated in the ensuing sections, the open interval   ( θ min k   , θ max k   )   is denoted as   Θ o k   for   k   = 1 ,   2 .  arXiv:1507.06980v2 [math.OC] 31 Aug 2015
III. M AIN   R ESULT  Theorem 1.   Any shortest path which is   C 1   and piecewise  C 2   of bounded curvature between the two targets with the departure angle   θ d   ∈   Θ 1   = [ θ min  1   , θ max  1   ]   at target 1 and the arrival angle   θ a   ∈   Θ 2   = [ θ min  2   , θ max  2   ]   at target 2 must be one of the following or a degenerate form of these: Case 1:   S   or   L ψ   or   R ψ   or   L ψ   R ψ   or   R ψ   L ψ   with   ψ > π . Case 2:   θ d   =   θ max  1   and   θ a   =   θ max  2   and the path is   LSR . Case 3:   θ d   =   θ max  1   and   θ a   =   θ min  2   and the path is either  LSL   or   LR ψ   L   with   ψ > π . Case 4:   θ d   =   θ min  1   and   θ a   =   θ min  2   and the path is   RSL . Case 5:   θ d   =   θ min  1   and   θ a   =   θ max  2   and the path is either  RSR   or   RL ψ   R   with   ψ > π . Case 6:   θ d   =   θ max  1   and   θ a   ∈   Θ o  2   and the path is either   LS  or   LR ψ   with   ψ > π . Case 7:   θ d   =   θ min  1   and   θ a   ∈   Θ o  2   and the path is either   RS  or   RL ψ   with   ψ > π . Case 8:   θ d   ∈   Θ o  1   and   θ a   =   θ max  2   and the path is either   SR  or   L ψ   R   with   ψ > π . Case 9:   θ d   ∈   Θ o  1   and   θ a   =   θ min  2   and the path is either   SL  or   R ψ   L   with   ψ > π .  Remark:   Note that in cases 1 and 6-9, the departure and arrival angles are implicitly specified by each of the paths. For example, if   L ψ   R ψ   with   ψ > π   exists between the two targets, as the length of the segment   L   is equal to the length of the segment   R , the departure and arrival angles are simply specified by geometry (we will later discuss this in the proofs; refer to Fig.2). Similarly, if   θ d   =   θ max  1   (case 6), the arrival angle at target 2 is determined by the   LS   or   LR   paths. The only remaining part would be to check if the arrival angle at target 2 lies in the interval   [ θ min  2   , θ max  2   ] . If it does, then the corresponding path is a candidate for an optimal solution to the Dubins interval problem. IV. T HE MINIMUM PRINCIPLE  Let   v o   be the speed of the vehicle, and   u ( t )   denote the control input for the vehicle at time   t . Let   x ( t ) , y ( t ) , θ ( t )  denote the position and angle coordinates of the vehicle as a function of time on the ground plane. At time   t   = 0 , let the vehicle be located at   ( x 1 , y 1 ) . Let the travel time of the vehicle be denoted by   T   . Note that   θ d   =   θ (0)   and   θ a   =   θ ( T   ) . The Dubins interval problem can be formulated as an optimal control problem as follows:  min  u ( t ) ∈ [ − 1 , 1]  ∫   T  0  1 dt   (1) subject to  dx dt   =   v o   cos   θ, dy dt   =   v o   sin   θ, dθ dt   =   u ρ ,   (2) and the following boundary conditions:  x (0) =   x 1 , x ( T   ) =   x 2 ,   (3)  y (0) =   y 1 , y ( T   ) =   y 2 ,   (4)  θ min  1   −   θ (0)   ≤   0 ,   (5)  θ (0)   −   θ max  1   ≤   0 ,   (6)  θ min  2   −   θ ( T   )   ≤   0 ,   (7)  θ ( T   )   −   θ max  2   ≤   0 .   (8) Let   the   adjoint   variables   associated   with   p ( t )   = ( x ( t ) , y ( t ) , θ ( t ))   be denoted as   Λ( t ) = ( λ x ( t ) , λ y   ( t ) , λ θ   ( t )) . The Hamiltonian associated with above system is defined as:  H (Λ , p, u ) = 1 +   v o   cos   θλ x   +   v o   sin   θλ y   +   u ρ λ θ   ,   (9) and the differential equations governing the adjoint variables are defined as:  dλ x  dt   = 0 , dλ y  dt   = 0 , dλ θ  dt   =   v o   sin   θλ x   −   v o   cos   θλ y   .   (10) Applying the fundamental theorem of Pontryagin [17] to the above problem, we obtain the following: If   u ∗   is an optimal control to the Dubins interval problem, then there exists a non-zero adjoint vector   Λ( t )   and   T   >   0   such that  p ( t ) ,   Λ( t )   being the solution to the equations in (2) and (10) for   u ( t ) =   u ∗ ( t ) , the following conditions must be satisfied:  •   ∀ t   ∈   [0 , T   ] ,   H (Λ , p, u ∗ )   ≡   min u ∈ [ − 1 , 1]   H (Λ , p, u ) .  •   ∀ t   ∈   [0 , T   ] ,   H (Λ , p, u ∗ )   ≡   0 .  •   Suppose   α 1 , α 2 , β 1 , β 2   are the Lagrange multipliers cor- responding to the boundary conditions in (5)-(8) respec- tively. Then, we have,  α 1 , α 2 , β 1 , β 2   ≥   0 ,   (11)  α 1 ( θ min  1   −   θ (0)) = 0 ,   (12)  α 2 ( θ (0)   −   θ max  1   ) = 0 ,   (13)  β 1 ( θ min  2   −   θ ( T   )) = 0 ,   (14)  β 2 ( θ ( T   )   −   θ max  2   ) = 0 ,   (15)  λ θ   ( T   ) =   β 2   −   β 1 ,   (16)  λ θ   (0) =   α 1   −   α 2 .   (17) Given a departure angle at target 1 and an arrival angle at target 2, the following facts are known for the basic Dubins problem in [15], [16]. We will use them in our proofs later.
Fact 1.   Consider any point   P   on an optimal path which is either an inflexion point of the path (point joining two curved segments or a point joining a curved segment and a straight line) or any point on a straight line segment of the path. Suppose the vehicle crosses this point at time   t   ∈   [0 , T   ] . Then,   λ θ   ( t ) = 0 .  Fact 2.   All the points of an optimal path where   λ θ   ( t ) = 0   lie on the same straight line.  Fact 3.   Consider any curved segment of an optimal path. Let the times   t 1 , t 2   be such that   0   ≤   t 1   < t 2   ≤   T   , the vehicle is located on the curved segment at times   t 1 , t 2 , and  λ θ   ( t 1 ) =   λ θ   ( t 2 ) = 0 . Then, the length of the curved segment between the times   t 1   and   t 2   must be greater than   πρ .  Fact   4.   For   any   t   ∈   [0 , T   ] ,   the   optimal   control  u ∗ ( t ) =   − sign ( λ θ   ( t ))   if   λ θ   ( t )   6   = 0 .  V. P ROOF OF THEOREM   1 The departure angle in any optimal solution must either be an interior point in   Θ 1   or belong to one of the boundary values of   Θ 1 . Similarly, the arrival angle in any optimal solution must either be an interior point in   Θ 2   or belong to one of the boundary values of   Θ 2 . The combination of choices for the departure angle and arrival angle coupled with   the   complementary   slackness   equations   in   (11)-(17) provides constraints for the values of   λ θ   (0)   and   λ θ   ( T   ) . These constraints can then be used to find the candidate solutions for solving the Dubins interval problem. The following lemma first shows the relationship between the departure, arrival angles and the constraints on   λ θ   (0)   and   λ θ   ( T   ) .  Lemma 1.   The constraints for the adjoint variable   λ θ   at times   t   = 0   and   t   =   T   corresponding to the departure and arrival angles are given in the table below:  Case No. Conditions on the departure and arrival angles of any op- timal path Implied constraints on  λ θ   (0)   and   λ θ   ( T   )  1   θ (0)   ∈   Θ o  1 ,   θ ( T   )   ∈   Θ o  2   λ θ   (0) = 0 , λ θ   ( T   ) = 0  2   θ (0) =   θ max  1   ,   θ ( T   ) =   θ max  2   λ θ   (0)   ≤   0 , λ θ   ( T   )   ≥   0  3   θ (0) =   θ max  1   ,   θ ( T   ) =   θ min  2   λ θ   (0)   ≤   0 , λ θ   ( T   )   ≤   0  4   θ (0) =   θ min  1   ,   θ ( T   ) =   θ min  2   λ θ   (0)   ≥   0 , λ θ   ( T   )   ≤   0  5   θ (0) =   θ min  1   ,   θ ( T   ) =   θ max  2   λ θ   (0)   ≥   0 , λ θ   ( T   )   ≥   0  6   θ (0) =   θ max  1   ,   θ ( T   )   ∈   Θ o  2   λ θ   (0)   ≤   0 , λ θ   ( T   ) = 0  7   θ (0) =   θ min  1   ,   θ ( T   )   ∈   Θ o  2   λ θ   (0)   ≥   0 , λ θ   ( T   ) = 0  8   θ (0)   ∈   Θ o  1 ,   θ ( T   ) =   θ max  2   λ θ   (0) = 0 , λ θ   ( T   )   ≥   0  9   θ (0)   ∈   Θ o  1 ,   θ ( T   ) =   θ min  2   λ θ   (0) = 0 , λ θ   ( T   )   ≤   0  Proof:   Consider the first set of conditions,   θ (0)   ∈   Θ o  1 ,  θ ( T   )   ∈   Θ o  2 , in the table. If   θ (0)   ∈   Θ o  1 , then equations (12) and (13) imply   α 1   = 0   and   α 2   = 0   respectively. Using (17), we obtain   λ θ   (0) =   α 1   −   α 2   = 0 . Similarly, if   θ ( T   )   ∈   Θ o  2 , then equations (14) and (15) imply   β 1   = 0   and   β 2   = 0   respectively. Using (16), we obtain   λ θ   ( T   ) =   β 2   −   β 1   = 0 . Each of the other constraints in the table can be verified using a similar procedure. Hence proved. We now use the constraints on   λ θ   (0)   and   λ θ   ( T   )   to infer the candidate solutions for the Dubins interval problem.  Lemma 2.   Let   λ θ   (0) =   λ θ   ( T   ) = 0 . Then the optimal path for the Dubins interval problem must be either   S   or   L ψ   or  R ψ   or   L ψ   R ψ   or   R ψ   L ψ   with   ψ > π . Proof:   An optimal path can just be a straight line from fact 2. From fact 3, a curved segment of length greater than  πρ   can satisfy the boundary conditions   λ θ   (0) =   λ θ   ( T   ) = 0 . In addition, any path containing three curved segments and satisfying the boundary conditions must have the length of each   curved   segment   (between   any   two   inflexion   points) greater than   πρ ; however, as shown in [16], such a path cannot be optimal. Therefore, an optimal path may consist of either one or two curved segments with the length of each segment greater than   πρ . If an optimal path consists of exactly two curved segments, then there are three points ( ( x 1 , y 1 ) ,   ( x 2 , y 2 )   and the inflexion point) where   λ θ   ( t )   becomes zero for   t   ∈   [0 , T   ] . From fact 2, all these three points must lie on the same straight line. Therefore, the length of the first curved segment must be equal to the length of the second curved segment as shown in Fig. 2 (in this case,   θ (0) =   θ ( T   ) ). λ θ   (0) = 0   λ θ   ( T   ) = 0  ( x 1 , y 1 )   ( x 2 , y 2 )  Fig. 2.   A   RS   path with the boundary values of   λ θ   equal to 0.  Note that a set of constraints, say   λ θ   (0)   ≤   0 , λ θ   ( T   )   ≥   0 , can   be   satisfied   if   either   λ θ   (0)   =   λ θ   ( T   )   =   0   or  λ θ   (0)   <   0 , λ θ   ( T   )   =   0   or   λ θ   (0)   <   0 , λ θ   ( T   )   >   0   or  λ θ   (0) = 0 , λ θ   ( T   )   >   0   is satisfied. The following lemma identifies all the candidate solutions for any combination of these constraints on   λ θ   (0)   and   λ θ   ( T   ) .  Lemma 3.   Candidate optimal paths for the Dubins interval problem corresponding to the constraints on   λ θ   (0)   and   λ θ   ( T   )  are given in the table below:
Constraints   on   λ θ   (0)  and   λ θ   ( T   )  Candidate solutions  ( ψ > π )  λ θ   (0) = 0 , λ θ   ( T   ) = 0   S , L ψ   , R ψ   , L ψ   R ψ   , R ψ   L ψ  λ θ   (0)   <   0 , λ θ   ( T   ) = 0   LS, LR ψ   with   ψ > π λ θ   (0)   <   0 , λ θ   ( T   )   <   0   LSL, LR ψ   L   with   ψ > π λ θ   (0)   <   0 , λ θ   ( T   )   >   0   LSR λ θ   (0) = 0 , λ θ   ( T   )   <   0   SL, RL ψ   with   ψ > π λ θ   (0) = 0 , λ θ   ( T   )   >   0   SR, LR ψ   with   ψ > π λ θ   (0)   >   0 , λ θ   ( T   ) = 0   RS, RL ψ   with   ψ > π λ θ   (0)   >   0 , λ θ   ( T   )   <   0   RSL λ θ   (0)   >   0 , λ θ   ( T   )   >   0   RSR, RL ψ   R   with   ψ > π  Proof:   The candidate solutions corresponding to   λ θ   (0) =  λ θ   ( T   ) = 0   has already been shown in lemma 2. Consider the next set of constraints   λ θ   (0)   <   0   and   λ θ   ( T   ) = 0 . If   λ θ   (0)   <   0 , the first segment of the path must be   L   (fact 4).   LSR ψ   or  LSL ψ   with   ψ >   0   is not possible because this path would violate fact 2 unless the length of the straight line is equal to 0.   LRL   is also not possible because the length of the   R  segment and the last   L   segment would each be greater than  πρ   which then cannot be optimal [16]. Therefore, the possible candidates are   LS   or   LR ψ   with   ψ > π . Each of the remaining set of the constraints can be shown using a similar procedure. The theorem follows by combining lemmas 1 and 3. VI. S OLUTION FOR THE   S PECIAL   C ASE  In this special case of the Dubins interval problem, the departure angle   θ d   is given while the arrival angle at target 2 must belong to a closed interval   Θ 2 .  Theorem 2.   Any shortest path which is   C 1   and piecewise  C 2   of   bounded   curvature   between   the   two   targets   with the departure angle   θ d   at target 1 and the arrival angle  θ a   ∈   Θ 2   = [ θ min  2   , θ max  2   ]   at target 2 must be one of the following or a degenerate form of these: Case 1: The path is either   LS   or   RS   or   LR ψ   or   RL ψ   with  ψ > π . Case 2:   θ a   =   θ max  2   and the path is either   LSR   or   RSR RL ψ   R   with   ψ > π . Case 3:   θ a   =   θ min  2   and the path is either   RSL   or   LSL LR ψ   L   with   ψ > π .  This theorem can be proved following the same procedure as in the previous section. R EFERENCES [1]   J.-H. Lee, O. Cheong, W.-C. Kwon, S. Shin, and K.-Y. Chwa, “Ap- proximation of curvature-constrained shortest paths through a sequence of points,” in   Algorithms - ESA 2000 , ser. Lecture Notes in Computer Science, M. Paterson, Ed.   Springer Berlin Heidelberg, 2000, vol. 1879, pp. 314–325. [2]   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 [3]   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. [4]   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. [5]   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. [6]   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. [7]   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. [8]   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. [9]   Z. Tang and U. Ozguner, “Motion planning for multitarget surveillance with mobile sensor agents,”   Robotics, IEEE Transactions on , vol. 21, no. 5, pp. 898–908, Oct 2005. [10]   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. [11]   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. [12]   J. Le Ny, E. Feron, and E. Frazzoli, “On the dubins traveling salesman problem.”   IEEE Trans. Automat. Contr. , vol. 57, no. 1, pp. 265–270, 2012. [13]   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. [14]   L.E.Dubins, “On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tan- gents,”   American Journal of Mathematics , vol. 79, no. 3, pp. 487–516, 1957. [15]   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 [16]   X.-N. Bui, J.-D. Boissonnat, P. Soueres, and J.-P. Laumond, “Shortest path synthesis for dubins non-holonomic robot,” in   Robotics and Au- tomation, 1994. Proceedings., 1994 IEEE International Conference on , May 1994, pp. 2–7 vol.1. [17]   L.   S.   Pontryagin,   V.   G.   Boltianski,   R.   V.   Gamkrelidze,   E.   F. Mishchenko, and D. E. Brown, “The mathematical theory of optimal processes,” London, Paris, 1964, a Pergamon Press book. [Online]. Available: http://opac.inria.fr/record=b1122221 [18]   E. Garcia, D. W. Casbeer, K. Pham, and M. Pachter, “Cooperative aircraft defense from an attacking missile,” in   Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on .   IEEE, 2014, pp. 2926– 2931. [19]   E. Garcia, D. W. Casbeer, and M. Pachter, “Active target defense differential game with a fast defender,”   arXiv preprint arXiv:1502.02747 , 2015. [20]   S. Manyam and S. Rathinam, “A tight lower bounding procedure for the dubins traveling salesman problem,”   Presented at the International Symposium on Mathematical Programming , 2015. [Online]. Available: http://arxiv.org/abs/1506.08752