Optimal trajectories of curvature constrained motion in the Hamilton-Jacobi formulation. (English) Zbl 1307.49029
Summary: We propose a PDE approach for computing time-optimal trajectories of a vehicle which travels under certain curvature constraints. We derive a class of Hamilton-Jacobi equations which models such motions; it unifies two well-known vehicular models, the Dubins’ and Reeds-Shepp’s cars, and gives further generalizations. Numerical methods (finite difference for the Reeds-Shepp’s car and semi-Lagrangian for the Dubins’ car) are investigated for two-dimensional domains and surfaces.
MSC:
| 49M25 | Discrete approximations in optimal control |
| 49L20 | Dynamic programming in optimal control and differential games |
| 65L05 | Numerical methods for initial value problems involving ordinary differential equations |
References:
| [1] | Backer, J., Kirkpatrick, D.: Finding curvature-constrained paths that avoid polygonal obstacles. In: SCG ’07: Proceedings of the Twenty-Third Annual Symposium on Computational Geometry, pp. 66–73, New York, NY, ACM (2007). · Zbl 1221.68291 |
| [2] | Bakolas, E., Tsiotras, P.: The asymmetric sinistral/dextral Markov–Dubins problem. In: IEEE Conference on Decision and Control, Shanghai (2007) · Zbl 1223.49046 |
| [3] | Barles, G., Souganidis, P.E.: Convergence of approximation schemes for fully nonlinear second order equations. Asymptot. Anal. 4(3), 271–283 (1991) · Zbl 0729.65077 |
| [4] | Bardi, M., Capuzzo-Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton–Jacobi–Bellman Equations. Systems & Control: Foundations & Applications. Birkhäuser Boston Inc., Boston, MA. With appendices by Maurizio Falcone and Pierpaolo Soravia. (1997). · Zbl 0890.49011 |
| [5] | Bardi M., Falcone, M., Soravia, P.: Fully discrete schemes for the value function of pursuit–evasion games. Advances in dynamic games and applications (Geneva, 1992). In: Basar T., Haurie A. (eds.) Annals of the International Society of Dynamic Games, vol. 1, pp. 89–105. Birkhäuser Boston, Boston, MA (1994). · Zbl 0828.90147 |
| [6] | Bardi, M., Falcone, M., Soravia, P.: Numerical methods for pursuit–evasion games via viscosity solutions. Stochastic and differential games. In: Annals of the International Society of Dynamic Games, vol. 4, pp. 105–175. Birkhäuser Boston, Boston, MA (1999). · Zbl 1018.49027 |
| [7] | Barraquand, J., Latombe, J.-C.: Nonholonomic multibody mobile robots: controllability and motion planning in the presence of obstacles. Algorithmica 10(2), 121–155 (1993) · Zbl 0779.70003 · doi:10.1007/BF01891837 |
| [8] | Bellman, R.: Dynamic Programming. Princeton University Press, Princeton, NJ, Princeton Landmarks in Mathematics (2010). (Reprint of the 1957 edition, With a new introduction by Stuart Dreyfus 2010) · Zbl 1205.90002 |
| [9] | Bokanowski, O., Martin, S., Munos, R., Zidani, H.: An anti-diffusive scheme for viability problems. Appl. Numer. Math. 56(9), 1147–1162 (2006) · Zbl 1098.65073 · doi:10.1016/j.apnum.2006.03.004 |
| [10] | Bokanowski, O., Forcadel, N., Zidani, H.: Reachability and minimal times for state constrained nonlinear problems without any controllability assumption. SIAM J. Control Optim. 48(7), 4292–4316 (2010) · Zbl 1214.49025 · doi:10.1137/090762075 |
| [11] | Cardaliaguet, P., Quincampoix, M., Saint-Pierre, P.: Optimal times for constrained nonlinear control problems without local controllability. Appl. Math. Optim. 36(1), 21–42 (1997) · Zbl 0884.49002 |
| [12] | Cardaliaguet, P., Quincampoix, M., Saint-Pierre, P.: Numerical schemes for discontinuous value functions of optimal control. Set-Valued Anal. 8(1–2), 111–126 (2000) · Zbl 0988.49016 · doi:10.1023/A:1008774508738 |
| [13] | Chen, G.-Q., Su, B.: On global discontinuous solutions of Hamilton–Jacobi equations. C. R. Math. 334(2), 113–118 (2002) · Zbl 1002.35029 · doi:10.1016/S1631-073X(02)02228-8 |
| [14] | Chen, Y., Shu, C.-W.: A discontinuous galerkin finite element method for directly solving the Hamilton–Jacobi equations. J. Comput. Phys. 223(1), 398–415 (2007) · Zbl 1124.65090 · doi:10.1016/j.jcp.2006.09.012 |
| [15] | Chitsaz, H., LaValle, S.M.: Time-optimal paths for a Dubins airplane. In: Proceedings IEEE Conference Decision and Control (2007) |
| [16] | Chitour, Y., Sigalotti, M.: Dubins problem on surfaces. In: IEEE Conference on Decision and Control, Seville (2005) · Zbl 1090.53042 |
| [17] | Crandall, M.G., Pierre-Louis, L.: Viscosity solutions of Hamilton–Jacobi equations. Trans. Am. Math. Soc. 277(1), 1–42 (1983) · Zbl 0599.35024 · doi:10.1090/S0002-9947-1983-0690039-8 |
| [18] | Crandall, M.G., Pierre-Louis, L.: Two approximations of solutions of Hamilton–Jacobi equations. Math. Comp. 43(167), 1–19 (1984) · Zbl 0557.65066 · doi:10.1090/S0025-5718-1984-0744921-8 |
| [19] | Cowlagi, R.V., Tsiotras, P.: Existence and synthesis of curvature-bounded paths inside nonuniform rectangular channels. In: Proceedings of the 2010 American Control Conference, Baltimore, MD (2010). |
| [20] | 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(3), 497–516 (1957) · Zbl 0098.35401 · doi:10.2307/2372560 |
| [21] | Falcone, M.: Fast marching methods for front propagation. Lecture notes at ”Introduction to Numerical Methods for Moving Boundaries”, November (2007). |
| [22] | Falcone, M., Ferretti, R.: Semi-lagrangian schemes for Hamilton–Jacobi equations, discrete representation formulae and godunov methods. J. Comput. Phys. 175(2), 559–575 (2002) · Zbl 1007.65060 · doi:10.1006/jcph.2001.6954 |
| [23] | Gonzalez, R., Rofman, E.: On deterministic control problems: an approximation procedure for the optimal cost i. the stationary problem. SIAM J. Control Optim. 23(2), 242–266 (1985) · Zbl 0563.49024 · doi:10.1137/0323018 |
| [24] | Giga, Y., Sato, M.-H.: A level set approach to semicontinuous viscosity solutions for Cauchy problems. Commun. Partial Differ. Equ. 26(5–6), 813–839 (2001) · Zbl 1005.49025 · doi:10.1081/PDE-100002379 |
| [25] | Hu, C., Shu, C.-W.: A discontinuous galerkin finite element method for Hamilton-Jacobi equations. SIAM J. Sci. Comput. 21, 666–690 (1999) · Zbl 0946.65090 · doi:10.1137/S1064827598337282 |
| [26] | Ishii, H.: Perron’s method for Hamilton–Jacobi equations. Duke Math. J. 55(2), 369–384 (1987) · Zbl 0697.35030 · doi:10.1215/S0012-7094-87-05521-9 |
| [27] | Jacobs, P., Canny, J.: Planning Smooth Paths for Mobile Robots, pp. 271–342. Kluwer Academic, Norwell, MA (1992). · Zbl 0798.70002 |
| [28] | Kao, C.Y., Osher, S., Qian, J.: Lax–Friedrichs sweeping scheme for static Hamilton–Jacobi equations. J. Comput. Phys. 196(1), 367–391 (2004) · Zbl 1053.65088 · doi:10.1016/j.jcp.2003.11.007 |
| [29] | Kao, C.-Y., Osher, S., Tsai, Y.-H.: Fast sweeping methods for static Hamilton–Jacobi equations. SIAM J. Numer. Anal. 42(6), 2612–2632 (2004) · Zbl 1090.35016 · doi:10.1137/S0036142902419600 |
| [30] | Konkimalla, P., Lavalle S.M.: Efficient computation of optimal navigation functions for nonholonomic planning. In: Proceedings of First IEEE Int’l Workshop on Robot Motion and, Control, pp. 187–192 (1999). |
| [31] | Kumar, A., Vladimirsky, A.: An efficient method for multiobjective optimal control and optimal control subject to integral constraints. J. Comput. Math. 28(4), 517–551 (2010) · Zbl 1240.90345 |
| [32] | LaValle, S. M.: Planning Algorithms. Cambridge University Press, Cambridge, U.K. http://planning.cs.uiuc.edu/ (2006) · Zbl 1100.68108 |
| [33] | Laumond, J.-P., Jacobs, P.E., Taix, M., Murray, R.M.: A motion planner for nonholonomic mobile robots. IEEE Trans. Robot. Autom. 10(5), 577–593 (1994) · doi:10.1109/70.326564 |
| [34] | Lygeros, J., Pappas, G.J., Sastry, S.: An Introduction to Hybrid System Modeling, Analysis, and Control. Preprints of the First Nonlinear Control Network Pedagogical School, Athens, Greece (1999) |
| [35] | Markov, A.A.: Some examples of the solution of a special kind of problem on greatest and least quantities, (in russian). Soobshch. Karkovsk. Mat. Obshch 1, 250–276 (1887) |
| [36] | Margellos, K., Lygeros, J.: Hamilton–Jacobi formulation for reach–avoid differential games. IEEE Trans. Autom. Control 56(8), 1849–1861 (2011) · Zbl 1368.49044 · doi:10.1109/TAC.2011.2105730 |
| [37] | Oberman, A.M.: Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton–Jacobi equations and free boundary problems. SIAM J. Numer. Anal 44(2):879–895 (electronic) (2006). · Zbl 1124.65103 |
| [38] | Patsko, V.S., Turova, V.L.: Numerical study of the ”homocidal chauffeur” differential game with the reinforced pursuer. Game Theory Appl. 12, 123–152 (2007) · Zbl 1133.91326 |
| [39] | Patsko, V.S., Turova, V.L.: From Dubins’ car to Reeds and Shepp’s mobile robot. Comput. Vis. Sci. 12, 345–364 (2009) · Zbl 1216.49035 · doi:10.1007/s00791-008-0109-x |
| [40] | 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 |
| [41] | Reif, J.H., Hongyan, W.: Nonuniform discretization for kinodynamic motion planning and its applications. SIAM J. Comput. 30(1), 161–190 (2000) · Zbl 0959.68139 · doi:10.1137/S0097539798331975 |
| [42] | Rouy, E., Tourin, A.: A viscosity solutions approach to shape-from-shading. SIAM J. Numer. Anal. 29(3), 867–884 (1992) · Zbl 0754.65069 · doi:10.1137/0729053 |
| [43] | Saint-Pierre, P.: Approximation of the viability kernel. Appl. Math. Optim 29(2), 187–209 (1994) · Zbl 0790.65081 · doi:10.1007/BF01204182 |
| [44] | Sethian, J.A.: A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. 93, 1591–1595 (1995) · Zbl 0852.65055 · doi:10.1073/pnas.93.4.1591 |
| [45] | Sonneborn, L., Van Vleck, F.: The bang-bang principle for linear control systems. SIAM J. Control 2, 151–159 (1965) · Zbl 0196.46702 |
| [46] | Soueres, P., Laumond, J.-P.: Shortest paths synthesis for a car-like robot. IEEE Trans. Autom. Control 41(5), 672–688 (1996) · Zbl 0864.93076 · doi:10.1109/9.489204 |
| [47] | Sussmann, H.J., Tang, G.: Shortest paths for the Reeds–Shepp car: a worked out example of the use of geometric techniques in nonlinear optimal control, pp. 91–10. Technical report, SYCON, Report (1991). |
| [48] | Sussmann, H.: The Markov–Dubins problem with angular acceleration control. In: IEEE Conference on Decision and Control, San Diego (1997) |
| [49] | Takei, R., Tsai, R., Shen, H., Landa, Y.: A practical path-planning algorithm for a vehicle with a constrained turning radius: a Hamilton–Jacobi approach. In: American Control Conference, 2010. ACC ’10, vol. 7. Montreal, QC (2010). |
| [50] | Tsai, Y.-H.R., Cheng, L.-T., Osher, S., Zhao, H.-K.: Fast sweeping algorithms for a class of Hamilton–Jacobi equations. SIAM J. Numer. Anal. 41(2):673–694 (electronic), (2003). · Zbl 1049.35020 |
| [51] | Tsai, Y.-H. R., Giga, Y., Osher, S.: A level set approach for computing discontinuous solutions of Hamilton–Jacobi equations. Math. Comput. 72(241):159–181 (electronic), (2003). · Zbl 1013.65088 |
| [52] | Tsitsiklis, J.N.: Efficient algorithms for globally optimal trajectories. IEEE Trans. Autom. Control 40(9), 1528–1538 (1995) · Zbl 0831.93028 · doi:10.1109/9.412624 |
| [53] | Wang, H., Agarwal, P.K.: Approximation algorithms for curvature-constrained shortest paths. In: SODA ’96: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 409–418. Philadelphia, PA, USA (1996). · Zbl 0847.68110 |
| [54] | Zhao, H.: A fast sweeping methog for eikonal equations. Math. Comput. 74(250), 603–627 (2004) · Zbl 1070.65113 · doi:10.1090/S0025-5718-04-01678-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
