On the Length of Dubins Path with Any Initial and Terminal Configurations
Li Dai, Zheng Xie
College of Science, National University of Defense Technology, Changsha, Hunan, China
Email address:
To cite this article:
Li Dai, Zheng Xie. On the Length of Dubins Path with Any Initial and Terminal Configurations.Pure and Applied Mathematics Journal.Vol.4, No. 6, 2015, pp. 248-254. doi: 10.11648/j.pamj.20150406.14
Abstract: Dubins has proved in 1957 that the minimum length path between an initial and a terminal configuration can be found among the six paths {LSL, RSR, LSR, RSL, RLR, LRL}. Skel and Lumelsky have studied the length of Dubins path with the initial configuration (0, 0; α) and the terminal configuration (d, 0; β) and the minimal turning radius ρ=1 in 2001. We extended the Skel and Lumelsky’s results to the case that the initial and terminal configuration is,, respectively (where), and the minimal turning radius is.
Keywords: Dubins Set, Dubins Path, Dubins Traveling Salesman Problem, Computational Geometry
1. Introduction
The problem of finding the shortest smooth path between two configurations in the plane appear in various applications, such as when joining pieces of railways^{1} or planning two and three-dimensional pipe networks. In robotics, this problem plays a central role in most of the work on nonholonomic motion planning^{2-4}. In unmanned aerial vehicle (UAV), the kinematics of the UAV can be approximated by the Dubins vehicle, too^{5}. The Dubins distance in the path planning for UAV is needed to be computed^{5-7}. Let the initial and terminal configurations is and, respectively, where and is the position, andis the orientation angle (heading). The task is to find the shortest smooth path from to such that the path curvature is limited by , where is the minimal turning radius.
The problem of finding the shortest smooth path between two configurations in the plane was firstly considered by Dubins^{8}. The classical 1957 result by Dubins^{}gives a sufficient set of paths (Dubins path) which always contains the shortest path. The Dubins set includes six admissible paths and
,
where and are arc of the minimal allowed radius turning left or turning right, respectively, is a line segment.
Shkel and Lumelsky have considered the length of the six Dubins path in 2001^{9} with the initial configuration , the terminal configurationand the minimal turning radius. Also they studied the logical classification scheme which allows one to extract the shortest path from the Dubins set directly, without explicitly calculating the candidate paths for ‘long path case’ and ‘short path case’.
In this paper, we studied the length of Dubins path with initial configuration and terminal configuration, and the minimal turning radius. Although we can convert this situation into [9] by coordinate transformation. It is still worthy of study. For example, in order to find out the optimal tour of DTSP (Dubins Traveling Salesman Problem, which has been attracted a lot of attention^{5,10-16}for it is a useful abstractions for the study of problems related to motion planning and task assignment for uninhabited vehicles. ), we need to do different coordinate transformations and this will waste computing time.
We propose a formula for calculate the length of Dubins path between any initial configuration and terminal configuration , and any minimal turning radius in section 2. In section 3, we expend the results in section 2 to the case with . An application in DTSP is provided in section 4.
2. The Length of Dubins Path with
Let be the initial configuration and be the terminal configuration.
Three corresponding operators, (for left turn), (for right turn), (for straight), are needed, which transform an arbitrary configuration into its corresponding image configuration,
(1)
where index indicates that the motion has turned angle (in rad) along the arc with the minimal radius (the length of the arc is) and indicates the length along the line segment. With these elementary transformations, any path in the Dubins set
,
can be expressed in terms of the corresponding equations. For example, a path made of segments, of the length , respectively, which starts at configuration , must end at . The length of the Dubins path is calculated as
.
So, the value of is the key problem. To get the value of , we will now consider elements of Dubins set one-by-one and derive the operator equations for the length of each path.
Letbe the Euclidean distance between andin the plane. Let be the minimal radius. Firstly, letand will be discussed later in Theorem 1.
1. . By applying the corresponding operators (1), we have the following equations:
The solutions of this system with respect to the segments and is found as
(2)
where and
The length of as a function of the boundary conditions can be now written as , whereare calculated by (2).
2. . By applying the corresponding operators (1), we have the following equations:
The solutions of this system with respect to the segments and is found as
(3)
where and
The length of as a function of the boundary conditions can be now written as , where are calculated by (3).
3. . By applying the corresponding operators (1), we have the following equations:
The solutions of this system with respect to the segments and is found as
(4)
Where, , and
The length of as a function of the boundary conditions can be now written as , where are calculated by (4).
4. . By applying the corresponding operators (1), we have the following equations:
The solutions of this system with respect to the segments and is found as
(5)
where, , and
The length of as a function of the boundary conditions can be now written as , where are calculated by (5).
5. . By applying the corresponding operators (1), we have the following equations:
The solutions of this system with respect to the segments and is found as the minimum of the following two cases. Let
and
,
Case 1.
(6)
Case2.
(7)
The length of as a function of the boundary conditions can be now written as , where are calculated by (6) and are calculated by (7).
It is worth to noting that both of the two cases are needed to be considered (but [9] only considered the case 1). For example, letbe the initial configuration and be the terminal configuration, then and , so . See Fig. 1(a). On the other hand, letbe the initial configuration and be still the terminal configuration, then and , so . See Fig. 1(b).
Figure 1. Two cases for Dubins path.
6. . By applying the corresponding operators (1), we have the following equations:
The solutions of this system with respect to the segments and is found as the minimum of the following two cases. Let
and
.
Case 1.
(8)
Case2.
(9)
The length of as a function of the boundary conditions can be now written as , whereare calculated by (8) and are calculated by (9).
3. The Length of Dubins Path with
Now, we consider the case for.
Theorem 1 Let and be the initial configuration and the terminal configuration, respectively. Let and the length of Dubins path is denoted by . Let denote the length of the corresponding Dubins path of the minimum turn radiuswith initial configuration and the terminal configuration , where, then
Proof we take Dubins pathas an example to prove. Let , then we have
(10)
That is
(11)
Let . Now (11) can be rewritten as
(12)
Compare (12) with Dubins path when, we can get the solutions of (12) by (4). Let the length of Dubins path in (12) is denoted by and the length in (4) is denoted by, then
. □
Theorem 1 laid a solid foundation for computing the length of Dubins tour of travelling salesman problem with any minimal turning radius.
4. An Application in DTSP
Above all, the formula to calculatefor the length of Dubins path is provided which is applicable to any initial configuration , any terminal configuration and any minimal turning radius. Next, we consider its application in DTSP.
For the instance considered in this section, the vertices are generated randomly, independently and uniformly in a 5 by 5 square (see Fig.2). The vertices are labeled as and their positions and headings are shown in Tab. 1.
10 Vertex Configuraton(TSP: 12.6239) | |||||
Vertex | X | Y | Heading () | Heading () | Heading () |
1 | 4.0579 | 2.6552 | 3.9132 | 5.0913 | 5.5396 |
2 | 3.6489 | 2.7603 | 3.7546 | 0.0029 | 0.5892 |
3 | 3.9223 | 1.1900 | 3.6622 | 3.3706 | 2.6511 |
4 | 3.1338 | 1.8687 | 2.7529 | 2.4887 | 2.7337 |
5 | 1.1574 | 1.8527 | 3.1024 | 3.2398 | 2.8227 |
6 | 0.2346 | 1.9660 | 2.2669 | 2.3065 | 3.47468 |
7 | 0.3445 | 3.5166 | 1.2351 | 1.2029 | 0.5435 |
8 | 0.9754 | 4.4559 | 0.4972 | 0.5113 | 0.8874 |
9 | 2.5774 | 4.4722 | 5.9065 | 5.8899 | 5.5635 |
10 | 3.5949 | 3.5127 | 5.4060 | 5.3556 | 5.3026 |
By using the formula in section 2 and 3, we can get the length of the Dubins path from to, (set ). Denote the length of Dubins path from to, e.g.. See Tab. 2.
radius | |||
| 0.4637 | 2.7617 | 5.9110 |
| 1.6501 | 2.0622 | 4.4585 |
| 1.0726 | 1.1520 | 1.0529 |
| 1.9775 | 2.0034 | 2.0023 |
| 0.9371 | 0.9721 | 0.9582 |
| 1.5623 | 1.6073 | 5.5117 |
| 1.1337 | 1.1420 | 1.1556 |
| 1.6049 | 1.6181 | 1.8043 |
| 1.3995 | 1.4032 | 1.4007 |
| 1.0108 | 0.9749 | 0.9845 |
total | 12.8122 | 15.6968 | 25.2396 |
The Dubins tour for the 10 vertex instance with different turning radiusare presented in Fig.3. For this instance, the length of ETSP is 12.6239. From Fig.3, we can see that the Dubins length are all larger than the length of ETSP and it is increasing rapidly as the minimal turning radiusgoes up.
(a) Length 12.8122 with. (b) Length 15.6968 with. (c) Length 25.2369 with.
5. Summary
In this paper, the formula to calculatefor the length of Dubins path is provided which is applicable to any initial point , any final point and any minimal turning radius. We have proved the formula theoretically and experimentally with its application in DTSP. Numeral experiment has shown that the formulas are correct and efficient.
Acknowledgement
The authors would like to thank anonymous referees for several useful comments.
References