# 2D Dubins Path in Environments with Obstacle

Authors: Dongxiao Yang; Didong Li; Huafei Sun
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We recapitulate the achievement about the Dubins path as well as some precise proofs which are important but omitted by Dubins. Then we prove that the shortest path (R*-geodesic) in environments with an obstacle consists of no more than five segments, each of which is either an arc or a straight line. To obtain such R*-geodesic, an effective algorithm is presented followed by a numerical simulation as verification.


---

## Body

## 1. Introduction

Nowadays, Unmanned Aerial Vehicles (UAVs) are comprehensively applied in a wide range like avionics, GPS-based navigation, flight control techniques, reconnaissance and surveillance, weather, and atmospheric research. In addition, they are also widely used in both conventional combat roles and innovative roles which were not previously possible, such as operations in chemical and biological weapons environments and operations that require microair vehicles [1].Therefore, one of the most important issues in their development is path planning. A path planning algorithm is aiming at producing one or several flyable paths for UAVs, subject to certain constraints. The path length might be the first factor that should be taken into consideration because the path length decides the traveling time and energy consumption. Besides, the trajectory has to meet the speed and turn limits of the UAVs so that the UAVs could fly safely. Now we can present this problem from the perspective of mathematics.Given two pointsu and v in a plane, each with a prescribed direction of motion U and V in it; the question being asked is to find the shortest smooth path of bounded curvature R that joins them. The classical result [2] achieved by Dubins in 1957 gives a sufficient set of paths (each consisting of circular arcs and straight line segments) which always contains the shortest one. Then, Shkel and Lumelsky [3] made classification for the Dubins set, while Chitsaz and Lavalle [4] discussed the directions of the paths, which are more efficient approaches to calculate the shortest path.For 3D cases, Reeds and Shepp [5] made a “CLC conjecture” in 1990 that was widely believed in the past, which generalized the result for 2D cases directly to 3D cases. Unfortunately, such conjecture was disproved by Sussmann in 1995 [6], and he proved that the shortest path might also be a helicoidal arc that has a constant curvature and its torsion satisfies a certain differential equation.Although such path is exactly the shortest one, it is too complicated to be easily applied in engineering. As a result, researchers began to find other models to get some paths which are easier to be calculated but might be longer than the shortest path. In some papers such as [1, 7–18], the authors considered some approaches to get the final path. One of the advantages of such approaches is that it could be used in the environments with some obstacles only after a little bit changes. A disadvantage is that neither of them is exactly the shortest path.When it comes to more real and common conditions: UAVs fly through urban environments full of high buildings, and new methods are required to generate trajectories that traverse the regions and its associated obstacles [1, 19].Unfortunately, when considering the Dubins problem with obstacles, the original result will no longer be suitable, because the Dubins path might pass through the obstacles so the result needs to be changed a little. For 3D cases, the approaches used in [8–17] can be used only by a little change, because the result is not the shortest paths in either condition. It is a pity that we cannot get the shortest path with obstacles in 3D cases. Instead, it is possible to find the shortest path with obstacles in 2D cases. In this paper, we prove that the shortest path consists of no more than five parts, which is either an arc or a straight line under the assumption that there is only one circular obstacle. What is more, both specific algorithm and numerical simulation are presented.


## 2. General Case

