Narrative planning is the use of automated planning to construct, communicate, and understand stories, a form of information to which human cognition and enaction is pre-disposed. We review the narrative planning problem in a manner suitable as an introduction to the area, survey different plan-based methodologies and affordances for reasoning about narrative, and discuss open challenges relevant to the broader AI community.

Story sifting (or story recognition) allows for the exploration of events, stories, and patterns that emerge from simulated storyworlds. The goal of this work is to reduce the authoring burden for creating sifting queries. In this paper, we use the event traces of simulated storyworlds to create Dynamic Character Networks that track the changing relationship scores between characters in a simulation. These networks allow for the fortunes between any two characters to be plotted against time as a story arc. Similarity scores between story arcs from the simulation and a user’s query arc can be calculated using the Dynamic Time Warping algorithm. Events corresponding to the story arc that best matches the query arc can then be returned to the user, thus providing an intuitive means for users to sift a variety of stories without coding a search query. These components are implemented in our experimental prototype ARC SIFT. The results of a user study support our expectation that ARC SIFT is an intuitive and accurate tool that allows human users to sift stories out from a larger chronicle of events emerging from a simulated story world.

Narrative Generation has attracted significant interest as a novel application of Automated Planning techniques. However, the vast amount of narrative material available opens the way to the use of Deep Learning techniques. In this paper, we explore the feasibility of narrative generation through self-supervised learning, using sequence embedding techniques or auto-encoders to produce narrative sequences. We use datasets of well-formed plots generated by a narrative planning approach, using pre-existing, published, narrative planning domains, to train generative models. Our experiments demonstrate the ability of generative sequence models to produce narrative plots with similar structure to those obtained with planning techniques, but with significant plot novelty in comparison with the training set. Most importantly, generated plots share structural properties associated with narrative quality measures used in Planning-based methods. As plan-based structures account for a higher level of causality and narrative consistency, this suggests that our approach is able to extend a set of narratives with novel sequences that display the same high-level narrative properties. Unlike methods developed to extend sets of textual narratives, ours operates at the level of plot structure. Thus, it has the potential to be used across various media for plots of significant complexity, being initially limited to training and generation operating in the same narrative genre.

AI Planning has been shown to be a useful approach for the generation of narrative in interactive entertainment systems and games. However, the creation of the underlying narrative domain models is challenging: the well documented AI planning modelling bottleneck is further compounded by the need for authors, who tend to be non-technical, to create content. We seek to support authors in this task by allowing natural language (NL) plot synopses to be used as a starting point from which planning domain models can be automatically acquired. We present a solution which analyses input NL text summaries, and builds structured representations from which a pddl model is output (fully automated or author in-the-loop). We introduce a novel sieve-based approach to pronoun resolution that demonstrates consistently high performance across domains. In the paper we focus on authoring of narrative planning models for use in interactive entertainment systems and games. We show that our approach exhibits comprehensive detection of both actions and objects in the system-extracted domain models, in combination with significant improvement in the accuracy of pronoun resolution due to the use of contextual object information. Our results and an expert user assessment show that our approach enables a reduction in authoring effort required to generate baseline narrative domain models from which variants can be built.

The visualization of procedural knowledge from textual documents using 3D animation may be a way to improve understanding. We are interested in applying this approach to documents relating to patient education for bariatric surgery: a domain with challenging textual documents describing behavior recommendations that contain few procedural steps and leave much commonsense knowledge unspecified. In this work we look at how to automatically capture knowledge from a range of differently phrased recommendations and use that with implicit knowledge about compliance and violation, such that the recommendations can be visualized using 3D animations. Our solution is an end-to-end system that automates this process via: analysis of input recommendations to uncover their conditional structure; the use of commonsense knowledge and deontic logic to generate compliance and violation rules; and mapping of this knowledge to update a default knowledge base, which is used to generate appropriate sequences of visualizations. In this paper we overview this approach and demonstrate its potential.

In this article, we discuss an innovative media entertainment application called Interactive Movietelling. As an offspring of Interactive Storytelling applied to movies, we propose to integrate narrative generation through artificial intelligence (AI) planning with video processing and modeling to construct filmic variants starting from the baseline content. The integration is possible thanks to content description using semantic attributes pertaining to intermediate-level concepts shared between video processing and planning levels. The output is a recombination of segments taken from the input movie performed so as to convey an alternative plot. User tests on the prototype proved how promising Interactive Movietelling might be, even if it was designed at a proof of concept level. Possible improvements that are suggested here lead to many challenging research issues.

Despite recent progress in plan-based narrative generation, one major limitation is that systems tend to produce a single plotline whose progression entirely determines the narrative experience. However, for certain narrative genres such as serial dramas and soaps, multiple interleaved subplots are expected by the audience, as this tends to be the norm in real-world, human-authored narratives. Current narrative generation techniques have overlooked this important requirement, something which could improve the perceived quality of generated stories. To this end, we have developed a flexible plan-based approach to multiplot narrative generation, that successfully generates narratives conforming to different subplot profiles, in terms of the number of subplots interleaved and the relative time spent on each presentation. We have identified specific challenges such as: distribution of virtual characters across subplots; length of each subplot presentation; and transitioning between subplots.

Narrative generation represents an application domain for AI planning where plan quality is related to properties such as shape of plan trajectory. In our work we have developed a plan-based approach to narrative generation that uses character relationships as a key determinant in controlling plan shape (relationships are key in genres such as serial dramas and soaps). Our approach is implemented in a demonstration Interactive Narrative, called NetworkING, set in the medical drama genre. The system features a user-friendly mechanism for specifying relationships between virtual characters, via a social network and real-time visualisation of generated narratives on a 3D stage.

