Stackelberg Surveillance

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

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)

Downloads

Published

2015-12-22

How to Cite

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

Issue

Vol. 39 No. 4 (2015)

Section

Regular papers

License

I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.

I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.

In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.

I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal.  The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.


Copyright ©  Slovenian Society Informatika