BiPOCL: A Discourse-Driven Story Planner for Procedural Narrative Generation (Extended Abstract)

David R. WinerIJCAI 2016

Introduction

In the field of automated narrative generation, a fundamental distinction is made between the story (the chronological sequence of events, or fabula) and the discourse (the specific way those events are presented to an audience). Traditionally, these two components are handled via a "story-then-discourse" pipeline: a planner first generates a complete story, which is then passed to a discourse planner for presentation.

However, this sequential approach often leads to the "incompatibility problem." Because the story planner is "blind" to the narrator's communicative goals, it may generate a story that lacks the necessary evidence to support the intended discourse effects. For instance, if a narrator aims to convey that a specific bridge is dangerous, a standard story planner might generate a sequence where every character crosses safely, leaving the discourse planner with no narrative material to justify the claim of danger.

This paper introduces BiPOCL (Bipartite Partial-Order Causal Link), a novel planning algorithm designed to solve this incompatibility by generating the story and its discourse simultaneously.

The BiPOCL Framework

BiPOCL moves away from the pipeline model in favor of a tightly coupled, bipartite search process. It builds upon the classic POCL algorithm, which treats plan generation as a search through "plan-space," identifying and repairing "flaws" such as missing steps or inconsistent orderings.

Key Technical Innovations

  • Bipartite Search: The planner simultaneously searches for solutions to two distinct but interlinked problems: the story problem and the discourse problem. By treating these as a single search space, the system ensures that every narrative choice supports a communicative goal.
  • Couplings: These are formal associations that link discourse variables to specific story elements. For example, a discourse action intended to "convey danger" is explicitly coupled with a story element where a character suffers a negative consequence.
  • Prerequisites as Search Pruning: Unlike previous systems that relied on late-stage constraints, BiPOCL uses "prerequisites" for discourse actions. This allows the planner to prune the search space early if it determines that a story element cannot be created to satisfy a specific discourse requirement, significantly improving search focus.
  • Bipartite Completeness: The authors define this property to guarantee that the planner will find a compatible pair of story and discourse solutions if such a pair exists, ensuring the algorithm is robust across different narrative domains.

Discourse-Driven Storytelling

The core insight of BiPOCL is that discourse should not merely react to a pre-existing story; it should drive the story's creation. The narrator’s need to elicit a specific effect—such as establishing a character's bravery or a location's peril—acts as a functional requirement that forces the story planner to include specific types of events.

To facilitate this, the system employs a meta-plan language based on narrative theory. This allows authors to specify high-level constraints like "conflict" or "tellability," moving the system beyond simple goal-reaching toward the generation of content that is structurally and rhetorically interesting. Furthermore, BiPOCL utilizes structural nesting, treating story elements as hierarchical trees. This allows the planner to navigate different levels of detail (from high-level character plans to specific literals) to find the perfect element to couple with a discourse action.

Results and Proof of Concept

As an architectural and theoretical advancement, the paper focuses on the framework's capability rather than empirical benchmarks. The authors provide a proof of concept demonstrating how a communicative goal (e.g., showing a location is dangerous) successfully triggers the generation of specific story events (e.g., a character dying at that location). A standard, uncoupled story planner would likely have ignored such events unless they were strictly necessary to reach a physical goal state.

By successfully integrating STRIPS-style operators with narrative-theoretic couplings, BiPOCL provides a formal method for ensuring that the "what" of a story always supports the "how" of its telling.

Limitations and Future Work

While BiPOCL offers a powerful new way to generate narratives, it faces challenges regarding authoring complexity. Currently, creating discourse operators requires deep expertise in narrative-theoretic planning. Future iterations of the system aim to encapsulate these low-level details to make the tool more accessible to creative authors. Additionally, because searching two plan spaces simultaneously is computationally expensive, the authors identify the need for more sophisticated heuristics to improve search efficiency and explore complex discourse effects like "good timing" and suspense.

Summary updated

BibTeX
@inproceedings{winer2016bipocl,
  author = {David R. Winer},
  title = {{BiPOCL: A Discourse-Driven Story Planner for Procedural Narrative Generation (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure