Plexus: an interactive story telling system based on the small-world networks model

F. Bertacchini

Department of Linguistics, University of Calabria, Italy.

e-mail: francesca_bertacchini@yahoo.it

C. Senatore

Department of Linguistics, University of Calabria, Italy.

e-mail: caterina.senatore@unical.it, a.talarico@hotmail.it

1. Talarico

Department of Linguistics, University of Calabria, Italy.

e-mail: a.talarico@hotmail.it

Abstract

In this paper, a story telling system, based on the small-world networks model, is presented. The idea is to generate a rich deal of stories, which in turn can be represented as real theatrical events.

The prologue is the main node, from which stories and character are generated, selected from many alternatives. Each character instantiates a sub-network and many paths can be generated, according to mathematical functions. Each story that a character performs is a node in a network (linked with the other stories and to the main node). In this way, the system creates a fractal narrative structure, with scale invariance, which can be reiterated ad libitum, thus producing webs of complex stories.

A first example of one of this web of stories that it is possible to generate will be presented during the conference, realized in multimedia and in a real theatrical play.

The performance has been realized by using the idea of experimenting the spreading of the information in a network of people, by using the technology of the mobile phone and other auxiliary devices. The experiment aims at demonstrating that the effects of technology are like an infectious virus, which spreads suddenly in the network. During the play and the multimedia presentation, many generative patterns, related to the fractal nature of the narrative structures will be presented.

1. Introduction

In order to put in evidence how people are connected, Stanley Milgram [1] sent some letters addressed to a stockbroker in Boston, Massachusetts, to a random set of people in Nebraska, with the instructions that the letters were sent again to the stockbroker, by passing them from person to person. People passed their letters to someone who was, in some social sense, related to the stockbroker. In this way, a good number of Milgram’s letters reached their destination, and Milgram found that it was necessary an average of six steps for a letter to arrive from Nebraska to Boston. He concluded that six was the average number of passages separating couples of people involved, and argued that a similar separation might characterize the relationship of any two people in the entire world. This process has been called “six degrees of separation” [2] and it is now known as small-world effect [3]. Since then, many scientists begun to study social relationships in order to detect laws of organization, in networks. The concept of network is very important for modelling communication between individuals, the spread of an infectious desease in a community, the organization of DNA in biological world, the trasmission of information in neural cells and many other processes that take place directly between individuals or elements of a set. Later, Granovetter [4]studied the process of interconnectivity in a group, detecting strong and weak links. The first category ties familiar individuals and very close friends, the second puts in contact only individuals with a superficial relationship, which can serve as social bridges, for passing from a networks to another one. In the paper “Collective dynamics of smallworld networks”, Watts and Strogatz [5] linked the study of social networks to the mathematical theory of graphs. According to this approach, a network contains many elements, called nodes, which are linked to each other by archs. The set of archs and nodes produces the networks. Watts and Strogatz explored the properties of connected networks of elements, independently of their qualities. They found similarities in real-world networks, individuating high levels of aggregation and low average of separation. The most important result they found is that small-world graphs, those possessing both short average person-to-person distances and clustering of acquaintances, show behaviors very different from either regular lattices or random graphs, thus producing a great quantity of different configurations in the links of these networks.

Instead, some networks show characteristics in addition to the small-world effect which may be related to their function. An example is the World WideWeb, which, according to Barabasi and collegues [6-8], appears to have a scale-free distribution of the coordination numbers of vertices. It is a network with a scale invariance (the organization is the same at different levels) which presents the following characteristics:

a. presence of nodes with a high number of links (connectors);

b. when a node establishes a new link, it prefers to connect itself to a node which has already many links;

c. exponential growth of nodes, which are called hubs.

