PaperlayerView exact revision on arXiv

Source-linked AI summary

Narrative Planning: Balancing Plot and Character

Mark Owen Riedl, Robert Michael Young

arXiv:1401.3841v1cs.AI

TL;DR

The paper addresses narrative-generation systems that must produce causally coherent stories while making character actions understandable as intentional. It presents IPOCL, a refinement-search planner that models character goals and commitments, and finds that its generated narratives better support comprehension of character goals, intentions, and motivations than POCL narratives.

  • Problem

    Conventional planners generate sound action sequences but do not consider whether character actions are natural or believable from the character’s or audience’s perspective.

  • Method

    IPOCL models narrative generation as refinement-search planning and adds character goals, intentionality, and commitment structures to causally sound plot planning.

  • Results

    IPOCL-generated narratives supported reader comprehension of character goals, intentions, and motivations better than narratives generated by the control condition.

  • Takeaways & Limitations

    Narrative planning benefits from reasoning about individual and potentially conflicting character goals, not only from finding sound operations that achieve a goal situation.

  • Takeaways & Limitations

    IPOCL assumes every character intention is successfully achieved, limiting narratives involving repeated failures or one character defeating another.

Abstract

from arXiv · show

Narrative, and in particular storytelling, is an important part of the human experience. Consequently, computational systems that can reason about narrative can be more effective communicators, entertainers, educators, and trainers. One of the central challenges in computational narrative reasoning is narrative generation, the automated creation of meaningful event sequences. There are many factors -- logical and aesthetic -- that contribute to the success of a narrative artifact. Central to this success is its understandability. We argue that the following two attributes of narratives are universal: (a) the logical causal progression of plot, and (b) character believability. Character believability is the perception by the audience that the actions performed by characters do not negatively impact the audiences suspension of disbelief. Specifically, characters must be perceived by the audience to be intentional agents. In this article, we explore the use of refinement search as a technique for solving the narrative generation problem -- to find a sound and believable sequence of character actions that transforms an initial world state into a world state in which goal propositions hold. We describe a novel refinement search planning algorithm -- the Intent-based Partial Order Causal Link (IPOCL) planner -- that, in addition to creating causally sound plot progression, reasons about character intentionality by identifying possible character goals that explain their actions and creating plan structures that explain why those characters commit to their goals. We present the results of an empirical evaluation that demonstrates that narrative plans generated by the IPOCL algorithm support audience comprehension of character intentions better than plans generated by conventional partial-order planners.

1. Introduction

Narrative generation aims to create understandable stories with both causally coherent plots and believable, intentional characters. IPOCL addresses these requirements through refinement-search planning that represents and explains character goals.

  • Motivation: Dynamic narrative generation can adapt stories to users, expand replay value, and create interactions beyond designers’ initial scenarios.The paper contrasts this with fixed design-time scripts, which limit adaptation, story variety, and replay value.
  • Narrative Requirements: Narrative understandability depends especially on logical causal progression and character believability.Causal progression concerns events obeying story-world rules, while believability concerns audience acceptance of character actions.
  • Planning Approach: Planning represents narrative action, temporality, and causality, but conventional planners do not model character believability.The paper therefore treats ordinary planning as insufficient for narrative generation.
  • Contribution: IPOCL extends refinement search by identifying character goals that explain actions and constructing plan structures that explain commitment to those goals.It is designed to preserve causally sound plot progression while modeling character intentionality.

2. Narrative and Planning

