Calculus of Variations and Geometric Measure Theory

M. Bardi - J. P. Maldonado Lopez

A Dijkstra-type algorithm for dynamic games

created by bardi on 17 Jul 2013
modified on 20 May 2016


Published Paper

Inserted: 17 jul 2013
Last Updated: 20 may 2016

Journal: Dyn. Games Appl.
Year: 2015
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