State-of-the-Art in Automated Story Generation Systems Research

ABSTRACT

This paper presents a review of research works from the last several years in automated story generation systems. These systems are categorised into interactive story generation systems and non-Interactive story generation systems. Interactive systems are those that collaborate with a user/author during the process of creating and/or executing the story. The extent of user interaction varies across systems but remains an integral part of the creation and/or the unfolding of the story. Non-Interactive systems concentrate on complete automation of the creative process involved in narrative generation to create diverse and interesting stories. Interactive story generators specifically designed for video game narratives are reviewed as a separate sub-class of interactive story generation systems. Also reviewed are the methods used for evaluation of story generation systems as a way to explore the possibility of having standard methods of evaluation within the research community. The paper includes a discussion of trends and directions of the research discipline.

KEYWORDS:

• Automated narrative generation
• interactive narratives
• automated story generation
• storytelling systems
• computational creativity

Acknowledgments

The compiling and writing of this paper was partially supported by the US National Science Foundation under their International Research Experience for Students (IRES) program via grant #1458272.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1. Fabula comes from Russian romantic narratology to mean the sequence of events in the story. It contains all the events in a story in the proper sequence.

2. The term sjuzhet also comes from Russian romantic narratology to mean what parts of the fabula are revealed to the reader as part of the telling of the story.

3. Classical AI planning research began in the late 1960s with the STRIPS system. It sought to find a sequence of actions that would transform the world from an initial state to a goal state. It combined theorem proving through resolution with heuristic state-space searches. It assumes complete knowledge about and control over the world, and that all actions are deterministic in nature. See (Fikes and Nilsson, 1993) for a brief introduction to AI planning systems.

4. HTNs compose a plan as a set of primitive tasks whose sequence is governed by a network of constraints. It has some rough similarity to STRIPS.

5. Partial-order planning is a planning strategy based on least-commitment planning, where only essential ordering is decided and all other ordering is treated flexibly (Weld, 1994). “The idea of a partial-order planner is to have a partial ordering between actions and only commit to an ordering between actions when forced.”  (Poole and Mackworth, 2017).

6. LSTMs are a form of neural networks that use a constant error flow to bridge over gaps in time-based learning, such as would exist in composing narratives. See (Hochreiter and Schmidthube, 1997) for further information.

7. Haslum defines compilation as “… a systematic remodeling of the problem such that a classical plan for the reformulated problem meets also the non-classical requirements.” (Haslum, 2012, p. 383),

8. Briefly, CBR looks for similarities between a current problem and historical problems in memory (in the form of cases) that were once successfully resolved. A solution that resolved a similar problem in the past can be applied to the current problem if the problems are sufficiently similar. See (Kolodner, 1993) for a full description of CBR.

9. The ramification problem is when an action taken has unintended secondary or tertiary consequences or effects that were not envisioned.

10. Constructivist Theory – learning theory in education which states that the learner (or reader in this case) understands material based on their own unique experiences (Western Governors University, 2020).

11. For further information on Cased-Based Planning, refer to Hammond (1986) and Kolodner (1993).

12. Plans are defined as a set of primitive actions in the world. Complete knowledge of the world is necessary.

13. State-space Planning – process for searching for a solution from a state space, which contains all of the data to be searched; the resulting plan is a path through the state space (Nau, 2012)

14. BDI is a common paradigm for creating intelligent software agents. See Bratman (1992). It assumes that agents have three mental attitudes: beliefs (knowledge about the world); desires (goals, and plans to achieve these goals); and intentions (commitment to pursue the desires).

15. CxBR is a context-centric paradigm for intelligent reasoning by agents in tactical simulations. See (Gonzalez, 2014) for a full description of Context-Based Reasoning.

16. That is, they work as a result of a complex set of computations with their weights, but it is not normally clear how the weights affect their solutions.

17. Q-Learning is a reinforcement learning algorithm that is values-based and model-free and works by learning the value of the optimal policy independent of the agent actions (Shyalika, 2019). Reinforcement learning, in general uses trial and error to find a behavior (called a policy) by rewarding moves by the learning agent that lead to success and punishing those that result in failure.

18. Sequence-to-sequence neural networks are deep networks that can learn sequences of words or images of arbitrary lengths, something that mainstream deep neural networks cannot easily do. See (Sutskever, Vinyals & Le, 2014)

19. https://github.com/shivam5992/textstat

Additional information

Funding

This work was supported by the Office of International Science and Engineering [ISE-1458272].