The paper formalizes narrative generation as fabula planning: finding sound, believable character actions that achieve author goals. It argues that conventional planning must be extended to account for audience-perceived intentionality.

  • Narrative Background: A narrative’s fabula is the temporally ordered sequence of story-world events, whereas the sjuzet is the subset presented through narration.The distinction separates events that occur in the story world from how those events are communicated.
  • Narrative Background: Narrative comprehension is associated with causal event structure and the attribution of intentions to characters.These properties motivate attention to both plot causality and character goals.
  • Narrative Background: Character believability is the audience’s perception that character actions preserve suspension of disbelief, especially through goal-oriented behavior.Internal attributes such as desires and intentions manifest through decisions and behaviors.
  • Planning Model: The fabula planning problem seeks a sound and believable action sequence transforming initial state I into a state satisfying goal propositions G.This combines conventional planning soundness with narrative requirements for believable character action.
  • Planning Challenges: Conventional planners select actions for goal achievement without considering whether characters or audiences find those actions natural and believable.The paper identifies this as a limitation of using standard planning directly for narrative generation.
  • Planning Challenges: The authors note that modifying domain assumptions to forbid implausible actions can unnecessarily restrict the narratives an automated system may generate.They use examples such as princesses killing kings or characters locking themselves in towers.
  • Planning Challenges: Heuristic believability ranking guides search but cannot guarantee a believable plan when a shorter sound solution is found first.The planning problem terminates once any sound sequence achieves the goal situation.
  • Intentionality: IPOCL separates author goals from character goals, discovering character goals that explain behavior and constructing structures that illustrate intention formation.The planner must achieve the author’s outcome while making character intentions appear distinct from the author’s desires.

3. Related Work

Related systems include simulation-based generators that model character behavior and deliberative planners that pursue author goals. IPOCL modifies POCL search to combine global causal structure with audience-oriented character intentionality.

  • Simulation-Based Generation: Simulation-based systems progressively determine character actions as the story-world context evolves.They establish characters and world context, then generate behavior over time.
  • Simulation-Based Generation: Simulation systems can produce short or oddly structured narratives when character goals or world facts do not support intended actions.The paper cites Tale-Spin as an example of this failure mode.
  • Deliberative Generation: Deliberative systems pursue author intentions and use global structure to select actions, avoiding some causal problems of temporally local simulation.Existing deliberative systems, however, conflate character goals with human author goals without considering audience perspective.
  • POCL Planning: POCL planners iteratively identify and repair flaws, including unsatisfied preconditions and causal threats, using partial-order constraints and causal links.The paper uses the standard POCL algorithm as the comparison point for IPOCL.
  • IPOCL: IPOCL modifies search-based POCL planning so characters appear to form intentions and act toward them while achieving author-indicated outcomes.The resulting narratives aim to combine logical causal progression with believable characters.

4. Intent-Driven Planning

IPOCL extends conventional partial-order causal-link planning to generate fabula plans whose character intentionality is observable alongside causally sound plot progression. It searches plans and agent intentions together, using character-aware action schemata and intentionality reasoning.

  • IPOCL approach: IPOCL generates fabula plans in which characters act intentionally and their intentionality is observable.It extends conventional POCL planning with an expanded plan representation, completeness definition, and action-selection mechanisms.
  • Planning problem: Fabula planning supports multiple character agents that need not cooperate, while the outcome need not be intended by any character.These requirements differ from conventional planning assumptions involving a single agent or cooperating agents pursuing an intended goal state.
  • IPOCL approach: The planner searches the space of plans and agent intentions simultaneously, revising plans when audience-perspective intentionality tests fail.Agent intentions are checked for plausibility during search rather than treated as separate from planning.
  • Planning problem: IPOCL planning problems comprise an initial state, character-agent symbols, a goal situation, and a set of action schemata.The extended language also specifies which actions may be unintentional and which action parameters denote intentional actors.
  • Action representation: IPOCL action schemata use STRIPS-like preconditions and effects, plus constraints that filter applicable parameter bindings.The special intends predicate appears only in action effects and represents a reasonable character goal that may later be acted upon.
  • Action representation: Happenings may occur without character intention, whereas non-happening actions ordinarily require an actor whose intention the action fulfills.Examples include accidents, involuntary reactions, and forces of nature; action schemata identify intentional actors through an actors slot.

4.2 Character Intentionality in Fabula Planning

IPOCL represents character intentionality with frames of commitment that connect a character’s goal to goal-directed actions and a motivating event. A complete plan must be causally sound and intentional for every non-happening action.

  • Frames of commitment: A frame of commitment records a character, the character’s goal, the associated plan steps, and a final step achieving that goal.All steps in the frame are performed by the same character, and the other steps precede the final step.
  • Frames of commitment: Each frame requires a motivating step that establishes intends(a, ga) before the character’s goal-directed actions begin.The motivating step makes commitment to the goal reasonable from the audience’s perspective.
  • Plan completeness: IPOCL treats commitments as persistent through time, although their release is represented only by the temporal boundaries of the intentionality interval.A character remains committed even when the desired world state is undone.
  • Frames of commitment: Character intentions are represented both as intends(a, ga) propositions and as frames of commitment linking intentions to subsequent actions.The proposition records a potential intention, while the frame captures whether and how the character acts on it.
  • Plan intentionality: An action is intentional when it belongs to a frame of commitment; actions outside such intervals are orphans unless marked as happenings.A character action may belong to more than one interval of intentionality.
  • Plan completeness: A complete IPOCL plan establishes every step precondition, resolves every causal threat, and makes every non-happening step intentional.The first two conditions are conventional causal completeness; a causally complete plan can still contain orphans.

4.3 Integrating Intentionality into Least-Commitment Planning

IPOCL extends least-commitment causal planning with motivation and intent reasoning. It repairs flaws by discovering frames of commitment, linking motivating actions to goals, and assigning actions to intentional intervals.

  • Flaw types: IPOCL adds open motivation, intent, and intentional threat flaws to the open conditions and causal threats handled by conventional POCL planning.These flaws capture missing motivation, unexplained same-character actions, and conflicting character goals.
  • Frame discovery: Frame discovery creates character commitments by selecting an action effect as an internal goal and adding an open motivation flaw.The newly created frame includes the selected action and the character performing it.
  • Intent planning: IPOCL searches existing commitment frames when a step causally supports a same-character action or serves an action through another character’s contracted subgoal.Each eligible frame receives an intent flaw so search can decide whether the step belongs to that intentional interval.
  • Termination: The algorithm terminates only with consistent orderings and bindings, no remaining flaws, and every plan step assigned to a frame of commitment.Otherwise, inconsistent or unrepaired partial plans fail.
  • Motivation planning: Motivation planning repairs open motivation flaws by finding an action that establishes intends(a, ga) and ordering it before the frame’s other actions.A character cannot begin pursuing a goal before committing to it.
  • Intent planning: IPOCL propagates intent flaws to permit actions to belong to multiple frames, while unresolved orphan steps force backtracking when planning completes.Overloaded actions constrain the placement of motivating steps because each motivating step must precede the earliest frame action.

4.4 An Example

The example traces IPOCL’s construction of a story in which a Villain bribes the President and the President becomes corrupt. The planner adds character goals, motivating actions, and commitment frames to explain the actions.

  • Initial plan: The example’s author goal is corrupt(President), achieved by instantiating Bribe(Villain, President, $).The Bribe action has corrupt(President) as an effect and becomes the final step of a Villain commitment frame.
  • Villain intentionality: IPOCL selects controls(Villain, President) as the Villain’s character goal, distinct from the story outcome despite being satisfied by the same action.The selected goal creates a frame of commitment whose final step is Bribe.
  • Villain intentionality: The Villain’s frame initially has an open motivation flaw because no action yet explains the Villain’s commitment to controlling the President.The initial state may satisfy this motivation condition in the example.
  • Contracted subgoal: To satisfy Bribe’s has(Villain, $) precondition, IPOCL instantiates Give(Hero, Villain, $), then assigns the Hero the goal has(Villain, $).The Hero’s commitment is in service to the Bribe action.
  • Contracted subgoal: The planner chooses Coerce(Villain, Hero, has(Villain, $)) to motivate the Hero’s goal and considers whether the coercion itself belongs to a Villain commitment frame or remains an orphan.Frame discovery can use the coercion’s intention effect to construct another Villain frame.

4.5 Complexity of the IPOCL Algorithm

IPOCL’s search complexity grows with action instantiations, effects, actors, and repaired flaws. In the example domain, a domain-specific heuristic solved the problem, whereas a domain-independent heuristic exhausted virtual memory.

  • Complexity: IPOCL has computational complexity O(c(b(e + 1)a)n), with n representing search-space depth.The depth counts repaired open-condition, motivation, intent, causal-threat, and intentional-threat flaws.
  • Complexity: The worst-case branching factor is b(e + 1)a because the planner chooses action instantiations, possible commitment-goal effects, and intentions for participating actors.Here, b is the number of legal action instantiations, e the number of effects, and a the number of actors.
  • Complexity: The corresponding IPOCL solution depth is bounded by n_IPOCL = 2n_POCL.Each newly instantiated step can additionally generate a frame of commitment and an open motivation flaw.
  • Example performance: 12.3 hours and 1,857,373 generated nodes characterized the example-domain run with a domain-specific heuristic; 673,079 nodes were visited.The run used a 3GHz Intel Core2 Duo system with 3GB of RAM and 100GB of virtual memory.
  • Example performance: The domain-independent heuristic could not solve the problem before the system ran out of virtual memory.The authors report that better heuristic evaluation functions are needed and that sibling-node discrimination is difficult.

