Plot Induction and Evolutionary Search for Story Generation

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1562–1572, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Plot Induction and Evolutionary Search for Story Generation Neil McIntyre and Mirella Lapata School of Informatics, University of Edinburgh 10 Crichton Street, Edinburgh, EH8 9AB, UK n.d.mcintyre@sms.ed.ac.uk, mlap@inf.ed.ac.uk Abstract In this paper we develop a story genera- tor that leverages knowledge inherent in corpora without requiring extensive man- ual involvement. A key feature in our ap- proach is the reliance on a story planner which we acquire automatically by record- ing events, their participants, and their precedence relationships in a training cor- pus. Contrary to previous work our system does not follow a generate-and-rank archi- tecture. Instead, we employ evolutionary search techniques to explore the space of possible stories which we argue are well suited to the story generation task. Experi- ments on generating simple children’s sto- ries show that our system outperforms pre- vious data-driven approaches. 1 Introduction Computer story generation has met with fasci- nation since the early days of artificial intelli- gence. Indeed, over the years, several genera- tors have been developed capable of creating sto- ries that resemble human output. To name only a few, TALE-SPIN (Meehan, 1977) generates sto- ries through problem solving, MINSTREL (Turner, 1992) relies on an episodic memory scheme, es- sentially a repository of previous hand-coded sto- ries, to solve the problems in the current story, and MAKEBELIEVE (Liu and Singh, 2002) uses commonsense knowledge to generate short stories from an initial seed story (supplied by the user). A large body of more recent work views story gener- ation as a form of agent-based planning (Swartjes and Theune, 2008; Pizzi et al., 2007). The agents act as characters with a list of goals. They form plans of action and try to fulfill them. Interesting stories emerge as plans interact and cause failures and possible replanning. The broader appeal of computational story gen- eration lies in its application potential. Examples include the entertainment industry and the devel- opment of tools that produce large numbers of plots automatically that might provide inspiration to professional screen writers (Agudo et al., 2004); rendering video games more interesting by allow- ing the plot to adapt dynamically to the players’ actions (Barros and Musse, 2007); and assisting teachers to create or personalize stories for their students (Riedl and Young, 2004). A major stumbling block for the widespread use of computational story generators is their reliance on expensive, manually created resources. A typi- cal story generator will make use of a knowledge base for providing detailed domain-specific infor- mation about the characters and objects involved in the story and their relations. It will also have a story planner that specifies how these characters interact, what their goals are and how their ac- tions result in different story plots. Finally, a sen- tence planner (coupled with a surface realizer) will render an abstract story specification into natural language text. Traditionally, most of this knowl- edge is …

Content truncated to 500 words