Conference Proceeding Article
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.
Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
Proceedings of 26th IAAAI Conference on Innovative Applications in Artificial Intelligence: 29-31 July 2014, Quebec City
City or Country
Menlo Park, CA
BROWN, Matthew; Saisubramanian, Sandhya; VARAKANTHAM, Pradeep Reddy; and Tambe, Milind.
STREETS: Game-Theoretic Traffic Patrolling with Exploration and Exploitation. (2014). Proceedings of 26th IAAAI Conference on Innovative Applications in Artificial Intelligence: 29-31 July 2014, Quebec City. 2966-2971. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/2222
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.