4.6 Limitations and Future Work

The paper identifies limitations in IPOCL’s opportunistic intention discovery, guaranteed goal achievement, weak handling of contradictory intentions, and heuristic quality, while outlining alternative strategies and future improvements.

  • Search and representation: Opportunistic discovery of character intentions expands the searchable narrative space but significantly increases branching, limiting IPOCL’s ability to generate long narratives.The authors regard opportunistic intention discovery as vital for finding narratives with both causal progression and believable character motivation.
  • Narrative scope: IPOCL assumes every intention is achieved, limiting narratives with repeated failures or direct hero–villain defeat.A villain can instead achieve a goal before the hero achieves a conflicting goal, but this changes the represented narrative structure.
  • Narrative scope: Partial-order planning cannot naturally represent actions supporting intentions that remain unachieved, and forward chaining may introduce excessive intentions.Seeding intermediate author goals can force some structures, but requires the author to anticipate aspects of the resulting narrative.
  • Intentional consistency: IPOCL has only weak mechanisms for detecting or preventing contradictory character intentions.The authors suggest better heuristics or reasoning at the frame-of-commitment level, but those extensions remain future work.
  • Heuristics: Better heuristics are needed, including domain-dependent heuristics that use knowledge about characters, settings, or preferences over narrative structure.The example heuristic penalizes character goals judged unreasonable according to intuitions about characters and story types.

5. An Evaluation of Character Intentionality in IPOCL-Generated Fabula Plans

The evaluation compared IPOCL and conventional POCL narratives using QUEST-based predictions and human goodness-of-answer judgments. IPOCL produced narratives whose character goals, intentions, and motivations were better supported in reader comprehension.

  • Evaluation design: The evaluation tested whether IPOCL fabulas support comprehension of character intentions better than fabulas generated by conventional planning algorithms.Participants answered questions about character actions, while QUEST predictions provided an objective comparison framework.
  • Evaluation design: QUEST predicts question-answering performance from graphical story structures that encode relationships between events and perceived character goals.Its arc-search procedures distinguish legal from illegal answers, and structural distance corresponds to human goodness-of-answer judgments.
  • Evaluation design: The POCL and IPOCL conditions used identical story-world initialization, including an Aladdin-based setting, characters, operators, and outcome.IPOCL additionally used actor, happening, and intends information in action schemata, whereas POCL ignored those annotations.
  • Evaluation design: Both planners’ fabula plans were rendered into natural-language narratives and converted into QUEST-compatible structures for predicted question-answering performance.Longbow produced discourse plans from the fabulas before template matching rendered the POCL and IPOCL narratives.
  • Results: t = 1.8743 (p < 0.05) for “poor” question-answer pairs, with IPOCL participants giving significantly lower goodness-of-answer ratings than POCL participants.This result supports Hypothesis 2.
  • Results and discussion: Human judgments may treat an answer as good when there is no evidence against the possibility that a character action was intentional.The authors speculate that readers simultaneously consider multiple explanations for character behavior until evidence disproves them.
  • Results: The authors conclude that IPOCL narratives better supported reader comprehension of character goals, intentions, and motivations than the control narratives.Because both conditions used identical initialization parameters, the generation algorithm was identified as the most significant independent variable.

6. Conclusions

