Harbor attack: A pursuit-evasion game

This paper studies a concrete pursuit-evasion game in which the evader, a.k.a. the intruder, tries to reach a harbor via a rectangular channel, while the pursuer, a.k.a. the defender, tries to stop him. Our goal is to develop insight into the nature of this game, the impact of the quality of information, and the potential evasion and defense numerical algorithms for its solution. We assume that the evader and pursuer are governed by so called "bicycle" dynamics, with bounded controls, but when convenient we simplify matters by assuming that the controls are impulses, which enables us to assume that the pursuer and evader can change direction instantaneously, subject to bounds on velocities, not accelerations. Under the assumption of impulsive control, we show, by exhibiting specific strategies, that if the intruder is faster than the defender, and if the channel is wide enough, then the intruder succeeds. Conversely, if the intruder is slower than the defender, then the probability of the intruder reaching the harbor, when the the intruder and defender strategies are a Nash equilibrium, depends on the width of the channel and the detection range. These results can be used to determine whether a single defender is sufficient to defend the harbor. A mathematical formulation of the harbor defense game takes the form of a generalized max-min problem, in which the strategy constraint-set of the intruder depends on the strategies of the pursuer. Generalized max-min problems do not lead to corresponding min-max problems and so one cannot talk about a duality gap. Also, in general, they are numerically intractable. However, in the particular case under consideration, we show that the generalized max-min problem can be converted to a regular max-min problem using exact penalty functions, and that then they become solvable using the method of outer approximations. We also show that the solutions of the generalized max-min problems can be used to define a receding horizon feedback control law for the pursuer, which enables the pursuer to take into account modeling errors and the unpredictable strategies of the intruder.