Narrative Planning for Belief and Intention Recognition

Planning algorithms generate sequences of actions that achieve a goal, but they can also be used in reverse: to infer the goals that led to a sequence of actions. Traditional plan-based goal recognition assumes agents are rational and the environment is fully observable. Recent narrative planning models represent agents as believable rather than perfectly rational, meaning their actions need to be justified by their goals, but they may act in ways that are not optimal, and they may possess incorrect beliefs about the environment. In this work we propose a technique for inferring the goals and beliefs of agents in this context, where rationality and omniscience are not assumed. We present two evaluations that investigate the effectiveness of this approach. The first uses partial observation sequences and shows how this impacts the algorithm’s accuracy. The second uses human data and compares the algorithm’s inferences to those made by humans.

Full Paper:

PDF

Citation:

Rachelyn Farrell, Stephen G. Ware. Narrative planning for belief and intention recognition. In Proceedings of the 16th AAAI international conference on Artificial Intelligence and Interactive Digital Entertainment, pp. 52-58, 2020.

[bibtex]

Camelot: An Interactive Narrative Sandbox Tool

Camelot is a customizable engine for building simple 3D adventure games, designed for use in interactive narrative research. The engine is controlled by basic text commands sent over standard input, allowing a Camelot game to be controlled by an external program, or experience manager, that can be written in almost any programming language. You can find the latest release and API documentation using the above link.

The project’s design is a collaborative effort by all of us at the Narrative Intelligence Lab. It was built in Unity by Alex Shirvani and Edward Garcia. I wrote the in-house scripting language we use to quickly build Camelot experience managers for testing, demos, and experiments.

Camelot was first showcased as a Playable Experience at AIIDE 2018, and later as its own tutorial workshop at AIIDE 2019: CamJam.

Multi-Agent Narrative Experience Management as Story Graph Pruning

In many intelligent interactive narratives, the player controls an avatar while an experience manager controls non-player characters (NPCs). The space of all stories can be viewed as a story graph, where nodes are states and edges are actions taken by the player, by NPCs, or by both jointly. In this paper, we cast experience management as a story graph pruning problem. We start with the full graph and prune intelligently until each NPC has at most one action in every state. Considering the entire graph allows us to foresee the long-term consequences of every pruning decision on the space of possible stories. By never pruning player actions, we ensure the experience manager can accommodate any choice. When used to control the story of an adventure game, players found our technique generally produced higher agency and more believable NPC behavior than a control.

Full Paper:

PDF

Citation:

Stephen G. Ware, Edward T. Garcia, Alireza Shirvani, Rachelyn Farrell. Multi-agent narrative experience management as story graph pruning. In Proceedings of the 15th AAAI international conference on Artificial Intelligence and Interactive Digital Entertainment, pp. 87-93, 2019.

[bibtex]

Combining Intentionality and Belief: Revisiting Believable Character Plans

In this paper we present two studies supporting a plan-based model of narrative generation that reasons about both intentionality and belief. First we compare the believability of character plans taken from the spaces of valid classical plans, intentional plans, and belief plans. We show that the plans that make the most sense to humans are those in the overlapping regions of the intentionality and belief spaces. Second, we validate the model’s approach to representing anticipation, where characters form plans that involve actions they expect other characters to take. Using a short interactive scenario we demonstrate that players not only find it believable when NPCs anticipate their actions, but sometimes actively anticipate the actions of NPCs in a way that is consistent with the model.

Full Paper:

PDF

Citation:

Alireza Shirvani, Rachelyn Farrell, Stephen G. Ware. Combining intentionality and belief: revisiting believable character plans. In Proceedings of the 14th AAAI International Conference on Artificial Intelligence and Interactive Digital Entertainment, pp. 222-228, 2018.

[bibtex]

Causal Link Semantics for Narrative Planning using Numeric Fluents

Narrative planners would be able to represent richer, more realistic story domains if they could use numeric variables for certain properties of objects, such as money, age, temperature, etc. Modern state-space narrative planners make use of causal links—structures that represent causal dependencies between actions—but there is no established model of a causal link that applies to actions with numeric preconditions and effects. In order to develop a semantic definition for causal links that handles numeric fluents and is consistent with the human understanding of causality, we designed and conducted a user study to highlight how humans perceive enablement when dealing with money. Based on our evaluation, we present a causal semantics for intentional planning with numeric fluents, as well as an algorithm for generating the set of causal links identified by our model from a narrative plan.

Full Paper:

PDF

Citation:

Rachelyn Farrell, Stephen G. Ware. Causal link semantics for narrative planning using numeric fluents. In Proceedings of the 13th AAAI International Conference on Artificial Intelligence and Interactive Digital Entertainment, pp. 193-199, 2017.

[bibtex]

