Part of the book series:Lecture Notes in Computer Science ((LNAI,volume 10003))
Included in the following conference series:
Abstract
Many real-world security problems can be modeled using Stackelberg security games (SSG), which model the interactions between defender and attacker.Green security games focus on environmental crime, such as preventing poaching, illegal logging, or detecting pollution. A common problem in green security games is to optimize patrolling strategies for a large physical area such as a national park or other protected area. Patrolling strategies can be modeled as paths in a graph that represents the physical terrain. However, having a detailed graph to represent possible movements in a very large area typically results in an intractable computational problem due to the extremely large number of potential paths. While a variety of algorithmic approaches have been explored in the literature to solve security games based on large graphs, the size of games that can be solved is still quite limited. Here, we introduce abstraction methods for solving large graph-based security games. We demonstrate empirically that these abstraction methods can result in dramatic improvements in solution time with modest impact on solution quality.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Govt of Mozambique announces major decline in national elephant population (May 2015).http://press.wcs.org/News-Releases/articleType/ArticleView/articleId/6760/Government-of-Mozambique-Releases-Elephant-Population-Numbers.aspx
The IUCN Red List of threatened species, April 2015.http://www.iucnredlist.org/
Estimate of global financial losses due to illegal fishing, February 2016.http://www.worldwildlife.org/threats/illegal-fishing
Batz, G.V., Geisberger, R., Neubauer, S., Sanders, P.: Time-dependent contraction hierarchies and approximation. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 166–177. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13193-6_15
Billings, D., Burch, N., Davidson, A., Holte, R., Schaeffer, J., Schauenberg, T., Szafron, D.: Approximating game-theoretic optimal strategies for full-scale poker. In: The International Joint Conference on Artificial Intelligence (IJCAI), pp. 661–668 (2003)
Bowling, M., Burch, N., Johanson, M., Tammelin, O.: Heads-up limit hold’em poker is solved. Science347(6218), 145–149 (2015)
Breton, M., Alj, A., Haurie, A.: Sequential Stackelberg equilibria in two-person games. J. Optim. Theory Appl.59(1), 71–97 (1988)
Brown, M., Haskell, W.B., Tambe, M.: Addressing scalability and robustness in security games with multiple boundedly rational adversaries. In: Poovendran, R., Saad, W. (eds.) GameSec 2014. LNCS, vol. 8840, pp. 23–42. Springer, Heidelberg (2014). doi:10.1007/978-3-319-12601-2_2
Brown, N., Ganzfried, S., Sandholm, T.: Hierarchical abstraction, distributed equilibrium computation, and post-processing, with application to a champion no-limit Texas hold’em agent. Technical report (2014)
Fang, F., Nguyen, T.H., Pickles, R., Lam, W.Y., Clements, G.R., An, B., Singh, A., Tambe, M., Lemieux, A.: Deploying paws: field optimization of the protection assistant for wildlife security. In: Proceedings of the Innovative Applications of Artificial Intelligence (IAAI) (2016)
Fang, F., Stone, P., Tambe, M.: When security games go green: designing defender strategies to prevent poaching and illegal fishing. In: International Joint Conference on Artificial Intelligence (IJCAI) (2015)
Field, C., Laws, R.: The distribution of the larger herbivores in the Queen Elizabeth National Park, Uganda. J. Appl. Ecol. 273–294 (1970)
Ganzfried, S., Sandholm, T.: Potential-aware imperfect-recall abstraction with earth mover’s distance in imperfect-information games. In: Conference on Artificial Intelligence (AAAI) (2014)
Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 319–333. Springer, Heidelberg (2008). doi:10.1007/978-3-540-68552-4_24
Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact routing in large road networks using contraction hierarchies. Transp. Sci.46, 388–404 (2012)
Gilpin, A., Sandholm, T.: A competitive texas hold’em poker player via automated abstraction and real-time equilibrium computation. In: Proceedings of the National Conference on Artificial Intelligence (AAAI), vol. 21, p. 1007 (2006)
Gilpin, A., Sandholm, T.: Better automated abstraction techniques for imperfect information games, with application to texas hold’em poker. In: International Foundation for Autonomous Agents and Multiagent Systems (AAMAS), p. 192 (2007)
Gilpin, A., Sandholm, T.: Lossless abstraction of imperfect information games. J. ACM (JACM)54(5), 25 (2007)
Gilpin, A., Sandholm, T., Sørensen, T.B.: Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of texas hold’em poker. In: Proceedings of the Conference on Artificial Intelligence (AAAI), vol. 22, p. 50 (2007)
Gilpin, A., Sandholm, T., Sørensen, T.B.: A heads-up no-limit texas hold’em poker player: discretized betting models and automatically generated equilibrium-finding programs. In: International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 911–918 (2008)
Haskell, W.B., Kar, D., Fang, F., Tambe, M., Cheung, S., Denicola, E.: Robust protection of fisheries with compass. In: Association for the Advancement of Artificial Intelligence (AAAI), pp. 2978–2983 (2014)
Jain, M., Kardes, E., Kiekintveld, C., Ordónez, F., Tambe, M.: Security games with arbitrary schedules: a branch and price approach. In: Association for the Advancement of Artificial Intelligence (AAAI) (2010)
Kiekintveld, C., Jain, M., Tsai, J., Pita, J., Ordóñez, F., Tambe, M.: Computing optimal randomized resource allocations for massive security games. In: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-, vol. 1, pp. 689–696. International Foundation for Autonomous Agents and Multiagent Systems (AAMAS) (2009)
Kroer, C., Sandholm, T.: Extensive-form game abstraction with bounds. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation, pp. 621–638 (2014)
Leitmann, G.: On generalized stackelberg strategies. J. Optim. Theory Appl.26(4), 637–643 (1978)
Nguyen, T.H., Fave, F.M.D., Kar, D., Lakshminarayanan, A.S., Yadav, A., Tambe, M., Agmon, N., Plumptre, A.J., Driciru, M., Wanyama, F., Rwetsiba, A.: Making the most of our regrets: regret-based solutions to handle payoff uncertainty and elicitation in green security games. In: Khouzani, M.H.R., Panaousis, E., Theodorakopoulos, G. (eds.) GameSec 2015. LNCS, vol. 9406, pp. 170–191. Springer, Heidelberg (2015). doi:10.1007/978-3-319-25594-1_10
Paruchuri, P., Pearce, J.P., Marecki, J., Tambe, M., Ordonez, F., Kraus, S.: Playing games for security: an efficient exact algorithm for solving bayesian stackelberg games. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, vol. 2, pp. 895–902. International Foundation for Autonomous Agents and Multiagent Systems (AAMAS) (2008)
Pita, J., Bellamane, H., Jain, M., Kiekintveld, C., Tsai, J., Ordóñez, F., Tambe, M.: Security applications: lessons of real-world deployment. ACM SIGecom Exchanges8(2), 5 (2009)
Sandholm, T., Singh, S.: Lossy stochastic game abstraction with bounds. In: Proceedings of the 13th ACM Conference on Electronic Commerce, pp. 880–897 (2012)
Shieh, E., An, B., Yang, R., Tambe, M., Baldwin, C., DiRenzo, J., Maule, B., Meyer, G.: Protect: a deployed game theoretic system to protect the ports of the united states. In: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, vol. 1, pp. 13–20. International Foundation for Autonomous Agents and Multiagent Systems (AAMAS) (2012)
Skiena, S.: Dijkstra’s Algorithm. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, pp. 225–227. Addison-Wesley, Reading (1990)
Storandt, S.: Route planning for bicycles-exact constrained shortest paths made practical via contraction hierarchy. In: International Conference on Automated Planning and Scheduling (ICAPS), vol. 4, p. 46 (2012)
Tsai, J., Kiekintveld, C., Ordonez, F., Tambe, M., Rathi, S.: Iris-a tool for strategic security allocation in transportation networks (2009)
Von Stengel, B., Zamir, S.: Leadership with commitment to mixed strategies (2004)
Yang, R., Ford, B., Tambe, M., Lemieux, A.: Adaptive resource allocation for wildlife protection against illegal poachers. In: Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, pp. 453–460. International Foundation for Autonomous Agents and Multiagent Systems (AAMAS) (2014)
Yang, R., Jiang, A.X., Tambe, M., Ordonez, F.: Scaling-up security games with boundedly rational adversaries: a cutting-plane approach. In: The International Joint Conference on Artificial Intelligence (IJCAI) (2013)
Yin, Z., Jiang, A.X., Tambe, M., Kiekintveld, C., Leyton-Brown, K., Sandholm, T., Sullivan, J.P.: Trusts: scheduling randomized patrols for fare inspection in transit systems using game theory. AI Mag.33(4), 59 (2012)
Zinkevich, M., Johanson, M., Bowling, M., Piccione, C.: Regret minimization in games with incomplete information. In: Advances in Neural Information Processing Systems (NIPS), pp. 1729–1736 (2007)
Author information
Authors and Affiliations
University of Texas at El Paso, 500 W University Ave, El Paso, TX, 79902, USA
Anjon Basak & Christopher Kiekintveld
University of Southern California, 941 Bloom Walk, SAL 300, Los Angeles, CA, 90089, USA
Fei Fang & Thanh Hong Nguyen
- Anjon Basak
You can also search for this author inPubMed Google Scholar
- Fei Fang
You can also search for this author inPubMed Google Scholar
- Thanh Hong Nguyen
You can also search for this author inPubMed Google Scholar
- Christopher Kiekintveld
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toAnjon Basak.
Editor information
Editors and Affiliations
Campus de la UAB, IIIA-CSIC, Bellaterra, Spain
Nardine Osman
Campus de la UAB, IIIA-CSIC, Cerdanyola, Spain
Carles Sierra
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Basak, A., Fang, F., Nguyen, T.H., Kiekintveld, C. (2016). Abstraction Methods for Solving Graph-Based Security Games. In: Osman, N., Sierra, C. (eds) Autonomous Agents and Multiagent Systems. AAMAS 2016. Lecture Notes in Computer Science(), vol 10003. Springer, Cham. https://doi.org/10.1007/978-3-319-46840-2_2
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-319-46839-6
Online ISBN:978-3-319-46840-2
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative