Optimal Patrol to Uncover Threats in Time When Detection Is Imperfect
Loading...
Authors
Lin, Kyle Y.
Atkinson, Michael
Glazebrook, Kevin D.
Subjects
Advisors
Date of Issue
2013-08-12
Date
Publisher
Language
Abstract
This paper considers a patrol problem, where a patroller traverses a graph through
edges to detect potential attacks at nodes. Attackers arrive at each node according
to independent Poisson processes and take a random amount of time to complete an
attack. The patroller takes one time unit to move to and inspect an adjacent node,
and at the end of the inspection will detect an ongoing attack at the same node with
some probability. A cost is incurred if an attack completes before it is detected. The
attack time distribution, the cost due to a successful attack, and the detection prob-
ability all depend on the attack node. A linear program to compute the optimal
solution for this patrol problem, although possible, quickly becomes computationally
intractable for moderate-size problems. Our main contribution is to develop e cient
index policies|based on Lagrangian relaxation methodology, and also on approximate
dynamic programming|which typically achieve within 1% of optimality with compu-
tation time orders of magnitude less than what is required to compute the optimal
policy. The ndings can also be used to construct e ective patrol policies against a
strategic attacker, who chooses which node to attack to cause the maximum expected
cost to the patroller.
Type
Article
Description
Series/Report No
Department
Operations Research
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.