A graph-theoretic approach to protect static and moving targets from adversaries

J. P. Dickerson, G. I. Simari, V. S. Subrahmanian, Sarit Kraus

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Scopus citations

Abstract

The static asset protection problem (SAP) in a road network is that of allocating resources to protect vertices, given any possible behavior by an adversary determined to attack those assets. The dynamic asset protection (DAP) problem is a version of SAP where the asset is following a fixed and widely known route (e.g., a parade route) and needs to bo protected. We formalize what it means for a given allocation of resources to be "optimal" for protecting a desired set of assets, and show that randomly allocating resources to a single edge cut in the road network solves this problem. Unlike SAP, we show that DAP is not only an NP-complete problem, but that approximating DAP is also NP-hard. We provide the GreedyDAP heuristic algorithm to solve DAP and show experimentally that it works well in practice, using road network data for real cities.

Original languageEnglish (US)
Title of host publication9th International Joint Conference on Autonomous Agents and Multiagent Systems 2010, AAMAS 2010
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages299-306
Number of pages8
ISBN (Print)9781617387715
StatePublished - 2010
Externally publishedYes
Event9th International Joint Conference on Autonomous Agents and Multiagent Systems 2010, AAMAS 2010 - Toronto, ON, Canada
Duration: May 10 2010 → …

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume1
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference9th International Joint Conference on Autonomous Agents and Multiagent Systems 2010, AAMAS 2010
Country/TerritoryCanada
CityToronto, ON
Period5/10/10 → …

Keywords

  • Adversarial Reasoning
  • Agent Systems
  • Game Theory

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'A graph-theoretic approach to protect static and moving targets from adversaries'. Together they form a unique fingerprint.

Cite this