In this section, we recapitulate the original proof given by Dubins [2], because this approach is also used in Theorem 13 in Section 3. As a result, parts of them are omitted. On the other hand, the proofs of some details which are very important but not obvious in his paper are omitted. Hence, we give the proofs with the details which are quite useful for the proofs of our results.LetP(s) be a curve in 𝔼2 parameterized by arc length s. If
(1)∥P′(s1)-P′(s2)∥≤R-1|s1-s2|
we say that the curve P has an average curvature always less than or equal to R-1.LetC=C(u,U,v,V,R) be the collection of all curves P defined on a closed interval [0,L], where L=L(P) varies with P, such that P(s)∈E2 for 0≤s≤L; ∥P′(S)∥≡1; the average curvature of P is everywhere less than or equal to R-1; P(0)=u,P′(0)=U,P(L)=v and P′(L)=V.Definition 1.
The path which has minimal length inC=C(u,U,v,V) is called the R-geodesic for C denoted by RC.Suppose that the arc with radiusR is C and the straight line is L.Theorem 2.
Every planarR-geodesic is necessarily a continuously differentiable curve which is either (1) CLC or (2) CCC or a subpath of type (1) or (2) (see also Figure 1).Figure 1This is the most important theorem in [2] and we present the proofs, beginning with the existence of the R-geodesic.Proposition 3.
For anyn, u, U, v, V, and R, there exists a path in C=C(n,u,U,v,V,R) of minimal length.Proof.
Letl be the infimum of lengths of all curves in C. There exists a sequence Pn∈C such that the length ln is monotonely decreasing to l. On one hand, since ∥Pn′∥≡1, it follows that Pn′ are uniformly bounded. On the other hand, since ∥P′(s1)-P′(s2)∥≤R-1|s1-s2|, it follows that Pn′ are also equicontinuous. Let P~n be the restriction of Pn on closed interval [0,l], hence, P~n satisfy all conditions above and are defined on a common compact set [0,l]. Then by Ascoli's theorem, there is a subsequence of family P~n whose derivatives converge uniformly on [0,l] to a function Q. Then, P~n converge uniformly in [0,l] to a function P with length l. It is easy to check that P is exactly the R-geodesic RC.Remark 4.
The pathsPn are defined on different interval [0,ln], so the Ascoli's theorem could not be applied. To solve this problem, we restrict Pn on a common compact interval [0,l] denoted by P~n. This step is very important but was omitted by Dubins in [2], so we present it here as a complement.Then we only relate several propositions without proof.Proposition 5.
Let P be a planar curve of length less than or equal toπR/8. Then P is an R-geodesic if and only if P is of type CLC.Then it is easy to prove the following.Proposition 6.
LetP be a planar curve defined on a closed finite interval [0,l] parameterized by arc length. Then if P is a R-geodesic, it is a continuously differentiable curve which consists of a finite number of pieces, each of which is either a straight line segment or an arc of a circle of radius R.In fact, theR-geodesic contains no more than three pieces, it is sufficient to show that no path consisting of four arc and straight line segments can be an R-geodesic. So we consider all the eight paths of these types: CCCC, CCCL, CCLC, CLCC, CLCL, LCCC, LCCL, and LCLC.Lemma 7.
If a curve is anR-geodesic, then so is the curve obtained by traversing the path in the opposite direction.Therefore, we only need to consider five types:CCCC, CCCL, CCLC, CLCL, and LCCL.Lemma 8.
If a curve is anR-geodesic, then so is every subpath of the curve.Thus, it is sufficient to show that none of the following three types of curves is anR-geodesic: CCCC, CCL, and LCL. Then we consider three lemmas to rule out such cases without proof but only Figures 2, 3, and 4, respectively.Figure 2Figure 3Figure 4Lemma 9.
No curve of typeLCL is an R-geodesic.Lemma 10.
No curve of typeCCCC is an R-geodesic.Lemma 11.
No curve of typeCCL is an R-geodesic.As a result, every planarR-geodesic has no more than three pieces except LCL, so it is either CCC or CLC or a subpath of them. Now we have proved Theorem 2.


## 3. Environments with One Obstacle

In this section, we consider the path in the environments with one obstacle and prove that the shortest path consists of no more than five segments where each is either an arc or a straight line.Denote the open circular area byO and we suppose that R≤r(O) because the radius of obstacle is always far larger than R in practical problems. Suppose that E2* is the complementary set of O and D is the arc along the bound of O. Let u,v,U,andletV be vectors in E2 and ∥U∥=∥V∥=1, R>0. Let C*=C*(2,u,v,U,V,R,andO) be the collection of all curves P in E2* with an average curvature less than or equal to R-1 everywhere.Definition 12.
The shortest path inC* is called the R*-geodesic denoted by RC*.If theR*-geodesic is the same as R-geodesic, we call the obstacle an ineffective obstacle. If they are different, we call it an effective one. Our ultimate goal in this section is to prove the following Theorem 13.Theorem 13.
R
*-geodesic is one of CCDCC, CLDLC, CCDLC, CLDCC, CCC, CLC, or a subpath of them.Figure5 is the type CLDLC.Figure 5Before proving Theorem13, we prove several propositions and lemmas first. If the obstacle is ineffective, the R-geodesic is showed in Theorem 2, without any difference, so we only consider the case that the obstacle is effective. The obstacle is ineffective means that the R*-geodesic is the same as the R-geodesic which does not pass through the obstacle O. On the other hand, the obstacle in effective means that the original R-geodesic passes through the obstacle O such that the new R*-geodesic is different.Proposition 14.
For anyn, u, U, v, V, and R, there exists an P in C*=C*(n,u,U,v,V,R) of minimal length.Proof.
As in Proposition3, such Pn′ are uniformly bounded and equicontinuous. Since E2* is closed in E2, the Ascoli's theorem also holds, so Pn′ converge uniformly to Q. Others are the same.Besides, Propositions5 and 6 also hold in such case.Proposition 15.
LetP be a planar curve defined on a closed finite interval [0,l] parameterized by arc length. Then if P is an R*-geodesic, it is a continuously differentiable curve which consists of a finite number of pieces, each of which is either a straight line segment or an arc of a circle of radius R.Before we rule out the possibility of a curve which consists of more than five pieces to be theR*-geodesic, we prove a lemma.Lemma 16.
IfU or V is tangent to the obstacle O, then O is ineffective; it is to say that the original R-geodesic does not pass through O.Proof.
Theorem2 shows that the original R-geodesic consists of arc or straight lines; both u and v are tangent to the arcs. Since the obstacle O is exactly the bound of the starting circle, R-geodesic does not pass through the obstacle, which is shown in Figure 6.Figure 6In order to prove Theorem13, we consider two cases.


