Narrative planning is the use of automated planning to construct, communicate, and understand stories, a form of information to which human cognition and enaction is pre-disposed. We review the narrative planning problem in a manner suitable as an introduction to the area, survey different plan-based methodologies and affordances for reasoning about narrative, and discuss open challenges relevant to the broader AI community.

Increasingly, research on narrative planning is expanding the expressive range of narrative generation systems, producing plot lines with structures like failed action, mistaken character belief and the integration of authorial and character-centered plans and intentions. Evaluation of these systems’ expressive capabilities is essential to determining their strengths. Some prior evaluative methods have measured the efficacy of narrative planners by characterizing a user’s experience during generated narratives. These approaches have focused on comparing the mental model a user forms during the experience of a narrative with the plan data structure that served as the basis of the narrative’s plot, but have not considered evaluating the user’s understanding of failed actions in narrative. To that end, we propose an algorithm to translate plans containing failed actions into a commonly used cognitive mode of narrative comprehension called QUEST. We then sketch how this translation will play a role in a planned evaluation of users’ experiences reading stories produced by narrative planning systems that generate stories with failed actions.

An open challenge for AI in digital games is narrative experience management, the problem of automatically directing virtual characters in an interactive story to produce specific narrative effects for human participants. One important aspect of interactive narrative quality is participant choice, which provides the central distinction between interactive and linear storytelling. Most experience management work identifies storytelling patterns an agent should value or guides participants through high-value story trajectories. However, the types and quality of choices available in an interactive story are influenced not only by a model of narrative and specific story character actions, but also the world design that affords situations and actions. In this paper, we present a method for generating all unique, accessible choice combinations for a story world as a first step towards experience-driven interactive narrative world design. We benchmark the approach against several baselines and discuss its use as a tool for human and automated world designers.

In automatically generated interactive narratives (INs) with strong story structure, there is often a tension between player choice and author constraints. This tension arises when the player contradicts a story the system is in the process of telling. When this happens there are two options available to an IN storyteller that preserve the author's intentions. First, called accommodation, finds a new story that matches the player's action while preserving author constraints. Second, called intervention, removes unwanted effects from the player's action. Neither of these alternatives are ideal. For accommodation, a new story is not always available. For intervention, the player could notice the inconsistent effects of their actions. In this paper, we present a new approach to mediate between player choice and authorial constraints, called perceptual experience management, which mitigates drawbacks of both accommodation and intervention by incorporating a model of player knowledge into the strong story experience management process. This model is used to widen the space of possible accommodations and constrain the space of possible interventions to better balance author control and player choice. These two strategies are implemented in the general mediation engine, an experience manager capable of procedurally generating and revising a game world.

Plan-based story generation has operationalized concepts from the Belief-Desire-Intention (BDI) theory of mind to create goal-driven character agents with explainable behavior. However, these character agents are limited in that they do not capture the dynamic nature of intentions. To address this limitation, we define a plan-based intention revision model and propose an evaluation using the QUEST cognitive model to assess the explainability of an intention revision.

Character intention revision is an essential component of stories, but it has yet to be incorporated into story generation systems. However, intentionality, one component of intention revision, has been explored in both narrative generation and logical formalisms. The intention revision in storytelling (IRIS) system adopts the belief/desire/intention framework of intentionality from logical formalisms and combines it with preexisting concepts of intentionality in narrative. IRIS also introduces the crucial concept of intention revision for the protagonist of the story. The IRIS system uses its generative power alongside psychological and narrative models of suspense to computationally create suspenseful stories. It has been used in the creation of suspenseful noninteractive text stories and an interactive text-based video game.

In this paper, we present The Best Laid Plans, an interactive narrative adventure game, and the planning technologies used to generate and adapt its story in real time. The game leverages computational models of intentionality and conflict when controlling the non-player characters (NPCs) to ensure they act believably and introduce challenge into the automatically generated narratives. We evaluate the game's ability to generate NPC behaviors that human players recognize as intentional and as conflicting with their plans. We demonstrate that players recognize these phenomena significantly more than in a control with no NPC actions and not significantly different from a control in which NPC actions are defined by a human author.

We present an approach to incorporate interesting and compelling characters in planning-based narrative generation. The approach is based on a computational model that utilizes character actions to portray these as having distinct and well-defined personalities.

Interactive storytelling has been receiving a growing attention from AI and game communities and a number of computational approaches have shown promises in generating stories for games. However, there has been little research on stories evoking specific cognitive and affective responses. The goal of the work we describe here is to develop a system that produces a narrative designed specifically to arouse suspense from its reader. Our approach attempts to create stories that manipulate the reader's suspense level by elaborating on the story structure that can influence the reader's narrative comprehension at a specific point in her reading. Adapting theories developed by cognitive psychologists, our approach uses a plan-based model of narrative comprehension to determine the final content of the story in order to manipulate the reader's suspense. In this paper, we describe our system implementation and empirical evaluations to test the efficacy of this system.

