Sunday, October 18, 2009

Asset Protection

Finally submitted my first (real) academic paper this week, to the AAMAS (Autonomous Agents and Multi-Agent Systems) 2010 conference in Toronto. Hopefully it will get accepted, although their roughly 20% acceptance rate does not bode well.

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. We develop a polynomial time algorithm for SAP and experimentally show that it works effectively in practice. We also formalize DAP. 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.

My (out of date) writeup on the project can be found here.

Labels: , , ,


Post a Comment

Subscribe to Post Comments [Atom]

<< Home