Planning algorithms for interactive storytelling

ABSTRACT

Interactive storytelling (IS) is an important research topic in the broader area of interactive digital entertainment. Research in IS focuses in the search for techniques that allow the creation of systems that can generate stories that change as a consequence of a player's actions. There have been numerous articles attempting to reach this goal by employing a planning algorithm as part of the solution, but they typically do not discuss in detail why a given planning algorithm was used. Given this reality, this article makes two main contributions. First, it proposes an initial set of criteria that can be used to evaluate how well a given planning algorithm fits IS systems. Second, on the basis of these criteria, it presents an analysis using available planning systems.

REFERENCES

• 1: Fahiem Bacchus , Froduald Kabanza, Using temporal logics to express search control knowledge for planning, Artificial Intelligence, v.116 n.1-2, p.123-191, Jan. 2000 [doi>10.1016/S0004-3702(99)00071-5]
• 2: BAL, M. 1998. Teoria de la Narrativa: una introduccion a la narratologia, 5th ed. Catreda, Madrid.
• 3: Leandro Motta Barros , Soraia Raupp Musse, Introducing narrative principles into planning-based interactive storytelling, Proceedings of the 2005 ACM SIGCHI International Conference on Advances in computer entertainment technology, p.35-42, June 15-17, 2005, Valencia, Spain [doi>10.1145/1178477.1178482]
• 4: Avrim L. Blum , Merrick L. Furst, Fast planning through planning graph analysis, Artificial Intelligence, v.90 n.1-2, p.281-300, Feb. 1997 [doi>10.1016/S0004-3702(96)00047-1]
• 5: Blai Bonet , Héctor Geffner, Planning as heuristic search, Artificial Intelligence, v.129 n.1-2, p.5-33, June 2001 [doi>10.1016/S0004-3702(01)00108-4]
• 6: CAVAZZA, M. AND CHARLES, F. 2005. Dialogue generation in character-based interactive storytelling. In Proceedings of the AAAI First Annual Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE'05, Marina del Rey, CA). AAAI Press, Menlo Park, CA.
• 7: CHARLES, F., IBANEZ, M. L., MEAD, S. J., BISQUERRA, A. F., AND CAVAZZA, M. 2003. Planning formalisms and authoring in interactive storytelling. In Proceedings of TIDSE'03: Technologies for Interactive Digital Storytelling and Entertainment, S. Gobel et al. eds. Fraunhofer IRB Verlag, Darmstadt, Germany.
• 8: Angelo E. M. Ciarlini , Cesar T. Pozzer , Antonio L. Furtado , Bruno Feijó, A logic-based tool for interactive generation and dramatization of stories, Proceedings of the 2005 ACM SIGCHI International Conference on Advances in computer entertainment technology, p.133-140, June 15-17, 2005, Valencia, Spain [doi>10.1145/1178477.1178495]
• 9: COLES, A. I. AND SMITH, A. J. 2004. Marvin: Macro-actions from reduced versions of the instance. In Fourth International Planning Competition Booklet (IPS'04), ICAPS 2004.
• 10: Chris Crawford, Chris Crawford on Interactive Storytelling (New Riders Games), New Riders Games, 2004
• 11: EDELKAMP, S. AND HOFFMANN, J. 2004. PDDL2.2: The language for the classical part of the 4th International Planning Competition. Tech. Rep. 195, Albert Ludwigs Univ. Inst. fur Informatik, Freiburg, Germany. Jan.
• 12: FOX, M. AND LONG, D. 2001. Hybrid STAN: Identifying and managing combinatorial optimisation subproblems in planning. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 01, Seattle, WA), B. Nebel, ed. Morgan Kaufmann, 445-452.
• 13: GEREVINI, A., SAETTI, A., SERINA, I., AND TONINELLI, P. 2004. Planning in PDDL2.2 domains with LPG-TD. In Fourth International Planning Competition Booklet (IPS'04), ICAPS 2004.
• 14: GEREVINI, A. AND SERINA, I. 2002. LPG: a planner based on local search for planning graphs. In Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS'02, Toulouse, France). AAAI Press.
• 15: HASLUM, P. AND GEFFNER, H. 2000. Admissible heuristics for optimal planning. In Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2000). 140-149.
• 16: HOFFMANN, J. 2003. The Metric-FF planning system: Translating "ignoring delete lists" to numeric state variables. J. Artificial Intell. Research 20, 291-341.
• 17: HOFFMANN, J. AND NEBEL, B. 2001. The FF planning system: Fast plan generation through heuristic search. J. Artificial Intell. Research 14, 253-302.
• 18: Henry Kautz , Bart Selman, Planning as satisfiability, Proceedings of the 10th European conference on Artificial intelligence, p.359-363, August 1992, Vienna, Austria
• 19: Jana Koehler , Bernhard Nebel , Jörg Hoffmann , Yannis Dimopoulos, Extending Planning Graphs to an ADL Subset, Proceedings of the 4th European Conference on Planning: Recent Advances in AI Planning, p.273-285, September 24-26, 1997
• 20: LEBOWITZ, M. 1985. Story-telling as planning and learning. Poetics 14, 483-502.
• 21: MATEAS, M. AND STERN, A. 2005. Structuring content in the Facade interactive drama architecture. In Proceedings of the AAAI First Annual Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE'05, Marina del Rey, CA). AAAI Press, Menlo Park, CA.
• 22: Mark Riedl , C. J. Saretto , R. Michael Young, Managing interaction between users and agents in a multi-agent storytelling environment, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860694]
• 23: RIEDL, M. O. AND YOUNG, R. M. 2003. Character-focused narrative generation for execution in virtual worlds. In Virtual Storytelling. Proceedings of ICVS 2003: International Conference on Virtual Storytelling (Toulouse, France). Lecture Notes in Computer Science 2897. Springer, New York, 47-56.
• 24: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.0 General
          Subjects: Games

General Terms:
Algorithms, Experimentation

Keywords:
STRIPS-like planning systems, interactive storytelling