We present work toward computationally defining a model of narrative comprehension vis-à-vis memory of narrative events, via an automated planning knowledge representation, capable of being used in a narrative generation context.

This paper describes our effort for a planning-based computational model of narrative generation that is designed to elicit surprise in the reader's mind, making use of two temporal narrative devices: flashback and foreshadowing. In our computational model, flashback provides a backstory to explain what causes a surprising outcome, while foreshadowing gives hints about the surprise before it occurs. Here, we present Prevoyant, a planning-based computational model of surprise arousal in narrative generation, and analyze the effectiveness of Prevoyant. The work here also presents a methodology to evaluate surprise in narrative generation using a planning-based approach based on the cognitive model of surprise causes. The results of the experiments that we conducted show strong support that Prevoyant effectively generates a discourse structure for surprise arousal in narrative.

The eleven articles in this special issue focus on the use of computational modeling in developing the narratives for video programs and online games. Narratives are perceived to be central to cultures, to the ways people communicate, and, many have argued, to cognition itself. The articles in this issue explore these issues and reports on technologies and computer applications that support narrative programming.

Conflict is an essential element of interesting stories. In this paper, we operationalize a narratological definition of conflict and extend established narrative planning techniques to incorporate this definition. The conflict partial order causal link planning algorithm (CPOCL) allows narrative conflict to arise in a plan while maintaining causal soundness and character believability. We also define seven dimensions of conflict in terms of this algorithm's knowledge representation. The first three-participants, reason, and duration-are discrete values which answer the “who?” “why?” and “when?” questions, respectively. The last four-balance, directness, stakes, and resolution-are continuous values which describe important narrative properties that can be used to select conflicts based on the author's purpose. We also present the results of two empirical studies which validate our operationalizations of these narrative phenomena. Finally, we demonstrate the different kinds of stories which CPOCL can produce based on constraints on the seven dimensions.

This work seeks to validate the use of a situation model (a model for the comprehension processes in non-interactive narrative) for use modeling a player's comprehension process within interactive narratives and games. Unlike conventional narratives, games contain actions and events that might not carry any narrative significance; consequently, a cognitive model of player understanding may require a new distinction between "narratively important" and "narratively unimportant" events. This hypothesis was tested in an experiment using Event Segmentation Theory. Our results failed to reject the null hypothesis (Fisher's exact test, p = 1) but were insightful. Narrative importance seems to be perceptually oriented, and dependent on the outcomes of the event in question. Although our data failed to reject the null hypothesis, more work must be done before rejecting the necessity of the distinction between narratively important and unimportant events when modeling a player's comprehension process of an unfolding story-focused game.

Conflict is an essential element of interesting stories. In previous work, we proposed a formal model of narrative conflict based on intentional planning that is designed to facilitate story generation. This paper presents the results of an experiment to test whether or not our model can answer "who?" "why?" and "when?" questions about conflict similarly to humans analyzing the same stories. Our model has some success at predicting which conflicts human readers will report and performs well at recognizing which characters are in conflict and for how long.

Focalization, perspective-taking in stories, restricts narrative information to the eye of a character, allowing the audience limited perception for a particular effect. This paper briefly describes the work in narrative theories on focalization and our computational model of focalization in narrative generation using an Artificial Intelligence planning-based approach. Keys to the story generation with focalization are the use of distinctive knowledge (i.e., distinctive plan libraries) and the concept of focalizing factors for each focal character in the story.

Online multiplayer gaming has emerged as a popular form of entertainment. During these games, the players' main focus is usually placed on achieving the objectives that must be completed to win the game. Over the course of the game, however, their interactions may result in interesting emergent narratives that go unnoticed. Afterthought is a system that monitors player activity, recognizes instances of story elements in gameplay and renders cinematic highlights of the story-oriented game play, allowing players to view these emergent narratives after completing their gameplay session. This paper outlines Afterthought's design at a high level.

In this paper, we describe ongoing work in the Liquid Narrative group extending computational models of narrative structure. The work looks specifically at two elements of narrative structure that have seen little explicit attention: conflict and intent revision. Our approach employs a planning-based model to represent the plans build and operated upon by characters within a story and an explicit cognitive model of the narrative we expect users to build as a result of viewing or participating in the story. This work has potential impact on the creation of new types of narrative-based interactions within computer games and other virtual worlds.

