New AI Patrols Randomly to Catch More Criminals
This could make police patrols less predictable and more effective.
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.
- A new AI method makes patrol routes random to catch criminals off guard.
- It uses Markov chains, a math concept, to create unpredictable patterns.
- This could improve security without adding more guards or police.
Why It Matters
This could lead to safer neighborhoods and more efficient use of security resources.