Börje F Karlsson

Antonio L Furtado
email: furtado@inf.puc-rio.br

Conceptual Model and System for Genre-focused Interactive Storytelling

Keywords: storytelling, conceptual model, genre, plan generation / recognition

This paper describes a conceptual model for the definition of a genre in the context of Interactive Storytelling and its implementation in LogTell-R, a system for the interactive creation of stories. This work builds on a previous system and experiments with plan recognition and discusses the foundations of our model to allow the creation of varied and coherent stories within a genre.

Introduction

Schank [START_REF] Schank | Computer Models of Thought and Language[END_REF] writes that humans understand the world in terms of stories. Arguably, the human brain has a natural affinity not only for enjoying narratives, but also for creating them [START_REF] Wallis | Making Games that Make Stories[END_REF]. Thus, the dynamic and interactive generation of stories is an interesting problem. However, the generation of stories that are coherent and interesting, while accounting for authors, and audience interactions remains an unsettled issue. A wide range of approaches has tried to integrate storytelling and interactive entertainment (narrative and gameplay), with limited success, mostly by overly restricting user interaction options. While this may be a pragmatic attempt to simplify the problem space, we feel that more generative approaches are required if the field is to become truly successful. One of the main open problems in the generative craft of stories resides in how stories may be generated and told. While it is probably not possible to define an ideal general model for good stories, we claim that sound methods to organize and combine events must be considered to confer enough dramatic power to narratives. Some approaches do make use of special narrative functions that enforce narrative principles in the context of the whole story (like raising tension, introducing dilemmas, or some mechanism to "move the story forward") [START_REF] Karlsson | A Model and an Interactive System for Plot Composition and Adaptation, based on Plan Recognition and Plan Generation[END_REF], but while these efforts improve user engagement they still do not guarantee diversity of experience. A possible avenue for the development of more generative systems that can create interesting stories is related to the definition of a genre. Once a genre is specified with some rigour in a constructive way, it becomes possible not only to determine whether a given plot is a legitimate representative of the genre, but also to generate such plots. To tackle the problem of creating a more generative model to support the production of stories, we draw on previous system-building experience and on the four master tropes identified by semiotic research, namely: metaphor, metonymy synecdoche, and irony (which are the basic rhetorical structures by which we make sense of experience [START_REF] Burke | A Grammar of Motives[END_REF][START_REF] Culler | On Deconstruction[END_REF]). By offering mechanisms derived from event relations connected to these tropes, we intend to augment the expressiveness of the narrative model. This paper describes a conceptual model used to represent plots in a given genre and presents extensions to better support event relations and enhance the space of possibly interesting stories in the context of a plot generation system. We outline how an intended genre (to whose conventions the plots must conform) can be modelled and describe LogTell-R [START_REF] Karlsson | A Model and an Interactive System for Plot Composition and Adaptation, based on Plan Recognition and Plan Generation[END_REF], an extended version of LOGTELL [START_REF] Ciarlini | A Logic-based Tool for Interactive Generation and Dramatization of Stories[END_REF]. This new system uses plan recognition and plan generation in the creation of stories and a plot algebra to help define the story space. We then show how the new system works on the basis of the identified event relations, also indicating what is done to narrow the gap between the conceptual model and the implementation while helping to construct the possible plots. Finally, we offer some remarks on the results obtained.

Story Generation Systems

Story generation systems (SGSs) employ different strategies to configure their story models, which can be broadly classified as character-based, plot-based, and userexperience models. In character-based models, the storyline results from the interaction among virtual agents. Their main advantage is the ability for anytime user intervention, but, while powerful in terms of interaction, such interference level may lead the plot to uncharacteristic situations. Additionally, there is no guarantee that narratives emerging from the interaction between agents will create interesting drama. By contrast, in plot-based models, characters should follow more rigid rules, specifying the intended plot structure. User intervention is thus more limited, but it is usually easier to guarantee coherence and a measure of dramatic power. Lastly, SGSs with user-experience models, focus on the user by addressing individual preferences via user profiling and measuring the interestingness of story pieces. We feel that an approach that fits in between plot-based and character-based is the best option, given that plots and characters are interlocking elements that cannot exist without each other [START_REF] Glassner | Interactive Storytelling: Techniques for 21st Century Fiction[END_REF]. Specifically, we try to conciliate both. User-experience concerns can be dealt with at later stages; as long as we can guarantee that enough variety of stories can be generated, possibly while considering changes in dramatization / presentation of story events. Even though it is argued that the key aspect of an interactive narrative is the story representation used to encode the author's vision of the experiences (story space [START_REF] Magerko | A Comparative Analysis of Story Representations for Interactive Narrative Systems[END_REF]), little attention is given to what qualities such space should have. Most approaches to plot-influenced storytelling models consider only stories formed by sequences of events using their inherent temporal characteristics or simple causality relations, which are clearly not enough to guarantee interesting and varied stories. Other approaches use dilemma-inducing or tension-raising events, paying no attention to the relations between events in the plot model. Few efforts dedicate enough attention to relations between events. Three relevant exceptions are [START_REF] Pinhanez | Interval Scripts: A Design Paradigm for Story-Based Interactive Systems[END_REF], [START_REF] Lang | A Declarative Model for Simple Narratives[END_REF], and [START_REF] Nakasone | ISRST: An interest based storytelling model using rhetorical relations[END_REF]. Pinhanez [START_REF] Pinhanez | Interval Scripts: A Design Paradigm for Story-Based Interactive Systems[END_REF] deals with a temporal model of events, providing mechanisms to handle their interlacing temporal relations.