Narrative, and in particular storytelling, is an important part of the human experience. Consequently, computational systems that can reason about narrative can be more effective communicators, entertainers, educators, and trainers. One of the central challenges in computational narrative reasoning is narrative generation, the automated creation of meaningful event sequences. There are many factors -- logical and aesthetic -- that contribute to the success of a narrative artifact. Central to this success is its understandability. We argue that the following two attributes of narratives are universal: (a) the logical causal progression of plot, and (b) character believability. Character believability is the perception by the audience that the actions performed by characters do not negatively impact the audience's suspension of disbelief. Specifically, characters must be perceived by the audience to be intentional agents. In this article, we explore the use of refinement search as a technique for solving the narrative generation problem -- to find a sound and believable sequence of character actions that transforms an initial world state into a world state in which goal propositions hold. We describe a novel refinement search planning algorithm -- the Intent-based Partial Order Causal Link (IPOCL) planner -- that, in addition to creating causally sound plot progression, reasons about character intentionality by identifying possible character goals that explain their actions and creating plan structures that explain why those characters commit to their goals. We present the results of an empirical evaluation that demonstrates that narrative plans generated by the IPOCL algorithm support audience comprehension of character intentions better than plans generated by conventional partial-order planners.

In this paper, we present the design, implementation, and evaluation of an end-to-end camera planning system called Darshak. Darshak automatically constructs cinematic narrative discourse of a given story in a 3-D virtual environment. It utilizes a hierarchical partial-order causal link (POCL) planning algorithm to generate narrative plans that contain story events and camera directives for filming them. Dramatic situation patterns, commonly used by writers of fictional narratives, are formalized as communicative plan operators that provide a basis for structuring the cinematic content of the story's visualization. The dramatic patterns are realized through abstract communicative operators that represent operations on a viewer's beliefs about the story and its telling. Camera shot compositions and transitions are defined in this plan-based framework as execution primitives. Darshak's performance is evaluated through a novel user study based on techniques used to evaluate existing cognitive models of narrative comprehension. Initial study reveals significant effect of the choice of visualization strategies on measured viewer comprehension. It further shows significant effect of Darshak's choice of visualization strategy on comprehension.

A description of a novel domain-independent framework that automatically generates and fades scaffolding supports for task-oriented learning within exploratory environments. Both student knowledge and tutorial assistance is modeled through plan-based interactive narrative.

We propose a novel evaluation methodology for intelligent camera control systems based on established techniques of measuring story comprehension from cognitive psychology. The proposed methodology can be used specifically for evaluating the effectiveness of the camera system in communicating the story. We introduce a psychological model of question answering called QUEST and present a preliminary evaluation design of videos automatically generated by Darshak, an intelligent cinematic camera planning system. Initial results from our analysis are encouraging and motivate further work in evaluation of intelligent camera control systems as well as cognitive models of story comprehension through the visual medium.

This poster describes a framework that automatically generates learning support scaffolds to guide task-based learning. The aim is to combine the exploratory learning principles prominent in digital games with the rich user modeling and adaptation of intelligent tutoring systems.

In interactive plan-based narrative environments, users' actions must be monitored to ensure that conditions necessary for the execution of narrative plans are not compromised. In the Zocalo system, management of user actions has been performed on a reactionary basis by a process called mediation. In this paper, we describe an extension to this approach,proactive mediation, which calculates responses to user input in an anticipatory manner. A proactive mediation module accepts as input a plan describing the actions being performed by the user (generated by a plan recognition system) and identifies portions of that plan that jeopardize the causal structure of the overall narrative. Once these portions are identified, proactive mediation generates modifications to the narrative plan structure that avoid the unwanted interaction between user and story. This extension to the original mediation algorithm provides more responses to a user's actions and generates responses that are tailored to the user's activity.

The problem of providing help for complex application interfaces has been a source of interest for a number of researcher efforts. As the computational power of computers increases, typical applications not only increase in functionality but also in the degree of interaction with the computational environment in which they reside. This paper describes an ongoing project to design an Intelligent Help System (IHS) that provides context-sensitivity not only through its modeling of application states but also its modeling of the interaction between applications and between an application and the environment in which it resides.

The creation of novel, engaging and dynamic interactive stories presents a unique challenge to the designers of systems for interactive entertainment, education and training. Unlike conventional narrative media, an interactive narrative-based system may be required to generate its own story structure, determine the appropriate interface elements to use to convey the storys action and manage the effective interaction of a user within the story as it plays out. Here we describe the architecture of the Mimesis system, which integrates a 3D graphical gaming environment with intelligent techniques for generating and controlling interaction with and within a narrative in order to create an engaging and coherent user experience