Optimal Escape Interdiction on Transportation Networks

Optimal Escape Interdiction on Transportation Networks

Youzhi Zhang, Bo An, Long Tran-Thanh, Zhen Wang, Jiarui Gan, Nicholas R. Jennings

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 3936-3944. https://doi.org/10.24963/ijcai.2017/550

Preventing crimes or terrorist attacks in urban areas is challenging. Law enforcement officers need to respond quickly to catch the attacker on his escape route, which is subject to time-dependent traffic conditions on transportation networks. The attacker can strategically choose his escape path and driving speed to avoid being captured. Existing work on security resource allocation has not considered such scenarios with time-dependent strategies for both players. Therefore, in this paper, we study the problem of efficiently scheduling security resources for interdicting the escaping attacker. We propose: 1) a new defender-attacker security game model for escape interdiction on transportation networks; and 2) an efficient double oracle algorithm to compute the optimal defender strategy, which combines mixed-integer linear programming formulations for best response problems and effective approximation algorithms for improving the scalability of the algorithms. Experimental evaluation shows that our approach significantly outperforms baselines in solution quality and scales up to realistic-sized transportation networks with hundreds of intersections.
Keywords:
Multidisciplinary Topics and Applications: AI&Security and Privacy
Multidisciplinary Topics and Applications: Multidisciplinary Topics and Applications