• Previous Article
    Necessary conditions for a weak minimum in optimal control problems with integral equations on a variable time interval
  • DCDS Home
  • This Issue
  • Next Article
    A semi-Lagrangian scheme for a degenerate second order mean field game system
September  2015, 35(9): 4293-4322. doi: 10.3934/dcds.2015.35.4293

Higher order discrete controllability and the approximation of the minimum time function

1. 

Università di Padova, Dipartimento di Matematica, via Trieste 63, 35121 Padova, Italy

Received  April 2014 Revised  October 2014 Published  April 2015

We give sufficient conditions to reach a target for a suitable discretization of a control affine nonlinear dynamics. Such conditions involve higher order Lie brackets of the vector fields driving the state and so the discretization method needs to be of a suitably high order as well. As a result, the discrete minimal time function is bounded by a fractional power of the distance to the target of the initial point. This allows to use methods based on Hamilton-Jacobi theory to prove the convergence of the solution of a fully discrete scheme to the (true) minimum time function, together with error estimates. Finally, we design an approximate suboptimal discrete feedback and provide an error estimate for the time to reach the target through the discrete dynamics generated by this feedback. Our results make use of ideas appearing for the first time in [3] and now extensively described in [12]. Numerical examples are presented.
Citation: Giovanni Colombo, Thuy T. T. Le. Higher order discrete controllability and the approximation of the minimum time function. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4293-4322. doi: 10.3934/dcds.2015.35.4293
References:
[1]

M. Bardi, A boundary value problem for the minimum-time function,, SIAM J. Control Optim., 27 (1989), 776. doi: 10.1137/0327041. Google Scholar

[2]

M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations,, Birkhäuser, (1997). doi: 10.1007/978-0-8176-4755-1. Google Scholar

[3]

M. Bardi and M. Falcone, An approximation scheme for the minimum time function,, SIAM J. Control Optim., 28 (1990), 950. doi: 10.1137/0328053. Google Scholar

[4]

