Protecting Moving Targets with Multiple Mobile Resources

By Fei Fang, Albert Xin Jiang, Milind Tambe. 2013

39 citations recorded by the source corpus.

In recent years, Stackelberg Security Games have been successfully applied to solve resource allocation and scheduling problems in several security domains. However, previous work has mostly assumed that the targets are stationary relative to the defender and the attacker, leading to discrete game models with finite numbers of pure strategies. This paper in contrast focuses on protecting mobile targets that leads to a continuous set of strategies for the players. The problem is motivated by several real-world domains including protecting ferries with escort boats and protecting refugee supply lines. Our contributions include: (i) A new game model for multiple mobile defender resources and moving targets with a discretized strategy space for the defender and a continuous strategy space for the attacker. (ii) An efficient linear-programming-based solution that uses a compact representation for the defender's mixed strategy, while accurately modeling the attacker's continuous strategy using a novel sub-interval analysis method. (iii) Discussion and analysis of multiple heuristic methods for equilibrium refinement to improve robustness of defender's mixed strategy. (iv) Discussion of approaches to sample actual defender schedules from the defender's mixed strategy. (iv) Detailed experimental analysis of our algorithms in the ferry protection domain.

Subfields: Civil and Structural Engineering, Control and Systems Engineering, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Control and Systems Engineering

1. Xiaolong Wang
2. Simon Shaolei Du
3. Yi Wu
4. Huazhe Xu
5. Jorge Armando Mendez Mendez
6. Eric Eaton

In Statistics and Probability

1. Simon Shaolei Du
2. Yu Wang

Citations in the corpus

• Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, background): “…of equilibria satisfying desirable properties, e.g., admissibility (Banks & Sobel, 1987), subgame perfection (Selten, 1965), Pareto efficiency (Bernheim et al., 1987) or robustness against opponent’s deviation from best response in security-related applications (Fang et al., 2013; An et al., 2011).”