Previous Interactive Storytelling systems have been designed to allow active user intervention in an unfolding story, using established multi-modal interactive techniques to influence narrative development. In this paper we instead explore the use of a form of passive interaction where users' affective responses, measured by physiological proxies, drive a process of narrative adaptation. We introduce a system that implements a passive interaction loop as part of narrative generation, monitoring users' physiological responses to an on-going narrative visualization and using these to adapt the subsequent development of character relationships, narrative focus and pacing. Idiomatic cinematographic techniques applied to the visualization utilize existing theories of establishing characteristic emotional tone and viewer expectations to foster additional user response. Experimental results support the applicability of filmic emotional theories in a non-film visual realization, demonstrating significant appropriate user physiological response to narrative events and "emotional cues". The subsequent narrative adaptation provides a variation of viewing experience with no loss of narrative comprehension.

The dominant interaction paradigm in Interactive Storytelling (IS) systems so far has been active interventions by the user by means of a variety of modalities. PINTER is an IS system that uses physiological inputs - surface electromyography (EMG) and galvanic skin response (GSR) [1] - as a form of passive interaction, opening up the possibility of the use of traditional filmic techniques [2, 3] to implement IS without requiring immersion-breaking interactive responses. The goal of this demonstration is to illustrate the ways in which passive interaction combined with filmic visualisation, dialogue and music, and a plan-based narrative generation approach can form a new basis for an adaptive interactive narrative.

We present a novel approach to the automatic generation of filmic variants within an implemented Video-Based Storytelling (VBS) system that successfully integrates video segmentation with stochastically controlled re-ordering techniques and narrative generation via AI planning. We have introduced flexibility into the video recombination process by sequencing video shots in a way that maintains local video consistency and this is combined with exploitation of shot polysemy to enable shot reuse in a range of valid semantic contexts. Results of evaluations on output narratives using a shared set of video data show consistency in terms of local video sequences and global causality with no loss of generative power.

Currently, automatic generation of filmic variants faces a number of key technical issues and thus it usually resorts to the shooting of multiple versions of alternative scenes. However, recent advancements in video analysis has made this objective feasible, though semantic consistency must be somehow preserved. This demo presents a video-based storytelling (VBS) system that successfully integrates video processing with narrative generation by means of a shared semantic description. The novel filmic variants are constructed through a flexible video recombination process that takes advantage of the polysemy of baseline video segments. The short output video clips shown in this demo prove how the generated narratives are semantically consistent while keeping generative power intact.

Virtual characters are at the epicentre of Interactive Storytelling systems and in recent years multiple AI planning approaches have been described to specify their autonomous behaviour. This demonstrator provides an overview of our novel approach to the definition of virtual characters aimed at achieving a balance between character autonomy and global plot structure which proposes the notion of a character's Point of View. Additionally, the demonstrator offers the active spectator the ability to discover the story described from the perspective of a number of different characters. We present our fully-implemented Interactive Narrative based on Shakespeare's Merchant of Venice. The system, which features a novel AI planning approach to story generation, can generate very different stories depending on the Point of View adopted and support dynamic modification of the story world which results in different story consequences.

In the paper we present a prototype of video-based storytelling that is able to generate multiple story variants from a baseline video. The video content for the system is generated by an adaptation of forefront video summarisation techniques that decompose the video into a number of Logical Story Units (LSU) representing sequences of contiguous and interconnected shots sharing a common semantic thread. Alternative storylines are generated using AI Planning techniques and these are used to direct the combination of elementary LSU for output. We report early results from experiments with the prototype in which the reordering of video shots on the basis of their high-level semantics produces trailers giving the illusion of different storylines.

We have seen ten years of the application of AI planning to the problem of narrative generation in Interactive Storytelling (IS). In that time planning has emerged as the dominant technology and has featured in a number of prototype systems. Nevertheless key issues remain, such as how best to control the shape of the narrative that is generated (e.g., by using narrative control knowledge , i.e., knowledge about narrative features that enhance user experience) and also how best to provide support for real-time interactive performance in order to scale up to more realistic sized systems. Recent progress in planning technology has opened up new avenues for IS and we have developed a novel approach to narrative generation that builds on this. Our approach is to specify narrative control knowledge for a given story world using state trajectory constraints and then to treat these state constraints as landmarks and to use them to decompose narrative generation in order to address scalability issues and the goal of real-time performance in larger story domains. This approach to narrative generation is fully implemented in an interactive narrative based on the “Merchant of Venice.” The contribution of the work lies both in our novel use of state constraints to specify narrative control knowledge for interactive storytelling and also our development of an approach to narrative generation that exploits such constraints. In the article we show how the use of state constraints can provide a unified perspective on important problems faced in IS.

Many known planning tasks have inherent constraints concerning the best order in which to achieve the goals. A number of research efforts have been made to detect such constraints and to use them for guiding search, in the hope of speeding up the planning process. We go beyond the previous approaches by considering ordering constraints not only over the (top-level) goals, but also over the sub-goals that will necessarily arise during planning. Landmarks are facts that must be true at some point in every valid solution plan. We extend Koehler and Hoffmann's definition of reasonable orders between top level goals to the more general case of landmarks. We show how landmarks can be found, how their reasonable orders can be approximated, and how this information can be used to decompose a given planning task into several smaller sub-tasks. Our methodology is completely domain- and planner-independent. The implementation demonstrates that the approach can yield significant runtime performance improvements when used as a control loop around state-of-the-art sub-optimal planning systems, as exemplified by FF and LPG.