Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Journal of Scientific Computing
Erschienen in: Journal of Scientific Computing 2-3/2013

01.02.2013

Optimal Trajectories of Curvature Constrained Motion in the Hamilton–Jacobi Formulation

verfasst von: Ryo Takei, Richard Tsai

Erschienen in: Journal of Scientific Computing | Ausgabe 2-3/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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.
Vorheriger Artikel A Robust Reconstruction for Unstructured WENO Schemes
Nächster Artikel High Order Well-Balanced WENO Scheme for the Gas Dynamics Equations Under Gravitational Fields

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
We note that a similar problem laying railroad tracks that connect already existing tracks was considered by Markov [35].
 
2
Later, we demonstrate that, in practice, the Lipschitz continuity of \(f\) in with respect to space can be dropped.
 
3
We note that are several notions for discontinuous viscosity solutions [13, 24, 26, 51].
 
Literatur
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).
2.
Bakolas, E., Tsiotras, P.: The asymmetric sinistral/dextral Markov–Dubins problem. In: IEEE Conference on Decision and Control, Shanghai (2007)
3.
Barles, G., Souganidis, P.E.: Convergence of approximation schemes for fully nonlinear second order equations. Asymptot. Anal. 4(3), 271–283 (1991)MathSciNetMATH
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).
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).
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).
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)MathSciNetCrossRefMATH
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)
9.
Bokanowski, O., Martin, S., Munos, R., Zidani, H.: An anti-diffusive scheme for viability problems. Appl. Numer. Math. 56(9), 1147–1162 (2006)MathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
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)MathSciNetMATH
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)MathSciNetCrossRefMATH
13.
Chen, G.-Q., Su, B.: On global discontinuous solutions of Hamilton–Jacobi equations. C. R. Math. 334(2), 113–118 (2002)MathSciNetMATH
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)MathSciNetCrossRef
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)
17.
Crandall, M.G., Pierre-Louis, L.: Viscosity solutions of Hamilton–Jacobi equations. Trans. Am. Math. Soc. 277(1), 1–42 (1983)CrossRefMATH
18.
Crandall, M.G., Pierre-Louis, L.: Two approximations of solutions of Hamilton–Jacobi equations. Math. Comp. 43(167), 1–19 (1984)MathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
25.
Hu, C., Shu, C.-W.: A discontinuous galerkin finite element method for Hamilton-Jacobi equations. SIAM J. Sci. Comput. 21, 666–690 (1999)MathSciNetCrossRefMATH
26.
27.
Jacobs, P., Canny, J.: Planning Smooth Paths for Mobile Robots, pp. 271–342. Kluwer Academic, Norwell, MA (1992).
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)MathSciNetCrossRefMATH
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)MathSciNetCrossRef
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)MathSciNetMATH
32.
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)CrossRef
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)MathSciNetCrossRef
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).
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)MathSciNet
39.
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)MathSciNetCrossRef
41.
Reif, J.H., Hongyan, W.: Nonuniform discretization for kinodynamic motion planning and its applications. SIAM J. Comput. 30(1), 161–190 (2000)MathSciNetCrossRefMATH
42.
43.
44.
Sethian, J.A.: A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. 93, 1591–1595 (1995)MathSciNetCrossRef
45.
Sonneborn, L., Van Vleck, F.: The bang-bang principle for linear control systems. SIAM J. Control 2, 151–159 (1965)
46.
Soueres, P., Laumond, J.-P.: Shortest paths synthesis for a car-like robot. IEEE Trans. Autom. Control 41(5), 672–688 (1996)MathSciNetCrossRefMATH
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).
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).
52.
Tsitsiklis, J.N.: Efficient algorithms for globally optimal trajectories. IEEE Trans. Autom. Control 40(9), 1528–1538 (1995)MathSciNetCrossRefMATH
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).
54.
Zhao, H.: A fast sweeping methog for eikonal equations. Math. Comput. 74(250), 603–627 (2004)CrossRef
Metadaten
Titel
Optimal Trajectories of Curvature Constrained Motion in the Hamilton–Jacobi Formulation
verfasst von
Ryo Takei
Richard Tsai
Publikationsdatum
01.02.2013
Verlag
Springer US
Erschienen in
Journal of Scientific Computing / Ausgabe 2-3/2013
Print ISSN: 0885-7474
Elektronische ISSN: 1573-7691
DOI
https://doi.org/10.1007/s10915-012-9671-y

Weitere Artikel der Ausgabe 2-3/2013

Journal of Scientific Computing 2-3/2013 Zur Ausgabe

OriginalPaper

Error Forgetting of Bregman Iteration

Preface

Preface

OriginalPaper

Statistical Density Estimation Using Threshold Dynamics for Geometric Motion

OriginalPaper

Higher-Order TV Methods—Enhancement via Bregman Iteration

OriginalPaper

Negative-Order Norm Estimates for Nonlinear Hyperbolic Conservation Laws

OriginalPaper

A Multiscale Method for Highly Oscillatory Dynamical Systems Using a Poincaré Map Type Technique