Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Dijkstra-Type Algorithm for Dynamic Games

  • Published:
Dynamic Games and Applications Aims and scope Submit manuscript

Abstract

We study zero-sum dynamic games with deterministic transitions and alternating moves of the players. Player 1 aims at reaching a terminal set and minimizing a possibly discounted running and final cost. We propose and analyze an algorithm that computes the value function of these games extending Dijkstra’s algorithm for shortest paths on graphs. We also show the connection of these games with numerical schemes for differential games of pursuit-evasion type, if the grid is adapted to the dynamical system. Under suitable conditions, we prove the convergence of the value of the discrete game to the value of the differential game as the step of approximation tends to zero.

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

Access this article

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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alfaro T, Henzinger T, Kupferman O (2007) Concurrent reachability games. Theor Comput Sci 386:188–217

    Article  MathSciNet  MATH  Google Scholar 

  2. Andrews J, Vladimirsky A (2014) Deterministic control of randomly-terminated processes. Interfaces Free Bound 16:1–40

    Article  MathSciNet  MATH  Google Scholar 

  3. Bardi M, Capuzzo-Dolcetta I (1997) Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations. Birkhäuser Boston Inc, Boston

    Book  MATH  Google Scholar 

  4. Bardi M, Bottacin S, Falcone M (1995) Convergence of discrete schemes for discontinuous value functions of pursuit-evasion games. In: New trends in dynamic games and applications. Ann. Internat. Soc. Dynam. Games, 3, Birkhäuser Boston, pp 273–304

  5. Bardi M, Falcone M and Soravia P (1994) Fully discrete schemes for the value function of pursuit-evasion games. In: Advances in dynamic games and applications. Ann. Internat. Soc. Dynam. Games, 1, Birkhäuser Boston, pp 89–105

  6. Bardi M, Falcone M, Soravia P (1999) Numerical methods for pursuit-evasion games via viscosity solutions. In: Bardi M, Parthasarathy T, Raghavan e TES (eds) Stochastic and differential games: theory and numerical methods. Ann. Internat. Soc. Dynam. Games, 4. Birkhäuser, Boston, pp 105–175

  7. Bardi M, Soravia P (1991) Approximation of differential games of pursuit-evasion by discrete-time games. In: Differential games-developments in modelling and computation, Lecture Notes in Control and Inform. Sci., 156, Springer, pp 131–143

  8. Bardi M, Soravia P (1994) A comparison result for Hamilton-Jacobi equations and applications to some differential games lacking controllability. Funkcial Ekvac 37:19–43

    MathSciNet  MATH  Google Scholar 

  9. Bardi M, Terrone G (2013) On the homogenization of some non-coercive Hamilton-Jacobi-Isaacs equations. Commun Pure Appl Anal 12:207–236

    Article  MathSciNet  MATH  Google Scholar 

  10. Bertsekas D (2001) Dynamic programming and optimal control, 2nd edn, vol II. Athena Scientific, Boston

    Google Scholar 

  11. Bertsekas D (2015) Robust shortest path planning and semicontractive dynamic programming, Report LIDS-2915

  12. Cacace S, Cristiani E, Falcone M (2014) Can local single-pass methods solve any stationary Hamilton-Jacobi equation? SIAM J Sci Comput 36:A570–A587

    Article  MathSciNet  MATH  Google Scholar 

  13. Cacace S, Cristiani E, Falcone M, Picarelli A (2012) A patchy dynamic programming scheme for a class of Hamilton–Jacobi–Bellman equations. SIAM J Sci Comput 34:A2625–A2649

    Article  MathSciNet  MATH  Google Scholar 

  14. Cardaliaguet P, Quincampoix M, Saint-Pierre P (1999) Set-valued numerical analysis for optimal control and differential games. In: Bardi M, Parthasarathy T, Raghavan e TES (eds) Stochastic and differential games: theory and numerical methods. Ann. Internat. Soc. Dynam. Games. Birkhäuser, Boston, pp 177–247

  15. Cristiani E (2009) A fast marching method for Hamilton–Jacobi equations modeling monotone front propagations. J Sci Comput 39:189–205

    Article  MathSciNet  MATH  Google Scholar 

  16. Cristiani E, Falcone M (2006) A fast marching method for pursuit-evasion games. In: Communications to SIMAI congress 1. doi:10.1685/CSC06059

  17. Cristiani E, Falcone M (2009) Fully-discrete schemes for the value function of pursuit-evasion games with state constraints. In: Advances in dynamic games and their applications, Ann. Internat. Soc. Dynam. Games, 10. Birkhäuser Boston, pp 177–206

  18. Dijkstra EW (1959) A note on two problems in connection with graphs. Numer Math 1:269–271

    Article  MathSciNet  MATH  Google Scholar 

  19. Falcone M, Ferretti R (2014) Semi-Lagrangian approximations schemes for linear and Hamilton-Jacobi equations. SIAM, Philadelphia

    MATH  Google Scholar 

  20. Filar JA, Raghavan TES (1991) Algorithms for stochastic games—A survey. Z Oper Res 35:437–472

    MathSciNet  MATH  Google Scholar 

  21. Filar JA, Vrieze OJ (1996) Competitive Markov decision processes. Springer, Berlin

    Book  MATH  Google Scholar 

  22. Fredman ML, Tarjan RE (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J Assoc Comput Mach 34:596–615

    Article  MathSciNet  Google Scholar 

  23. Grüne L, Junge O (2008) Global optimal control of perturbed systems. J Optim Theory Appl 136:411–429

    Article  MathSciNet  MATH  Google Scholar 

  24. Kushner HJ (2004) The Gauss-Seidel numerical procedure for Markov stochastic games. IEEE Trans Autom Control 49:1779–1784

    Article  MathSciNet  Google Scholar 

  25. LaValle SM (2006) Planning algorithms. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

  26. McEneaney WM (2006) Max-plus methods for nonlinear control and estimation. Birkhäuser Boston Inc, Boston

    MATH  Google Scholar 

  27. Parthasarathy T, Raghavan TES (1981) An orderfield property for stochastic games when one player controls transition probabilities. J Optim Theory Appl 33:375–392

    Article  MathSciNet  MATH  Google Scholar 

  28. Raghavan TES, Syed Z (2003) A policy-improvement type algorithm for solving zero-sum two-person stochastic games of perfect information. Math Program Ser A 95:513–532

    Article  MathSciNet  MATH  Google Scholar 

  29. Sethian JA (1996) A fast marching level set method for monotonically advancing fronts. Proc Nat Acad Sci USA 93:1591–1595

    Article  MathSciNet  MATH  Google Scholar 

  30. Sethian JA (1999) Level set methods and fast marching methods. Evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science, Second edn. Cambridge University Press, Cambridge

    MATH  Google Scholar 

  31. Sethian JA, Vladimirsky A (2003) Ordered upwind methods for static Hamilton–Jacobi equations: theory and algorithms. SIAM J Numer Anal 41:325–363

    Article  MathSciNet  MATH  Google Scholar 

  32. Shapley LS (1953) Stochastic games. Proc Nat Acad Sci USA 39:1095–1100

    Article  MathSciNet  MATH  Google Scholar 

  33. Sorin S (2002) A first course on zero-sum repeated games, Mathématiques & Applications, vol 37. Springer, Berlin

    Google Scholar 

  34. Tsitsiklis JN (1995) Efficient algorithms for globally optimal trajectories. IEEE Trans Autom Control 40:1528–1538

    Article  MathSciNet  MATH  Google Scholar 

  35. Vladimirsky A (2008) Label-setting methods for multimode stochastic shortest path problems on graphs. Math Oper Res 33:821–838

    Article  MathSciNet  MATH  Google Scholar 

  36. von Lossow M (2007) A min-max version of Dijkstra’s algorithm with application to perturbed optimal control problems. In: Proceedings of the 6th international congress on industrial and applied mathematics (ICIAM07), Proceedings of the applied mathematics and mechanics, vol 7, pp 4130027–4130028

Download references

Acknowledgments

We are very grateful to Alex Vladimirsky for many insightful remarks that helped us to improve the paper. We also thank an anonymous referee for several useful comments and suggestions.

Author information

Authors and Affiliations

  1. Dipartimento di Matematica, Università degli Studi di Padova, Via Trieste, 63-35121, Padua, Italy

    Martino Bardi

  2. UPMC Univ Paris 06, CNRS, UMR 7586, IMJ-PRG, Sorbonne Universités, Case 247, 4 Place Jussieu, 75005, Paris, France

    Juan Pablo Maldonado López

  3. Sorbonne Paris Cité, UMR 7586, Univ Paris-Diderot, 75013, Paris, France

    Juan Pablo Maldonado López

Authors
  1. Martino Bardi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juan Pablo Maldonado López
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Martino Bardi.

Additional information

This study was partially supported by the Fondazione CaRiPaRo Project “Nonlinear Partial Differential Equations: models, analysis, and control-theoretic problems” and the European Project Marie Curie ITN “SADCO—Sensitivity Analysis for Deterministic Controller Design”.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bardi, M., Maldonado López, J. A Dijkstra-Type Algorithm for Dynamic Games. Dyn Games Appl 6, 263–276 (2016). https://doi.org/10.1007/s13235-015-0156-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13235-015-0156-0

Keywords

Mathematics Subject Classification

Search

Navigation