Stackelberg Surveillance

Bikramjit Banerjee, Landon Kraemer


Bayesian Stackelberg game theory has recently been applied for security-resource allocation at ports and airports, transportation, shipping and infrastructure, modeled as security games. We model the interactions in a camera surveillance problem as a security game, and show that the Stackelberg equilibrium of this game can be formulated as the solution to a non-linear program (NLP). We provide two approximate solutions to this formulation: (a) a linear approximation based on an existing approach (called ASAP), and (b) a hill-climbing based policy search approximation. The rst reduces the problem to a single (but dicult) linear program, while the second reduces it to a set of (easier) linear programs. We consider two variants of the problem: one where the camera is visible, and another where it is contained in a tinted enclosure. We show experimental results comparing our approaches to standard NLP solvers.

Full Text:



K. Fujimura and H. Samet. Planning a time-

minimal motion among moving obstacles. Algo-

rithmica, 10:41{63, 1993.

V. Lesser, C. Ortiz, and M. Tambe, editors. Dis-

tributed Sensor Networks: A multi-agent perspec-

tive. Kluwer, 2003.

J. Park, J.S. Choi, J. Kim, S. Ji, and B.H. Lee.

Long-term stealth navigation in a security zone

where the movement of the invader is moni-

tored. International Journal of Control, Automa-

tion and Systems, 8(3):604{614, 2010.

P. Paruchuri, J.P. Pearce, M. Tambe, F. Ordonez,

and S. Kraus. An ecient heuristic approach for

security against multiple adversaries. In Proc. 6th

Intl. AAMAS Conference, 2007.

J. Pita, M. Jain, J. Marecki, F. Ordonez, C. Port-

way, M. Tambe, C. Western, P. Paruchuri, and

S. Kraus. Deployed ARMOR protection: The ap-

plication of a game-theoretic model for security at

the Los Angeles International Airport. In Proc.

th Intl. AAMAS Conference, 2008.

J. Pita, M. Tambe, C. Kiekintveld, S. Cullen, and

E. Steigerwald. GUARDS: Game theoretic secu-

rity allocation on a national scale. In Proc. 10th

Intl. AAMAS Conference, 2011.

M. Tambe. Security and Game Theory. Cam-

bridge University Press, 2012.

J. Tsai, S. Rathi, C. Kiekintveld, F. Ordonez, and

M. Tambe. IRIS-A tool for strategic security al-

location in transportation networks. In Proc. 8th

Intl. AAMAS Conference, 2009.

Website. NEOS Server: State-of-the-art solvers

for numerical optimization. http://www.neos-

R. Zivan, R. Glinton, and K. Sycara. Distributed

constraint optimization for large teams of mobile

sensing agents. In Proc. International Confer-

ence on Intelligent Agent Technology (IAT), pages

{354, 2009.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.