Optimal interdiction of urban criminals with the aid of real-time information
File(s)AAAI19_Urban.pdf (719.91 KB)
Accepted version
Author(s)
Jennings, Nick
Zhang, Youzhi
Guo, Qingyu
An, Bo
Tran-Thanh, Long
Type
Conference Paper
Abstract
Most violent crimes happen in urban and suburban cities. With emerging tracking techniques, law enforcement officers can have real-time location information of the escaping criminals and dynamically adjust the security resource allocation to interdict them. Unfortunately, existing work on urban network security games largely ignores such information. This paper addresses this omission. First, we show that ignoring the real-time information can cause an arbitrarily large loss of efficiency. To mitigate this loss, we propose a novel NEtwork purSuiT game (NEST) model that captures the interaction between an escaping adversary and a defender with multiple resources and real-time information available. Second, solving NEST is proven to be NP-hard. Third, after transforming the non-convex program of solving NEST to a linear program, we propose our incremental strategy generation algorithm, including: (i) novel pruning techniques in our best response oracle; and (ii) novel techniques for mapping strategies between subgames and adding multiple best response strategies at one iteration to solve extremely large problems. Finally, extensive experiments show the effectiveness of our approach, which scales up to realistic problem sizes with hundreds of nodes on networks including the real network of Manhattan.
Date Issued
2019-07-17
Date Acceptance
2018-12-01
Citation
AAAI 2019, 2019, pp.1262-1269
Publisher
AAAI
Start Page
1262
End Page
1269
Journal / Book Title
AAAI 2019
Copyright Statement
© 2019, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.
Intelligence (www.aaai.org). All rights reserved.
Identifier
https://www.aaai.org/ojs/index.php/AAAI/article/view/3921
Source
33rd AAAI Conference on Artificial Intelligence
Subjects
Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science, Theory & Methods
Engineering, Electrical & Electronic
Computer Science
Engineering
GAMES
Publication Status
Published
Start Date
2019-01-27
Finish Date
2019-02-01
Coverage Spatial
Hawaii, USA
Date Publish Online
2019-07-17