×

On reachability and minimum cost optimal control. (English) Zbl 1068.93011

Summary: Questions of reachability for continuous and hybrid systems can be formulated as optimal control or game theory problems, whose solution can be characterized using variants of the Hamilton-Jacobi-Bellman or Isaacs partial differential equations. The formal link between the solution to the partial differential equation and the reachability problem is usually established in the framework of viscosity solutions. This paper establishes such a link between reachability, viability and invariance problems and viscosity solutions of a special form of the Hamilton-Jacobi equation. This equation is developed to address optimal control problems where the cost function is the minimum of a function of the state over a specified horizon. The main advantage of the proposed approach is that the properties of the value function (uniform continuity) and the form of the partial differential equation (standard Hamilton-Jacobi form, continuity of the Hamiltonian and simple boundary conditions) make the numerical solution of the problem much simpler than other approaches proposed in the literature. This fact is demonstrated by applying our approach to a reachability problem that arises in flight control and using numerical tools to compute the solution.

MSC:

93B03 Attainable sets, reachability
93B30 System identification
93B12 Variable structure systems
49L25 Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games
93B40 Computational methods in systems theory (MSC2010)

Software:

Kronos; Uppaal
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alur, R.; Henzinger, T.; Lafferriere, G.; Pappas, G., Discrete abstractions of hybrid systems, Proceedings of the IEEE, 88, 7, 971-984 (2000)
[2] Alur, R., & Kurshan, R. (1996). Timing analysis in COSPAN. In R. Alur & T. A. Henzinger (Eds.), Hybrid systems III; Alur, R., & Kurshan, R. (1996). Timing analysis in COSPAN. In R. Alur & T. A. Henzinger (Eds.), Hybrid systems III
[3] Asarin, E.; Bournez, O.; Dang, T.; Maler, O.; Pnueli, A., Effective synthesis of switching controllers for linear systems, Proceedings of the IEEE, 88, 7, 1011-1025 (2000)
[4] Aubin, J.-P., Viability theory (1991), Birkhäuser: Birkhäuser Boston · Zbl 0755.93003
[5] Aubin, J.-P.; Lygeros, J.; Quincampoix, M.; Sastry, S.; Seube, N., Impulse differential inclusionsA viability approach to hybrid systems, IEEE Transactions on Automatic Control, 47, 1, 2-20 (2002) · Zbl 1364.49018
[6] Bardi, M.; Capuzzo-Dolcetta, I., Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman Equations (1997), Birkhäuser: Birkhäuser Basel · Zbl 0890.49011
[7] Barron, E., Differential games with maximum cost, Nonlinear analysis: Theory, methods & applications, 14, 11, 971-989 (1990) · Zbl 0708.90104
[8] Barron, E., Viscosity solutions and analysis in \(L^∞\), (Clarke, F.; Stern, R.; Sabidussi, G., Nonlinear analysis, differential equations and control. Nonlinear analysis, differential equations and control, Proceedings of the NATO Advanced Study Institute, NATO science series C: Mathematical and Physical Sciences, Vol. 528 (1999), Kluwer: Kluwer Boston) · Zbl 0973.49024
[9] Barron, E.; Ishii, H., The Bellman equation for minimizing the maximum cost, Nonlinear Analysis: Theory, Methods & Applications, 13, 9, 1067-1090 (1989) · Zbl 0691.49030
[10] Bengtsson, J., Larsen, K., Larsson, F., Petterson, P., & Yi, W. (1996). UPAAL: A tool suit for automatic verification of real-time systems. In Hybrid systems III; Bengtsson, J., Larsen, K., Larsson, F., Petterson, P., & Yi, W. (1996). UPAAL: A tool suit for automatic verification of real-time systems. In Hybrid systems III
[11] Botchkarev, O., & Tripakis, S. (2000). Verification of hybrid systems with linear differential inclusions using ellipsoidal approximations. In N. Lynch, B. H. Krogh (Eds.), Hybrid systems: Computation and control; Botchkarev, O., & Tripakis, S. (2000). Verification of hybrid systems with linear differential inclusions using ellipsoidal approximations. In N. Lynch, B. H. Krogh (Eds.), Hybrid systems: Computation and control · Zbl 1037.93510
[12] Cardaliaguet, P.; Quincampoix, M.; Saint-Pierre, P., Set-valued numerical analysis for optimal control and differential games, (Bardi, M.; Raghavan, T.; Parthasarathy, T., Stochastic and differential games: Theory and numerical methods. Stochastic and differential games: Theory and numerical methods, Annals of the International Society of Dynamic Games, Vol. 4 (1999), Birkhäuser: Birkhäuser Boston), 177-247 · Zbl 0982.91014
[13] Cardaliaguet, P.; Quincampoix, M.; Saint-Pierre, P., Numerical schemes for discontinuous value functions of optimal control, Set Valued Analysis, 8, 111-126 (2000) · Zbl 0988.49016
[14] Cardaliaguet, P.; Quincampoix, M.; Saint-Pierre, P., Pursuit differential games with state constraints, SIAM Journal of Control and Optimization, 39, 5, 1615-1632 (2001) · Zbl 1140.91320
[15] Chutinam, A., & Krogh, B. (1999). Verification of polyhedral-invariant hybrid automata using polygonal flow pipe approximations. In F. W. Vaandrager, J. H. van Schuppen (Eds.), Hybrid systems: Computation and control; Chutinam, A., & Krogh, B. (1999). Verification of polyhedral-invariant hybrid automata using polygonal flow pipe approximations. In F. W. Vaandrager, J. H. van Schuppen (Eds.), Hybrid systems: Computation and control · Zbl 0954.93020
[16] Crandall, M.; Lions, P.-L., Viscosity solutions of Hamilton-Jacobi equations, Transactions of the American Mathematical Society, 277, 1, 1-42 (1983) · Zbl 0599.35024
[17] Daws, C., Olivero, A., Trypakis, S., & Yovine, S. (1996). The tool KRONOS. In R. Alur, T. Henzinger, E. Sontag (Eds.), Hybrid systems III; Daws, C., Olivero, A., Trypakis, S., & Yovine, S. (1996). The tool KRONOS. In R. Alur, T. Henzinger, E. Sontag (Eds.), Hybrid systems III
[18] Evans, L., Partial differential equations (1998), American Mathematical Society: American Mathematical Society Providence, RI
[19] Evans, L.; Souganidis, P., Differential games and representation formulas for solutions of Hamilton-Jacobi-Isaacs equations, Indiana University Mathematics Journal, 33, 5, 773-797 (1984) · Zbl 1169.91317
[20] Fialho, I.; Georgiou, T., Worst case analysis of nonlinear systems, IEEE Transactions on Automatic Control, 44, 6, 1180-1197 (1999) · Zbl 0957.93022
[21] Flemming, W.; Soner, H., Controlled Markov processes and viscosity solutions (1993), Springer: Springer New York · Zbl 0773.60070
[22] Greenstreet, M., & Mitchell, I. (1998). Integrating projections. In S. Sastry, T. Henzinger (Eds.), Hybrid systems: Computation and control; Greenstreet, M., & Mitchell, I. (1998). Integrating projections. In S. Sastry, T. Henzinger (Eds.), Hybrid systems: Computation and control
[23] Henzinger, T. A., Ho, P. H., & Toi, H. W. (1995). A user guide to HYTECH. In E. Brinksma, W. Cleaveland, K. Larsen, T. Margaria, B. Steffen (Eds.), TACAS 95: Tools and algorithms for the construction and analysis of systems; Henzinger, T. A., Ho, P. H., & Toi, H. W. (1995). A user guide to HYTECH. In E. Brinksma, W. Cleaveland, K. Larsen, T. Margaria, B. Steffen (Eds.), TACAS 95: Tools and algorithms for the construction and analysis of systems
[24] Kurzhanski, A., & Varaiya, P. (2000). Ellipsoidal techniques for reachability analysis. In N. Lynch, & B. H. Krogh (Eds.), Hybrid systems: Computation and control; Kurzhanski, A., & Varaiya, P. (2000). Ellipsoidal techniques for reachability analysis. In N. Lynch, & B. H. Krogh (Eds.), Hybrid systems: Computation and control · Zbl 0962.93009
[25] Livadas, C.; Lygeros, J.; Lynch, N., High-level modeling and analysis of the traffic alert and collision avoidance system (TCAS), Proceedings of the IEEE, 88, 7, 926-948 (2000)
[26] Livadas, C., & Lynch, N. (1998). Formal verification of safety-critical hybrid systems. In S. Sastry, & T. Henzinger (Eds.), Hybrid systems: Computation and control; Livadas, C., & Lynch, N. (1998). Formal verification of safety-critical hybrid systems. In S. Sastry, & T. Henzinger (Eds.), Hybrid systems: Computation and control
[27] Lygeros, J. (2002). Reachability, viability and invariance: An approach based on minimum cost optimal control; Lygeros, J. (2002). Reachability, viability and invariance: An approach based on minimum cost optimal control
[28] Lygeros, J.; Godbole, D.; Sastry, S., Verified hybrid controllers for automated vehicles, IEEE Transactions on Automatic Control, 43, 4, 522-539 (1998) · Zbl 0904.90057
[29] Lygeros, J.; Tomlin, C.; Sastry, S., Controllers for reachability specifications for hybrid systems, Automatica, 35, 349-370 (1999) · Zbl 0943.93043
[30] Mitchell, I., Bayen, A., & Tomlin, C. (2001). Validating a Hamilton-Jacobi approximation to hybrid system reachable sets. In M. Di Benedetto, A. Sangiovanni-Vincentelli (Eds.), Hybrid systems: Computation and control; Mitchell, I., Bayen, A., & Tomlin, C. (2001). Validating a Hamilton-Jacobi approximation to hybrid system reachable sets. In M. Di Benedetto, A. Sangiovanni-Vincentelli (Eds.), Hybrid systems: Computation and control · Zbl 0996.93503
[31] Mitchell, I., Bayen, A., & Tomlin, C. A time-dependent Hamilton-Jacobi formulation of Reachable sets for continuous dynamic games. IEEE Transactions on Automatic Control; Mitchell, I., Bayen, A., & Tomlin, C. A time-dependent Hamilton-Jacobi formulation of Reachable sets for continuous dynamic games. IEEE Transactions on Automatic Control · Zbl 1366.91022
[32] Mitchell, I., & Tomlin, C. (2000). Level set methods for computation in hybrid systems. In N. Lynch, & B. H. Krogh (Eds.), Hybrid systems: Computation and control; Mitchell, I., & Tomlin, C. (2000). Level set methods for computation in hybrid systems. In N. Lynch, & B. H. Krogh (Eds.), Hybrid systems: Computation and control · Zbl 0952.93006
[33] Nuic, A. (2000). User manual for the base of aircraft dataBADArevision 3.3; Nuic, A. (2000). User manual for the base of aircraft dataBADArevision 3.3
[34] Oishi, M.; Tomlin, C.; Gopal, V.; Godbole, D., Addressing multiobjective control: Safety and performance through constrained optimization, (Di Benedetto, M.; Sangiovanni-Vincentelli, A., Hybrid systems: Computation and control. Hybrid systems: Computation and control, Lecture Notes in Computer Science, Vol. 2034 (2001), Springer: Springer Berlin), 459-472 · Zbl 0995.49501
[35] Osher, S.; Sethian, J., Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, 79, 12-49 (1988) · Zbl 0659.65132
[36] Quincampoix, M., & Serea, O.-S. (2002). A viability approach for optimal control with infimum cost; Quincampoix, M., & Serea, O.-S. (2002). A viability approach for optimal control with infimum cost · Zbl 1058.49004
[37] Sethian, J. A., Level set methods: Evolving interfaces in geometry, fluid mechanics, computer vision, and materials science (1996), Cambridge University Press: Cambridge University Press New York · Zbl 0859.76004
[38] Seube, N.; Moitie, R.; Leitmann, G., Viability analysis of an aircraft flight domain for take-off in a windshear, Mathematical and Computer Modelling, 36, 633-641 (2002) · Zbl 1032.76030
[39] Tomlin, C. (1998). Hybrid control of air traffic management systems; Tomlin, C. (1998). Hybrid control of air traffic management systems
[40] Tomlin, C.; Lygeros, J.; Sastry, S., A game theoretic approach to controller design for hybrid systems, Proceedings of the IEEE, 88, 7, 949-969 (2000)
[41] Tomlin, C.; Mitchell, I.; Ghosh, R., Safety verification of conflict resolution manoeuvres, IEEE Transactions on Intelligent Transportation Systems, 2, 2, 110-120 (2001)
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.