Building on the same principle, the Joseph system [START_REF] Lang | A Declarative Model for Simple Narratives[END_REF] claims to provide a formal framework to relate story components to one another. In it, a story is modelled as having two sub-components, a setting and an episode list, both of which have temporal intervals associated with them and information about event relationships is specified in its rules. The Joseph system is (to our knowledge) the first system constructed from an explicit, formal model for stories. ISRST argues that relations determined by the rhetorical context of events is key [START_REF] Nakasone | ISRST: An interest based storytelling model using rhetorical relations[END_REF] and introduce an ontology model based on the organization of events. In ISRST, a relation is a binding between two entities, which refers to a specific rhetorical function. They further claim that "its use is impractical for the purpose of content creation, since most human beings make use of a more limited set of relations to construct and remember stories" [START_REF] Nakasone | ISRST: An interest based storytelling model using rhetorical relations[END_REF]. To match this limitation, a reduced set of nine relations is considered. However, their ideas are not implemented in a concrete system.

Lastly, content creation tools in place to make the underlying complexity of the knowledge base transparent to authors is paramount, especially if the representation uses complex models or specialized programming languages. For example, although Façade has been a successful experiment, its architecture requires a great effort from authors. It uses four different content languages and took two years to author a game with only one scene, two characters, and that takes about 20 minutes to complete [START_REF] Mateas | Façade: An Experiment in Building a Fully-Realized Interactive Drama[END_REF].

3

The LOGTELL Plot Composition Model

In summary, LOGTELL is a logic-based tool for the interactive generation and dramatization of stories via the use of a plan-generation system. The main difference between its conceptual model and similar planning systems is that it does not assume the existence of one goal for the story as a whole. Instead, at the beginning of the plot (and after each planning phase), goal-inference rules are used to consider new goals induced for the various characters. Its design borrows notions from narratology, in particular, the distinction of three levels in literary composition: fabula, story, and text [START_REF] Bal | Narratology[END_REF]. At the fabula level, the characters in the narrative are introduced, as well as the narrative plot -corresponding to a chronological sequence of events. The story level concerns a different representation specific to these events and how they are narrated to an audience, be it through a temporal re-ordering of the events or other narrative techniques. The last level relates to the medium used to tell the story, such as natural language, movie, or any other communication medium.

When breaking down the IS problem into its smaller sub-parts, a similar separation is observed between the story generation and narration phases [START_REF] Karlsson | A Model and an Interactive System for Plot Composition and Adaptation, based on Plan Recognition and Plan Generation[END_REF]. In SGSs, this breakdown means that different modules handle the two parts. In discussing the conceptual model behind the story space in LOGTELL, we are interested only in the fabula level, within its Plot Manager, where the narrative plot being manipulated consists of a partially-ordered set of events. Here we should recall that plot managers, in general, are interactive story generators that receive as input an already created piece of story (initially empty) and present as output a suggestion on how to continue the story. Their main function is to effect corrections so the story plot can develop correctly. If some inconsistency is detected in the input, the manager intervenes in order to ensure that the original goal can be reached, satisfying all the necessary constraints.

To model a chosen environment to which the plots to be composed should belong, it is necessary to specify at least: a) what can exist at some state of the underlying world; b) how states can be changed; and c) the factors driving the characters to act.

Accordingly, LOGTELL defines three schemas: static, dynamic and behavioural, representing, respectively: a) Storyworld: the world description takes the form of a set of facts (state), introducing the characters and their initial situation (relationships and attributes); b) World State Changes: narratives are composed of events and an event is a transition from a valid world state to another, which should also be valid; and c) Character's behaviour: to model the reasons for each character's actions, LOGTELL uses goal-inference rules specifying (in a logic formalism) the motivations of these agents when certain situations occur.

State transitions consist of a limited repertoire of pre-defined domain-oriented operations. A similar notion has been proposed by Vladimir Propp [START_REF] Propp | Morphology of the Folktale[END_REF]. LOGTELL equates the notion of event with the state-change brought about by the execution of an operation by some agent. The dynamic schema is thus composed of a repertoire of pre-defined operations (typical of the chosen genre) in which characters can take part.

The generation of a plot starts by inferring goals for the characters from the initial configuration. A planner inserts events in the plot in order to allow the characters to try to fulfill their goals. The result is then presented to the user. If the user accepts it, the process continues by inferring new goals. The process alternates goal-inference and plan generation until the user decides to stop or no new goal is inferred.

