Optimal Patrol to Uncover Threats in Time When Detection Is Imperfect

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.