A Linear Programming Approach to the Search Game on a Network with Mobile Hider
Edward James Anderson, Miguel Aramendía · SIAM Journal on Control and Optimization · 1992
This paper discusses a search game on a network Q with two players, a searcher and a hider, who each move with continuous trajectories starting from different points subject to a maximal speed and termination time T. This is a zero-sum game with payoff given by the time elapsed until the searcher reaches a point that is occupied by the hider (if this happens), and T otherwise. The problem is formulated as an infinite-dimensional linear program, and the extreme points and the reduced cost functional are studied. An algorithm is derived for this problem, and how it works on an example is demonstrated.