To further explore the possibilities of generating varied coherent stories in the given "fairy-tale genre", we enabled mechanisms also for plan-recognition. Experiments with the system demonstrate that combining plan-recognition/generation and user participation constitutes a promising strategy towards the production of plots which are both diverse and coherent, as it helps guide the user [START_REF] Karlsson | Applying the Plan-Recognition/Plan-Generation Paradigm to Interactive Storytelling[END_REF]. However, that does not guarantee dramatic power. Sound methods to combine events must be considered to accomplish this goal; which led to the necessity to further extend the utilized model. We do not claim that the present effort is sufficient to create a fully immersive experience. We endeavour, as a more limited objective, to explore the possibilities of generating a large variety of stories by applying this strategy over a given genre.

Event Relations in Plot Composition

Many narratologists agree that the most important relation between events is the causal one. Nevertheless, this is not the only relation taken into consideration when human beings try to create story patterns in their minds [START_REF] Nakasone | ISRST: An interest based storytelling model using rhetorical relations[END_REF]. The impact on the audience very much depends on how events are combined. Furtado [START_REF] Ciarlini | Event Relations in Plan-Based Plot Composition[END_REF] suggests that at least four concerns are involved in plot composition: a) the plot must be formed by a coherent sequence of events; b) for each position in the sequence, several alternative choices should apply; c) non-trivial interesting sequences must permit unexpected shifts along the way; and d) one may need to go down to details to better visualize the events or, conversely, to summarize detailed event sequences. These concerns have led to the identification of four relations between pairs of events that play a basic role in a story, and to the introduction of a fourfold perspective of plot composition in the context of IS. The four relations are: a) syntagmatic -the occurrence of the first leaves the world in a state wherein the occurrence of the second is coherent. The syntagmatic relation between events induces a weak form of causality or enablement, which justifies their sequential ordering inside the plot; b) paradigmatic -the events can be seen as alternative ways to accomplish a similar kind of higher-level action, so that both achieve the same basic effect in a significantly different way; c) antitheticthe events oppose or contradict each other, since the occurrence of each of them implies a radically different context; and d) meronymic -referring to the decomposition of an event into lower-level events, thus providing a more detailed account of the action on hand.

The first two relations were already handled in LOGTELL. To extend its functionality, we included the use of a hierarchy of (generalized) events and planrecognition mechanisms during the plot composition phase [START_REF] Karlsson | Applying the Plan-Recognition/Plan-Generation Paradigm to Interactive Storytelling[END_REF]. This hierarchy consists of a conveniently structured library containing sequences of events with partial order relationships between them, which can be adapted if necessary to specific circumstances. The typical plans (also called complex operations) stored in the library result from meronymic relations between other operations (Proppinspired). Complex operations formed by generalization are also represented, branching down to specialized operations corresponding to alternative ways to reach the same main effects.

