Solution Density and Search Strategy in Narrative Generation
- 8 February 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Games
- Vol. 14 (4) , 715-724
Abstract
Intelligent narrative systems coordinate a cast of non-player characters to make the story experience meaningful for the player. Narrative generation involves a tradeoff between plot-structure requirements and quality of character behavior. We study this tradeoff using the example of narrative planning benchmarks. A narrative planning problem calls for a sequence of actions that leads to an overall plot goal being met, while creating 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. 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, suggesting that other important factors exist. The results also highlight the diversity and difficulty of solving narrative planning problems. Our work opens further investigation into characterizing narrative planning algorithms and how they interact with specific domains.Keywords
Funding Information
- National Science Foundation (IIS-1911053)
This publication has 27 references indexed in Scilit:
- Automated narrative planning model extensionAutonomous Agents and Multi-Agent Systems, 2021
- Tension Space Analysis for Emergent NarrativeIEEE Transactions on Games, 2020
- A Survey on Story Generation Techniques for Authoring Computational NarrativesIEEE Transactions on Computational Intelligence and AI in Games, 2016
- Intentionality and Conflict in The Best Laid Plans Interactive Narrative Virtual EnvironmentIEEE Transactions on Computational Intelligence and AI in Games, 2015
- A Computational Model of Narrative Generation for Surprise ArousalIEEE Transactions on Computational Intelligence and AI in Games, 2013
- Story Planning: Creativity Through Exploration, Retrieval, and Analogical TransformationMinds and Machines, 2010
- Analyzing the expressive range of a level generator2010
- Density condensation of Boolean formulasDiscrete Applied Mathematics, 2006
- Towards Integrating Plot and Character for Interactive Drama2006
- Strips: A new approach to the application of theorem proving to problem solvingArtificial Intelligence, 1971