Skip to main content
SpringerLink
Log in

Set-Valued Numerical Analysis for Optimal Control and Differential Games

  • Chapter
Stochastic and Differential Games

Part of the book series: Annals of the International Society of Dynamic Games ((AISDG,volume 4))

Abstract

This chapter deals with theoretical and numerical results for solving qualitative and quantitative control and differential game problems. These questions are treated in the framework of set-valued analysis and viability theory. In a way, this approach is rather well adapted to look at these several problems with a unified point of view. The idea is to characterize the value function as a viability kernel instead of solving a Hamilton—Jacobi—Bellmann equation. This allows us to easily take into account state constraints without any controllability assumptions on the dynamic, neither at the boundary of targets, nor at the boundary of the constraint set. In the case of two-player differential games, the value function is characterized as a discriminating kernel. This allows dealing with a large class of systems with minimal regularity and convexity assumptions. Rigorous proofs of the convergence, including irregular cases, and completely explicit algorithms are provided.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alziary de Roquefort (1991) Jeux différentiels et approximation numérique de fonctions valeur. RAIRO Math. Model. Numer. Anal. 25, pp. 517–560.

    MathSciNet  MATH  Google Scholar 

  2. Aubin J.-P. and Cellina A. (1984) Differential Inclusions, Springer-Verlag, Berlin.

    Book  MATH  Google Scholar 

  3. Aubin J.-P. and Frankowska H. (1992) Set-Valued Analysis, Birkhaüser, Boston.

    Google Scholar 

  4. Aubin J.-P. (1992) Viability Theory, Birkhaüser, Boston.

    Google Scholar 

  5. Byrnes C. I. and Isidori A. (1988) Local stabilization of minimum-phase nonlinear systems. Syst. Contr. Let. Vol. 11, pp. 9–17.

    Article  MathSciNet  MATH  Google Scholar 

  6. Bardi M. (1989) A boundary value problem for the minimum time function. SIAM J. Control and Opti. 26, pp. 776–785.

    Article  MathSciNet  Google Scholar 

  7. Bardi, M., Bottacin, S., and Falcone M. (1995) Convergence of discrete schemes for discontinuous value functions of pursuit-evasion games, New Trends in Dynamic Games and Applications, G.J. Olsder Ed., pp. 273–304, Birkaüser, Boston.

    Google Scholar 

  8. Bardi M., Falcone M., and Soravia P. (1993) Fully discrete schemes for the Value function of pursuit-evasion games, in T. Bagar and A. Haurie, Eds., Annals of Dynamic Games, Vol. 1, Birkaüser, Boston.

    Google Scholar 

  9. Bardi M. and Soravia P. (1990) Approximation of differential games of pursuit-evasion by discrete-time games, Differential games - Developments in modelling and computation, R.P. Hamalainen and H.K. Ethamo Eds., Lecture Note Control Inform Sci. 156, pp. 131–143, Springer.

    Google Scholar 

  10. Bardi M. and Soravia P. (1991) Hamilton-Jacobi Equations with singular boundary conditions on a free boundary and applications to differential games. Trans. American Math. Soc. 325(1), pp. 205–229.

    Article  MathSciNet  MATH  Google Scholar 

  11. Bardi M. and Staicu V. (1993) The Bellman equation for time-optimal control of noncontrollable, Nonlinear systems Acta Applic. Math. 31, pp. 201–223.

    Article  MathSciNet  MATH  Google Scholar 

  12. Barles G. and Perthame B. (1988) Exit time problems in optimal control and vanishing viscosity method. SIAM J. Control and Opti. 26, pp. 1133–1148.

    Article  MathSciNet  MATH  Google Scholar 

  13. Barles G. and Souganidis P.E. (1991) Convergence of approximation schemes for fully non-linear systems. Asymptotic Anal. 4, pp. 271–283.

    MathSciNet  MATH  Google Scholar 

  14. Barles G. (1993) Discontinuous viscosity solutions of first-order Hamilton—Jacobi Equations: A guided visit. Nonlinear Analysis, Theory Methods and Appl. 9,pp. 1123–1134.

    Article  MathSciNet  Google Scholar 

  15. Barron E. and Jensen R. (1992) Optimal control and semicontinuous viscosity solutions. Proc. American Math. Soc. 113, pp. 397–402.

    Article  MathSciNet  Google Scholar 

  16. Bernhard P. (1976) Commande Optimale, decentralisation, et jeux dynamiques. Dunod.

    Google Scholar 

  17. Bernhard P. (1979) Contribution à l’étude des jeux différentiels à some nulle et information parfaite. Thèse Université de Paris VI.

    Google Scholar 

  18. Bernhard P. (1988) Differential games, in Systems and Control Encyclopedia,Theory Technology Application, M.G. Singh, Ed., Pergamon Press.

    Google Scholar 

  19. Bernhard P. (1990) A simple game with a singular focal line. J. of Optimization Theory and Appl. 64(2),pp. 419–428.

    Article  MathSciNet  MATH  Google Scholar 

  20. Bernhard P. and Larrouturou B. (1989) Etude de la barrière pour un problème de fuite optimale dans le plan. preprint Rapport de recherche INRIA.

    Google Scholar 

  21. Breakwell J.V. (1977) Zero-sum differential games with terminal payoff. In Differential Game and Applications,Hagedorn P., Knobloch H.W., and Olsder G.H., Eds., Lecture Notes in Control and Information Sciences Vol. 3, Springer Verlag, Berlin.

    Google Scholar 

  22. Byrnes C.I. & Isidori A. (1990) Régulation asymptotique de Systèmes non Linéaires. Comptes-Rendus de l’Académie des Sciences Paris, 309, pp. 527–530, Paris.

    MathSciNet  Google Scholar 

  23. Capuzzo-Dolcetta I. and Falcone M. (1989) Discrete dynamic programming and viscosity solutions of the Bellman Equation. Ann. I.H.P. Anal. Non Lin. 6, pp. 161–183.

    MathSciNet  MATH  Google Scholar 

  24. Caratheorody C. (1935) Calculus of Variations and Partial Differential Equations of the First Order (1989 Edition) Chelsea Publishing Company, New York.

    Google Scholar 

  25. Cardaliaguet P., Quincampoix M., and Saint-Pierre P. (1994) Some Algorithms for Differential Games with two Players and one Target. Mathematical Modelling and Numerical Analysis 28(4), pp. 441–461.

    MathSciNet  MATH  Google Scholar 

  26. Cardaliaguet P., Quincampoix M., and Saint-Pierre P. (1994) Temps optimaux pour des problèmes avec contraintes et sans contrôlabilité locale, Comptes Rendus de l’Académie des Sciences, T.318, s I, 1994, pp. 607–612.

    Google Scholar 

  27. Cardaliaguet P., Quincampoix M., and Saint-Pierre P. (1997) Optimal times for constrained non-linear control problems without local controllability. Applied Math. ê4 Optim. 35, pp. 1–22.

    MathSciNet  Google Scholar 

  28. Cardaliaguet P., Quincampoix M., and Saint-Pierre P. (1995) Differential games with state constraints Preprint. Cahiers de Mathématiques de la Décision. Université Paris IX Dauphine.

    Google Scholar 

  29. Cardaliaguet P. (1996) A differential game with two players and one target. SIAM J. Contr. Optim. 34(4), pp. 1441–1460.

    Article  MathSciNet  MATH  Google Scholar 

  30. Cardaliaguet P. (1997) Non smooth semi-permeable barriers, Isaacs equation and application to a differential game with one target and two players. Applied Math. and Optim. 36, pp. 125–145.

    MathSciNet  MATH  Google Scholar 

  31. Cardaliaguet P. (in preparation) Direct Construction of Generalized Motion of a Front Moving along its Normal Direction.

    Google Scholar 

  32. Cardaliaguet P. (in preparation) Regularity Results for Discontinuous Value Functions of Control Problems and Convergence Rates of their Approximations.

    Google Scholar 

  33. Chentsov A.G. (1976) On a Game Problem of Converging at a Given Instant of Time. Math USSR Sbornik 20(3), pp. 353–376.

    Google Scholar 

  34. Chentsov A.G. (1978) An Iterative Program Construction for Differential Games with Fixed Termination Time. Soviet Math Doklady 19(3), pp. 559–562.

    MATH  Google Scholar 

  35. Colombo G. and Krivan V. (1993) A Viability algorithm. J. Diff. Equations 102, pp. 236–243

    Article  MathSciNet  MATH  Google Scholar 

  36. Crandall M.G. and Lions P.L. (1983) Viscosity solutions of Hamilton-Jacobi equations. Trans. Amer. Math. Soc. 277, pp. 1–42.

    Article  MathSciNet  MATH  Google Scholar 

  37. Doyen L. and Saint-Pierre P. (1995) Scale of viability and minimal time of crisis. Set-Valued Analysis 5, pp. 227–245.

    Article  MathSciNet  Google Scholar 

  38. Elliot N.J. and Kalton N.J. (1972) The existence of value in differential games of pursuit and evasion. J. Differential Equations 12, pp. 504–523.

    Article  MathSciNet  Google Scholar 

  39. Evans L.C. and Souganidis P.E. (1984) Differential games and representation formulas for solutions of Hamilton-Jacobi equations. Indiana Univ. Math. J. 33, pp. 773–797.

    Article  MathSciNet  MATH  Google Scholar 

  40. Frankowska H. (1987) L’équation d’Hamilton-Jacobi Contingente. Comptes-Rendus de l’Académie des Sciences 303, Série 1, pp. 733–736, Paris.

    MathSciNet  Google Scholar 

  41. Frankowska H. (1991) Lower semicontinuous solutions to HamiltonJacobi—Bellman equations. Proceedings of 30th CDC Conference, IEEE, Brighton, England.

    Google Scholar 

  42. Frankowska H. (1993) Lower semicontinuous solutions of HamiltonJacobi—Bellman equations. SIAM J. Control and Optimization 31(1), pp. 257–272.

    Article  MathSciNet  MATH  Google Scholar 

  43. Frankowska H. and Quincampoix M. (1991) Viability kernels of differential inclusions with constraints: Algorithm and applications. J. Math. of Syst. Est. and Control 1(3), pp. 371–388.

    MathSciNet  Google Scholar 

  44. Frankowska H. and Quincampoix M. (1991) Un algorithme déterminant les noyaux de viabilité pour les inclusions différentielles avec contraintes Comptes-Rendus de l’Académie des Sciences. Série I. Paris, t. 312, pp. 31–36.

    MathSciNet  MATH  Google Scholar 

  45. Frankowska H., Plascasz M., and Rzezuchowski T. (1995) Measurable Viability Theorem and Hamilton—Jacobi—Bellman Equations. J. Diff. Eqs. 116(2), pp. 265–305.

    Article  MATH  Google Scholar 

  46. Isidori A. (1995) Nonlinear control Systems, 2nd Ed. Springer-Verlag, Berlin.

    Book  MATH  Google Scholar 

  47. Isaacs R. (1965) Differential Games, Wiley, New York.

    MATH  Google Scholar 

  48. Krasovskii N.N. and Subbotin A.I. (1988) Game-Theorical Control Problems, Springer-Verlag, New York.

    Book  Google Scholar 

  49. Plaskacz S. (1993) Personal communication.

    Google Scholar 

  50. Pontryagin N.S. (1968) Linear Differential Games I and II, Soviet Math. Doklady 8(3 & 4), pp. 769–771; 910, 912.

    Google Scholar 

  51. Pourtallier O. and Tidball M. (1994) Approximation of the Value Function for a Class of Differential Games with Target, Preprint Volume to the Sixth International Symposium on Dynamic Games and Applications, St-Jovite, Québec, Canada.

    Google Scholar 

  52. Quincampoix M. (1991) Playable differential games. J. Math. Anal. Appl. 1(1), pp. 194–211.

    Article  MathSciNet  Google Scholar 

  53. Quincampoix M. (1992) Differential inclusions and target problems. SIAM J. Control and Optim. 30(2), pp. 324–335.

    Article  MathSciNet  MATH  Google Scholar 

  54. Quincampoix M. and Saint-Pierre P. (1995) An Algorithm for Viability Kernels in Holderian Case: Approximation by discrete dynamic systems. Summary in J. of Math. Syst. est. and Control 5(1), pp. 115–118.

    MathSciNet  MATH  Google Scholar 

  55. Roxin E. (1969) The axiomatic approach in differential games. J. Optim. Theory Appl. 3, pp. 153–163.

    Article  MathSciNet  MATH  Google Scholar 

  56. Rozyev I. and Subbotin A.I. (1988) Semicontinuous solutions of Hamilton—Jacobi equations. PMM U.S.S.R. 52(2), pp. 141–146.

    MathSciNet  MATH  Google Scholar 

  57. Saint-Pierre P. (1991) Viability of boundary of the viability kernel. J. Differential and Integral Eq. 4(3), pp. 1147–1153.

    MathSciNet  MATH  Google Scholar 

  58. Saint-Pierre P. (1994) Approximation of the viability kernel. Appl. Math. and Opt. 29, pp. 187–209.

    Article  MathSciNet  MATH  Google Scholar 

  59. Soner M.H. (1986) Optimal control problems with state space constraints. SIAM J. on Control and Optimization 24, pp. 552–562; 1110–1122.

    Article  MathSciNet  MATH  Google Scholar 

  60. Soravia P. (1993) Discontinuous viscosity solutions to Dirichlet problems for Hamilton—Jacobi equations with convex Hamiltonians. Commun. P.D.E. 18, pp. 1493–1514.

    Article  MathSciNet  MATH  Google Scholar 

  61. Subbotin A.I. (1993) Discontinuous solutions of a Diriclet type boundary value problem for first order partial differential equations. Russian J. Anal. Math. Model. 8, pp. 145–164.

    MathSciNet  MATH  Google Scholar 

  62. Subbotin A.I. (1991) Existence and uniqueness results for the Hamilton-Jacobi equations. Nonlinear Anal. T.M.A. 16, pp. 683–699.

    Article  MathSciNet  MATH  Google Scholar 

  63. Varaiya P. (1967) The existence of solution to a differential game. SIAM J. Control Optim. 5, pp. 153–162.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Centre de Recherche Viabilité, Jeux, Contrôle, France

    Pierre Cardaliaguet, Marc Quincampoix & Patrick Saint-Pierre

  2. CNRS ERS 664, University of Paris, Dauphine, France

    Pierre Cardaliaguet, Marc Quincampoix & Patrick Saint-Pierre

Authors
  1. Pierre Cardaliaguet
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marc Quincampoix
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Patrick Saint-Pierre
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dipartimento di Matematica Pura e Applicata, Università degli Studi di Padova, 35131, Padova, Italy

    Martino Bardi

  2. Department of Mathematics, University of Illinois, Chicago, IL, USA

    T. E. S. Raghavan

  3. Indian Statistical Institute, New Delhi, India

    T. Parthasarathy

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer Science+Business Media New York

About this chapter

Cite this chapter

Cardaliaguet, P., Quincampoix, M., Saint-Pierre, P. (1999). Set-Valued Numerical Analysis for Optimal Control and Differential Games. In: Bardi, M., Raghavan, T.E.S., Parthasarathy, T. (eds) Stochastic and Differential Games. Annals of the International Society of Dynamic Games, vol 4. Birkhäuser, Boston, MA. https://doi.org/10.1007/978-1-4612-1592-9_4

Download citation

  • DOI: https://doi.org/10.1007/978-1-4612-1592-9_4

  • Publisher Name: Birkhäuser, Boston, MA

  • Print ISBN: 978-1-4612-7208-3

  • Online ISBN: 978-1-4612-1592-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation