TL;DR
This paper surveys the field of narrative planning, which uses automated planning techniques to generate, communicate, and understand stories. It argues that narrative planning is crucial for AI systems to interact with humans more effectively and explores the challenges and diverse approaches within this interdisciplinary field.
What Problem Does This Paper Address?
The paper addresses the challenge of enabling AI systems to understand, generate, and communicate stories. While humans naturally engage with narratives, building AI that can do so requires formalizing complex concepts like plot, discourse, and narration. This is a significant problem because storytelling is fundamental to human cognition and communication, and AI systems that can master it would unlock new possibilities in areas like personalized learning, healthcare, and intelligence analysis. The authors aim to provide a comprehensive overview of the current state of narrative planning, highlighting its foundational concepts, methodologies, and open challenges for the broader AI community.
Methods
The paper frames narrative planning as a "story director" problem, where an AI agent crafts a narrative plan. This involves adapting classical AI planning techniques (like STRIPS) to represent narrative elements. The authors discuss three key planning paradigms:
- Plan-space Planning: This approach focuses on refining partial plans by identifying and fixing "flaws" that violate narrative quality, such as ensuring character intentions are believable or motivations are clear.
- Hierarchical Planning: This method uses abstract compound actions that can be decomposed into sub-plans, allowing for more expressive modeling of narrative phenomena across plot, discourse, and narration layers. It enables authors to exert more control over narrative quality.
- Heuristic Search: This is the dominant approach, using forward search through state space with domain-independent heuristics. The challenge here is encoding narrative-theoretic phenomena effectively to leverage the efficiency of heuristic search.
The paper also distinguishes between different layers of narrative: plot (events and world evolution), discourse (informational and intentional structure of communication), and narration (the medium of presentation).
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Narrative Planning is Inherently Design-Oriented: The quality of a narrative is assessed relative to authorial intent, making it a design task rather than a purely technical optimization problem. This means there's no single "right" way to plan a story, but rather "better" or "worse" approaches depending on the desired narrative effects.
- Beyond Classical Planning Goals: Narrative planning must go beyond simply achieving a set of goal conditions (G). It needs to account for authorial intent through the process of plan construction, ensuring qualities like comprehensibility and believability.
- The Importance of "Flaws" and "Fixes": In plan-space planning, narrative-specific flaws (e.g., "Unknown Intent," "Open Motivation") and their corresponding fixes are crucial for modeling narrative quality, particularly character believability.
- Narrative Layers Require Different Formalisms: Plot planning often resembles multi-agent planning, discourse planning deals with audience belief dynamics, and narration planning is less explored but crucial for realizing the story in a medium.
- Convergence on "Fundamental Particles": Despite diverse motivations, narrative planning communities converge on core concepts like characters, locations, and actions, which are fundamental to human mental models of stories.
- Causal Coherence is Key for Comprehensibility: A causally coherent narrative plan is essential for audiences to derive temporal sequences and understand the story.
- Believability and Motivational Coherence: For a story to be believable, actions must be motivated, not just causally linked. This often requires modeling character intentions.
Key Results
The paper is a survey and conceptual framework, not an empirical study with quantitative results. Its primary contribution is the structured overview and synthesis of the narrative planning field, highlighting:
- The core problem of formalizing narrative for AI.
- The three main planning paradigms used (plan-space, hierarchical, heuristic search).
- The key narrative-theoretic concepts that need to be modeled (plot, discourse, narration, character intentions, believability, causal coherence).
- The distinction between outcome goals and trajectory goals.
- The identification of open challenges, particularly increasing expressive range and incorporating cognitive-driven generation.
Limitations and Future Work
Limitations:
- The paper acknowledges that a universal set of narrative dimensions is unlikely due to the design-oriented nature of storytelling.
- While plan-space planning offers theoretical guarantees, its performance can be a drawback.
- Narration planning (realizing the story in a specific medium) is relatively under-explored compared to plot and discourse planning.
Future Work:
- Expanding Expressive Range: Developing planning systems that can capture a wider breadth of structural features in narrative output, including actions that fail, explicit conflict, and controlled uncertainty.
- Cognitive-Driven Narrative Generation: Strengthening the connection between narrative generation and comprehension, by better accounting for how human readers construct mental models of stories during generation.
- Co-evolving Plot, Discourse, and Narration: Moving beyond the traditional NLG pipeline to simultaneously develop all layers of narrative.
- Leveraging Heuristic Search: Finding better ways to encode narrative-theoretic phenomena to take advantage of efficient heuristic search approaches.
Summary updated