These kind of networks can represent complex systems such as social, economic and biological networks and narrative models of cognition as well. According to Gazzaniga [9], the left and the right emispheres of human brain behave in different ways: while the left emisphere generates many false reconstructions of events, the right one produces true characteristics of stories. From false memories, narrative creativity has developed as an “interpretation mechanism”. Humans use this mechanism not only for interpreting social events but also for representing them, as it happens when we tell a story. Narrative thought is a form of reasoning which grows in complexity and organization as brain developes, which has some methods for building up interpretative models of reality and for verifying them. So narrative is an important part of the way we interact with and make sense of the world. According to Propp [10], a story is an essential description of events in a temporal unit, that are produced by characters, each of them having specific characteristics and functions in the story development. Propp has been a pioneer in evidencing the social networks that characters create in producing the plot. In recent years, traditional AI and innovative agent-based technologies have developed Interactive Storytelling systems [11, 12] as an indipendent research field. An interactive story telling is a stystem that allows a user to make decisions that can potentially impact the direction of a narrative. Brenda Laurel [13] defines an interactive drama as a “first-person experience within a fantasy world, in which the User may create, enact and observe a character whose choices and actions affect the course of events just as they might in a play. The structure of the system proposed in the study utilizes a playwriting expert system that enables first-person participation of the User in the development of the story or plot, and orchestrates system-controlled events and characters so as to move the action forward in a dramatically interesting way”. Some key problems of this sector such as narrative control, the duality between characters and the plot, the user interaction with the story are progressively being solved and new prototypes are being developed [14], with the aim of exploring creative way of expanding the narrative search space [15], of representing the generation of non-linear networks of connected stories [16] and of creating characters, which live in virtual worlds, have embodied cognition and develop stories in a creative way [17].

In this paper we present an interactive story telling system, where the characters’ tasks are organized by a small-world networks structure, in order to produce creative plots, to be represented later in a real situation. The aim of this system is to automatically generate stories linked to scientific themes and to represent them by alternative methods and techonologies, such as theatrical representation and Augmented Virtual Reality. The theoretical framework in which we designed the system is generative art [18], with the idea of implementing more complex interactive narrative [19], to be used as basis for the Interactive storytelling system characters and for actors in a real theatrical situation.

2. The architecture of the interactive story telling system

Two fundamental types of narrative, linear and branching, are used in computer games and education and training applications [16]. Linear narrative is a method in which a sequence of events is narrated from the beginning to the end of a story, without variations or possibility for a user of altering the way in which the story develops or ends. In branching narrative systems, there are many points in the story where some actions or decisions made by the user alter the way in which a narrative develops or ends. Branching narratives [20] are tipically represented as directed graphs, in which each node represents a linear, scripted scene, followed by a decision points. Arcs between nodes represent decisions that can be made by the user. The variability the user can experience in these kind of systems is scripted into the system at the design time, and it is thus limited to the knowledge the designer has of the user’s needs and preferences and the user that makes the same choices at the same decision points in two consecutive sessions will have the same experiences.

The architecture of the interactive storytelling system, based on the small-world networks model, is represented in Figure 1.

Figure 1. Architecture of the interactive storytelling system.

A networks of characters which are hubs are at first selected by the user. Characters are situated in historical, geographical and social contexts. The prologue is the main node, and it is connected with a set of written stories, with video and audio sequences, with virtual worlds. Each of these media has been stored in different databases. From the Prologue the user selects a story: this is the interactive story telling generator. Every possible path through the graph of this network represents a story. In turn, for each character the user can instantiate a sub-network, and many paths can be generated, according to a formal grammar. At this level the events generator produces audio, video or simulation, related to a series of events, which in turn represent a networks. In fact, each story that a character performs is a node in a network (linked with the other stories and to the main node). In this way, the system creates a fractal narrative structure, with scale invariance, which can be reiterated ad libitum, thus producing webs of complex stories. At each level of the architecture, the characters’ galleries, the prologue, the storytelling generator and the events generator the user can make some decisions. This process develops the user’s sense of control over the development of the story. In fact, the user can add elements at each level of the architecture and create arcs in order to produce creative connections within the plot in the branching story graph.

