NDLI: Harbor attack: A pursuit-evasion game

Content Provider	IEEE Xplore Digital Library
Author	Walrand, J. Polak, E. Hoam Chung
Copyright Year	2011
Description	Author affiliation: Department of Electrical Engineering and Computer Sciences, University of California Berkeley, California - 94720 (Walrand, J.; Polak, E.) \|\| Department of Mechanical and Aerospace Engineering, Monash University, Clayton, Victoria - 3800, Australia (Hoam Chung)
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.
Starting Page	1584
Ending Page	1591
File Size	923416
Page Count	8
File Format	PDF
ISBN	9781457718175
e-ISBN	9781457718182
DOI	10.1109/Allerton.2011.6120357
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-09-28
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Heuristic algorithms Games Approximation algorithms Sensors Trajectory Approximation methods Vehicle dynamics
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in