Computing time-dependent policies for patrolling games with mobile targets

We study how a mobile defender should patrol an area to protect multiple valuable targets from being attacked by an attacker. In contrast to existing approaches, which assume stationary targets, we allow the targets to move through the area according to an a priori known, deterministic movement schedules. We represent the patrol area by a graph of arbitrary topology and do not put any restrictions on the movement schedules. We assume the attacker can observe the defender and has full knowledge of the strategy the defender employs. We construct a game-theoretic formulation and seek defender's optimal randomized strategy in a Stackelberg equilibrium of the game. We formulate the computation of the strategy as a mathematical program whose solution corresponds to an optimal time-dependent Markov policy for the defender. We also consider a simplified formulation allowing only stationary defender's policies which are generally less effective but are computationally significantly cheaper to obtain. We provide experimental evaluation examining this trade-off on a set of test problems covering various topologies of the patrol area and various movement schedules of the targets.

• Publication year

  2011

• Venue

  Adaptive Agents and Multi-Agent Systems

• Publication date

  2011-05-02

• Fields of study

  Computer Science

• Identifiers
  DOI 10.65109/zxmh3190
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Security and Game Theory: IRIS – A Tool for Strategic Security Allocation in Transportation Networks

  2011cited by this paper
• Optimal defender allocation for massive security games : A branch and price approach

  2010influential reference
• Stackelberg vs. Nash in security games: interchangeability, equivalence, and uniqueness

  2010influential reference
• Asynchronous Multi-Robot Patrolling against Intrusions in Arbitrary Topologies

  2010cited by this paper
• Computing optimal randomized resource allocations for massive security games

  2009influential reference
• Leader-follower strategies for robotic patrolling in environments with arbitrary topologies

  2009influential reference
• Extending Algorithms for Mobile Robot Patrolling in the Presence of Adversaries to More Realistic Settings

  2009cited by this paper
• Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport

  2008cited by this paper
• The impact of adversarial knowledge on adversarial planning in perimeter patrol

  2008cited by this paper
• Multi-robot perimeter patrol in adversarial settings

  2008influential reference
• Global Optimization with Polynomials and the Problem of Moments

  2000cited by this paper
• Bilinear separation of two sets inn-space

  1993cited by this paper

• Multi-Defender Single-Attacker Perimeter Defense Game on a Cylinder: Special Case in which the Attacker Starts at the Boundary

  2026cites this paper
• Sea-cret Agents: Maritime Abduction for Region Generation to Expose Dark Vessel Trajectories

  2025cites this paper
• Patrol Security Game: Defending Against Adversary with Freedom in Attack Timing, Location, and Duration

  2024cites this paper
• Who Let the Guards Out: Visual Support for Patrolling Games

  2024cites this paper
• Minimizing Expected Intrusion Detection Time in Adversarial Patrolling

  2022cites this paper
• Enhancing Security-Problem-Based Deep Learning in Mobile Edge Computing

  2022cites this paper
• Regstar: Efficient Strategy Synthesis for Adversarial Patrolling Games

  2021cites this paper
• Game Theory for Unmanned Vehicle Path Planning in the Marine Domain: State of the Art and New Possibilities

  2021cites this paper
• Scalable Optimal Classifiers for Adversarial Settings under Uncertainty

  2021cites this paper
• Deep R-Learning for Continual Area Sweeping

  2020cites this paper
• Adversarial Patrolling with Drones

  2020cites this paper
• Multi-robot adversarial patrolling: Handling sequential attacks

  2019influential citation
• Defending on networks: applying game theory to prevent illegal activities in structured security domains

  2019cites this paper
• ON DYNAMIC PATROLLING SECURITY GAMES

  2019cites this paper
• Solving Security Problems in MEC Systems

  2019cites this paper
• Patrol Scheduling Against Adversaries with Varying Attack Durations

  2019cites this paper
• A Memetic Approach for Sequential Security Games on a Plane with Moving Targets

  2019cites this paper
• A Simple and Efficient Algorithm to Compute Epsilon-Equilibria of Discrete Colonel Blotto Games: Epsilon-Equilibria of Discrete Colonel Blotto Games

  2018cites this paper
• Synthesizing Efficient Solutions for Patrolling Problems in the Internet Environment

  2018cites this paper
• From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games

  2018cites this paper
• Catching Captain Jack: Efficient Time and Space Dependent Patrols to Combat Oil-Siphoning in International Waters

  2018cites this paper
• Speed Trap Optimal Patrolling: STOP Playing Stackelberg Security Games

  2018cites this paper
• Spatio-Temporal Games Beyond One Dimension

  2018cites this paper
• Solving Patrolling Problems in the Internet Environment

  2018cites this paper
• Efficient Computation of Approximate Equilibria in Discrete Colonel Blotto Games

  2018cites this paper
• Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games

  2018cites this paper
• A Simple and Efficient Algorithm to Compute Epsilon-Equilibria of Discrete Colonel Blotto Games Extended

  2018cites this paper