Transgressive plots based on antithetic relations can add a dramatic impact, by introducing unexpected turns in the narrative, e.g. by the sudden recognition of a wrong belief, or by a radical change of fortune (Aristotle's "discovery" and "reversal"). If his beloved princess is abducted, the hero would normally rescue herbut the antithetically related capture event would be justified if she unexpectedly falls in love with the captor (the so-called Stockholm syndrome). Mechanisms to support this kind of dramatic change must be provided, one of the possibilities being to allow arbitrary user interventions at certain points (recalling the deus ex-machina device).

Genre as Story Space

Finding an answer to the question of what constitutes a given literary genre should allow one to determine whether or not a story can be classified as belonging to it.

However proving that a conceptual model M for specifying a genre G, formulated as discussed in this paper, can fully capture how the genre is understood by a literary expert can be an over-ambitious effort. Yet, a useful approximation is attainable, taking the form of a definition by extension. If a system can generate stories according to the specified conceptual model M, the space of plots that can be generated might be regarded as constituting a genre G M defined by the model, where plot has the usual meaning of sequence of events. It would be left to the designer of M the task of refining the model specification in order to achieve increasingly closer matches between the intuitive view of G and G M . This is basically the role of the presented conceptual model. As argued, it determines the genre of the stories to be generated in correspondence to the story space of a system that uses that model. Such definition of genre as the set of stories that can be generated from a model is consistent with the way game designers discuss/describe genres by example [START_REF] Wallis | Making Games that Make Stories[END_REF].

While the story space of our example scenario refers to a simple medieval fantasy genre, our conceptual modelling method should be able to cope with an ample variety of genres of higher complexity. The structure of each story space thus specified is determined by the observed event relations. From an informal viewpoint (cf. Figure 1), events can be seen as nodes and syntagmatic, paradigmatic relations as connecting edges drawn over a plane, while meronymic relations appear as projections of events into event sequences over another plane. Antithetic relations between nodes can be seen as specifying constraints crosscutting the story space. Recall that paths formed by syntagmatic relations correspond to plots, whereas paradigmatic relations indicate alternatives -whose choice may entail, as signaled by antithetic relations, the exclusion of certain other alternatives branching from subsequent nodes.

Supporting the identified relations also brings extra benefits. Plot libraries can be organized as combined is-a and part-of hierarchies, which is a convenient way to deal with plots by taking advantage of the similarity or analogy among situations. While the part-of links result directly from meronymic relations, denoting in consequence composition / decomposition, the is-a links express the notion of generalization / specialization. If two or more events stand in a paradigmatic relation, their main effects should coincide, although they may differ with respect to less important sideeffects. For instance, abduction and elopement can be seen as alternative forms of villainy. This justifies the introduction of a new event, which might be named villainy (or some more specific term), and its placement in a hierarchy above the other two one-event plots, i.e. it generalizes both. These relations contribute to the hierarchical structure of the library and, once it is constructed, its component patterns can then be reused during the plot composition process to help create new plots. Because our approach employs plan-generation/plan-recognition while composing a plot, we regard "typical plots" in our context as synonymous to typical plans. These relations also bring a particularly convenient way to deal with entire plots, helping visualize their dramatic structure.

Finally, let us recall that we have addressed the fabula level only, where one simply indicates which events should be included in the plots. One especially complex problem to be faced at the next level -story/narration, where the concern is how to tell the events -is how to properly convert the events into forms adequate for dramatization.

LogTell-R

To implement this model we extended LOGTELL's interaction modes and dynamic schema level, i.e. the set of operations that can transform the storyworld, to take into consideration the four relations previously presented. As mentioned before, the Plot Manager module originally dealt only with the syntagmatic and paradigmatic axes. The changes introduced in our new prototype now allow meronymic relations by introducing complex operations, and antithetic relations, by employing motifs.

When dealing with support for antithetic relations, since we emphasize interactive composition, we considered the possibility of user interventions that can result in some sort of discontinuity being produced. If we see a disruption not as a discontinuity in one context, but as an attempt to put together two originally incompatible contexts, then the notion of blending [START_REF] Casanova | Generalization and Blending in the Generation of Entity-Relationship Schemas by Analogy[END_REF] immediately comes to mind, as the technique or artisanship of conciliating the pending conflicts, which often requires a great deal of creativity. Incompatibilities between events -which we have been characterizing in terms of antithetic event relations -are usually induced by some factor involving the current value of a property or the beliefs of a character. A genre can in general be seen as a contract between author and audience [START_REF] Glassner | Interactive Storytelling: Techniques for 21st Century Fiction[END_REF] -in the sense that the audience knows what to expect -even if some event almost crosses the borderline of plausibility. Fortunately, blending can be achieved in a convenient way by resorting to folktale motifs [START_REF] Thompson | Motif-Index of Folk-Literature[END_REF], which often encode ingenious solutions to contradictions or dead-ends in a tale, while seeming to fit with the conventions of their encompassing genres. In order to support this mediation, LogTell-R permits the insertion of a motif at an appropriate position in the plot. This motif must come from a pre-defined set, and takes the form of a special (pseudo-)operation. Motifs are associated with either a goal specification or a set of post-conditions. In our proof-ofconcept, we selected a set of genre-suitable motifs (e.g. life token -that allows to do without the unrealistic assumption that characters are omniscient). Motifs also act as dramatization tools, providing the audience a convincing explanation of why certain events must ensue. In our prototype, a motif is associated with a script defining the behaviour of the involved characters when dramatizing it. Support for complex operations in plan recognition and the use of the hierarchy of typical plans can be seen as a complement to generation. The benefits of the plan library structure itself are twofold: it helps better visualize story structure, showing how to adequately chain events into a narrative scheme (like the three-parts classic structure [START_REF] Karlsson | A Model and an Interactive System for Plot Composition and Adaptation, based on Plan Recognition and Plan Generation[END_REF]); and it helps in more easily understanding and analyzing the space of stories that can be generated. In LogTell-R, plot generation still happens in a stepwise fashion. A new way of choosing alternatives is enabled by selecting events and asking the plan-recognizer to retrieve generalizations containing them. Exploiting the meronymic axis at different levels of detail, plausible alternatives may be located by essentially walking up and down over the hierarchy. Instead of asking the system for suggestions, the user may also simply find it helpful to visually inspect the library of typical plans associated with the genre (Figure 2), and use it as inspiration to guide the composition of a plot.

As our approach is centered on the concept of hierarchies of typical plans and given that conceptual models tend to remain too far removed from system implementations, we narrow this gap with the help of an intermediate logical design stage. The approach utilized is a plot manipulation algebra (PMA) [START_REF] Karlsson | A Plot-Manipulation Algebra to Support Digital Storytelling[END_REF] for the creation of the hierarchy of typical plans. An added benefit of using PMA (supported by the planner to check pre-and post-conditions of operations) in the knowledge base editor is that one can more easily experiment with different ways to chain the events, and use this knowledge to revise the specification so as to improve the system's story space. Starting with the set of operations relevant for the genre (e.g. abduct, murder, liberate), algebra operands are applied to define the necessary relations between events (e.g. generalizations or placement of constraints on undesired event combinations). At each step, the user can visualize how the typical plan hierarchy is "grown".

Concluding remarks

Few approaches to IS address the problem of what is a proper story space or the characteristics of events pertaining to a plot, preferring to focus on more controlled environments and stories. We feel that more generative approaches are necessary for the field to become truly successful. It is important to stress, however, that we do not propose to achieve a fully immersive experience. We endeavour, instead, to explore the possibilities of generating a large variety of coherent and interesting stories through the use of plan-generation and recognition over the conceptual model of a genre.

Our approach targets sound methods to organize and combine events, in ways that may confer enough dramatic power to the generated narratives. By extending our conceptual model, we augment its expressiveness and provide tools to prospective authors intent on creating and telling stories. Although the process of plot composition and adaptation could surely be enriched beyond what is presented here, our system provides a sound basis to treat genres that exhibit a good degree of regularity.

Having authorial tools make the complexities of the model transparent to authors is a major goal, primarily to reduce the burden on authors using the system, but also to guide them in the creation of interesting stories. Creating an interactive environment that behaves as expected is a tiresome task, as it is performed mostly by trial and error.

Fig. 1 .

 1 Fig.1. Relations between events in the story space[START_REF] Ciarlini | Event Relations in Plan-Based Plot Composition[END_REF]

Fig. 2 .

 2 Fig. 2. Hierarchy of typical plans used in most of our experiments


Katharine Neil
email: katharine.neil@gmail.com

Denise De Vries
email: denise.devries@flinders.edu.au

Stéphane Natkin
email: stephane.natkin@cnam.fr

A Tool for Evaluating, Adapting and Extending Game Progression Planning for Diverse Game Genres

Keywords: game design, progression planning, design tools

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Designing game progression, commonly understood as a structure consisting of serially introduced unique challenges [START_REF] Juul | The open and the closed: Games of emergence and games of progression[END_REF], can be a demanding task for a game designer. To design a game's progression is to design the way that game is experienced by the player over time; the way gameplay elements are introduced is largely responsible for its aesthetics of pacing, challenge and variety. Currently computational support is not used for this task, despite the increasing importance and sophistication of progression within game design. In response to the need for tools to aid progression design thinking, Butler, Smith, Liu & Popovic have proposed a general architecture for "progression planning" tools which they have implemented within their level authoring tool for their educational game Refraction [START_REF] Butler | A mixed-initiative tool for designing level progressions in games[END_REF]. As a demonstration of this concept, the Refraction tool ably hints at its potential. However, its strength as a tool to help solve challenging progression design problems remains largely untested; as Butler et al acknowledge, Refraction game's genre and scope as a puzzle game with modest progression design needs limits its applicability to other games.

We have sought to implement, evaluate and build upon this progression planning approach, by orienting it towards more demanding and more varied progression design problems. To this purpose we used three game design case studies in contrasting genres, all at the early progression design phase of their development: a top-down shooter with puzzle elements, a casual strategy game and an adventure game. In this paper we describe how we adapted and extended Butler et al's progression planning concept to support progression design for these games.

Research Objectives

We have two main research goals for this work. The first is to evaluate and explore how Refraction's progression tool approach can be applied to the progression design challenges of games other than Refractionparticularly its universality in terms of servicing the needs of games of contrasting genres. The second, which foreshadows the first, is to discover and reveal the ways in which Butler et al's approach requires adapting or extending in order to apply it. This paper focuses on the results of our second objective.

Our Approach

There exists a wide gulf between the primitive document-editing and nonstandardised diagramming practices that many game designers currently use and the advanced automated design and reasoning based research being applied to the problem of game design tools in the research community. While mixed initiative game design research is exploring the potential of computers to participate in design thinking and serve not merely as "tool" but as collaborator or expert [3][4], practitioners still do their design thinking typically without any computational support. With a "first, do no harm" philosophy in mind, it is the "low-tech" elements of Refraction's progression planning tools -its simple constraints editing and visualisations that interest us the most. We see them as a possible first step forward from the nascent formal approaches being explored within current practice, in that they support what many designers are more or less already doing. In building upon this aspect of the Refraction tool we also serve our aim of working at a sufficiently generic level so as to adapt the approach to other games. Accordingly, when implementing Refraction's approach we have in certain cases chosen to simply visualize the data and allow the designer to conduct their own analysis and policing of design moves (as done with pen and paper) rather than add computational support, choosing and thereby necessarily restricting the form that support should take.

Method

It was not practical to use the Refraction progression planning tool itself as a starting point for our work, as it is integrated with the game's level editor and generation system. We began, therefore, by building our own progression planning tool based on Refraction's approach. We then adapted and extended our tool with a view to simultaneously servicing the specific needs of three game design case studies. These case studies were all at the early progression design point of their design cycle. The games have been under development by the primary author of this paper for between six months and three years. The designs represent three game genres: a casual strategy game, an adventure game and a top-down shooter. Usefully, these genres vary quite markedly in the nature of their progression. Servicing these contrasting design needs helps enforce a degree of universality in our tool design. Our games cannot be representative of all game genres, however, and like Refraction's system, the design of our tool was inevitably driven by the needs of specific games rather than the needs of all possible games. Intuitively, the progression planning requirements of all three of our games go beyond the concept-based progression units used for the Refraction game. Most notably, unlike Refraction the games are all, to some degree, non-linear in their progression structure. This feature invokes the challenge of how to plan progression that does not take the form of linear sequence.

System Model

Here we describe our tool and how it builds upon, modifies and extends the model used by Refraction's progression planning tool. Our system, inspired by Refraction's, comprises constraints, plan and idea repository components (see Fig. 1). While our system performs a similar role, our differing workflow approach is manifest in some important functional differences. Refraction's system uses its simple constraints calculations to drive generative features and analyze design moves, generating the progression plan and, optionally, the levels themselves. Our system removes the generative features and much of the automated analysis performed by their system, and instead focuses on presenting and organizing the results of our calculations to the designer. Most notably, our system, created to serve all three of our case studies, does not include a procedural level generation system or an integrated level editor. We have replaced this component with a designer's notebook style feature for storing and tagging ideas, design patterns and work-in-process levels, which can then be filtered according to data created in the progression plan component. We have also extended the constraints and progression plan components, adding additional calculations and visualization features, including a graph traversal algorithm to the progression plan component in order to apply constraints to nonlinear level progressions.

Progression Constraints Component

As in Refraction's tool, our progression constraints component allows the game designer to create game elements and constraints by defining some elements as explicit prerequisites and co-requisites of other elements. An element can be as concrete and quantifiable as an ammo pickup, for example; or a quality the level might contain like "intense combat". As well as providing a matrix-style editor, the tool automatically infers transitive prerequisites (as does Refraction's tool). This is a non-trivial calculation for a designer to perform manually.

