Narrative Planning: Balancing Plot and Character
  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.
