A Time-expanded Network Exact Algorithm for Solving Escape Interdiction Games скачать в хорошем качестве

A Time-expanded Network Exact Algorithm for Solving Escape Interdiction Games

Speaker: Peter Gill (Monash University) Title: A Time-expanded Network Exact Algorithm for Solving Escape Interdiction Games Summary: Escape interdiction games model a game of ’cops and robbers’ where one criminal (attacker) desires to escape some city along its roads from some crime scene, and the local police force (defender) desires to capture the criminal within the city before they can escape. The city road network is modelled as a weighted directed network with start nodes for each player, and a target node for the attacker. In this variant, each defender agent can only interdict the attacker on a node in the network, not on an edge. Thus we allow defender agents to stop at a node for some length of time, but also to dynamically move around the network to possibly interdict somewhere else at a later time. We ask that the entire scenario takes place within some finite time horizon $T_{\max}$. Each defender agent moves at the same speed, though the attacker may move at a different speed. We assume neither player has access to real-time information on the other player’s whereabouts. This is naturally a two-player zero-sum game, and hence we want to find Nash equilibria. Discretisation of the strategy spaces plays a crucial part in ensuring that the computation of Nash equilibria is tractable. We present new attacker and defender exact oracles (algorithms that find a best response strategy against some mixed strategy) that utilise network flow on a partially time-expanded network for computing Nash equilibria in a double oracle algorithm. Computational results show our new oracles outperform the existing oracles in the literature and are comparable with the current state of the art heuristic in finding Nash equilibria for this variant of escape interdiction game. Bio: Peter is a 1st year Ph.D. student at Monash University, currently focussing on dynamic discretisation of time-dependent linear programs. He is supervised by Prof. Andreas Ernst and Dr. Pierre Le Bodic.