Open-World Planning for Story Generation

1 Introduction

The standard approach to incorporating storytelling into a computer system is to script a story at design time. That is, a system's designers determine ahead of time what the story should be and hard-code the story into the system. An alternative approach is to generate stories either dynamically or on a per-session basis using planning.

Young [1999] suggests that planning has many benefits as a model of narrative.

• Plans are comprised of partially ordered steps. If steps are character actions, then a plan is a good model of a story fabula - a chronological enumeration of events that occur in the story world.
• Planning algorithms construct plans based on causal dependencies between steps. This ensures that all events are part of causal chains, resulting in coherent story structure.

Story planners such as Universe [Lebowitz, 1985] and IPOCL [Riedl and Young, 2004] require a predefined world description as input. The task of creating the world in which a story is set is already accomplished by the "human author" - the user - and a story planner only has to find a plot that can be performed in the story world. It is possible for the human author to describe a story world initial state that cannot be transformed through character actions into the desired outcome. In this case, the responsibility for a planner's failure lies with the human author. Another

R. Michael Young

Department of Computer Science North Carolina State University Raleigh, NC 27695 young@csc.ncsu.edu

possibility is that the story planner can find a solution plan, but the solution plan is strangely structured because the planner must work around limitations inherent in the initial state description.

It is our belief that a story planner that has discretion over the description of the initial story world state will:

• Be able to avoid failure conditions that are attributed to the human author's definition of the initial world state.
• Find better quality solutions because the planner does not need to work around limitations inherent in the human author's description of the initial world state.

2 Initial State Revision

The use of the closed world assumption (CWA) presupposes complete and correct knowledge about the world. Since the universe of discourse that describes any story world is potentially infinite, the practical implementation of the CWA is to enumerate everything about the world that is known to be true so that everything that is not explicitly declared to be true is presumed false. Since story worlds are often fictional, the CWA places a burden on the human author to completely specify the story world or risk limiting the stories that can be constructed by the planner. However, there may be many aspects of the story world that the human author may not have a preference over.

The Initial State Revision (ISR) algorithm partitions knowledge about the initial world state into three sets: known true (T), false (F), and undetermined (U). T is the set of atomic ground sentences that are known to be true. F is the set of atomic ground sentences that are known to be false or are assumed to be false because their true value is not specified by the human author. U is the set of atomic (but not necessarily ground) sentences whose truth values are undetermined but not assumed to be false. U is the set of knowledge about the state of the world that the human author has explicitly designated as having no preference over. Consequently the possible values of U define possible worlds in which the story can be set. Initial state revision reduces the set of possible worlds by committing to values of sentences in the undetermined set as necessary to produce the best possible story plot.

simultaneously true in the initial state of the world. ISR utilizes mutual exclusion sets (also called mutex sets). A mutex set is a set of sentences such that no two sentences can both be true in the initial state. If a sentence in a mutex set is determined to be true, then all other sentences in the mutex set are determined to be false. In the example, the sentences in U are all mutually exclusive to ensure that the gun cannot be in more than one place.

3 Conclusions

Planners are constrained to operate in the world as provided by their users. For an agent operating in a limited domain, it is possible for the world to be completely specified. For infinitely large domains such as a fictional story world, it is impossible to encode every fact about the world. The closed world assumption places a burden on the human author to describe a world that supports story generation. It is possible, however, that despite the human author's intentions, the story world description does not adequately suit storytelling, resulting in planner failure or in solution story plans that are oddly structured to overcome limitations of the world description. The ISR planning algorithm assumes creative control over aspects of the story world description. With control over the initial state of the story world, a story planner can find better story plans because it is not limited by assumptions made by the human author.

Acknowledgements

The work presented here has been supported by the National Science Foundation CAREER Award #0092586.