Optimal Patrol to Uncover Threats in Time When Detection Is Imperfect
Lin, Kyle Y.
Glazebrook, Kevin D.
MetadataShow full item record
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.
RightsThis 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.
Showing items related by title, author, creator and subject.
Lin, Kyle Y.; Atkinson, Michael P.; Chung, Timothy H.; Glazebrook, Kevin D. (2013);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, ...
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 ...
Chung, H.; Polak, E.; Royset, J.O.; Sastry, S.S. (American Control Conference, 2011-06);Given a number of patrollers, the channel patrol problem consists of determining the periodic trajectories that the patrollers must trace out so as to maximize the probability of detection of the intruder. We formulate ...