 |
Center for Nonlinear Studies |
Optimal Network Interdiction of Unreactive Markovian Evaders
The network interdiction problem arises in a variety of areas including military logistics, infectious disease control, and counter-terrorism. In the classical formulation the task is to find b edges to remove from a weighted network G(N,E) that maximally interfere with motion from a source node s to a target node t. In practical applications, G represents a transportation or activity network; node or edge removal is performed by an interdictor agent against an evader agent who wants to traverse G from node s to node t along the least-cost route. In many interdiction scenarios both agents have incomplete information or the evaders lack planning time. For example, in law enforcement, sometimes when authorities place roadblocks on the transportation network to catch criminals, the authorities do not know the criminals' locations and the criminals do not know where the roadblocks are.
Consequently I introduce a model of network interdiction in which the evaders are assumed to take a Markovian random walk from s to t guided by the least-cost path and do not to react to interdiction decisions. The interdiction objective is to find an interdiction edge set, of size at most b, that maximizes the probability of the evaders passing through that set. I prove that this is NP-hard, but unlike the classical problem the objective function is submodular and the solution can be approximated within 1-1/e using a greedy algorithm. Additionally I exploit submodularity to introduce a ``priority'' (or ``lazy'') evaluation strategy that speeds up the greedy algorithm by orders of magnitude. These results bring closer the goal of finding realistic solutions to the interdiction problem on global-scale networks.