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

1 Narrative in Cognitive Science and AI

Narrative intelligence is fundamental for organizing experiences, understanding our surroundings, and forming predictions about the future [Schank, 1995]. Computational systems that leverage narrative intelligence benefit applications that involve stories including entertainment, education, skill training, and legal decision-making.

AI planning research is a popular source of data structures and algorithms for understanding, generating, and reasoning about stories [Young et al., 2014]. Narratologists frequently distinguish the story (i.e. fabula) of narrative from the discourse [Chatman, 1980], and plans have proven useful for modeling both story and discourse [Young, 2007]; they are effective for modeling discourse because a coherent sequence of communicative actions is plan-like [Cohen and Perrault, 1979], and plans are effective for modeling stories because stories are composed of events with cause-effect relations with characters themselves forming plans to achieve goals. Psychological studies have demonstrated that plans capture many of the key aspects of narratives that spectators use to understand narrative discourse [Radvansky et al., 2014; Cardona-Rivera et al., 2016].

2 Problems for Narrative Systems

One of the central items in the narrative planning research agenda is to adapt planners originally designed for efficient problem solving to produce plans which are interesting by virtue they have properties worth telling (i.e. tellable) [Pratt, 1977]. However, narratologists often disagree on which properties make a story tellable. Some properties such as conflict are essential for tellability [Ware et al., 2014]. However, other properties may depend on the goals of the narrator. For example, a screenwriter may add an event at the story level (e.g. a non-central character slips off a narrow bridge) in order to elicit a discourse effect (e.g. believing this bridge is a dangerous obstacle for the protagonist). In this work, a narrative theoretic meta-plan language is used to specify constraints to support story tellability.

A typical approach to planning-based narrative generation is a story-then-discourse pipeline approach, in which a story is produced from a story planner and passed as input to a discourse planner, which then produces a plan for telling the story [Jhala and Young, 2010]. As a consequence, the story is created in isolation and not tailored for the discourse plan. If there are story constraints associated with discourse actions, an input plan that solves a story problem may not meet some set of constraints needed to solve the discourse problem (i.e. the story plan is incompatible with the discourse goals), even though a solution to the story problem exists that meets those constraints. We call a planner that generates both story and discourse plans from story and discourse problems bipartite complete just when the planner will find a compatible pair of story and discourse solutions when one exists.

⇤These match the formatting instructions of IJCAI-07. The support of IJCAI, Inc. is acknowledged.

3 The Bipartite Planner

Partial-order causal link (POCL) planning is a classic AI algorithm for searching through plan-space such that each branch in the search is a refinement to a plan. Through an iterative process of identifying flaws in the plan and repairing them in a least-commitment manner [Penberthy and Weld, 1992], valid solutions are discovered. The BiPOCL planner is a bipartite 1 plan-space algorithm which scaffolds a story to support discourse goals of a discourse plan. The planner searches for solutions to two problems, a story problem and a discourse problem, where a solution is a plan of actions to bring an initial state to a goal state. Flaws are incrementally selected and resolved using plan refinement methods, and new flaws are detected. A branch in the search is discontinued when bindings and orderings in either plan are inconsistent.

At the story level, the solution represents the actions of characters in the storyworld, where characters are agents that adopt plans and have conflicts, to bring the storyworld from an initial to a goal state. At the discourse level, the solution is the communicative plan of a narrator agent, and the state of the world is a conjunction of ground literals indicating what a spectator agent believes is true and not true about the story world. The terms of these literals are discourse variables that become associated with story elements, the plan-based narrative-theoretic data structures of the story plan; these associations are called couplings. Each communicative action (i.e. discourse plan step) is an instantiated STRIPS-style operator with preconditions and effects [Fikes and Nilsson, 1972], plus a specification of minimal prerequisite criteria for variables in the action that story elements must possess to form a coupling. When a communicative action is added, the variables of that step and its prerequisite criteria are posted as flaws for the story plan. This type of flaw is resolved by reusing an existing story element or by creating and adding an element to the plan meeting the criteria, and adding a coupling between the variable and the element.

1 The term 'bipartite' refers here to the story and discourse parts of narrative [Young, 2007].

As an example, consider a communicative action to convey that a location is dangerous by virtue that some character has died at that location. In the associated story plan, a location is coupled with the location variable in the discourse operator, and a character dies at this location via available rules of the story world, including rules about character intentionality (e.g. a character only consents to actions on a path to a goal of that character) [Ware et al., 2014]. As a result, the spectator believes the location is dangerous.

Story elements may be nested (i.e. they are often composite structures) and can be composed into a tree of elements. For example, a characters plan is an element that contains an agent, a goal literal, a step that motivated the adoption of the goal, etc., and each of these elements are composed of more primitive elements. After a coupling is formed, appropriate dependencies must be tracked such as when a discourse variable forms a coupling with a composite story element that has a descendant element in a coupling with another discourse variable. A story element function is used to navigate the story element tree and determine if a coupling is possible.

The algorithm continues detecting and refining flaws until a valid solution is found or all branches are terminated. A BiPOCL solution is considered valid when both story and discourse solutions are valid and every discourse variable is coupled with a story element.

4 Conclusion and FutureWork

With prior approaches to story and discourse generation, a story solution is passed through a story-then-discourse pipeline. In this discourse-driven approach to narrative planning, constraints for the story solution are discovered as part of the search for the discourse solution. The BiPOCL planner is bipartite complete because it adopts prerequisites rather than constraints. Prerequisites differ from constraints in Darshak because prerequisites prune the story search space during discourse plan refinement search, whereas constraints on the story prune the discourse search space during discourse plan refinement. This achieves bipartite completeness because prerequisites may be formed before story refinement and can therefore avoid possible inconsistencies between prerequisites and existing story elements. 2

With the current design, authoring discourse action operators requires familiarity with narrative theoretic planning structures, so future work will alleviate this burden for users by encapsulating low level details about plans. In addition, structural properties that are of representational benefit for eliciting discourse effects have been identified (e.g. good timing [Winer et al., 2015]) and BiPOCL will be expanded to leverage these properties in an actionable way. Finally, work is needed to implement the proposed algorithm and find heuristics to improve the search time.

2 Such a proof follows the reasoning for completeness of UCPOP [Penberthy and Weld, 1992].