Patrolling security games: definition and algorithms for solving large instances with single patroller and single intruder

DOI10.1016/j.artint.2012.03.003zbMath1251.68254OpenAlexW2032243783WikidataQ115101553 ScholiaQ115101553MaRDI QIDQ1761280

Nicola Gatti, Francesco Amigoni, Nicola Basilico

Publication date: 15 November 2012

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2012.03.003

zbMATH Keywords

algorithmic game theorysecurity gamesadversarial patrolling

Mathematics Subject Classification ID

Noncooperative games (91A10) 2-person games (91A05) Applications of game theory (91A80) Artificial intelligence for robotics (68T40)

Related Items (17)

Infrastructure security games ⋮ Optimizing periodic patrols against short attacks on the line and other networks ⋮ Patrolling a Pipeline ⋮ Technical Note—Optimal Patrol of a Perimeter ⋮ Continuous Patrolling Games ⋮ Adversarial patrolling with spatially uncertain alarm signals ⋮ Patrolling a Border ⋮ On the approximation ratio of the random Chinese postman tour for network search ⋮ A two‐stage network interdiction‐monitoring game ⋮ Continuous patrolling and hiding games ⋮ A Monte Carlo tree search approach to finding efficient patrolling schemes on graphs ⋮ Adiabatic quantum games and phase-transition-like behavior between optimal strategies ⋮ A dynamic extremum seeking scheme for three-player attack-defense with unknown gradient ⋮ Multi-robot adversarial patrolling: handling sequential attacks ⋮ Multi-robot adversarial patrolling strategies via lattice paths ⋮ Static search games played over graphs and general metric spaces ⋮ Adversarial Patrolling in a Uniform

Uses Software

• AMPL
• GameShrink
• Radish

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Modeling Language for Mathematical Programming
• Temporal linear relaxation in IBM ILOG CP optimizer
• Multi-robot area patrol under frequency constraints
• Patrol mobile robots and chaotic trajectories
• A practical solution approach for the cyclic inventory routing problem
• Search games
• Infiltration games on arbitrary graphs
• Efficient computation of equilibria for extensive two-person games
• A distributed ant algorithm for efficiently patrolling a network
• The period routing problem
• Lossless abstraction of imperfect information games
• Multiagent Systems
• Vehicle Routing with Time Windows
• Perfect Equilibrium in a Bargaining Model
• Sequential Equilibria
• Special cases of traveling salesman and repairman problems with time windows
• Ambushing Random Walks I: Finite Models
• Randomized Pursuit-Evasion in Graphs
• Two-Person Zero-Sum Games for Network Interdiction
• Nonlinear Programming
• The Hide and Seek Game of Von Neumann

This page was built for publication: Patrolling security games: definition and algorithms for solving large instances with single patroller and single intruder