Attention:The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, November 12th until 12:00 AM ET on Friday, November 13th due to maintenance. We apologize for the inconvenience.


Search for: All records

Award ID contains: 2145153

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. 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. 
    more » « less
    Free, publicly-accessible full text available November 11, 2026
  2. 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. 
    more » « less
  3. 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. 
    more » « less
  4. 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. 
    more » « less
  5. Interactive story systems today sit at three extremes. Emergent multi‑agent simulations give each character local intelligence but no global view, often losing plot structure. Reactive systems makes fast, state‑based decisions. They form plans using hand-authored rules without searching for action sequences, so these systems can respond quickly but can wander if long-term rules are not explicitly authored. Centralized narrative planners reason globally to craft coherent, goal‑directed plots, yet are computationally expensive. In my doctoral work I treat these not as isolated choices but as the three corners of a triangle spectrum of narrative generation. I propose hybrid, landmark‑guided approaches that can scale to larger domains. I am also exploring how large language models (LLMs) can be embedded within these hybrid approaches themselves. This paper outlines research questions, methodology, progress to date, evaluation plan, and requested feedback. 
    more » « less
  6. 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. 
    more » « less
  7. 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. 
    more » « less
  8. Most narrative planners currently lack the ability to model characters believing in multiple different possibilities or actions with different outcomes. By introducing a sense of uncertainty into narrative planning, we can model more realistic human behavior as well as generate new types of stories. In particular, stories surrounding a detective or a mystery require some form of uncertainty for the story to sound reasonable to a reader. 
    more » « less
  9. 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. 
    more » « less
  10. 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. 
    more » « less