Inserted: 17 jul 2013
Last Updated: 20 may 2016
Journal: Dyn. Games Appl.
Doi: DOI 10.1007/s13235-015-0156-0
We study zero-sum dynamic games with deterministic transitions and alternating moves of the players. Player 1 aims at reaching a terminal set and minimising a possibly discounted running and final cost. We propose and analyse 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.
Keywords: Zero-sum dynamic games , Discrete time games, Pursuit-evasion games, Dijkstra algorithm