Harbor attack: A pursuit-evasion game

Jean Walrand, Elijah Polak, Hoam Chung

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

15 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011
Subtitle of host publicationMonticello, Illinois, USA; 28-30 September 2011
EditorsBarb Horner, Jana Lenz, Becky Lonberger
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages1584-1591
Number of pages8
ISBN (Electronic)9781457718168, 9781457718182
ISBN (Print)9781457718175
DOIs
Publication statusPublished - 2011
EventAnnual Allerton Conference on Communication, Control and Computing 2011 - Allerton Park and Retreat Center, University of Illinois, Monticello, United States of America
Duration: 28 Sep 201130 Sep 2011
Conference number: 49th

Conference

ConferenceAnnual Allerton Conference on Communication, Control and Computing 2011
Abbreviated titleAllerton 2011
CountryUnited States of America
CityMonticello
Period28/09/1130/09/11

Cite this