Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Abstraction Methods for Solving Graph-Based Security Games

  • Conference paper
  • First Online:

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

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

References

  1. 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

  2. The IUCN Red List of threatened species, April 2015.http://www.iucnredlist.org/

  3. Estimate of global financial losses due to illegal fishing, February 2016.http://www.worldwildlife.org/threats/illegal-fishing

  4. 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

    Chapter  Google Scholar 

  5. 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)

    Google Scholar 

  6. Bowling, M., Burch, N., Johanson, M., Tammelin, O.: Heads-up limit hold’em poker is solved. Science347(6218), 145–149 (2015)

    Article  Google Scholar 

  7. Breton, M., Alj, A., Haurie, A.: Sequential Stackelberg equilibria in two-person games. J. Optim. Theory Appl.59(1), 71–97 (1988)

    Article MathSciNet MATH  Google Scholar 

  8. 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

    Google Scholar 

  9. 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)

    Google Scholar 

  10. 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)

    Google Scholar 

  11. 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)

    Google Scholar 

  12. Field, C., Laws, R.: The distribution of the larger herbivores in the Queen Elizabeth National Park, Uganda. J. Appl. Ecol. 273–294 (1970)

    Google Scholar 

  13. 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)

    Google Scholar 

  14. 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

    Chapter  Google Scholar 

  15. Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact routing in large road networks using contraction hierarchies. Transp. Sci.46, 388–404 (2012)

    Article  Google Scholar 

  16. 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)

    Google Scholar 

  17. 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)

    Google Scholar 

  18. Gilpin, A., Sandholm, T.: Lossless abstraction of imperfect information games. J. ACM (JACM)54(5), 25 (2007)

    Article MathSciNet MATH  Google Scholar 

  19. 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)

    Google Scholar 

  20. 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)

    Google Scholar 

  21. 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)

    Google Scholar 

  22. 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)

    Google Scholar 

  23. 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)

    Google Scholar 

  24. 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)

    Google Scholar 

  25. Leitmann, G.: On generalized stackelberg strategies. J. Optim. Theory Appl.26(4), 637–643 (1978)

    Article MathSciNet MATH  Google Scholar 

  26. 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

    Chapter  Google Scholar 

  27. 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)

    Google Scholar 

  28. 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)

    Article  Google Scholar 

  29. Sandholm, T., Singh, S.: Lossy stochastic game abstraction with bounds. In: Proceedings of the 13th ACM Conference on Electronic Commerce, pp. 880–897 (2012)

    Google Scholar 

  30. 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)

    Google Scholar 

  31. Skiena, S.: Dijkstra’s Algorithm. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, pp. 225–227. Addison-Wesley, Reading (1990)

    Google Scholar 

  32. 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)

    Google Scholar 

  33. Tsai, J., Kiekintveld, C., Ordonez, F., Tambe, M., Rathi, S.: Iris-a tool for strategic security allocation in transportation networks (2009)

    Google Scholar 

  34. Von Stengel, B., Zamir, S.: Leadership with commitment to mixed strategies (2004)

    Google Scholar 

  35. 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)

    Google Scholar 

  36. 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)

    Google Scholar 

  37. 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)

    Google Scholar 

  38. 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)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Texas at El Paso, 500 W University Ave, El Paso, TX, 79902, USA

    Anjon Basak & Christopher Kiekintveld

  2. University of Southern California, 941 Bloom Walk, SAL 300, Los Angeles, CA, 90089, USA

    Fei Fang & Thanh Hong Nguyen

Authors
  1. Anjon Basak

    You can also search for this author inPubMed Google Scholar

  2. Fei Fang

    You can also search for this author inPubMed Google Scholar

  3. Thanh Hong Nguyen

    You can also search for this author inPubMed Google Scholar

  4. Christopher Kiekintveld

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toAnjon Basak.

Editor information

Editors and Affiliations

  1. Campus de la UAB, IIIA-CSIC, Bellaterra, Spain

    Nardine Osman

  2. 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

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only


[8]ページ先頭

©2009-2025 Movatter.jp