Graph and Matrix Interfaces.

To this component we have added an editable graph-based view as an alternative to the matrix view. We chose to include a graph-based view upon discovering that the progression plan for our adventure game could be in fact better described and supported by taking the form of progression constraints, leaving the progression structure itself for managing the higher level episodic narrative. As in matrix view, graph edges are automatically added when constraints are transitively inferred by the tool. This kind of computational support is useful for managing the binary but complex progression logic of an adventure game.

Progression Plan Component

Graph Interface.

The most signification modification we have made to Refraction's approach is expanding the progression plan out from their linear table form into a graph-based editor and analyzer. A graph allows for games that have a non-linear progression structures to be modeled. The designer uses the graph interface to create levels or mission stages as nodes and define connections between them as edges. He or she can select a node in the graph to edit the properties of the associated level.

Game Elements List.

Alongside the graph interface we display a list of all game elements. Any element in the list may be selected and added to the level's game elements list. The elements in the list are displayed differently, according to their eligibility for use in the currently selected level: eligible, ineligible and potentially eligible. Eligibility is based on the constraints defined using the Progression Constraints component: it is calculated using a graph traversal algorithm (our progression plan analyzer) to determine whether a given element satisfies the constraints governing the level. The inclusion of the "potentially eligible" type is due to the non-linear progression structure. It services the case where one or more, but not all, paths leading to the level satisfy the constraints associated with the listed element. Being "potentially eligible" may render the element appropriate or inappropriate for inclusion in the selected level, depending on the nature of the game or the element itself. The designer is left free to make an informed decision as to whether they wish to include the element based on this contextual information.

