Staying Ahead of the Game: Adaptive Robust Optimization for Dynamic Allocation of Threat Screening Resources

Staying Ahead of the Game: Adaptive Robust Optimization for Dynamic Allocation of Threat Screening Resources

Sara Marie Mc Carthy, Phebe Vayanos, Milind Tambe

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

We consider the problem of dynamically allocating screening resources of different efficacies (e.g., magnetic or X-ray imaging) at checkpoints (e.g., at airports or ports) to successfully avert an attack by one of the screenees. Previously, the Threat Screening Game model was introduced to address this problem under the assumption that screenee arrival times are perfectly known. In reality, arrival times are uncertain, which severely impedes the implementability and performance of this approach. We thus propose a novel framework for dynamic allocation of threat screening resources that explicitly accounts for uncertainty in the screenee arrival times. We model the problem as a multistage robust optimization problem and propose a tractable solution approach using compact linear decision rules combined with robust reformulation and constraint randomization. We perform extensive numerical experiments which showcase that our approach outperforms (a) exact solution methods in terms of tractability, while incurring only a very minor loss in optimality, and (b) methods that ignore uncertainty in terms of both feasibility and optimality.
Keywords:
Multidisciplinary Topics and Applications: AI&Security and Privacy
Knowledge Representation, Reasoning, and Logic: Game Theory
Agent-based and Multi-agent Systems: Noncooperative Games