Solution Density and Search Strategy in Narrative Generation

Cory Siler, Stephen G. Ware

Research output: Contribution to journalArticlepeer-review

Abstract

Intelligent interactive narrative systems coordinate a cast of nonplayer 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.

Original languageEnglish
Pages (from-to)715-724
Number of pages10
JournalIEEE Transactions on Games
Volume14
Issue number4
DOIs
StatePublished - Dec 1 2022

Bibliographical note

Funding Information:
This work was supported by the National Science Foundation under Grant IIS-1911053.

Publisher Copyright:
© 2018 IEEE.

Keywords

  • Intelligent systems
  • algorithm design and analysis
  • algorithms
  • artificial intelligence
  • computational and artificial intelligence
  • computer applications
  • computers and information processing
  • mathematics
  • modeling
  • systems engineering and theory

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Cite this