 |
Center for Nonlinear Studies |
The problem of network interdiction is broadly described as the question of how limited resources should be used by an "interdictor" to attempt to capture an "evader" moving through a network from a source node to a target node. One formulation of this problem has been introduced and investigated by members of the lab A. Gutfraind, A. Hagberg, and F. Pan (preprint). They assume that the evader is Markovian and utilize a new randomness parameter to quantify the uncertainty in the evader's motion. However, this randomness parameter does not extend to arbitrary Markov motions on the network and its relationship to other measures of randomness is not clear. A paper by Saerens et al. (Neural Computation 21, 2363-2404) suggests the use of a more well-established randomness measure: the entropy of the path probability distribution. They claim to efficiently solve the problem of finding the Markov motion with the smallest expected cost from the source to the target, given a specified entropy constraint. This is aptly described as a randomized shortest path problem. Their solution is a Markov chain that realizes a Boltzmann distribution for the path probability distribution. Here, we give some counterexamples to their claims, showing that they are in fact false in many instances. In addition, we discuss efforts towards solving the problem in said cases, and towards validating their solution in others. Not only does this work have implications for modeling an evader in network interdiction, but it also has implications for applications of the randomized shortest path problem in traffic science, artificial intelligence, bioinformatics, etc. (see Saerens et al.).
Host: Sasha Gutfraind