M. Bardi and M. Falcone, Discrete approximation of the minimal time function for systems with regular optimal trajectories,, Analysis and optimization of systems (Antibes, 144 (1990), 103. doi: 10.1007/BFb0120033. Google Scholar

[5]

G. Barles and B. Perthame, Discontinuous solutions of deterministic optimal stopping time problems,, RAIRO Modél. Math. Anal. Numér., 21 (1987), 557. Google Scholar

[6]

P. Cannarsa and C. Sinestrari, Semiconcave Functions, Hamilton-Jacobi Equations, and Optimal Control,, Birkhäuser, (2004). Google Scholar

[7]

F. Clarke, Discontinuous Feedback and Nonlinear Systems,, Proc. IFAC Conf. Nonlinear Control (NOLCOS), (2010), 1. Google Scholar

[8]

F. H. Clarke, Yu. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory,, Springer, (1998). Google Scholar

[9]

M. Falcone, Numerical solution of Dynamic programming equations,, Appendix A in the volume M. Bardi and I. Capuzzo Dolcetta, (1997). Google Scholar

[10]

M. Falcone, Numerical methods for differential games based on partial differential equations,, Int. Game Theory Rev., 8 (2006), 231. doi: 10.1142/S0219198906000886. Google Scholar

[11]

M. Falcone and R. Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations,, Numer. Math., 67 (1994), 315. doi: 10.1007/s002110050031. Google Scholar

[12]

M. Falcone and R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations,, SIAM, (2014). doi: 10.1137/1.9781611973051. Google Scholar

[13]

H. Federer, Curvature measures,, Trans. Amer. Math. Soc., 93 (1959), 418. doi: 10.1090/S0002-9947-1959-0110078-1. Google Scholar

[14]

R. Ferretti, High-Order Approximations of Linear Control Systems via Runge-Kutta Schemes,, Computing, 58 (1997), 351. doi: 10.1007/BF02684347. Google Scholar

[15]

L. Grüne and P. E. Kloeden, Higher order numerical schemes for affinely controlled nonlinear systems,, Numer. Math., 89 (2001), 669. doi: 10.1007/s002110000279. Google Scholar

[16]

E. Hairer, S. P. Nørsett and G. Wanner, Solving Ordinary Differential Equations I,, Springer, (1993). Google Scholar

[17]

A. Marigonda, Second order conditions for the controllability of nonlinear systems with drift,, Commun. Pur. Appl. Anal., 5 (2006), 861. doi: 10.3934/cpaa.2006.5.861. Google Scholar

[18]

A. Marigonda and S. Rigo, Controllability of some nonlinear systems with drift via generalized curvature properties,, SIAM J. Control, 53 (2014), 434. doi: 10.1137/130920691. Google Scholar

[19]

C. Nour, R. J. Stern and J. Takche, Proximal smoothness and the exterior sphere condition,, J. Convex Anal., 16 (2009), 501. Google Scholar

[20]

B. Piccoli and H. Sussmann, Regular synthesis and sufficiency conditions for optimality,, SIAM J. Control Optim., 39 (2000), 359. doi: 10.1137/S0363012999322031. Google Scholar

[21]

P. Soravia, Estimates of convergence of fully discrete schemes for the Isaacs equation of pursuit-evasion differential games via maximum principle,, SIAM J. Control Optim., 36 (1998), 1. doi: 10.1137/S0363012995291865. Google Scholar

[22]

M. Valadier, Quelques problèmes d'entraînement unilateral en dimension finie. (French) [Some problems of unilateral dragging in finite dimensions], Sém. Anal. Convexe, 18 (1988). Google Scholar

show all references

References:
[1]

M. Bardi, A boundary value problem for the minimum-time function,, SIAM J. Control Optim., 27 (1989), 776. doi: 10.1137/0327041. Google Scholar

[2]

M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations,, Birkhäuser, (1997). doi: 10.1007/978-0-8176-4755-1. Google Scholar

[3]

M. Bardi and M. Falcone, An approximation scheme for the minimum time function,, SIAM J. Control Optim., 28 (1990), 950. doi: 10.1137/0328053. Google Scholar

[4]

M. Bardi and M. Falcone, Discrete approximation of the minimal time function for systems with regular optimal trajectories,, Analysis and optimization of systems (Antibes, 144 (1990), 103. doi: 10.1007/BFb0120033. Google Scholar

[5]

G. Barles and B. Perthame, Discontinuous solutions of deterministic optimal stopping time problems,, RAIRO Modél. Math. Anal. Numér., 21 (1987), 557. Google Scholar

[6]

P. Cannarsa and C. Sinestrari, Semiconcave Functions, Hamilton-Jacobi Equations, and Optimal Control,, Birkhäuser, (2004). Google Scholar

[7]

F. Clarke, Discontinuous Feedback and Nonlinear Systems,, Proc. IFAC Conf. Nonlinear Control (NOLCOS), (2010), 1. Google Scholar

[8]

F. H. Clarke, Yu. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory,, Springer, (1998). Google Scholar

[9]

M. Falcone, Numerical solution of Dynamic programming equations,, Appendix A in the volume M. Bardi and I. Capuzzo Dolcetta, (1997). Google Scholar

[10]

M. Falcone, Numerical methods for differential games based on partial differential equations,, Int. Game Theory Rev., 8 (2006), 231. doi: 10.1142/S0219198906000886. Google Scholar

[11]

M. Falcone and R. Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations,, Numer. Math., 67 (1994), 315. doi: 10.1007/s002110050031. Google Scholar

[12]

M. Falcone and R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations,, SIAM, (2014). doi: 10.1137/1.9781611973051. Google Scholar

[13]

H. Federer, Curvature measures,, Trans. Amer. Math. Soc., 93 (1959), 418. doi: 10.1090/S0002-9947-1959-0110078-1. Google Scholar

[14]

R. Ferretti, High-Order Approximations of Linear Control Systems via Runge-Kutta Schemes,, Computing, 58 (1997), 351. doi: 10.1007/BF02684347. Google Scholar

[15]

L. Grüne and P. E. Kloeden, Higher order numerical schemes for affinely controlled nonlinear systems,, Numer. Math., 89 (2001), 669. doi: 10.1007/s002110000279. Google Scholar

[16]

E. Hairer, S. P. Nørsett and G. Wanner, Solving Ordinary Differential Equations I,, Springer, (1993). Google Scholar

[17]

A. Marigonda, Second order conditions for the controllability of nonlinear systems with drift,, Commun. Pur. Appl. Anal., 5 (2006), 861. doi: 10.3934/cpaa.2006.5.861. Google Scholar

[18]

A. Marigonda and S. Rigo, Controllability of some nonlinear systems with drift via generalized curvature properties,, SIAM J. Control, 53 (2014), 434. doi: 10.1137/130920691. Google Scholar

[19]

C. Nour, R. J. Stern and J. Takche, Proximal smoothness and the exterior sphere condition,, J. Convex Anal., 16 (2009), 501. Google Scholar

[20]

B. Piccoli and H. Sussmann, Regular synthesis and sufficiency conditions for optimality,, SIAM J. Control Optim., 39 (2000), 359. doi: 10.1137/S0363012999322031. Google Scholar

[21]

P. Soravia, Estimates of convergence of fully discrete schemes for the Isaacs equation of pursuit-evasion differential games via maximum principle,, SIAM J. Control Optim., 36 (1998), 1. doi: 10.1137/S0363012995291865. Google Scholar

[22]

M. Valadier, Quelques problèmes d'entraînement unilateral en dimension finie. (French) [Some problems of unilateral dragging in finite dimensions], Sém. Anal. Convexe, 18 (1988). Google Scholar

[1]

Robert Baier, Thuy T. T. Le. Construction of the minimum time function for linear systems via higher-order set-valued methods. Mathematical Control & Related Fields, 2019, 9 (2) : 223-255. doi: 10.3934/mcrf.2019012

[2]

Eduardo Martínez. Higher-order variational calculus on Lie algebroids. Journal of Geometric Mechanics, 2015, 7 (1) : 81-108. doi: 10.3934/jgm.2015.7.81

[3]

Weidong Zhao, Jinlei Wang, Shige Peng. Error estimates of the $\theta$-scheme for backward stochastic differential equations. Discrete & Continuous Dynamical Systems - B, 2009, 12 (4) : 905-924. doi: 10.3934/dcdsb.2009.12.905

[4]

Leonardo Colombo, David Martín de Diego. Higher-order variational problems on lie groups and optimal control applications. Journal of Geometric Mechanics, 2014, 6 (4) : 451-478. doi: 10.3934/jgm.2014.6.451

[5]

Maike Schulte, Anton Arnold. Discrete transparent boundary conditions for the Schrodinger equation -- a compact higher order scheme. Kinetic & Related Models, 2008, 1 (1) : 101-125. doi: 10.3934/krm.2008.1.101

[6]

Xiaojie Wang. Weak error estimates of the exponential Euler scheme for semi-linear SPDEs without Malliavin calculus. Discrete & Continuous Dynamical Systems - A, 2016, 36 (1) : 481-497. doi: 10.3934/dcds.2016.36.481

[7]

Giulia Cavagnari, Antonio Marigonda. Measure-theoretic Lie brackets for nonsmooth vector fields. Discrete & Continuous Dynamical Systems - S, 2018, 11 (5) : 845-864. doi: 10.3934/dcdss.2018052

[8]

Mohamed Assellaou, Olivier Bokanowski, Hasnaa Zidani. Error estimates for second order Hamilton-Jacobi-Bellman equations. Approximation of probabilistic reachable sets. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 3933-3964. doi: 10.3934/dcds.2015.35.3933

[9]

Marina Ghisi, Massimo Gobbino. Hyperbolic--parabolic singular perturbation for mildly degenerate Kirchhoff equations: Global-in-time error estimates. Communications on Pure & Applied Analysis, 2009, 8 (4) : 1313-1332. doi: 10.3934/cpaa.2009.8.1313

[10]

Konstantinos Chrysafinos. Error estimates for time-discretizations for the velocity tracking problem for Navier-Stokes flows by penalty methods. Discrete & Continuous Dynamical Systems - B, 2006, 6 (5) : 1077-1096. doi: 10.3934/dcdsb.2006.6.1077

[11]

Svetlana Matculevich, Pekka Neittaanmäki, Sergey Repin. A posteriori error estimates for time-dependent reaction-diffusion problems based on the Payne--Weinberger inequality. Discrete & Continuous Dynamical Systems - A, 2015, 35 (6) : 2659-2677. doi: 10.3934/dcds.2015.35.2659

[12]

Denis R. Akhmetov, Renato Spigler. $L^1$-estimates for the higher-order derivatives of solutions to parabolic equations subject to initial values of bounded total variation. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1051-1074. doi: 10.3934/cpaa.2007.6.1051

[13]

E. Fossas, J. M. Olm. Galerkin method and approximate tracking in a non-minimum phase bilinear system. Discrete & Continuous Dynamical Systems - B, 2007, 7 (1) : 53-76. doi: 10.3934/dcdsb.2007.7.53

[14]

Giovanni Colombo, Khai T. Nguyen. On the minimum time function around the origin. Mathematical Control & Related Fields, 2013, 3 (1) : 51-82. doi: 10.3934/mcrf.2013.3.51

[15]

Horst Osberger. Long-time behavior of a fully discrete Lagrangian scheme for a family of fourth order equations. Discrete & Continuous Dynamical Systems - A, 2017, 37 (1) : 405-434. doi: 10.3934/dcds.2017017

[16]

Ricardo Rosa. Approximate inertial manifolds of exponential order. Discrete & Continuous Dynamical Systems - A, 1995, 1 (3) : 421-448. doi: 10.3934/dcds.1995.1.421

[17]

Ming Su, Arne Winterhof. Hamming correlation of higher order. Advances in Mathematics of Communications, 2018, 12 (3) : 505-513. doi: 10.3934/amc.2018029

[18]

Simão P. S. Santos, Natália Martins, Delfim F. M. Torres. Noether currents for higher-order variational problems of Herglotz type with time delay. Discrete & Continuous Dynamical Systems - S, 2018, 11 (1) : 91-102. doi: 10.3934/dcdss.2018006

[19]

Saroj Panigrahi. Liapunov-type integral inequalities for higher order dynamic equations on time scales. Conference Publications, 2013, 2013 (special) : 629-641. doi: 10.3934/proc.2013.2013.629

[20]

Jean-Claude Saut, Jun-Ichi Segata. Asymptotic behavior in time of solution to the nonlinear Schrödinger equation with higher order anisotropic dispersion. Discrete & Continuous Dynamical Systems - A, 2019, 39 (1) : 219-239. doi: 10.3934/dcds.2019009

2018 Impact Factor: 1.143

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]