Multi-Agent Narrative Experience Management as Story Graph Pruning

In interactive narratives, experience management is used to control the world and the NPCs a player interacts with, encouraging particular types of stories or discouraging others. The space of all stories in a narrative can be understood as a story graph, with story states as nodes and actions in the story as directed edges. In this paper, we present experience management as a graph pruning problem. Starting with the full story graph, edges representing NPC actions may be pruned until there is at most one action per NPC per state. With the full graph available, the choice of what to prune may consider all possible futures, and we can ensure that undesirable stories are not reachable. By never pruning player actions, we ensure the player may make any choice and still be accommodated in the story. When this method was used to manage the story of an adventure game, players found our technique generally produced higher agency and more-believable NPC behaviors than a control. Finally, we discuss scaling the results of this method for practical use.

Full Paper:

PDF

Citation:

Stephen G. Ware, Edward T. Garcia, Mira Fisher, Alireza Shirvani, Rachelyn Farrell. Multi-agent narrative experience management as story graph pruning. IEEE Transactions on Games, 2022. (forthcoming)

[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]

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]

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]