The paper presents IPOCL as a deliberative fabula-generation approach that addresses character intentionality alongside causal plot progression. It reports improved narrative generation over conventional planners while acknowledging limitations in representing failure and jointly reasoning about fabula and sjuzet.

  • IPOCL extends planning-based narrative generation to support audience perception of character intentionality and causal plot progression.The objective is to generate narrative fabula with both properties.
  • IPOCL treats candidate narrative plans as flawed unless audiences can understand each character’s goals and motivations.It repairs intentionality flaws by attributing goals and generating event sequences that motivate them.
  • IPOCL cannot produce narratives in which characters fail to achieve their goals, because planners prune unsuccessful branches and backtrack.Conflicting character goals are temporally ordered so that each character ultimately succeeds serially.
  • The approach assumes fabula and sjuzet can be reasoned about separately, which may suffice for simple telling but not sophisticated effects such as suspense.More sophisticated audience effects may require reasoning about telling while determining what is told.
  • The authors report non-subjective empirical evidence of improvement over alternative conventional planners.They position the work as an incremental framework built from planning and cognitive science principles.

Appendix A.

The appendix documents the Aladdin planning domain used for evaluation, including its problem specification, heuristics, generated plans, QUEST diagrams, and a partial creation trace.

  • The appendix provides evaluation-domain details, including planning specifications, heuristics, complete generated-plan diagrams, QUEST diagrams, and a partial narrative-creation trace.

A.1 Planning Problem Specification for the Study

The evaluation uses PDDL-like planning formulations in which a problem specifies an initial state and goal situation, while operator schemata define available actions and IPOCL-specific planning heuristics guide search.

  • POCL and IPOCL receive the same evaluation inputs, although some input components are unused by POCL.
  • A planning problem specifies the initial world state and goal situation, while the operator library contains operator schemata.
  • Constraints are immutable propositions satisfied only by the initial state, whereas preconditions may be established through planning actions.
  • The domain encodes intentions through effects such as intended marriages, ordered objectives, and responses to threatening monsters.
  • IPOCL evaluates plan nodes with domain-independent and domain-dependent heuristic penalties, with solutions scored at 0.The heuristic combines penalties for actions, flaws, multiple frames per character, orphan actions, repeats, and unsupported character-goal combinations.

A.2 Plan Diagrams and QUEST Structures for the Study

The appendix presents POCL and IPOCL fabula plan diagrams alongside corresponding QUEST knowledge structures for the evaluation study. The diagrams distinguish actions, causal links, and temporal constraints, with IPOCL additionally showing commitment-related structure.

  • Figures 14 and 15 show automatically generated fabula plans for the POCL and IPOCL evaluation conditions.
  • Figures 16 and 17 show the QUEST structures corresponding to the POCL and IPOCL fabula plans.
  • In the plan diagrams, solid boxes denote actions and solid arrows denote causal links between action effects and successor preconditions.
  • Dashed arrows denote temporal constraints introduced by promotion or demotion strategies to resolve causal threats.

A.3 Trace

The IPOCL trace refines a fabula planning problem by resolving goal conditions, character motivations, intentionality flaws, and causal threats. The search ultimately adopts a step linking Aladdin’s intention to the solution.

  • Initial refinement: The trace begins from an initial plan seeking to satisfy Jafar’s marriage goal, exploring 98 children while selecting a refinement.A marriage action is created and given the motivation that Jafar intends to marry Jasmine.
  • Initial refinement: Jafar’s marriage intention is supported through falling in love, Jasmine’s reciprocal marriage intention, and a genie love spell.The spell is commanded by Jafar and requires the genie to be alive.
  • Lamp subplan: Aladdin’s intention to give Jafar the lamp is refined through an order, a pillage action, and conditions requiring Aladdin’s loyalty and survival.These refinements connect lamp possession to the plan’s intentional structure.
  • Causal threat resolution: The plan resolves the genie’s death goal by creating a slaying step and an appearance intended to make the genie scary, while addressing a causal threat to genie life.The trace explicitly records the threat being clobbered by the slaying step.
  • Intentionality refinement: IPOCL tests whether actions can be adopted into character-intention frames, including Aladdin’s lamp goal and Jafar’s marriage goal, while rejecting one Jasmine-related adoption.The trace records multiple adoptions, a no-adoption decision, and continued alternatives for achieving lamp possession.
  • Solution: The search finds a solution when step 9 is adopted by Aladdin’s frame for the intention that Jafar have the lamp.The trace marks this adoption as the solution found.
Loading 1401.3841v1…