Computing Optimal Monitoring Strategy for Detecting Terrorist Plots

Authors

  • Zhen Wang Nanyang Technological University
  • Yue Yin University of Chinese Academy of Sciences
  • Bo An Nanyang Technological University

DOI:

https://doi.org/10.1609/aaai.v30i1.10028

Abstract

In recent years, terrorist organizations (e.g., ISIS or al-Qaeda) are increasingly directing terrorists to launch coordinated attacks in their home countries. One example is the Paris shootings on January 7, 2015.By monitoring potential terrorists, security agencies are able to detect and stop terrorist plots at their planning stage.Although security agencies may have knowledge about potential terrorists (e.g., who they are, how they interact), they usually have limited resources and cannot monitor all terrorists.Moreover, a terrorist planner may strategically choose to arouse terrorists considering the security agency's monitoring strategy. This paper makes five key contributions toward the challenging problem of computing optimal monitoring strategies: 1) A new Stackelberg game model for terrorist plot detection;2) A modified double oracle framework for computing the optimal strategy effectively;3) Complexity results for both defender and attacker oracle problems;4) Novel mixed-integer linear programming (MILP) formulations for best response problems of both players;and 5) Effective approximation algorithms for generating suboptimal responses for both players.Experimental evaluation shows that our approach can obtain a robust enough solution outperforming widely-used centrality based heuristics significantly and scale up to realistic-sized problems.

Downloads

Published

2016-02-21

How to Cite

Wang, Z., Yin, Y., & An, B. (2016). Computing Optimal Monitoring Strategy for Detecting Terrorist Plots. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10028

Issue

Section

Technical Papers: Game Theory and Economic Paradigms