Deceptive Stochastic Patrolling via Markov Chain Lifting
This work introduces lifted Markov Chains as a new method for creating patrol strategies for mobile agents moving across a graph environment. By enlarging the state space with virtual copies of original states, it derives better patrol plans. The research proves these lifted chains perform at least as well as standard methods and shows significant performance gains on sparse graphs.