Proceedings

Counterplanning using Goal Recognition and Landmarks

Download BibTeX Cite

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Main track. Pages 4808-4814.

https://doi.org/10.24963/ijcai.2018/668

Abstract

In non-cooperative multi-agent systems, agents might want to prevent the opponents from achieving their goals. One alternative to solve this task would be using counterplanning to generate a plan that allows an agent to block other's to reach their goals. In this paper, we introduce a fully automated domain-independent approach for counterplanning. It combines; goal recognition to infer an opponent's goal; landmarks' computation to identify subgoals that can be used to block opponents' goals achievement; and classical automated planning to generate plans that prevent the opponent's goals achievement. Experimental results in several domains show the benefits of our novel approach.

  1. [Albrecht et al., 1997] David W. Albrecht, Ingrid Zukerman, Ann E. Nicholson, and Ariel Bud. Towards a bayesian model for keyhole plan recognition in large domains. In User Modeling, pages 365-376. Springer, 1997.
  2. [Boddy et al., 2005] Mark S. Boddy, Johnathan Gohde, Thomas Haigh, and Steven A. Harp. Course of action generation for cyber security using classical planning. In ICAPS, 2005.
  3. [Borck et al., 2015] Hayley Borck, Justin Karneeb, Ron Al- ford, and David W. Aha. Case-based behavior recognition in beyond visual range air combat. In FLAIRS, 2015.
  4. [Carbonell, 1978] Jaime G. Carbonell. Politics: Automated ideological reasoning. Cognitive Science, 2(1):27-51, 1978.
  5. [Carbonell, 1981] Jaime G. Carbonell. Counterplanning: A strategy-based model of adversary planning in real-world situations. Artificial Intelligence, 16(3):295-329, 1981.
  6. [Cox, 2007] Michael T. Cox. Perpetual self-aware cognitive agents. AI magazine, 28(1):32, 2007.
  7. [E-Martín et al., 2015] Yolanda E-Martín, María D. R- Moreno, and David E Smith. A fast goal recognition tech- nique based on Interaction estimates. In IJCAI, 2015. IJCAI
  8. [Edelkamp et al., 2009] Stefan Edelkamp, Carsten Elfers, Mirko Horstmann, Marcus-Sebastian Schröder, Karsten Sohr, and Thomas Wagner. Early warning and intrusion detection based on combined AI methods. In ICAPS, 2009.
  9. [Geib and Goldman, 2009] Christopher W. Geib and Robert P. Goldman. A probabilistic plan recognition algo- rithm based on plan tree grammars. Artificial Intelligence, 173(11):1101-1132, 2009.
  10. [Ghallab et al., 2004] Malik Ghallab, Dana Nau, and Paolo Traverso. Automated Planning: theory and practice. El- sevier, 2004.
  11. [Haslum, 2008] Patrik Haslum. Additive and reversed re- laxed reachability heuristics revisited. International Plan- ning Competition, 2008.
  12. [Hoffmann et al., 2004] Jörg Hoffmann, Julie Porteous, and Laura Sebastia. Ordered landmarks in planning. Journal of Artificial Intelligence Research, 22:215-278, 2004.
  13. [Hoffmann, 2015] Jörg Hoffmann. Simulated penetration testing: From" dijkstra" to" turing test++". In ICAPS, 2015.
  14. [Jarvis et al., 2005] Peter A. Jarvis, Teresa F. Lunt, and Karen L. Myers. Identifying terrorist activity with ai plan recognition technology. AI Magazine, 26(3):73, 2005.
  15. [Kabanza et al., 2010] Froduald Kabanza, Philipe Belle- feuille, Francis Bisson, Abder Rezak Benaskeur, and Hengameh Irandoust. Opponent behaviour recognition for real-time strategy games. In AAAI Workshop on Plan, Ac- tivity, and Intent Recognition, 2010.
  16. [Molineaux et al., 2010] Matthew Molineaux, Matthew Klenk, and David W. Aha. Goal-driven autonomy in a navy strategy simulation. In AAAI, 2010.
  17. [Obes et al., 2013] Jorge Lucangeli Obes, Carlos Sarraute, and Gerardo Richarte. Attack planning in the real world. arXiv preprint arXiv:1306.4044, 2013.
  18. [Ontañón et al., 2013] Santiago Ontañón, Gabriel Synnaeve, Alberto Uriarte, Florian Richoux, David Churchill, and Mike Preuss. A survey of real-time strategy game ai re- search and competition in starcraft. IEEE Transactions on Computational Intelligence and AI in games, 5(4):293- 311, 2013.
  19. [Pattison and Long, 2010] David Pattison and Derek Long. Domain independent goal recognition. In STAIRS, 2010.
  20. [Pereira et al., 2017] Ramon Fraga Pereira, Nir Oren, and Felipe Meneguzzi. Landmark-based heuristics for goal recognition. In AAAI, 2017.
  21. [Ramírez and Geffner, 2009] Miquel Ramírez and Hector Geffner. Plan recognition as planning. In IJCAI, 2009. IJCAI
  22. [Ramírez and Geffner, 2010] Miquel Ramírez and Hector Geffner. Probabilistic plan recognition using off-the-shelf classical planners. In AAAI, 2010.
  23. [Ramírez and Geffner, 2011] Miquel Ramírez and Hector Geffner. Goal recognition over POMDPs: Inferring the intention of a POMDP agent. In IJCAI, 2011. IJCAI
  24. [Richter and Westphal, 2010] Silvia Richter and Matthias Westphal. The LAMA planner: Guiding cost-based any- time planning with landmarks. Journal of Artificial Intel- ligence Research, 39:127-177, 2010.
  25. [Richter et al., 2011] Silvia Richter, Matthias Westphal, and Malte Helmert. LAMA 2008 and 2011. In International Planning Competition, 2011.
  26. [Rowe, 2003] Neil C. Rowe. Counterplanning deceptions to foil cyber-attack plans. In IEEE Workshop on Systems, Man and Cybernetics Society, 2003.
  27. [Sarraute et al., 2012] Carlos Sarraute, Olivier Buffet, and Jörg Hoffmann. POMDPs make better hackers: Account- ing for uncertainty in penetration testing. In AAAI, 2012.
  28. [Sukthankar et al., 2014] Gita Sukthankar, Christopher Geib, Hung Hai Bui, David Pynadath, and Robert P. Goldman. Plan, activity, and intent recognition: theory and practice. Newnes, 2014.
  29. [Vered and Kaminka, 2017] Mor Vered and Gal A. Kaminka. Heuristic online goal recognition in continuous domains. In IJCAI, 2017. IJCAI
  30. [Weber et al., 2010] Ben George Weber, Michael Mateas, and Arnav Jhala. Applying goal-driven autonomy to star- craft. In AIIDE, 2010.
  31. [Willmott et al., 2001] Steven Willmott, Julian Richardson, Alan Bundy, and John Levine. Applying adversarial plan- ning techniques to Go. Theoretical Computer Science, 252(1-2):45-82, 2001.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards