Story Generation with Crowdsourced Plot Graphs

Boyang Li, Stephen Lee-Urban, George Johnston, Mark O. Riedl

Introduction

Traditional artificial intelligence systems for story generation have historically relied on "knowledge-heavy" approaches. To narrate a specific scenario, such as a bank robbery, developers typically had to manually encode every possible action, character motivation, and world rule into a formal domain model. This manual process creates a significant bottleneck, preventing systems from scaling to the vast array of human experiences.

The Scheherazade system addresses this challenge by pursuing "open story generation." Instead of relying on hand-coded rules, it autonomously learns domain models from crowdsourced human narratives. By capturing common-sense narrative flow—such as the necessity of finding a vault before opening it—Scheherazade can generate coherent stories across diverse topics without pre-existing expert knowledge.

Methodology: From Narratives to Plot Graphs

The Scheherazade pipeline transforms raw human input into a structured "plot graph" through a multi-stage process:

  1. Crowdsourcing: Workers on Amazon Mechanical Turk (AMT) provide simple, linear stories about a target topic (e.g., "a bank robbery").
  2. Learning the Plot Graph: The system clusters similar sentences into discrete "plot events." It then uses statistical methods to establish precedence (which events must occur before others) and mutual exclusion (events that cannot both occur in the same story, such as a robber escaping versus being arrested).
  3. Generation: Stories are produced via a "biased random walk" through the learned graph. The system selects executable events based on typicality, adjacency, and co-occurrence to ensure the resulting narrative feels logical and "legal."
A learned plot graph for a bank robbery scenario, illustrating precedence constraints (arrows) and mutual exclusions (dotted lines).

Key Insights: The Role of Mutual Exclusion

A central contribution of this work is the formalization of mutual exclusion within plot graphs. Without this constraint, an AI might generate contradictory sequences where a character is simultaneously caught and escapes. By identifying "non-contradictory trajectories," the system ensures narrative coherence. Furthermore, the system distinguishes between mandatory events required for plot progression and optional events that provide flavor.

Evaluation and Results

To evaluate the system, the authors compared 100 computer-generated stories against 60 human-authored ones. Human judges were asked to edit these stories to improve their coherence, with the number of required edits serving as a proxy for quality.

Comparison of human-authored and computer-generated stories based on editing metrics.

The results demonstrated that computer-generated stories reached a level of quality comparable to those written by untrained humans. While the AI-generated stories were significantly longer on average (23.14 events vs. 12.78), the normalized rate of human edits required to "fix" them was statistically similar to the human baseline. This suggests that the learned plot graphs successfully captured the underlying logic of the domain.

Conclusion and Future Work

Scheherazade demonstrates that crowdsourcing can serve as a powerful surrogate for direct world experience in AI training. With only 60 human examples, the system could generate over a million unique, logically sound stories.

However, limitations remain. The system tends toward verbosity, often including every possible "correct" event rather than employing the natural ellipsis found in human storytelling. Future work will focus on improving prose quality—moving beyond simple sentence selection to more evocative language—and testing the model's performance on more abstract or emotionally complex narrative themes.

Summary updated

Abstract

Story generation is the problem of automatically selecting a sequence of events that meet a set of criteria and can be told as a story. Story generation is knowledge-intensive; traditional story generators rely on a priori defined domain models about fictional worlds, including characters, places, and actions that can be performed. Manually authoring the domain models is costly and thus not scalable. We present a novel class of story generation system that can generate stories in an unknown domain. Our system (a) automatically learns a domain model by crowdsourcing a corpus of narrative examples and (b) generates stories by sampling from the space defined by the domain model. A large-scale evaluation shows that stories generated by our system for a previously unknown topic are comparable in quality to simple stories authored by untrained humans.
BibTeX
@inproceedings{li2013story,
  author = {Boyang Li and Stephen Lee-Urban and George Johnston and Mark O. Riedl},
  title = {{Story Generation with Crowdsourced Plot Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8649},
}
Figure