Author ORCID Identifier

Date Available


Year of Publication


Degree Name

Doctor of Philosophy (PhD)

Document Type

Doctoral Dissertation




Computer Science

First Advisor

Dr. Stephen G. Ware


Interactive or branching stories are engaging and can be embedded into digital systems for a variety of purposes, but their size and complexity makes it difficult and time-consuming for humans to author them. Narrative planning algorithms can automatically generate large branching stories with guaranteed causal consistency, using a hand-authored library of story content pieces. The usability of such a system depends on both the quality of the narrative model upon which it is built and the ability of the user to create the story content library.

Current narrative planning algorithms use either a limited or no model of character belief, which typically leads to undesireable stories and difficult domain authoring challenges. Domain authoring is further complicated by a lack of intelligent tools for summarizing the content that a domain can produce so that its author can effectively evaluate it. In this work I extend a prior narrative planning framework to model deeply nested character beliefs, thus avoiding common character omniscience problems without overburdening the domain author. Human subjects evaluations demonstrate that the belief model tracks nested beliefs correctly, and that it improves overall character believability in solution spaces over previous models. This model makes domain authoring more intuitive, but also adds complexity to the story generation algorithm, making the planner's output even harder for the author to predict.

As a step toward more intelligent domain authoring tools, I present a novel method for measuring story similarity by encoding important story information into a fixed-length numeric vector. This enables automatic clustering of stories based on their semantic similarity, facilitating high-level communication of large story spaces. I compare the story similarity metric to assessments made by humans, and find the metric to be highly accurate in judging how similar two stories are to each other. I then demonstrate its use in clustering solution spaces, and evaluate two strategies for summarizing the content of the resulting clusters. I find both techniques to be more effective than a control in communicating large story spaces to humans. These contributions together advance the usability of narrative planning algorithms by improving their underlying narrative model and providing a basis for more intelligent domain authoring tools.

Digital Object Identifier (DOI)

Funding Information

This research was supported by the National Science Foundation (Grant #1647427) in 2016, and by the Department of Defense in 2018, 2019, and 2022.