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. BACCHUS, F. AND KABANZA, F. 2000. Using temporal logics to express search control knowledge for planning. Artificial Intell. 116, 1-2, 123-191.
2. BAL, M. 1998. Teoria de la Narrativa: una introduccion a la narratologia, 5th ed. Catreda, Madrid.
3. BARROS, L. M. AND MUSSE, S. R. 2005. Introducing narrative principles into planning-based interactive storytelling. In Proceedings of ACM SIGCHI International Conference on Advances in Computer Entertainment Technology (ACE 2005, Valencia, Spain), S. Z. ZhiYing and L. S. Ping, eds. ACM, New York, 35-42.
4. BLUM, A. AND FURST, M. 1997. Fast planning through planning graph analysis. Artificial Intell.90, 281-300.
5. BONET, B. AND GEFFNER, H. 2001. Planning as heuristic search. Artificial Intell. 1, 129, 5-33.
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. CIARLINI, A. E. M., POZZER, C. T., FURTADO, A. L., AND FEIJO, B. 2005. A logic-based tool for interactive generation and dramatization of stories. In Proceedings of ACM SIGCHI International Conference on Advances in Computer Entertainment Technology (ACE 2005, Valencia, Spain), S. Z. ZhiYing and L. S. Ping, eds. ACM, New York, 133-140.
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. CRAWFORD, C. 2004. Chris Crawford on Interactive Storytelling. New Riders Games, Indianapolis, IN.
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. KAUTZ, H. A. AND SELMAN, B. 1992. Planning as satisfiability. In Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI'92, Vienna), B. Neumann, ed. Wiley, New York, 359-363.
19. KOEHLER, J., NEBEL, B., HOFFMANN, J., AND DIMOPOULOS, Y. 1997. Extending planning graphs to an ADL subset. In Recent Advances in AI Planning. Fourth European Conference on Planning (ECP'97, Toulouse, France), Lecture Notes in Artificial Intelligence, 1348, S. Steel and R. Alami, eds. Springer, New York, 273-285.
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. RIEDL, M. O., SARETTO, C. J., AND YOUNG, R. M. 2003. Managing interaction between users and agents in a multi-agent storytelling environment. In Proceedings of AAMAS 2003: the Second International Joint Conference on Autonomous Agents and Multi-Agent Systems (Melbourne). ACM New York.
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. RUSSELL, S. AND NORVIG, P. 2002. Artificial Intelligence: A Modern Approach, 2nd ed. Prentice Hall, Englewood Cliffs, NJ.

Index Terms

• Applied computing

  • Computers in other domains

    • Personal computers and PC applications

      • Computer games

• Computing methodologies

  • Artificial intelligence

    • Planning and scheduling

• Information systems

  • Information systems applications

    • Multimedia information systems

      • Massively multiplayer online games

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Virtual worlds software

        • Interactive games

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design