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 railways1 or planning two and three-dimensional pipe networks. In robotics, this problem plays a central role in most of the work on nonholonomic motion planning2-4. In unmanned aerial vehicle (UAV), the kinematics of the UAV can be approximated by the Dubins vehicle, too5. The Dubins distance in the path planning for UAV is needed to be computed5-7. Let the initial and terminal configurations is and
, respectively, where
and
is the position,
and
is 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 Dubins8. The classical 1957 result by Dubinsgives 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 20019 with the initial configuration , the terminal configuration
and 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 attention5,10-16for 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
and
in the plane. Let
be the minimal radius. Firstly, let
and
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
, where
are 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, let
be the initial configuration and
be still the terminal configuration, then
and
, so
. See Fig. 1(b).
(a) (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
, where
are 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 radius
with 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.
Figure 2. An instance of 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.
Table 1. Configurations of the 10 vertices instance generated randomly.
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.
Table 2. The length of Dubins path.
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 radius
goes up.
(a) (b) (c)
(a) Length 12.8122 with. (b) Length 15.6968 with
. (c) Length 25.2369 with
.
Figure 3. The tour of DTSP.
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