Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

7-2014

Abstract

To dissuade reckless driving and mitigate accidents, cities deploy resources to patrol roads. In this paper, we present STREETS, an application developed for the city of Singapore, which models the problem of computing randomized traffic patrol strategies as a defenderattacker Stackelberg game. Previous work on Stackelberg security games has focused extensively on counterterrorism settings. STREETS moves beyond counterterrorism and represents the first use of Stackelberg games for traffic patrolling, in the process providing a novel algorithm for solving such games that addresses three major challenges in modeling and scale-up. First, there exists a high degree of unpredictability in travel times through road networks, which we capture using a Markov Decision Process for planning the patrols of the defender (the police) in the game. Second, modeling all possible police patrols and their interactions with a large number of adversaries (drivers) introduces a significant scalability challenge. To address this challenge we apply a compact game representation in a novel fashion combined with adversary and state sampling. Third, patrol strategies must balance exploitation (minimizing violations) with exploration (maximizing omnipresence), a tradeoff we model by solving a biobjective optimization problem. We present experimental results using real-world traffic data from Singapore. This work is done in collaboration with the Singapore Ministry of Home Affairs and is currently being evaluated by the Singapore Police Force.

Keywords

Game theory, multi-agent systems, planning, Markov decision processes, security, Traffic police, Singapore, police patrols

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of 26th IAAAI Conference on Innovative Applications in Artificial Intelligence: 29-31 July 2014, Quebec City

First Page

2966

Last Page

2971

ISBN

9781577356615

Publisher

AAAI Press

City or Country

Menlo Park, CA

Copyright Owner and License

Publisher

Additional URL

http://www.aaai.org/ocs/index.php/IAAI/IAAI14/paper/view/8301

Download

Share

COinS