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:

(Li Dai)

(Zheng Xie)

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¹ 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⁵. 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⁸. 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 2001⁹ 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-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 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).

(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 , 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.

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.

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.

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)                              (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

1. M. Krein, A. Nudelman. The Markov Moment Problem and Extremal Problems. The American Mathematical Society, Providence, RI, 1977.
2. P. Jacobs and J. Canny. Planning smooth paths for mobile robots. Proceedings of the IEEE International Conference on Robotics and Automation, Scottsdale, AZ, May 1989.
3. P. Jacobs, J. Laum and M. Taix. Efficient motion planners for nonholonomic mobile robots. Proceedings of the IEEE/RSJ International Workshop on Intelligent Robots and Systems, Osaka, Japan, August 1991.
4. J. Barraqu and, J. C. Latombe. On nonholonomic mobile robots and optimal maneuvering. Proceedings of the Fourth International Symposium on Intelligent Control, Albany, NY, 1989.
5. J. T. Isaacs and J. P. Hespanha. Dubins traveling salesman problem with neighborhoods: a graph-based approach. Algorithms, 6(2013): 84-99.
6. B. Yuan, M. Orlowska and S. Sadiq. On the optimal robot routing problem in wireless sendor networks. IEEE Trans. Data Eng. 19(2007):1252-1261.
7. K. J. Obermeyer. Path planning for a UAV performing reconnaissance of static ground targets in terrain. Proceedings of the AIAA Conference on Guidance, Navigation, and Control, Chicago, Illinois, USA, August 2009: 10-13.
8. 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, 79 (1957) 497-516.
9. A. M. Shkel and V. Lumelsky. Classification of the Dubins set. Robotics and Autonomous Systems, 34(2001)179-202.
10. J. L. Ny, E. Frazzoli and E. Feron. The Curvature-constrained Traveling Salesman Problem for High Point Densities. Proceedings of the IEEE Conference on Decision and Control, New Orleans, Louisiana, USA, 12-14 December 2007:5985-5990.
11. K. Savla, E. Frazzoli and F. Bullo. Traveling salesperson problems for the Dubins vehicle. IEEETrans. Autom. Control 53(2008) 1378-1391.
12. X. Ma and D. Castanon. Receding Horizon Planning for Dubins Traveling Salesman Problems. Proceedings of the IEEE Conference on Decision and Control, San Diego, California, USA, 13–15December 2006; pp. 5453-5458.
13. S. Rathinam, R. Sengupta and S. Darbha. A resource allocation algorithm for multiple vehiclesystems with non-holnomic constraints. IEEE Trans. Autom. Sci. Eng. 4 (2007) 98–104.
14. L. N. Jerone, J. Eric and F. Emilio. On the Dubins Traveling Salesman Problem. IEEE Transactions on Automatic Control, 57(2012):265-270.
15. I. Pantelis and S. Tal. Motion planning algorithms for the Dubins Traveling Salesperson Problem. Automatica, 53(2015)247-255.
16. E. B. Sylvester, K. David and P. Valentin. Discrete Dubins Paths. Ar Xiv: 1211.2365v1 [cs.DM] 11 Nov 2012.