Influencing User Choices in Interactive Narratives using Indexter’s Pairwise Event Salience Hypothesis

Indexter is a plan-based model of narrative that incorporates cognitive scientific theories about the salience—or prominence in memory—of narrative events. A pair of Indexter events can share up to five indices with one another: protagonist, time, space, causality, and intentionality. The pairwise event salience hypothesis states that a past event is more salient if it shares one or more of these indices with the most recently narrated event. In a previous study we used this model to predict users’ choices in an interactive story based on the indices of prior events. We now show that we can use the same method to influence them to make certain choices. In this study, participants read an interactive story with two possible endings. We influenced them to choose a particular ending by manipulating the salience of story events. We showed that users significantly favored the targeted ending.

Full Paper:

PDF

Playable:

Play the story here.

Citation:

Rachelyn Farrell, Stephen G. Ware. Influencing user choices in interactive narratives using Indexter’s pairwise event salience hypothesis. In Proceedings of the 13th AAAI International Conference on Artificial Intelligence and Interactive Digital Entertainment, pp. 37-42, 2017.
[bibtex]

A Possible Worlds Model of Belief for State-Space Narrative Planning

Abstract:

What characters believe, how they act based on those beliefs, and how their beliefs are updated is an essential element of many stories. State-space narrative planning algorithms treat their search spaces like a set of temporally possible worlds. We present an extension that models character beliefs as epistemically possible worlds and describe how such a space is generated. We also present the results of an experiment which demonstrates that the model meets the expectations of a human audience.

Full Paper:

PDF

Citation:

Alireza Shirvani, Stephen G. Ware, Rachelyn Farrell. A possible worlds model of belief for state-space narrative planning. In Proceedings of the 13th AAAI International Conference on Artificial Intelligence and Interactive Digital Entertainment, pp. 101-107, 2017.

[bibtex]

Asking Hypothetical Questions about Stories using QUEST

Many computational models of narrative include representations of possible worlds—events that never actually occur in the story but that are planned or perceived by the story’s characters. Psychological tools such as QUEST are often used to validate computational models of narrative, but they only represent events which are explicitly narrated in the story. In this paper, we demonstrate that audiences can and do reason about other possible worlds when experiencing a narrative, and that the Quest knowledge structures for each possible world can be treated as a single data structure. Participants read a short text story and were asked hypothetical questions that prompted them to consider alternative endings. When asked about events that needed to change as a result of the hypothetical, they produced answers that were consistent with answers generated by QUEST from a different version of the story.  When asked about unrelated events, their answers matched those generated by QUEST from the version of the story they read.

Full Paper:

PDF

Citation:

Rachelyn Farrell, Scott Robertson, Stephen G. Ware. Asking hypothetical questions about stories using QUEST. In Proceedings of the 9th International Conference on Interactive Digital Storytelling, pp. 136-146, 2016.

[bibtex]

Predicting User Choices in Interactive Narratives using Indexter’s Pairwise Event Salience Hypothesis

Indexter is a plan-based model of narrative that incorporates cognitive scientific theories about the salience of narrative events. A pair of Indexter events can share up to five indices with one another: protagonist, time, space, causality, and intentionality. The pairwise event salience hypothesis states that when a past event shares one or more of these indices with the most recently narrated event, that past event is more salient, or easier to recall, than an event which shares none of them. In this study we demonstrate that we can predict user choices based on the salience of past events. Specifically, we investigate the hypothesis that when users are given a choice between two events in an interactive narrative, they are more likely to choose the one which makes the previous events in the story more salient according to this theory.

Full Paper:

PDF

Playable:

The story used for this study is here!

Citation:

Rachelyn Farrell, Stephen G. Ware. Predicting user choices in interactive narratives using Indexter’s pairwise event salience hypothesis. In Proceedings of the 9th International Conference on Interactive Digital Storytelling, pp. 147-155, 2016.

[bibtex]

Fast and Diverse Narrative Planning through Novelty Pruning

Novelty pruning is a simple enhancement that can be added to most planners. A node is removed unless it is possible to find a set of n literals which are true in the current state and have never all been true in any of that plan’s previous states. Expanding on the success of the Iterated Width algorithm in classical planning and general game playing, we apply this technique to narrative planning. Using a suite of 8 benchmark narrative planning problems, we demonstrate that novelty pruning can be used with breadth-first search to solve smaller problems optimally and combined with heuristic search to solve larger problems faster. We also demonstrate that when many solutions to the same problem are generated, novelty pruning can produce a wider variety of solutions in some domains.

Full Paper:

PDF

Citation:

Rachelyn Farrell, Stephen G. Ware. Fast and diverse narrative planning through novelty pruning. In Proceedings of the 12th AAAI International Conference on Artificial Intelligence and Interactive Digital Entertainment, pp. 37-43, 2016.

[bibtex]