Level Game Elements.

The level's game elements list is where the designer defines the contents of the level, using game elements from the game elements list. The designer may simply indicate the presence of a concept used (e.g. "ranged combat") or they may specify the number of instances of the element in the level (e.g. 5 ammo pickups).

Progression Histories.

A designer may wish to know which game elements the player has experienced or has potentially experienced by the time they reach the selected level, based on the content of the levels that may or must be completed prior to it. This can be viewed for all possible paths to the level, or for a single path selected in a "Paths to selected level" list. For example, the designer might see that the player has encountered a minimum 4 ammo pickups but potentially a maximum of 16. Selecting a path also highlights all the levels along that path in the graph view.

Graph Element Visualization.

Refraction's tool includes a constraint editor and visualizer that plot the density and frequency of elements in the progression plan, in order to regulate progression considerations such as game pacing. In line with our approach, our tool computes this for the purpose of visualization only: we highlight all nodes of the progression graph that contain a selected game element, thus affording the designer a broad overview of where instances of a given element are used in their game.

Filtered Design Notebook Component

Our third component of the system, as noted above, is an alternative to Refraction's integrated level editor. Design process is commonly understood to be notoriously non-linear. 1 Here we provide a home for level design fragments or design patterns that do not yet have a home within the progression plan itself. Ideas can be tagged with one or more of the game elements it includes, and the notebook can be filtered by the level's game elements list to display all ideas that contain only the game elements relevant to that level.

Conclusion

