Student research opportunities
Planning a Story
Project Code: CECS_732
This project is available at the following levels:
CS single semester, Honours, Summer Scholar, Masters
Supervisor:
Dr Patrik HaslumOutline:
The plot (or narrative) of a story has some similarity with a plan, as it is usually defined in classical AI planning. It is a sequence of events, each of which can be viewed as an action that changes the state of the world. For a story to be perceived as coherent and plausible, the event sequence must be logically possible (i.e., preconditions achieved before an action takes place) and connected by causes and effects (i.e., each event contributes something to the story, by setting the stage for later events; this corresponds to a notion of non-redundancy in plans). The "goal" of a story, in this view, is the end state that the story's author has in mind. However, there more requirements on a narrative than on a plan: in addition to being logically sound, it should be believable, and perhaps also entertaining. One aspect of this is the believability of the actions of characters in the story: the characters actions should not only be possible, and be contributing to the overall goal of the story, but should be perceivable as contributing to the goals that the character has (which are not necessarily the same as the goal of the story). Each action done by each character in the story should be motivated by (i.e., directly or indirectly contribute to achieving) a goal of the character. Of course, goals of a character can change throughout the course of the story, as they are influenced by other characters, or events in the world around them. But each such change of a characters goals must also have a cause.
Using the connection between narratives and planning, Reidl and Young ("Narrative Planning: Balancing Plot and Character", Journal of AI Research, vol. 39, p. 217-268, 2010) created a "narrative planner", by extending an traditional partial-order causal link planner with a mechanism to enforce the extra constraint of respecting character motivations. However, it is also possible to compile the narrative planning problem into a classical planning problem, and solve it using any classical planner. (This is also much more efficient than Riedl &: Young's planner.) The compilation is described in a recent research note ("Narrative Planning: Compilations to Classical Planning", Journal of AI Research, vol. 44, p. 383-395, 2012).
Goals of this project
The study of compilations revealed that there are many limitations to the current narrative planning model: for example, it does not allow for characters that make mistakes or fail to achieve their goals, or for characters' state of knowledge. Perhaps some of these limitations can be removed by developing more comprehensive compilations. This is a topic for future research. At the same time, however, the compiled problems are already somewhat difficult for a classical planner to deal with (even when not very large), and will only become more so as more complications are added to the model. Thus, another question to explore is why these compiled problems are so difficult for current planners, and if that can be remedied by changing either the compilations or the planners.
Background Literature
Reidl and Young, "Narrative Planning: Balancing Plot and Character", Journal of AI Research, vol. 39, p. 217-268, 2010, which can be found in JAIR's on-line archive.
Haslum, "Narrative Planning: Compilations to Classical Planning", Journal of AI Research, vol. 44, p. 383-395, 2012, also available on-line from JAIR.
