More Like this

1. Language Models as Narrative Planning Heuristics

   https://doi.org/10.1145/3723498.3723815  

   Senanayake, Lasantha; Ware, Stephen G (April 2025, ACM)

   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
2. Solution Density and Search Strategy in Narrative Generation

   https://doi.org/10.1109/TG.2022.3149529  

   Siler, Cory; Ware, Stephen G. (January 2022, IEEE Transactions on Games)

   Intelligent interactive narrative systems coordinate a cast of non-player characters to make the overall story experience meaningful for the player. Narrative generation involves a tradeoff between plot-structure requirements and quality of character behavior, as well as computational efficiency. We study this tradeoff using the example of benchmark problems for narrative planning algorithms. A typical narrative planning problem calls for a sequence of actions that leads to an overall plot goal being met, while also requiring each action to respect constraints that create the appearance of character autonomy. We consider simplified solution definitions that enforce only plot requirements or only character requirements, and we measure how often each of these definitions leads to a solution that happens to meet both types of requirements—i.e., the density with which narrative plans occur among plot- or character-requirement-satisfying sequences. We then investigate whether solution densities can guide the selection of narrative planning algorithms. We compare the performance of two search strategies: one that satisfies plot requirements first and checks character requirements afterward, and one that continuously verifies character requirements. Our results show that comparing solution densities does not by itself predict which of these search strategies will be more efficient in terms of search nodes visited, suggesting that other important factors exist. We discuss what some of these factors could be. Our work opens further investigation into characterizing narrative planning algorithms and how they interact with specific domains. The results also highlight the diversity and difficulty of solving narrative planning problems. 

   more » « less
3. Adversarial Strong Story Experience Management

   https://doi.org/10.1609/aiide.v21i1.36828  

   Genoese-Zerbi, Valentina; Robertson, Justus (November 2025, Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment)

   In strong story experience management problems, an automated storytelling agent balances player autonomy with narrative structure in the context of an interactive story game world. However, it is possible for the game world to get softlocked in states outside narrative structures specified by the game designer. These states are called dead-ends. In this paper, we revisit adversarial strong story experience management, a framing of the experience management problem that models interactive storytelling as an adversarial game where dead-ends are losses. This framing is adversarial against narrative softlocks, not necessarily the player. We present a novel agent based on adversarial search and deep reinforcement learning, which is trained to avoid dead-ends while preserving player autonomy. We compare our approach to a reactive, narrative plan-based mediation system on a test set of games compatible with current narrative planning techniques. We show that our adversarial architecture outperforms narrative mediation on a suite of dead-end metrics during game trace and breadth-first tests of state transition system exploration, using classical and intentional planning domains. 

   more » « less
4. Causal Necessity as a Narrative Planning Step Cost Function

   https://doi.org/10.1609/aiide.v19i1.27511  

   Ware, Stephen G; Senanayake, Lasantha; Farrell, Rachelyn (October 2023, Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment)

   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. 

   more » « less
5. Online Reinforcement Learning-Based Pedagogical Planning for Narrative-Centered Learning Environments

   https://doi.org/10.1609/aaai.v38i21.30365  

   Fahid, Fahmid Morshed; Rowe, Jonathan; Kim, Yeojin; Srivastava, Shashank; Lester, James (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   Pedagogical planners can provide adaptive support to students in narrative-centered learning environments by dynamically scaffolding student learning and tailoring problem scenarios. Reinforcement learning (RL) is frequently used for pedagogical planning in narrative-centered learning environments. However, RL-based pedagogical planning raises significant challenges due to the scarcity of data for training RL policies. Most prior work has relied on limited-size datasets and offline RL techniques for policy learning. Unfortunately, offline RL techniques do not support on-demand exploration and evaluation, which can adversely impact the quality of induced policies. To address the limitation of data scarcity and offline RL, we propose INSIGHT, an online RL framework for training data-driven pedagogical policies that optimize student learning in narrative-centered learning environments. The INSIGHT framework consists of three components: a narrative-centered learning environment simulator, a simulated student agent, and an RL-based pedagogical planner agent, which uses a reward metric that is associated with effective student learning processes. The framework enables the generation of synthetic data for on-demand exploration and evaluation of RL-based pedagogical planning. We have implemented INSIGHT with OpenAI Gym for a narrative-centered learning environment testbed with rule-based simulated student agents and a deep Q-learning-based pedagogical planner. Our results show that online deep RL algorithms can induce near-optimal pedagogical policies in the INSIGHT framework, while offline deep RL algorithms only find suboptimal policies even with large amounts of data. 

   more » « less