### 3.1. Case 1:RC* does not intersect D

Proposition 17.
R
*-geodesic is CCC or CLC or subpath of them if it does not contain D.Proof.
It could be proved directly by Theorem2.


### 3.2. Case 2:RC* Intersects D

R
*-geodesic has several pieces including D. Now we prove that there are no more than five pieces.Proposition 18.
R
C
* has no more than five pieces.Proof.
We prove the proposition by contradiction.
Assume thatRC* has six pieces including D. Divide RC* into two pieces, with D as the middle piece: the former one is P1D, and the latter one is DP2.
It is obvious thatP1 and P2 have five pieces altogether; hence, one of them has more than two;pieces. We assume that P1 has three pieces and P2 has two; see also Figure 7.
Let the end point ofD be w; the tangent vector at w is W. Now consider CD*=C(2,u,U,w,W,O) and the corresponding R*-geodesic RCD*. From Lemma 8, we see that P1D is a subpath of R*-geodesic and so is also a R*-geodesic: the shortest path for condition CD*=C(2,u,U,w,W,O); hence, RCD*=P1D. Besides, RCD is the R-geodesic for CD=C(2,u,U,w,W).
SinceW is tangent to O, we know that RCD*=RCD from Lemma 16, so
(2)RCD=RCD*=P1D.
It is to say that theR-geodesic RCD for CD=C(2,u,U,w,W) contains four pieces: P1 has three and D has one, which is contradict to Theorem 2. Hence, our assumption is wrong and RC* has no more than five pieces.Figure 7Now we can prove Theorem13.Proof of Theorem13.
Firstly, consider case 2:RC* intersects D. From the proof of Proposition 18, especially (2), we know that both P1 and P2 has no more than two pieces. Thus, P1 is CC, CL, LC, or subpath of them. Since P1D=RCD, RCD is CCC or CLC or subpath of them from Theorem 2 and then we can rule out LC easily. Therefore, P1 is CC, CL, or subpath of them. Similarly, P2 is CC, LC, or subpath of them. According to Propositions 17 and 18, the R*-geodesic RC* is CCDCC, CLDLC, CCDLC, CLDCC, CCC, CLC, or a subpath of them.Now we have proved Theorem13 and solved the Dubins problem with obstacle.


## 3.1. Case 1:RC* does not intersect D

Proposition 17.
R
*-geodesic is CCC or CLC or subpath of them if it does not contain D.Proof.
It could be proved directly by Theorem2.


## 3.2. Case 2:RC* Intersects D

