Friday, February 12, 2010

A Graph-Theoretic Approach to Protect Static and Moving Targets from Adversaries

A few days ago, I submitted the camera-ready version of our AAMAS-2010 paper. The abstract, provided below, is a slightly edited version of that which was initially submitted back in October.

A Graph-Theoretic Approach to Protect Static and Moving Targets from Adversaries
J.P. Dickerson, G.I. Simari, V.S. Subrahmanian and Sarit Kraus

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 be 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.

Basically, given some set of targets T and some set of "enemy" source nodes S, we discuss methods to either protect from S a static T or choose an optimally protected path between two target nodes within T. The paper draws heavily from graph theory, game theory, and network interdiction.

A copy of the paper can be found here: PDF Link.

BibTeX citation information is here.