pipette
ESEspañol

Deceptive Stochastic Patrolling via Markov Chain Lifting

Yohan John, Gilberto Diaz-Garcia, Jason R. Marden, Francesco Bullo

Preprint

In the authors' words

In this paper we propose lifted Markov Chains (MCs) as a new paradigm for deriving patrol strategies for mobile agents on an environment represented as a graph. Lifted MCs operate on a state space that can be larger than the set of nodes of the graph, and a projection operation maps the MC state to the corresponding node of the graph. We prove bounds on the performance improvement of lifted MCs over non-lifted MCs, where the performance is measured by the Kemeny constant, and show a corresponding monotonicity for the Stackelberg game capture probability and return-time entropy. These bounds yield a result of independent interest that relates the Kemeny constant and the MC conductance for general MCs. We also provide a tractable method for optimizing lifted MCs on general graphs with edge weights encoding travel times. Simulation results on randomly generated and real-world graphs verify that lifted MCs achieve substantial improvements, particularly on sparse graphs.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 9. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 14 pages, 8 figures. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible