Seminar by Prof. Stefan Feuerriegel, ETHZ
Event details
| Date | 20.06.2019 |
| Hour | 15:00 › 16:30 |
| Speaker | Séminaire par Prof. Stefan Feuerriegel, ETHZ |
| Location | |
| Category | Conferences - Seminars |
"Effective Police Patrolling: A Stratified Monte Carlo Tree Search"
Résumé
Police patrolling was proven to prevent crime, and yet a corresponding decision problem that aids police management is lacking. As a remedy, this work formalizes effective police patrolling as a finite-horizon discrete-time Markov decision process (MDP). It yields a policy for choosing optimal pathways for multiple patrols with the objective of reducing crime risk. The MDP for multiple patrols yields a high-dimensional state-action space, which prohibits straightforward solutions. Therefore, we apply Monte Carlo tree search (MCTS) as a solution technique and, in order to obtain substantially better performance, develop a stratified MCTS: that is, we translate the discrete MDP into sub-problems of continuous optimal path planning modeled via the eikonal equation, i.e., a non-linear partial differential equation, where the optimal pathways correspond to solutions of ordinary differential equations. Given this formalization, we derive two novel MCTS roll-out policies, namely, a Dijkstra policy and a fast-marching policy. This allows us to provide theoretical guarantees that, under mild assumptions, both roll-out policies choose pathways that are locally optimal. The superiority of our stratified MCTS over a naive MCTS is confirmed in an extensive series of experiments. Furthermore, the decision heuristics which are currently applied in police practice are considerably outperformed. Our work entails important implications. Public sector management benefits from an effective use of resources and, methodologically, we establish that tailored, domain-specific roll-out policies can achieve theoretical optimality guarantees.
Résumé
Police patrolling was proven to prevent crime, and yet a corresponding decision problem that aids police management is lacking. As a remedy, this work formalizes effective police patrolling as a finite-horizon discrete-time Markov decision process (MDP). It yields a policy for choosing optimal pathways for multiple patrols with the objective of reducing crime risk. The MDP for multiple patrols yields a high-dimensional state-action space, which prohibits straightforward solutions. Therefore, we apply Monte Carlo tree search (MCTS) as a solution technique and, in order to obtain substantially better performance, develop a stratified MCTS: that is, we translate the discrete MDP into sub-problems of continuous optimal path planning modeled via the eikonal equation, i.e., a non-linear partial differential equation, where the optimal pathways correspond to solutions of ordinary differential equations. Given this formalization, we derive two novel MCTS roll-out policies, namely, a Dijkstra policy and a fast-marching policy. This allows us to provide theoretical guarantees that, under mild assumptions, both roll-out policies choose pathways that are locally optimal. The superiority of our stratified MCTS over a naive MCTS is confirmed in an extensive series of experiments. Furthermore, the decision heuristics which are currently applied in police practice are considerably outperformed. Our work entails important implications. Public sector management benefits from an effective use of resources and, methodologically, we establish that tailored, domain-specific roll-out policies can achieve theoretical optimality guarantees.
Practical information
- General public
- Free