Search for: All records

There has been much research into making planning-based story generators more efficient; however, the question remains whether the same efficiency could be achieved by reducing the problem to a more widely-studied search problem and leveraging existing solvers. We investigate this question for the narrative planning formalism used by Sabre, which models character goals and beliefs with deeply-nested theory of mind. We use answer set programming to develop a declarative implementation of the same planning formalism. Benchmarking our implementation, we find that existing, specialized planners remain the state of the art for solving their target problems as quickly as possible. However, the compactness and modularity of our approach will make it easier for researchers to develop prototype generators for new solution spaces that build on existing models. 

Narrative planning is the process of generating sequences of actions that form coherent and goal-oriented narratives. Classical implementations of narrative planning rely on heuristic search techniques to offer structured story generation, but often struggle with scalability because of large branching factors and deep search requirements. To improve the speed of narrative planning, we introduce Fog of War pruning, where Actions are only allowed if they involve people, places, and things that the protagonist character has discovered. This pruning technique restricts the planning to what is known from the perspective of the story's central character or characters, pruning branches of the search tree that involve actions beyond their current knowledge. This method is particularly useful in narratives where there is a strong protagonist focus and the story unfolds gradually as the character learns. This enables more efficient planning, while more closely aligning with how people would experience stories. Experiments across many narrative domains show that this technique not only speed up the search process, under identical search limits, also lets the planner solve more unique problems. 

Narrative planning can be used to create structured interactive experiences that dynamically respond to user input. Narrative planning works by generating a sequence of actions that achieves an author's desired goal while ensuring that there is an explanation for why each character takes each action in the sequence. An action in a sequence is considered necessary to that sequence if leaving the action out would prevent a later action in the sequence from being taken or prevent an author or character goal from being achieved. Using this definition, we define the causal width of a sequence to be the number of causally unnecessary actions, and we hypothesize sequences with a lower causal width are more likely to lead to a solution. We show that using causal width as a ranking mechanism can sometimes improve blind search, and ignoring stories with a high causal width can always improve the performance of heuristic search on a set of story benchmark problems. 

Supporting high-agency player experiences without compromising narrative control is one of the major challenges in digital interactive narrative design. Humans, on the other hand, frequently meet this challenge when cooperating to improvise a narrative. We present a study examining how humans improvise narratives when paired together as the player and game master of a digital interactive narrative. We collected gameplay logs from these experiences, as well as participants’ reported perceptions of narrative structure, personal agency, and the reasons for both their choices and their partners’. We found a strong link between perceptions of structure and of agency. We also found a tendency for participants to better identify the goals of their partner’s actions following sessions where game masters expressed higher agency. Finally, we characterize the experiences using principles of improv theatre, drawing from the data to analyze negative experiences of agency as failures in the improv partnership. 

A narrative planner decides the actions for all characters in a story while justifying each action according to the acting characters' own individual goals. However, an action that contributes to a goal may still seem irrational when considered alongside other actions the character may take; for instance, it may sacrifice a more important goal, or expose the character to unnecessary risks. We redefine the narrative planning character model to use a multiobjective framework where character actions are chosen from a Pareto front of best and safest options. We discuss how this framework can be applied to generate a policy for how the non-player characters should behave in any given state of an interactive narrative, and how we applied such a policy in the Traffic Stop de-escalation training simulation. 

We discuss the ongoing development of MicroTales, a collection of elements that can be combined to generate interactive narrative environments of varying size and complexity. MicroTales aims to fill a gap among existing AI benchmarks by featuring active non-player characters, a wide variety of actions, and the possibility to soft-lock the problem. Its purpose is to provide a clearly defined environment to compare different experience management algorithms without enforcing any one definition of what makes a good story. We present design goals and a sketch of an initial design, and invite community feedback to help make our benchmark reusable by other narrative intelligence researchers. 

Narrative planning algorithms generate stories as a sequence of actions that align with an author-defined goal while ensuring characters act believably, often requiring reasoning over nested beliefs. When theory of mind is represented, states include not only the factual world but also each character’s beliefs about the world and other characters' beliefs, potentially to infinite depth. In such planners, detecting duplicate states can prune redundant paths in the search space, but it is unclear whether it is too computationally expensive to justify. This paper investigates the cost and benefit of duplicate state detection using the Sabre planner, which models infinitely nested beliefs deterministically. We compare two approaches: tree search, which does not check for duplicate states, and graph search, which uses a recursive equivalence algorithm to detect and avoid duplicates. We provide a polynomial-time algorithm for detecting duplicate states and empirically show that using it significantly reduces the number of nodes generated and the total planning time across several benchmark problems. These findings suggest that duplicate detection in epistemic narrative planning is both feasible and beneficial. 

Narrative planning is the process of generating sequences of actions that form coherent and goal-oriented narratives. Classical implementations of narrative planning rely on heuristic search techniques to offer structured story generation but face challenges with scalability due to large branching factors and deep search requirements. Large Language Models (LLMs), with their extensive training on diverse linguistic datasets, excel in understanding and generating coherent narratives. However, their planning ability lacks the precision and structure needed for effective narrative planning. This paper explores a hybrid approach that uses LLMs as heuristic guides within classical search frameworks for narrative planning. We compare various prompt designs to generate LLM heuristic predictions and evaluate their performance against h+, hmax, and relaxed plan heuristics. Additionally, we analyze the ability of relaxed plans to predict the next action correctly, comparing it to the LLMs’ ability to make the same prediction. Our findings indicate that LLMs rarely exceed the accuracy of classical planning heuristics. 

Traffic Stop is a virtual reality de-escalation training simulation for police officers that has an interactive story driven by artificial intelligence. This project was funded by the U.S. National Science Foundation and led by Prof. Stephen Ware of the Narrative Intelligence Lab at the University of Kentucky. 

Player goals in games are often framed in terms of achieving something in the game world, but this framing can fail to capture goals centered on the player’s own mental model, such as seeking the answers to questions about the game world. We use a least-commitment model of interactive narrative to characterize these knowledge goals and the problem of knowledge goal recognition. As a first attempt to solve the knowledge goal recognition problem, we adapt a classical goal recognition paradigm, but in our empirical evaluation the approach suffers from a high rate of incorrectly rejecting a synthetic player’s true goals; we discuss how handling of player goals could be made more robust in practice.