A Graph Patrol Problem with Random Attack Times

Download
Author
Lin, Kyle Y.
Atkinson, Michael P.
Chung, Timothy H.
Glazebrook, Kevin D.
Date
2013Metadata
Show full item recordAbstract
This paper presents a patrol problem, where a patroller traverses a graph through edges to detect potential attacks at nodes.
To design a patrol policy, the patroller needs to take into account not only the graph structure, but also the different attack
time distributions, as well as different costs incurred due to successful attacks, at different nodes. We consider both random
attackers and strategic attackers. A random attacker chooses which node to attack according to a probability distribution
known to the patroller. A strategic attacker plays a two-person zero-sum game with the patroller. For each case, we give
an exact linear program to compute the optimal solution. Because the linear programs quickly become computationally
intractable as the problem size grows, we develop index-based heuristics. In the random-attacker case, our heuristic is
optimal when there are two nodes, and in a suitably chosen asymptotic regime. In the strategic-attacker case, our heuristic is
optimal when there are two nodes if the attack times are deterministic taking integer values. In our numerical experiments,
our heuristic typically achieves within 1% of optimality with computation time orders of magnitude less than what is
required to compute the optimal policy.
Description
The article of record as published may be found at http://dx.doi.org/10.1287/opre.1120.1149
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.Collections
Related items
Showing items related by title, author, creator and subject.
-
Optimal Patrol to Uncover Threats in Time When Detection Is Imperfect
Lin, Kyle Y.; Atkinson, Michael; Glazebrook, Kevin D. (2013-08-12);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 ... -
Optimal patrol to detect attacks at dispersed heterogeneous locations
McGrath, Richard G., Jr. (Monterey, California. Naval Postgraduate School, 2013-12);We study a patrol problem where several patrollers move between heterogeneous locations dispersed throughout an area of interest in order to detect enemy attacks. To formulate an e ective patrol policy, the patrollers ... -
Optimal Patrol on a Perimeter
Lin, Kyle Y. (ArXiv, 2020-02-11);A defender dispatches patrollers to circumambulate a perimeter to guard against potential attacks. The defender decides on the time points to dispatch patrollers and each patroller’s direction and speed, as long as the ...