• Mitigating the Curse of Correlation in Security Games by Entropy Maximization

  2017cites this paper
• Speed Trap Optimal Patrolling: STOP Playing Stackelberg Security Games

  2017cites this paper
• A Polynomial Time Algorithm for Spatio-Temporal Security Games

  2017cites this paper
• The Curse of Correlation in Security Games and Principle of Max-Entropy

  2017cites this paper
• Protecting the NECTAR of the Ganga River Through Game-Theoretic Factory Inspections

  2016cites this paper
• Advances in Practical Applications of Scalable Multi-agent Systems. The PAAMS Collection

  2016influential citation
• Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems

  2016influential citation
• NECTAR : Game-Theoretic Factory Inspection Scheduling and Explanation for Toxic Wastewater Abatement ∗

  2016cites this paper
• Model-predictive asset guarding by team of autonomous surface vehicles in environment with civilian boats

  2015influential citation
• Robotic Surveillance and Deployment Strategies

  2015cites this paper
• Improvements to the Linear Optimization Models of Patrol Scheduling for Mobile Targets

  2015cites this paper
• An extended study on addressing defender teamwork while accounting for uncertainty in attacker defender games using iterative Dec-MDPs

  2015cites this paper
• Security Games with Information Leakage: Modeling and Computation

  2015cites this paper
• Model-Predictive Strategy Generation for Multi-Agent Pursuit-Evasion Games

  2015cites this paper
• Strategy Synthesis in Adversarial Patrolling Games

  2015cites this paper
• Path Planning Algorithms for Robotic Agents

  2015cites this paper
• Robotic Surveillance and Markov Chains With Minimal Weighted Kemeny Constant

  2015cites this paper
• Solving adversarial patrolling games with bounded error: (extended abstract)

  2014cites this paper
• Computing Minimax Strategy for Discretized Spatio-Temporal Zero-Sum Security Games ?

  2014cites this paper
• Hybrid ACO/EA algorithms applied to the multi-agent patrolling problem

  2014cites this paper
• Le problème de la patrouille multiagent. Étude de convergence de l'évaluation des stratégies cycliques

  2014cites this paper
• The Multi-agent Patrolling Problem Theoretical Results about Cyclic Strategies

  2014cites this paper
• Computing Solutions in Infinite-Horizon Discounted Adversarial Patrolling Games

  2014cites this paper
• Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains

  2014influential citation
• An automated decision support model for remote patrolling

  2014cites this paper
• Multi-objective border patrolling optimization using game theory and evolutionary algorithms

  2014cites this paper
• Persistent patrolling in the presence of adversarial observers

  2014cites this paper
• Iterative Algorithms for Solving Finite Sequential Zero-Sum

  2014cites this paper
• Unleashing Dec-MDPs in Security Games: Enabling Effective Defender Teamwork

  2014cites this paper
• Monte Carlo Tree Search in Imperfect-Information Games

  2014cites this paper
• Protecting Moving Targets with Multiple Mobile Resources

  2013cites this paper
• Optimal patrol strategy for protecting moving targets with multiple mobile resources

  2013cites this paper
• Simulated Multi-robot Tactical Missions in Urban Warfare

  2013cites this paper
• Thwarting Adversaries with Unpredictability: Massive-scale Game-Theoretic Algorithms for Real-world Security Deployments

  2013cites this paper
• Developing Multiagent Algorithms for Tactical Missions Using Simulation

  2013cites this paper
• Solving extensive-form games with double-oracle methods

  2013cites this paper
• Introducing alarms in adversarial patrolling games: extended abstract

  2013cites this paper
• Agents vs. pirates: multi-agent simulation and optimization to fight maritime piracy

  2012cites this paper
• Tactical operations of multi-robot teams in urban warfare (demonstration)

  2012cites this paper
• Strategic analysis of complex security scenarios.

  2012cites this paper
• Security Games and Contagion (Extended Abstract)

  2012cites this paper
• Which Security Games are Hard to Solve ?

  2012cites this paper
• The Deployment-to-Saturation Ratio in Security Games

  2012influential citation
• Simulation-Aided Development of Multi-agent Algorithms for Tactical Missions

  2012cites this paper
• Adversarial patrolling games

  2012cites this paper
• Multi-agent simulation approach to development of applications for decentralized tactical missions

  2012cites this paper
• Computing Stackelberg Equilibria in Discounted Stochastic Games

  2012cites this paper
• Security Games for Controlling Contagion

  2012cites this paper
• A Study of Phase Transitions in Security Games

  2012influential citation
• Adversarial Patrolling Games ( Extended Abstract )

  2012cites this paper
• Using Multi-agent Simulation to Improve the Security of Maritime Transit

  2011cites this paper
• AgentC: Agent-based System for Securing Maritime Transit (Demonstration)

  2011cites this paper
• Security Games with Mobile Players

  2011cites this paper
• AgentC: agent-based system for securing maritime transit

  2011cites this paper