We have found that is possible to apply, adapt and extend Butler's progression planning approach to other game genres, by using three contrasting case studies with concrete progression planning challenges to discipline and inform this process. It being unlikely that we have anticipated all the needs of our three design case studies, further additions and modifications will probably need to be made during this process. Our next step is practice-based evaluation: we will integrate the tool into the progression design process of our three case studies, and diarize the experiences of the designer for analysis. This analysis will then be used towards developing a generic toolsupported progression design process that can be refined and tested with a wider group of designers and design cases.

Fig. 1 .

 1 Fig. 1. System model.

According to Donald Schon, "unpredictability is a central attribute of design -it is not necessarily the defining one, but it is important. It means that there is no direct path between the designer's intention and the outcome"[START_REF] Winograd | Bringing design to software[END_REF].


Marc Labadie

Béatrice Denoyes

Yann Guédon

Identification of flowering patterns specific to strawberry varieties in production condition using longitudinal data analysis

Identification of flowering patterns specific to strawberry varieties in production condition using longitudinal data analysis

Marc Labadie, Béatrice Denoyes, Yann Guédon

To cite this version:

Marc Labadie, Béatrice Denoyes, Yann Guédon. Identification of flowering patterns specific to strawberry varieties in production condition using longitudinal data analysis.

Introduction:

The development of soilless culture for strawberry production is a major socio-economic challenge. This technique improves competiveness by premature plantation (December) in warmed greenhouse (minimal temperature +8°C) allowing an extension of flowering and, thus, of fruit production. However, this cultural practice is dependent on extension of the flowering period. To this end, a better knowledge of flowering and vegetative growth of varieties is needed. Plant development is defined as a combination of processes which are subject to environmental, physiological and genetic constraints. Although flowering in strawberry was physiologically and genetically well described, little is known concerning the dynamic of these developmental processes along time.

The objective of this study was thus to identify phenological phases that characterize varieties in production condition.

Thirty two plants per genotype were phenotyped weekly during 28 weeks for their number of newly emerged flowers, leaves, crowns and stolons. We propose a new modelling framework based on multiple change-point models for the identification of phenological phases on the basis of plant follow-up data. Two multiple change-point models were built for each variety, one for flowering and another one for vegetative growth.

Results: Three flowering patterns were identified

Perspectives:

A direct extension would be to build multiple change-point models directly on the basis of multivariate plant follow-up data, combining flowering, vegetative growth and runnering variables. This would allow to identify global developmental phases relying on the different developmental processes in competition within plants.

Statistical model for longitudinal data analysis:

To identify flowering pattern, we hypothesize that: i) flowering pattern for a genotype takes the form of a succession of well-differentiated stationary flowering phases ii) the distribution of the number of weekly emerged inflorescences does not change substantially within each phase, but change markedly between phases.

These flowering patterns have been analyzed using segmentation models for each variety. This analysis consists of identifying synchronous phases on the 32 plants measured for a variety. We used the slope heuristic (Guédon, 2015b), a model selection criterion dedicated to the segmentation objective, to determine the number of flowering phases and different diagnostic tools to assess the assumption of the segmentation in stationary flowering phases (Guédon, 2013(Guédon, , 2015a)).

References:

Longitudinal data analysis illustrated with the Gariguette variety

Assessment of the 3 flowering patterns

Change in the rhythm of leaf emergence: Can we predict the flowering time using these changes?

A

  . Weekly number of newly emerged flowers during one cycle of production (Weekly mean in red). B. Flowering data (row: individual; column: date). The number of newly emerged flower is represented by color intensities from 0 (yellow) to 25 (red) C. Piecewise constant function (in black) representing the mean flowering level in each phase. Weekly mean number of newly emerged flowers ( red full line) and associated standard deviation (red dashed line) models during the season of production Successive flowering phases were identified using categorical multiple change-point models: (i) A first phase of high flowering intensity (64 to 110 days after plantation) common to all the varieties. (ii) either a second phase of low flowering intensity followed by a third final phase of high flowering intensity (pattern 1; Gariguette and Cléry) or a single second phase of low flowering intensity (pattern 2a; Capriss, Darselect) or intermediate flowering intensity (pattern 2b; Ciflorette and CIR107). The variety effect on the distribution of the number of newly emerged flowers in each flowering phase was tested using a one-way ANOVA on ranks (Kruskal-Wallis test and post-hoc analysis). The results are shown for (i) the first phase of high flowering intensity, (ii) the intermediate phase of low flowering intensity and (iii) the final phase of potentially high flowering intensity. When the two last flowering phases were merged (Capriss, Darselect, Ciflorette and CIR107), we use the common limit found for Gariguette and Cléry to split these two last phases.

  Plant materials: 6 varieties constrated by their number of cold hour, precocity and flowering


Roman Barták

Andrej Hraško

David Obdržálek
email: david.obdrzalek@mff.cuni.czandrej@hrasko.eu

Autonomous Landing of AR.Drone

