Search for: All records

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. 

Contemporary automated planning research emphasizes the use of domain knowledge abstractions like heuristics to improve search efficiency. Transformative automated abstraction techniques which decompose or otherwise reformulate the problem have a limited presence, owing to poor performance in key metrics like plan length and time efficiency. In this paper, we argue for a reexamination of these transformative techniques in the context of narrative planning, where classical metrics are less appropriate. We propose a model for automating abstraction by decomposing a planning problem into subproblems which serve as abstract features of the problem. We demonstrate the application of this approach on a low-level problem and discuss key features of the resulting abstract problem. Plans in the abstract problem are shorter, representing summaries of low-level plans, but can be directly translated into low-level plans for the original problem. 

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. 

Narrative planning generates a sequence of actions which must achieve the author's goal for the story and must be composed only of actions that make sense for the characters who take them. A causally necessary action is one that would make the plan impossible to execute if it were left out. We hypothesize that action sequences which are solutions to narrative planning problems are more likely to feature causally necessary actions than those which are not solutions. In this paper, we show that prioritizing sequences with more causally necessary actions can lead to solutions faster in ten benchmark story planning problems. 

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. 

We present an intelligent experience management architecture for a virtual reality police de-escalation training platform we are currently developing. Our aim is to direct the cast of non-player characters toward a scenario outcome appropriate to the player’s decisions, resulting in bad endings precisely when player’s mistakes enable them. We use a narrative planner to generate a story graph representing every possible narrative, and then we prune the graph to eliminate less believable non-player character actions. Unlike previous approaches based on story graph pruning, we implement an emotional planning model that lets us represent characters acting out of fear of bad outcomes as well as hope for good ones. We also incorporate experience management techniques for delaying commitment to hidden settings of the scenario and for capitalizing on player mistakes to demonstrate the negative consequences of not following best practices. 

Planning-based narrative generation is effective at producing stories with a logically-sound flow of events, but it can be limiting due to the rigidity of its constraints and the high burden on the domain author to define story-world objects, initial states, and author and character goals. Giving the system the freedom to add objects and events to the story-world history arbitrarily can improve variety and reduce authorial burden, but risks leading to stories that seem jarringly contrived to the audience. I propose to use question-answering as the antidote to contrivance in a highly-generative interactive narrative system: By modeling the player's beliefs about the story world, inferring the implicit questions the player may be asking through their interactions, and answering those questions in a way consistent with the player's prior knowledge, a system could focus on creating cohesion in the ways that matter most to the player while accepting a degree of contrivance in the details that the player is likely to overlook. 

We present an intelligent experience management architecture for a virtual reality police de-escalation training platform we are currently developing. Our aim is to direct the cast of non-player characters toward a scenario outcome appropriate to the player’s decisions, resulting in bad endings precisely when player’s mistakes enable them. We use a narrative planner to generate a story graph representing every possible narrative, and then we prune the graph to eliminate less believable non-player character actions. Unlike previous approaches based on story graph pruning, we implement an emotional planning model that lets us represent characters acting out of fear of bad outcomes as well as hope for good ones. We also incorporate experience management techniques for delaying commitment to hidden settings of the scenario and for capitalizing on player mistakes to demonstrate the negative consequences of not following best practices.