R
*-geodesic has several pieces including D. Now we prove that there are no more than five pieces.Proposition 18.
R
C
* has no more than five pieces.Proof.
We prove the proposition by contradiction.
Assume thatRC* has six pieces including D. Divide RC* into two pieces, with D as the middle piece: the former one is P1D, and the latter one is DP2.
It is obvious thatP1 and P2 have five pieces altogether; hence, one of them has more than two;pieces. We assume that P1 has three pieces and P2 has two; see also Figure 7.
Let the end point ofD be w; the tangent vector at w is W. Now consider CD*=C(2,u,U,w,W,O) and the corresponding R*-geodesic RCD*. From Lemma 8, we see that P1D is a subpath of R*-geodesic and so is also a R*-geodesic: the shortest path for condition CD*=C(2,u,U,w,W,O); hence, RCD*=P1D. Besides, RCD is the R-geodesic for CD=C(2,u,U,w,W).
SinceW is tangent to O, we know that RCD*=RCD from Lemma 16, so
(2)RCD=RCD*=P1D.
It is to say that theR-geodesic RCD for CD=C(2,u,U,w,W) contains four pieces: P1 has three and D has one, which is contradict to Theorem 2. Hence, our assumption is wrong and RC* has no more than five pieces.Figure 7Now we can prove Theorem13.Proof of Theorem13.
Firstly, consider case 2:RC* intersects D. From the proof of Proposition 18, especially (2), we know that both P1 and P2 has no more than two pieces. Thus, P1 is CC, CL, LC, or subpath of them. Since P1D=RCD, RCD is CCC or CLC or subpath of them from Theorem 2 and then we can rule out LC easily. Therefore, P1 is CC, CL, or subpath of them. Similarly, P2 is CC, LC, or subpath of them. According to Propositions 17 and 18, the R*-geodesic RC* is CCDCC, CLDLC, CCDLC, CLDCC, CCC, CLC, or a subpath of them.Now we have proved Theorem13 and solved the Dubins problem with obstacle.


## 4. Algorithm

Such Dubins problem mentioned above could be described as input and output. Inputs are as follows:(1)
initial pointPs(xs,ys) and initial velocity vs,(2)
final pointPf(xf,yf) and final velocity vf,(3)
minimal turning radius of the UAVsR,(4)
radius of the circular obstacleRD.While output is the length of the minimizing flyable path l.In order to calculate the output with inputs, we present an algorithm which contains seven steps.Step 1.
Calculate the initial turning circleCs by vs,Ps, and R, the final turning circle Cf by vf,Pf, and R. Denote the clockwise and counterclockwise circles by Cs1,Cf1 and Cs2,Cf2, respectively. Then calculate four groups of data according to the original algorithm, while each of them contains a pair of initial and final turning circle, coordinates of two tangent points, and the length of Dubins path.Step 2.
Judge that whether each of the four Dubins path passes through the obstacle circle.Case  1. If the path passes through the obstacle, go to Step 3.Case  2. Else, record the data and go to Step 7.Step 3.
Calculate the Dubins path betweenCs1 and obstacle circle D. Because the “final” velocity is uncertain, rule out two paths whose turning directions of vs and the common tangent line are different, where the other two remained S1D1 and S1D2; see also Figure 8.Figure 8Step 4.
Calculate the Dubins path between obstacle circleD and Cf1 by ruling out two of four paths as in Step 3 where DF11 and DF12 remained, as in Figure 9.Figure 9Step 5.
There are two possible combinations fromCs1 to Cf1: S1DF11 and S1DF12, where
(3)S1DF11=S1D1+DF11;S1DF12=S1D2+DF12.Step 6.
There are eight combinations in all includingS1DF11 and S1DF12. The other six paths areS1DF21 and S1DF22: from Cs1 to Cf2;S2DF11 and S2DF12: from Cs2 to Cf1;S2DF21 and S2DF22: from Cs2 to Cf2.Step 7.
Calculate the length of all the eight paths and select the minimal one as the shortest path.


## 5. Simulation

The parameters of UAVs and the obstacle are showed in Table1.Table 1
Value of parameter.
Parameter
Value
Unit
Initial coordinates
(0, 1000, 200)
m
Final coordinates
(3000, −1000, 200)
m
Initial velocity
(0, 30)
m/s
Final velocity
(−18, −24)
m/s
Obstacle coordinates
(1850, 50)
m
Obstacle radius
300
mSince the original path B intersects with the obstacle D, a new path E which does not intersect D is calculated, as in Figure10.Figure 10Put E together with three original paths A, C, and D, which do not intersect the obstacle, as in Figure11.Figure 11The lengths of the four paths are shown in Table2 so that the minimal one E could be selected directly.Table 2
Length comparisons.
Path
Length
Unit
A
4313.2
m
C
4667.1
m
D
4173.5
m
E
3823.3
m


## 6. Conclusion

In this paper, we present the achievements of Dubins and his proofs with some more important complement in details at first. Then we generalize the results to the more useful cases in environments with one obstacle and prove that the shortest path (R*-geodesic) consists of no more than five segments, where each is either an arc or a straight line. To calculate the R*-geodesic, an algorithm is discussed and also a numerical simulation is accomplished as verification.



---

*Source: 291372-2013-11-11.xml*