Abstract
Traditional AI planning often fails to capture the messy, emergent nature of storytelling. This paper presents Continual Multiagent Planning (CMP), a framework that models characters as autonomous agents with their own beliefs, desires, and emotions. By allowing plans to be adapted in real-time based on local perceptions, CMP generates narratives where drama arises from conflicting goals and information gaps.
Introduction
In traditional AI storytelling, planning is typically a top-down process resulting in a static sequence of actions. However, believable narratives require characters that act based on their own, often flawed, perceptions of the world. The gap between classical planning and "Narrative Intelligence"—incorporating motivation, emotion, and social interaction—remains a significant challenge. This paper addresses this by moving from a "God's eye view" to a multiagent system where the plot is an emergent property of character interactions.
The CMP Framework
The system relies on two core components: the Multiagent Planning Language (MAPL) and the Continual Multiagent Planning (CMP) algorithm.
MAPL extends standard planning languages like PDDL by using multi-valued state variables. This enables the modeling of "unknown" values and, crucially, nested beliefs (e.g., what Character A believes about Character B's knowledge). It also introduces "assertions"—counterfactual statements that drive characters to proactively seek information.
CMP serves as the execution engine. Unlike traditional planners that generate a complete plan before acting, CMP agents alternate between planning, executing a single step, and monitoring the environment. This "continual" approach allows agents to detect when a plan has been thwarted—such as a dragon appearing unexpectedly—and trigger an immediate replan.
Key Insights: Plots as Execution Histories
A central insight of this work is that a story plot is not a pre-defined plan, but rather the history of plans being made, executed, and revised. The resulting "plot graph" captures not just the physical actions, but the underlying motivations and (potentially false) beliefs.
As seen in the figure above, the system models mixed-initiative behavior. When Prince Valiant is asked to give a treasure to King Arthur, he realizes he does not know its location. This triggers a sub-dialogue where he requests the information from Arthur before proceeding with his primary goal. This causal coherence is essential for generating natural language descriptions of why characters act as they do.
Evaluation and Results
The framework was tested in a "Quests" domain featuring King Arthur, Prince Valiant, and Smaug the dragon. The system demonstrated high efficiency, generating a complex story involving 20 distinct plans across three characters in under 500ms on 2010-era hardware. Qualitatively, the generated stories exhibit natural causal flow and dramatic irony, such as characters making fatal mistakes due to false beliefs about their own strength relative to an opponent.
Conclusion
While CMP generates logically coherent and causally rich narratives, it currently lacks an internal metric for "interestingness" or dramatic quality. Future work aims to integrate "author" and "reader" models to evaluate and optimize the narrative impact of the generated plots, as well as more sophisticated natural language generation to move beyond simple templates.
Summary updated