At the moment we have created a network of characters with different functions. The historical characters are hubs, since they are very important (Galileo, Einstein). So their mark-up characteristic is denoted by a yellow color code. There is a network of characters which are not hubs (the terrorist, the teen-ager, Penelope). These characters are involved in some social networks and have particular stories. So their color code is red. There is another network of fantasy characters, (the butterfly, the horse, the fish) which has been developed in the ESG research group (http://galileo.cincom.unical.it/), by using two-dimensional self-replicanting Cellular Automata. The color code of these characters is blue.

Other important elements in this system are connectors, which can be technological and/or belonging to a specific social network. For example, a mobile phone or the Internet allow the characters to add a new dimension in the story plot, which is, in some sense, related to the way individuals communicate by using new information and communication systems.

The events generator is a formal language [21]. In contemporary research, a formal language is a set of finite-length words (i.e. a string of characters), obtained from some finite alphabet, while the scientific theory which deals with these entities is known as formal language theory (Figure 2).

Figure 2. In this diagram, the basic objects of formal language theory (alphabet, sentence, language and grammar) are represented. Grammars consist of rewrite rules: a particular string can be rewritten as another string. Such rules contain symbols of the alphabet (here a and b), and so-called ‘non-terminals’ (here S, A, B and F), and a null-element, e according to Chomsky’s approach . The grammar in this figure works as follows: each sentence begins with the symbol S. S is rewritten as aA. Then there are two choices: A can be rewritten as bA or aB. B can be rewritten as bB or aF. F always goes to e.

This formal language creates paths and free walking in the branching story graph, allowing the user’s sense of control of the storytelling system (Figure 3).

Paths generator	Walking
Length From 2 To 3 = 2 2à0à3 2 à 62 0 à 60 3 à 63 Length From 4 To 6 = 2 4à0à6 4 à 64 0 à60 6 à66	Length From 3 To 34 = 9 3à13à31à53à43à46à19à14à31à34 3à 63 13à 73 31à91 53 à 113 43à103 46 à 106 19 à 79 14 à 74 31 à 91 34 à 94

Figure 3. The dialogue boxes for the user is interaction. In the system, the language is developed by using natural numbers.

At each element of the path or of the random walking, the system associates to the formal grammar a set of media, which in turn are represented as 3D world or video clips.

In other words, the formal grammar instantiates a string in correspondence of which there is an audio-video sequence. The set of all the sequences produce the story. The grammar is context dependent. Changing the parameters of the choices, it is possible to generate new differents stories. For this reason this system fits well with the generative approach in arts. The user can add nodes to the network and create archs between past and future events, producing a generative and creative narrative that is different either from linear or brancing narratives.

Instead, the user’s interface metaphor exploits a physical world model of the networks. The networks have geographical characteristics and they produce 3d graphs. Each element of the networks is settled on a spherical surface, determined by longitudinal and latitudinal coordinates.

3. An example

The story starts in a random manner from one of the hubs (the professor) and creates, by a decision-making system, the task of the other characters, producing events ruled by a generative grammar. At the moment, the caracters that have been developed are represented in Figure 4.

Gallery of Historical Characters
Galileo		Einstein
Gallery of Social Characters
Teenager	Professor	Assistant	Revolutionary
Gallery of Fantasy Characters
ALMMA Robot	Chaos Robot	Alice	Illusionist
Spider	Horse	Butterfly	Fish
Gallery of Settings
Greek House	Greek Theatre	Agorà	Greek Temple
Gallery of Greek Masks
Hegemòn therápon	Pseudokóre	Kólax	Káto trichías
Gallery of Scenes
Video ALMMA	Video Evolution	Galileo Room	Agorà

Figure 4.In this Figure, some of the characters, real and simulated which have been developed for the interactive story-telling system.

Figure 5. In this Figure, a scene of the first play produced with the system. As it is possible to see, we have used an historical character, Galileo, situated in a modern environment.

Figure 6. In this image, a piece of the text generated by the story-telling system, elaborated on a story written by one of the authors.

One of the story we have generated is about an experiment which a professor elaborates and makes, using human pearsons as laboratory mice. In Figure 5, a scene of the prologue of the generated story is presented, while in Figure 6, a piece of the dialogue of the professor of the generated story.

4. Conclusions and future work

We made a contamination of different elements, approaches and methods for creating what we have called melting tools, the electric theather, the music of the story, classical and fantasy 3D environments. The electric theater is the result of the interplay between old and recent approaches, the idea that it is possible to use a storytelling system to write a rough play which, after modifications and improvements, can be represented as if it were written by a playwriter. Also music is a very important element of the electric theater, as the music is generated by using a software based on the small networks model as well (see Campolongo, in the poster session of the GA2005 Conference Proceedings). Furthermore, the electric theater uses 3D environments, multi-agent based technologies and Augmented reality systems. Future goals of this research project is to develop the performance in Augmented reality, using the synthetic and the real actors and mixing the behavior of both types of characters for realizing a new form of generative art. Furthermore, we think to develop a new model of narrative, based on the Barabasi scale-free model of networks.

References

[1] Milgram S. (1967). The small world problem. Psychology Today, 2, 60–67.

[2] Guare J. (1990). Six Degrees of Separation: A Play. Vintage (New York).

[3] Korte C., Milgram S. (1970). Acquaintance linking between white and negro populations: Application of the small world problem. Journal of Personality and Social Psychology, 15, 101-118.

[4] Granovetter M. S. (1973). The Strenght of Weak Ties, American Journal of Sociology, 78, 1360-1380.

[5] Watts D. J., Strogatz S. H. (1998). Collective dynamics of «small-world» networks. Nature, 393, 440-42.

[6] Albert R., Jeong H., Barabàsi A. L (1999). Diameter of the World Wide Web. Nature, 401,130-131.

[7] Albert R., Jeong H., Barabàsi A.L. (2000). Error and attack tolerance of complex networks. Nature, 406, 378 -382.

[8] Jeong H., Neda Z., Barabàsi A. L. (2003). Measuring preferential attachment in evolving networks. Europhys. Lett., 567-572.

[9] Gazzaniga M. (2005). Funzioni diverse per gli emisferi cerebrali. In Frontiere, Dai Neuroni alla Coscienza, Le Scienze, Roma.

[10] Propp W. (1928). Morfologija skazki, Leningrado. (Italian version: Morfologia della fiaba, Einaudi, Torino 1966).

[11] Cavazza M. (2003). Virtual Unreality: Storytelling in Virtual Environments, ACM VRST, 2003.

[12] Cavazza M., Charles F. (2005). Dialogue generation in character-based interactive storytelling. AAAI First Annual Artificial Intelligence and Interactive Digital Entertainment Conference, Marina del Rey, California, USA.

[13] Laurel B. (1986). Toward the Design of a Computer-Based Interactive Fantasy System. PhD diss., Drama Department, Ohio State University.

[14] Magerko B. (2005). Story Representation and Interactive Drama. AAAI First Annual Artificial Intelligence and Interactive Digital Entertainment Conference, Marina del Rey, California, USA.

[15] Riedl M. O., Young R. M. (2005a). Story planning as exploratory creativity: techniques for expanding the narrative search space. The IJCAI 2005 Workshop on Computational Creativity.

[16] Riedl M. O., Young R. M. (2005b). From linear story generation to branching stoy graphsAAAI First Annual Artificial Intelligence and Interactive Digital Entertainment Conference, Marina del Rey, California, USA.

[17] Tallyn E., Koleva B., Logan B., Fielding D., Benford S., Gelmini G., Madden N. (2005). Embodie reporting agents as an approach to creating narratives from live virtual worlds. Lectures Notes in Computer Science, Springer Ed., Proceedings of Virtual StoryTelling, 2005, Strasbourg.

[18] Soddu C. (2005). Milan, Visionary Variations. Gangemi editore, Milano.

[19] Charles F., Cavazza M. (2004). Exploring the Scalability of Character-based Storytelling. ACM Joint Conference on Autonomous Agents and Multi-Agent Systems, New York, USA, 872-879.

[20] Gordon A., van Lent M., van Velsen M., Carpenter P., Jhala A. (2004). Branching storylines in virtual reality environments for leadership development. Proceedings of the 16th Innovative Application of Artificial Intelligence Conference.

[21] Chomsky N. (1957). Syntactic Structures. The Hague, Mouton.