Inexpensive robotic toys are becoming widely available and though they are called toys, they provide gradually better sensing features and rising computational power. Adding new autonomous functions, such as autonomous landing for flying drones, helps the users with routine maneuvers and so allows using them with lower risk of breaks caused by loss of control in critical operational phases. In this paper we present software for autonomous landing of an AR.Drone -an affordable robotic quadricopter. This software uses an easy-tocustomize landing pattern and exploits only the sensors available on the drone. The whole landing process is simplified to a "push-button" approach for the end user, allowing for safer overall operation.

Introduction

AR.Drone by Parrot Inc. is a high-tech yet affordable flying toy -a quadricopter with several sensors including two cameras, accelerometer, gyroscope, sonar, and a built-in controller for basic stabilization. Pre-processed information from sensors can also be received via Wi-Fi so the computer can serve as a more powerful external brain for the drone. For controlling the drone from a computer and for visualizing information from sensors, several software applications exist. We use Control Tower [START_REF]ControlTower software[END_REF] as the basic computer interface to AR.Drone and we extended its functionally with autonomous landing to a user-customizable pattern. The idea is that the user flies the drone above the pattern and by pushing a button in the software GUI the drone autonomously lands on that pattern. Such functionality is great for beginner users who can control the drone in free space but are not able to precisely land or are afraid of controlling it low above the ground where mistakes in control or turbulences caused by airflow could easily cause crashing and then damaging of the drone.

Landing description

For autonomous landing, the drone must reliably detect the landing point. There exist methods for visual navigation (e.g. using an H-shaped landing pattern [START_REF] Yang | An Onboard Monocular Vision System for Autonomous Takeoff, Hovering and Landing of a Micro Aerial Vehicle[END_REF] or a specific circular pattern [START_REF] Lange | A Vision Based Onboard Approach for Landing and Position Control of an Autonomous Multirotor UAV in GPS-Denied Environments[END_REF]), however they require better visual sensors (cameras) and they usually do not support horizontal orientation.

We decided for the landing pattern consisting of two colored discs which makes it very easy to be prepared by an inexperienced user. The user can print any two colored discs; it is only important that the colors are different enough from each other and from the typical colors in the landing zone. This makes it much easier to use in real life (instead of being forced to use specially crafted and unalterable unique pattern). In addition to this easy customization of the landing pattern, the other advantage is that such pattern also defines the horizontal orientation.

To preprocess the picture, we straightforwardly use HSV filtering, image erosion, and image dilatation (these basic image pre-processing algorithms are readily available and described in the OpenCV library [START_REF]OpenCV software library[END_REF]). Then, to identify each disc in the picture, blob detection algorithm (described in [START_REF] Szeliski | Computer Vision: Algorithms and Applications[END_REF]) is used and the center of the disc pair is calculated to set the target landing point.

The drone is controlled using four independent standard proportional-integralderivative (PID) controllers [START_REF] King | Process Control: A Practical Approach[END_REF] fed by the distance to the target. The input for each PID controller is the coordinate part of the target distance in its specific direction and the output is one control value for the AD.Drone low-level interface functions (the pitch, roll, yaw, and vertical speed). The distance calculation is shown on Figure 1.

More details about the algorithms and their implementation can be found in [START_REF] Barták | On Autonomous Landing of AR.Drone: Hands-on Experience[END_REF]. The typical process to use autonomous landing is as follows. The user sets the HSV parameters of the two color blobs in the picture and optionally selects the horizontal angle (yaw) of the drone with respect to these two blobs. Any time later the user can invoke the "land on target" action to let the drone automatically land or the "lock on target" action to hover above the landing point at the current altitude. When the landing pattern disappears from the camera view, the system can optionally attempt to find it by flying in the direction where the pattern was lost ("estimate target").

Evaluation and Conclusion

During the tests it has proven the AR.Drone is able to land safely even when the environment conditions are too advantageous for manual control (e.g. air flow at ground Camera: Side view: level). Figure 2 presents the graphs showing the landing time, precision, and reliability of the landing from different original altitudes and orientations with or without the wind generated by two fans close to ground at the landing area. In this work we have shown how standard control software of a low-cost quadricopter AR.Drone can be extended by an automatic landing procedure. That lowers the bad chance to break the drone during landing which belongs to the most dangerous phases of the flight; especially the windy conditions are difficult for manual landing and often cause crashes and damages. This is important for users who exploit the drone as a toy, for playing and entertainment. Our preliminary experimental results show this extension is reliable under normal, non-laboratory conditions.

Fig. 1 .

 1 Fig. 1. Distance to the target calculation: dist(T,V) = v * tan(α+β), where β = arctan( tan(γ/2) * pixel_dist(T',S') / pixel_dist(C' 1 ,S') )

Fig. 2 .

 2 Fig. 2. Dependence of landing time (top left), precision (top right), and reliability (bottom) on the initial altitude (50, 100, 150, 200 cm) and orientation relative to the target (0°, 90°, 180°).

Acknowledgements. This research was supported by the Czech Science Foundation projects P103/10/1287 and P202/12/G061.