Curvature-constrained directional-cost paths in the plane. (English) Zbl 1259.49068

Chang, Alan J.; Brazil, Marcus; Rubinstein, J. Hyam; Thomas, Doreen A.

J. Glob. Optim. 53, No. 4, 663-681 (2012).

Summary: This paper looks at the problem of finding the minimum cost curvature-constrained path between two directed points where the cost at every point along the path depends on the instantaneous direction. This generalizes the results obtained by L. E. Dubins [Am. J. Math. 79, 497–516 (1957; Zbl 0098.35401)] for curvature-constrained paths of minimum length, commonly referred to as Dubins paths. We conclude that if the reciprocal of the directional-cost function is strictly polarly convex, then the forms of the optimal paths are of the same forms as Dubins paths. If we relax the strict polar convexity to weak polar convexity, then we show that there exists a Dubins path which is optimal. The results obtained can be applied to optimizing the development of underground mine networks, where the paths need to satisfy a curvature constraint and the cost of development of the tunnel depends on the direction due to the geological characteristics of the ground.

MSC:

49Q20	Variational problems in a geometric measure-theoretic setting
49K15	Optimality conditions for problems involving ordinary differential equations
49N90	Applications of optimal control and differential games

Keywords:

curvature constraint; Dubins’ paths; path optimization; directional cost; anisotropic velocity; Pontryagin’s minimum principle

Citations:

Zbl 0098.35401

References:

[1]	Boissonnat J.D., Cerezo A., Leblond J.: Shortest paths of bounded curvature in the plane. J. Intell. Rob. Syst. 11, 5–20 (1994) · Zbl 0858.49030 · doi:10.1007/BF01258291
[2]	Brazil M., Grossman P.A., Lee D.H., Rubinstein J.H., Thomas D.A., Wormald N.C.: Decline design in underground mines using constrained path optimisation. Trans. Inst. Min. Metall. A 117(2), 93–99 (2008)
[3]	Bui, X.N., Soueres, P., Boissonnat, J.D., Laumond, J.P.: The shortest path synthesis for non-holonomic robots moving forwards. INRIA, Nice-Sophia-Antipolis, Research Report 2153, (1993)
[4]	Dolinskaya, I.S.: Optimal path finding in direction, location and time dependent environments. Ph.D. thesis, Industrial and operations engineering, The University of Michigan (2009)
[5]	Dubins L.E.: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am. J. Math 79, 497–516 (1957) · Zbl 0098.35401 · doi:10.2307/2372560
[6]	Gehring, K., Fuchs, M.: Quantification of rock mass influence on cuttability with roadheaders, 28th ITA (International Tunnelling Association) General assembly and World tunnel congress, Sydney, (2002)
[7]	Laubscher D.H.: A geomechanics classification system for the rating of rock mass in mine design. J. S. Atr. Inst. Min. Metal 90(10), 257–273 (1990)
[8]	McGee, T.G., Spry, S., Hedrick, J.K.: Optimal path planning in a constant wind with a bounded turning rate. In: Proceedings of the AIAA conference on guidance, navigation and control, Ketstone, Colorado (2005)
[9]	Pontryagin, L.S.: The mathematical theory of optimal processes. vol. 4, Interscience, Translation of a Russian book. (1962)
[10]	Reeds J.A., Shepp L.A.: Optimal paths for a car that goes both forwards and backwards. Pac. J. Math. 145(2), 367–393 (1990) · doi:10.2140/pjm.1990.145.367
[11]	Sanfelice, R.G., Frazzoli, E.: On the optimality of dubins paths across heterogeneous terrain. In: Egerstedt, M., Mishra, B. (eds.) Hybrid Systems: Computation and Control, vol. 4981 pp.457–470. Springer, Heidelberg (2008) · Zbl 1144.93355
[12]	Shkel A.M., Lumelsky V.: Classification of the dubins set. Rob. Auton. Syst. 34(4), 179–202 (2001) · Zbl 1013.68248 · doi:10.1016/S0921-8890(00)00127-5
[13]	Soueres P., Laumond J.P.: Shortest paths synthesis for a car-like robot. IEEE Trans. Automat. Contr. 41(5), 672–688 (1996) · Zbl 0864.93076 · doi:10.1109/9.489204