Stackelberg Surveillance

Abstract

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.

References

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-

server.org/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.

Vol 39, No 4 (2015)

Authors

  • Bikramjit Banerjee The University of Southern Mississippi School of Computing 118 College Dr. #5106 Hattiesburg, MS 39406, U.S.A
  • Landon Kraemer The University of Southern Mississippi School of Computing 118 College Dr. #5106 Hattiesburg, MS 39406, U.S.A

Downloads

Published

12/22/2015

How to Cite

Banerjee, B., & Kraemer, L. (2015). Stackelberg Surveillance. Informatica, 39(4). Retrieved from https://www.informatica.si/index.php/informatica/article/view/1084

Issue

Vol. 39 No. 4 (2015)

Section

Regular papers

License

Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.

All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.

Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.