A Dijkstra-Type Algorithm for Dynamic Games

被引：0
作者：
Martino Bardi
Juan Pablo Maldonado López
机构：
[1] Università degli Studi di Padova,Dipartimento di Matematica
[2] Sorbonne Universités,UPMC Univ Paris 06, CNRS, UMR 7586, IMJ
[3] Univ Paris-Diderot,PRG
来源：
Dynamic Games and Applications | 2016年 / 6卷
关键词：
Zero sum dynamic games; Dijkstra algorithm; Pursuit evasion games; Discrete time games; 91A25; 65Kxx; 49N70; 91A23; 91A24; 49N75;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：263 / 276
页数：13
相关论文
共 35 条
  • [1] Alfaro T(2007)Concurrent reachability games Theor Comput Sci 386 188-217
  • [2] Henzinger T(2014)Deterministic control of randomly-terminated processes Interfaces Free Bound 16 1-40
  • [3] Kupferman O(1994)A comparison result for Hamilton-Jacobi equations and applications to some differential games lacking controllability Funkcial Ekvac 37 19-43
  • [4] Andrews J(2013)On the homogenization of some non-coercive Hamilton-Jacobi-Isaacs equations Commun Pure Appl Anal 12 207-236
  • [5] Vladimirsky A(2014)Can local single-pass methods solve any stationary Hamilton-Jacobi equation? SIAM J Sci Comput 36 A570-A587
  • [6] Bardi M(2012)A patchy dynamic programming scheme for a class of Hamilton–Jacobi–Bellman equations SIAM J Sci Comput 34 A2625-A2649
  • [7] Soravia P(2009)A fast marching method for Hamilton–Jacobi equations modeling monotone front propagations J Sci Comput 39 189-205
  • [8] Bardi M(1959)A note on two problems in connection with graphs Numer Math 1 269-271
  • [9] Terrone G(1991)Algorithms for stochastic games—A survey Z Oper Res 35 437-472
  • [10] Cacace S(1987)Fibonacci heaps and their uses in improved network optimization algorithms J Assoc Comput Mach 34 596-615
1234