Jérôme Euzenat
email: jerome.euzenat@inria.fr

Interaction-based ontology alignment repair with expansion and relaxation

Agents may use ontology alignments to communicate when they represent knowledge with different ontologies: alignments help reclassifying objects from one ontology to the other. These alignments may not be perfectly correct, yet agents have to proceed. They can take advantage of their experience in order to evolve alignments: upon communication failure, they will adapt the alignments to avoid reproducing the same mistake. Such repair experiments had been performed in the framework of networks of ontologies related by alignments. They revealed that, by playing simple interaction games, agents can effectively repair random networks of ontologies. Here we repeat these experiments and, using new measures, show that previous results were underestimated. We introduce new adaptation operators that improve those previously considered. We also allow agents to go beyond the initial operators in two ways: they can generate new correspondences when they discard incorrect ones, and they can provide less precise answers. The combination of these modalities satisfy the following properties: (1) Agents still converge to a state in which no mistake occurs. (2) They achieve results far closer to the correct alignments than previously found. (3) They reach again 100% precision and coherent alignments.

Introduction

Agents develop ontologies for representing the world they live in. When confronted to other agents, they use alignments which express the relations holding across entities, e.g., classes or properties, in the ontologies that they use. The result is a network of ontologies related by alignments that agents may use to interoperate. This network is built through interactions between agents that apply corrective actions when communication fails.

The present work aims at eliciting techniques through which agent may adapt these alignments when they find them incorrect. Work has already been performed to understand how this can happen [Euzenat, 2014;Chocron and Schorlemmer, 2016]. We further investigate these by (a) repeating an already performed experiment with updated tools, (b) introducing new similar operators, and (c) introducing new modalities addressing limitations of such operators.

The repetition of existing experiments allows us to correct the reference against which initial results were obtained and to show that agents reach alignments closer to the correct alignments than previously reported. We also highlight that, contrary to previously reported, agents may not achieve full correctness (100% precision). This is due to correct correspondences shadowing incorrect ones.

We introduce new operators and modalities aiming at addressing these problems: new operators correct faulty correspondences by refining them, the expansion modality adds new correspondences when regular operators destroy correspondences, and the relaxation modality enables agents to use shadowed correspondences.

The resulting operators improve the coverage of the alignments through preserving the convergence to 100% success rate, fully correct alignments and a high level of recall (70%).

After reviewing related work ( §2) from which the experimental setting ( §3) is inspired, we report on repeating one of these experiment with an updated environment ( §4). We complement existing operators and show that they improve the results of the previously proposed ones ( §5). Then, in order to overcome limitations of the initial random alignments, we introduce and test two modalities allowing agents to introduce random correspondences ( §6) and to provide imprecise answers ( §7).

Related work

Interacting agents need a way to understand each others to some degree. They can all use the same ontology or preserve heterogeneous ontologies. In the latter case, heterogeneity is often reduced by using alignments between these ontologies [START_REF] Payne | [END_REF]. However, because matching systems are not always correct or because agents change their ontologies, alignments may become incorrect. There have been various ways to solve this problem independently of agent tasks: gossipping to ensure a global coherence of the networks of ontologies [Aberer et al., 2003], logical repair to enforce consistency [Meilicke, 2011;[START_REF] Jiménez-Ruiz | [END_REF][START_REF] Santos | [END_REF] or conservativity [Jiménez-Ruiz et al., 2016] constraints. Such approaches have been integrated within agent systems through specific protocols [Aberer et al., 2003;[START_REF] Payne | [END_REF]].

Here we are considering approaches in which agents elaborate and repair alignments in the context of other tasks, achieving global repair through local action.

Cultural language evolution [START_REF] Steels | Experiments in cultural language evolution[END_REF] showed how a particular culture can be shared by a population of agents through communication. This work offers an experimental methodology: a population of agents has to play randomly an "interaction game" with precise rules. The outcome of the game is clearly identified as a success or a failure. In function of the outcome, agents adapt their language. The state of the system is monitored and especially the success rate which measures the convergence of agents to a stable state. This approach may be applied to language [START_REF] Steels | Experiments in cultural language evolution[END_REF] or ontologies [START_REF] Steels | Luc Steels. The origins of ontologies and communication conventions in multi-agent systems[END_REF].

It has been adapted to the evolution of ontology alignments: agents have their own ontologies related by public ontology alignments (network of ontologies). They play games involving the alignments. The games allow them to detect incorrect correspondences through their use and to locally repair the alignment. [Euzenat, 2014] showed that agents are able to repair alignments through playing a simple reclassification game. Several operators were compared and shown to match the capability of logic-based alignment repair systems.

This approach has also been considered in the context of more elaborate games. Interaction-situated semantic alignment [START_REF] Atencia | Manuel Atencia and Marco Schorlemmer. An interaction-based approach to semantic alignment[END_REF] considers ontology matching as framed by interaction protocols that agents use to communicate. Agents induce alignments between the different ontologies that they use depending on the success expectation of each correspondence with respect to the protocol. Failing dialogues lead them to revise their expectations and associated correspondences. [Chocron and Schorlemmer, 2016] promotes the combination of the evolutionary approach with classical matching but can be interpreted as a way to repair alignments through their use. This has recently been generalised to less constrained declarative protocols with isomorphic alignments [START_REF] Chocron | [END_REF].

We consider here very simple games with more elaborate ontologies involving subsumption and disjointness.

Experimental method

The experimental method that is used throughout this paper is directly derived from [Euzenat, 2014] as well as the software which has been used, and extended. Results are thus directly comparable.

The setting is deliberately abstract. This allows to control experiment variables, as our goal is to understand better which factors, in the setting and adaptation operators, influence the properties of the result. These experiments are randomised, which would be difficult with real-world data.

Setting

Objects in the world are described by a finite set of Boolean features (named a, b, c, etc.). Each object is described by the presence or absence of each feature, e.g., a ∧ ¬b ∧ ¬c ∧ d.

= = ≥ ≥ ≥ ≥ ≥ ≥ ≥ ≥ ≥ ≥ ≤ ≤ ≤ ≤
Figure 1: One central ontology and its correct correspondences to two other ontology fragments.

Objects, also called instances, are classified in ontologies which are strict hierarchies. Each class in the hierarchy corresponds to the conjunction of the features of its ancestors. For instance, the bottom-leftmost class in Figure 1 is defined by c ∧ ¬d ∧ ¬a. Each level in these hierarchies adds one constraint (positive or negated) related to exactly one feature. This means that classes not in subsumption relation are disjoint. Ontologies are incomplete since they have one level less than the environment has features (d for the middle ontology of Figure 1). Ontologies, expressed in OWL, only use a very simple description logic. The boolean separation, may seem universal and/or artificial, it is simply a minimal language that features subsumption and disjointness.

An alignment is a set of correspondences between two ontologies. A correspondence is an expression like C, r, C in which C and C identify classes of the two ontologies and r is the relation between these classes. We use relation symbols ≤, ≥ and = denoting subsumption and equivalence relations between classes. Figure 1 shows a fragment of the correct alignments, called reference, between one ontology and two others. Alignments are required to be functional -a class is subsumed by at most one more specific class in each alignment, but one class may subsume several classes-so as to be able to use them to reclassify instances.

Games

There are as many agents as ontologies (each agent has a different ontology). Agents do not have access to the ontologies of other agents -they know the class names but not their definitions-nor to the reference alignments. They are instead provided with random alignments with the constraint that the topmost classes of each ontology are equivalent and alignments are functional.

In each game, two agents are chosen at random, one agent (A) picks up an instance (i) at random and asks the other one (A ) in which class it would classify the instance in its own ontology (O) using the public alignment between O and O . A determines which correspondence is applicable and communicates both the correspondence ( C, r, C ) and the class (C). A considers the relations between C and the class D in which it would classify i.

If C is compatible with D (C subsumes D, noted D C) the interaction is considered successful, otherwise (C is disjoint from D, noted C⊥D) it is a failure. A then uses an adaptation operator to adapt the alignment (in this case, it only does it in case of failure). Various adaptation operators are discussed in further sections.

Measures

As agents play games, measures may be applied to the resulting situation (the current network of ontologies) and the evolution of the game. We use the same measures as in the initial experiments: -Success rate [START_REF] Steels | Experiments in cultural language evolution[END_REF] characterised by the ratio of success over games played is the main measure. -Semantic precision and recall [START_REF] Euzenat | Semantic precision and recall for ontology alignment evaluation[END_REF] is computed here instead of reporting directly F-measure. They measure the degree of correctness and completeness of the resulting alignments with respect to the known correct reference alignments.1 -Incoherence rate [START_REF] Meilicke | Christian Meilicke and Heiner Stuckenschmidt. Incoherence as a basis for measuring the quality of ontology mappings[END_REF] measures the proportion of incoherent correspondences in alignments taken one by one. -Convergence is the number of games taken to converge in all cases (it is an observed maximum, not an average) when the process converges.

We depart from the initial experiments by using the full reference alignments. It happens that the reference alignments in [Euzenat, 2014] only contained correspondences with leaves. We are now using a new reference alignment with 86 rather than 70 correspondences, in the case of 4 ontologies. As the experiments were always based on instances classified in leaves, this made few differences with respect to the validity of the game, but this led to incorrect F-measure (more precisely: underestimated precision and overestimated recall).

Repeated experiments

We first repeat the second and third experiments of [Euzenat, 2014] concerned respectively with comparing three operators and comparing them to a baseline given by the logical repairers LogMap Repair2 [START_REF] Jiménez-Ruiz | [END_REF] and Alcomo [Meilicke, 2011] which restore logical consistency in alignments, by suppressing a minimal set of correspondences. These systems are not in competition as they do not rely on the same type of information: logical repairers have access to all ontologies and alignments but no concrete instance; agents only have access to their ontology and related alignments but can count on the game results.

For repeating the experiments, after implementing new measures and references, we run the Lazy lavender platform3 with 4 agents over 10000 games. All results are the average of 10 runs (not necessarily the same). These are, with new operators over more games (10000 instead of 2000) and improved platform, the same tests as in the initial paper.

Adaptation operators

Agents use a specific adaptation operator to solve this problem. The initial experiment compared three operators: delete, replace and add. Assuming that the faulty correspondence C, r, C has been crossed by the object from C to C: delete simply removes the correspondence; replace in case r is =, then, in addition to delete, the same correspondence with a ≤ relation is added ( C, ≤, C ); add a correspondence between C and the direct superclass C of C is added ( C , ≥, C ), in addition to replace. These operators share two particular properties: -Safeness: after applying the operator, if the same instance is chosen, the problem would not occur again (maybe a different problem would occur); -Entailment: each correspondence added by any of the operators was entailed by the removed correspondence. The properties can be proved a priori. For the first one (safeness), the failure is due to the fact that D (i), D C , C, ≥, C entails C(i), but C(i) conflicts with D(i) and D⊥C. Each of these modalities discards C, ≥, C and the added correspondences do not permit to deduce C(i). Hence, if it is still entailed, this is for other reasons, that will eventually be found later, e.g., C, ≥, E with C E . For the second property (entailment): delete: nothing has to be entailed;

replace: C, =, C |= C, ≤, C add: C, ≥, C , C C |= C , ≥, C

Hypotheses

We expected (H1) to reach the same results as the initial experiment, in particular that (H2) these operators reach 100% precision, since they delete any correspondence that causes failures.

Results and discussion

Results are provided in the first two sections of Table 1. The obtained results are in line with those presented before in what concerns convergence, size of the alignments and the respective merits of the operators with respect to F-measure. However, there are three main differences.

The results in terms of F-measure, either concerning LogMap and Alcomo, or the adaptation operators beyond delete are higher than previously. This is due to the new (corrected) reference alignments. This shows that already with 4 agents, agent results are better than logical repairers.

The delete and replace operators have now different Fmeasure values. This is also due to the new reference.

Contrary to what was expected (H2), agents would not reach 100% precision. It may happen that an incorrect correspondence cannot be detected by the games because it does not cause any failure -such correspondences are shadowed by another correspondence. This is illustrated by Figure 2 (left part): although the red/dashed correspondence is strictly speaking incorrect (¬a ∧ ¬b ⇒ ¬b ∧ c is not true), it happens that whenever it is not true (the class ¬a ∧ ¬b ∧ ¬c), the other correspondence (blue/plain) will reclassify instances in the correct class. Hence, the incorrect correspondence does not cause any failure. This is actually like if agents reinvented non-monotonic inheritance: all birds fly (Bird F ly), unless they are emus (Bird ∧ Emu ¬F ly). [Euzenat, 2014] are not reported here. Figure 2: Typical cases of shadowing in which agents cannot identify the red/dashed correspondences as incorrect. Indeed, any instance that could highlight the error would be correctly reclassified by the blue/plain correspondences. Thus, the correct correspondences (green/dotted) could not be tested.

As a consequence, not only the result does not reach 100% precision, but it can even be incoherent (as in Figure 2).

New adaptation operators

Since recall is not very high, we introduced new operators similar to the previous ones expected to provide better results by improving on the previous operators. We first present them and then show how they perform in experiments. which class it belongs in its ontology (orange arrows). They identify the red correspondence (marked =) as erroneous: it leads to the conclusion that this instance belongs to a class which is disjoint from the identified class. delete removes this correspondence. replace replaces it with the subsumption part of the correspondence (≤) that has not been proved incorrect. add (addjoin) will add a (≥) correspondence from a (the common) subsumer of C (and D). The new refine operation will add (≥) correspondences to the subsumees of C not subsuming D . These operators still satisfy the properties of safeness and entailment. The argument for safeness is the same as before. Entailment follows from: addjoin: the argument provided for add is still valid. refine: C, ≥, C , C C |= C, ≥, C refadd: inherits from refine and add. So, the operators are still bounded by the initial random set of alignments.

Adaptation operators

In addition, to preserve the functionality of alignments, the correspondence is added by refine only if no other correspon- refine and refadd require extra steps of interaction to find out the subsumed classes in A 's ontology (alternatively the refine part could be performed by A ).

Hypotheses

Our initial hypotheses are that (H3) refine is better than replace, and (H4) refadd improves over add, addjoin and refine, especially with better recall.

Results and discussion

Results are provided in the third section of Table 1. refine loses precision and increases recall when compared to replace and the opposite when compared to add and addjoin). refine is thus found better than replace (H3) and already at least as good as LogMap and Alcomo in terms of F-measure.

Figure 4 shows the evolution over 2000 iterations of the success rate and F-measure of the six presented operators. refadd has an intermediate precision between add-addjoin and replace but, as expected, largely improves both recall. It thus largely improves F-measure (H4) but it is slower to converge than add. The combination of addjoin and refine, refadd is found to have a better recall and F-measure than both.

Expansion: beyond initial alignments

The results of these experiments are, as discussed in [Euzenat, 2014], very constrained by the initial random alignments that are provided to the system. Hence, here we propose to expand the set of correspondences and to measure their impact.

Expansion modality

We introduce a modality that, when the operators remove a correspondence and are not able to replace it by another correspondence, will add a new random one. This is a modality that can be associated with any operator above.

Agents rely on random correspondences in the sense that there is nothing which guides them towards a particular correspondence. If the correspondence is drawn at random each time, what is observed is that the process does not converge: agents tend to maintain a large number of correspondences (around 100 while the reference alignment has only 86 correspondences) and then they keep on replacing incorrect correspondences by random incorrect ones. Hence, the modality rules out some correspondences. First, in order to warrant convergence, the discarded correspondences are recorded and will not be reintroduced since they have been proved incorrect. Moreover, correspondences that the agent can find entailed by its ontology and the current alignment or by a recorded correspondence will not be added.

This modality does not satisfy any more either safeness nor entailment, which were satisfied by the initial operators.

Hypothesis

Our hypothesis is that (H5) the expansion modality increases recall, and hence overall F-measure, possibly at the expense of a slower convergence.

Results and discussion

Results are provided in Table 2. Hypothesis H5 is observed for all operators: they increase recall and decrease precision, increasing F-measure.

Operators still do not reach 100% recall. This is due to two combined phenomena: -Since instances are always in leaves, as soon as agents found the correct correspondence for a leaf, there is no way to repair the correspondences it shadows (Figure 2). -By the same phenomenon as before, it does not matter if the shadowed correspondences are correct or not because they are never solicited. Hence, incorrect correspondences may take the place of the correct ones which will never be added (because we enforce functionality). This is illustrated by Figure 2 (right-hand part): As soon as the agents have found the two correspondences in blue/plain, it is warranted that all instances falling in the two leaf classes will be correctly reclassified. However, agents only play with concrete objects that they classify in the leaves. Hence, whatever correspondence reaches their common ancestors, such as the red/dashed correspondence, will never be tested. In consequence, it will never cause a failure to be repaired.

Relaxation: exploring the shade

Agents only adapt perfectly to what they have to do, i.e., to succeed in the game. Hence they converge towards 100% success rates. They are not geared to find out nice and consistent theories about the world. Because they reach success in playing the game, incoherence remains. This is why they should be made more curious. To achieve this, we introduce a specific relaxation modality within the game: Agent A has the opportunity to not use the most specific correspondence when answering to A, but to chose a more general one. This is alike someone answering a question with a general statement and not the most specific answer she knows (this is Latin music vs. this is Brazilian bossa nova vs. this is a Luiz Bonfá tune).

With relaxation, when encountering a correspondence that applies to the current instance, agents use this correspondence only with a specific probability, called immediate consumption probability, which also applies to the shadowed correspondences. In case there is no shadowed correspondence but the top-most one, agents use the applicable correspondence.

Hypothesis

It is expected that relaxation enforces the monotonicity of the alignments. Hence, (H6) precision should increase and incoherence decrease.

Results and discussion

The same experiments as previously have been performed with the raw operators (as in §4 and 5) and with expansion ( §6). We set the immediate consumption probability to 80% (we found this value very close to the optimum, but make no claim about it here).

All operators now achieve 100% precision (Table 3): by having a chance to select the shadowed correspondences, they will be discarded if they are incorrect. This applies to the basic operators ( §4 and 5) as well as their expanded version ( §6). In consequence, the resulting alignments are always fully coherent (H6).

If relaxation increases precision, it decreases recall with respect to the non relaxing modality, most of the time leading to a lower F-measure. However, the combination of relaxation and expansion with the refadd operator ( §5) reaches improved results in both precision and recall leading to a very high Fmeasure. dotted), that would entail it, cannot be added because of the functionality constraint.

One remaining question is why do not agents reach 100% recall? There are two contributing issues: The first one is related to the reverse shadowing problem, illustrated by Figure 5, in which a more general correct but incomplete correspondence shadows its more specific instance. Due to the functionality constraint, the more specific correspondence will never be added. The other issue is that agents do not generate enough correspondences. This is mitigated by the remark that they are able to generate more correspondences than in the reference alignment. However, once converged to a 100% precision configuration, there are no more failure and thus no possibility of completion.

Conclusion

We repeated experiments with agent communication-based alignment repair and found that, contrary to previously reported, agents were not able to fully get rid of incorrect correspondences. We explained why and provided methods to improve existing adaptation operators. First, the refine operator recovers more entailed correspondences than before and the expansion modality allowed to extend alignments beyond initial ones. Then allowing agents to return imprecise answers enable them to test shadowed correspondences. The combination of these three elements leads to full precision and coherence of the resulting alignments and high recall.

With all presented operators, agents converge towards a state in which all communication is finally successful (their goal). As a by-product, applying purely local operators, concerned by one game instance, agents are able to reach global convergence towards correct alignments.

Comparison with logical repairers is not fair any more: They do not have the opportunity to generate and test new correspondences and thus to achieve better recall. Now that agents are able to generate correspondences by themselves, it becomes possible to make them start from scratch without the provided random correspondences. Determining when and how many correspondences remains a difficult issue.

Finally, with the provided collection of operators (and modalities), it is worth considering how agents, besides selecting correspondences, can select such operators, or how the environment could select agents with specific operators.

  Three new operators are introduced (with the same faulty correspondence C, r, C as above): addjoin is a variation of add which adds a correspondence between C and the lowest superclass C of C compatible with D ( C , ≥, C ); refine extends replace by adding a correspondence between C and the subclasses C of C that do not subsume the actual class of the object ( C, ≥, C );refadd is the combination of addjoin and refine.

Figure 3 Figure 3 :

 33 Figure 3: Illustration on two ontology fragments of the effect of the various operators on the correspondence C, =, C . ⊥ denotes class disjointness.

Figure 5 :

 5 Figure5: Reverse shadowing: the blue/plain correspondence is correct as it asserts that ¬d ∧ a ∧ b ⇒ a. However, the more specific correspondence ¬d ∧ a ∧ b ⇒ a ∧ b (green, dotted), that would entail it, cannot be added because of the functionality constraint.

Table 1 :

 1 Measures with the reference and initial network of ontologies, the initial network repaired with Alcomo and LogMap, those obtained by the 3 initial operators (delete, replace, add), and the 3 new operators (refine, addjoin, refadd) [4 agents; 10 runs; 10000 games]. Results of

	Network and operator reference initial Alcomo LogMap delete replace add refine addjoin refadd	Size 86 54 28 29 6 11 33 20 23 41	Success Incoherence Semantic Semantic Semantic rate degree Precision F-measure Recall 1.0 0.0 1.0 1.0 1.0 0.24 0.34 0.11 0.20 0.89 0.43 0.0 0.21 0.26 0.33 0.51 0.0 0.24 0.26 0.29 0.99 0.0 1.0 0.13 0.07 0.99 0.01 0.99 0.21 0.12 0.98 0.14 0.80 0.52 0.39 0.99 0.02 0.96 0.37 0.23 0.99 0.10 0.84 0.43 0.29 0.99 0.09 0.86 0.62 0.48	Convergence ----445 1478 1396 1133 1004 1266

  Operator Size Success Inc. Precision F-measure Recall

	delete replace refine add addjoin refadd	20 0.98 0.03 0.91 35 0.97 0.11 0.84 48 0.96 0.16 0.78 60 0.95 0.21 0.73 54 0.97 0.17 0.75 66 0.96 0.23 0.71	0.35 0.52 0.64 0.69 0.66 0.73	0.22 0.38 0.55 0.66 0.59 0.76
	Table 2: Results of all operators with the expansion modality with memory [4 agents; 10 runs; 10000 games].

Contrary to classical precision and recall, it is not possible to deduce them from the numbers given hereafter.

We used the version of LogMap made available for OAEI 2016.

http://lazylav.gforge.inria.fr

Acknowledgments

We thank the developers of Alcomo 4 and LogMap 5 for making their tools available.

Experiment material

Experiment records are available under the Lazy lavender 3 logbook at entries:


Towards a hybrid approach for supervising interactive adaptive systems

Damien Mondou, Armelle Prigent, Arnaud Revel, Nicolas Rempulski

Research area

The analysis of users' behavior (for example the visitors of a website or tourists using a dedicated mobile application) tackle a common problem: the rapid extraction of path's patterns. These patterns will go back to a user profile characterization and their behaviors. The goal is to achieve a dynamic content adaptation according to these behaviors and the specific context of navigation. Various works were interested in how to acquire and dynamically analyze navigation datas through contents by extracting relevant information about users's interest or motivation and proposing dynamic adaptations rules relevant for the specific situation. Two approaches allow to address this problem: one based on machine learning techniques (i.e. reinforcement algorithms) for extracting representative information on the basis of past navigations logs, the other is based on the dynamic observation of the behavior's user and a set of scenario of modification rules. Therefore our work intends to develop a generic framework, based on a formal model, for analyzing users' behavior and dynamic content adaptation using a hybrid approach combining learning and realtime observation/scenario modification.

State of the art

There are already a huge number of approaches related to the dynamic adaptation for interactive storytelling. We can classify them into three classes. First, scripted approaches [START_REF] Vega | A Petri Net Model for the Analysis of The Ordering of Actions in Computer Games[END_REF], [START_REF] Rempulski | Adaptive Storytelling Based On Model-Checking Approaches[END_REF] are based on an expert system controlling the user experience. The scripted approaches generate the narrative that is closest to the expectations of the latter based on the observation that is made and compared to a set of predefined rules. Modeling such an architecture is a complex task as all the possible paths for the user must be defined by the designer. Oriented agent approaches aim to the emergence of narratives based on a set of agents' behaviors [START_REF] Mateas | Fac ¸ade: An experiment in building a fully-realized interactive drama[END_REF]. The modularity of this way of modeling the system makes it easier to design but this approach makes it more difficult to control the quality and consistency of the generated model, what scripted approaches guarantee by their very structure. Finally, hybrid approaches try to find the balance between the user's freedom, and thus a high level of adaptation obtained with oriented agent approach, and the respect of the designer's frame (designed with scripted approaches). [Brian Magerko, 2003] offers such an hybrid interactive storytelling system, where the author specifies a generic framework without limiting the user's actions. The quality of the execution is carried out by a manager that dynamically analyzes the behavior of users to detect unanticipated behaviors.

The major difficulty stands in the representation of all the possible interactions between the user and the system. The model must garantee a high level of modularity, reusability and want be scalable enough to meet potential changes. In addition, supervision models requires having a formal model from which it is possible to extract the most relevant paths. Moreover, as one of our purpose is to mix machine learning (by adding or removing interactions for example) and dynamic formal analysis, our execution framework needs to manipulate a modular and easily alterable model depending on the execution context. Moreover, we need a model that is robust enough for a large number of states and transitions (as we are working on interactive systems). [START_REF] Li | Nested Timed Automata[END_REF] describes NeTA, a model based on nested timed automata. A set of automata is stored in a stack and the system behaves as the present automaton on the top of the stack. Time passes uniformly in all the automata. This approach is an extension of timed automata presented in [START_REF] Ah | A theory of timed automata[END_REF]] by adding a switching context. This context happens by the actions "push" and "pop" or by changing the top of the stack automaton. A second extension of timed automata is presented in [David, 2003]. Hierarchical timed automata allow to model systems easily with a large number of states and transitions. Automata are encapsulated in localities which can themselves be encapsulated in other localities. This model respects the semantics of timed automata by the passage of transitions and to model a system in depth but does not offer a modular modeling as proposed by our model.

Contribution

The first question is, which model can we use to represent and supervise a large interactive system without being confronted to the hard task of modeling complex system and to overcome state space explosion problem? Here, we intend to extend the work of [Rempulski, 2013] offering a representation based on I/O automata of complex systems. The model handles many entities, offering the designer a paradigm based on a simplified model such as modularity, multiple-inheritance and reuse of components.

The second question is, how to combine in a single system supervision, management of operations (top-down approach) and integration into the pilotage rules determined on the basis of the observations of the actual user's behavior (bottom-up approach)? The bottom-up approach allows, after a learning phase, to extract relevant information by analyzing an interactive system during its very execution. The reinforcement learning techniques [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF]] offer an iterative process to find an ideal sequence to achieve a goal in a given environment. The top-down approach aims to produce a representation of a system from a profile (user or context). [START_REF] Wang | Adam: An adaptive multimedia content description mechanism and its application in web-based learning[END_REF] proposes a new language, ADAM, to specify adaptive structures. These structures are defined through three dimensions: the spatial dimension, the temporal dimension and a dimension managing the adaptive (location, quality of contents and techniques of interaction), and will be used to generate content in adequacy with the user's profile. Also based on the user profile, [De Virgilio, 2012] offers a modeling language, AML for the adaptive design of web applications at the conceptual level. Thanks to the basic primitives, the response and the structure of the information provided to the user is adapted to the execution context of the application. Thus, unlike conventional approaches proposing an adaptation based on a model and a set of rules to re-scripting the activity, we wish here to offer a hybrid approach based on top-down control handset a bottom-up analysis. The aim is to bring these two approaches and to propose an iteration loop between learning and formal representation to improve the knowledge and dynamically into the model by relevance feedback. The different application areas have each specific features. Thus, if in the context of the narrative, interaction between entities is important, applying the model to interactive experiences in cultural sites requires increasing the model for the consideration of the spatial dimension.

A situation based model : #Telling

In this section, we present the situation based model that has been initiated in [Rempulski, 2013] and that we aim to extend and improve in the bottom-up part of our system. It has been combined with a tool developped at the L3I lab. #Telling is a software platform, developed in C#, allowing the designer to create a modular system, control its execution and perform property checks.

A three-layer framework

In our approach, modeling a system is divided into three parts:

• We first define the system abstractly, as reusable components. Thus, the designer defines a set of actants, with their behaviors, grouped into situations. This step creates the abstraction layer.

• By instantiating the actants into actors and situations into scenes, the designer creates the implementation layer.

• Finally, the system dynamical description is defined by orders the scenes previously created, by defining a set of plots. The scenes execution order is then created and constitutes the dynamic layer.

Figure 1 shows the order in which items have to be created. Here, the designer has defined three actants A1, A2 and A3. The situation Sit1 is composed of actants A1 and A2 and the situation Sit2 of actants A2 and A3. An actant can appear in many situations.

In the second layer, these actants are then instantiated in an entity called an Actor. Three actors are defined: Act1 implementing the roles of actants A1 and A2 by multiple inheritance, the actant Act2 implementing the role of the actant A2 and the actant Act3 implementing A3. The scene Sc1 is an instantiation of the situation Sit1 and is composed of actor Act1. The scene Sc2 is an instantiation of the situation Sit2 and is composed of actors Act2 and Act3.

Finally, the designer arranges the scenes by creating three plots represented by the graph of the expected execution frame (from scenes to scenes). The execution order of the system can be the Plot P1(Sc1) → Plot P2(Sc1) → Plot P3(Sc2) or Plot P1(Sc1) → Plot P3(Sc2).

This method presents two advantages. First, the design is based on three layers that helps modularity and reuse. The abstraction layer helps the designer to constructs generic entities (actants) and a generic way of combining them. The second one (instantiation layer) is devoted to the implementation of generic entities and supports modularity by multiple inheritance of actants into concrete actors and combinations of actors in a concrete situation of execution (so called a scene). Finally, the dynamic layer helps organizing those concrete scenes into execution schemes. This approach constitutes a great support for extensible systems and reuse of entities for modeling. The second contribution concerns the dynamic construction of the systems global finite state automata from behaviors. Here, the designer has only to describe atomic behaviors for actants. The automata executing situations is constructed automatically.

In order to improve the system, we have produced an example of a lift. This example, helps us to test the gain for modeling task (using the modularity paradigm to add floors) and to test the limit of automatic construction of the global system with #Telling (state space explosion). For this system, represented in Figure 2, we can define the actants User, Cabin, Door, ControllerDoor and ControllerShifting. These five actants could be grouped into two differents situations: Floor0 and Floor1. By instantiating this situation into scene and actants into actors, we could define two plots, one per floor.

Designing abstract entities

The abstraction layer defines an abstract model of the system. It defines the prototypic roles (actants) and the generic situations. Actants define a set of behaviors which are the atomic elements of our model. They represent an action making the actant evolve. Our model construction paradigm is based on these behaviors composition. The abstraction layer is defined by the tuple (A, S,V ) with A is a set of actants, S is a set of situations and V is a set of variables.

Each entity defined in the system contains its own automata (whose construction is performed automatically), which can be synchronized to the other entities when they are grouped into situation.

Implementing entities in the story

Entities defined in the abstraction layer are generic. This second layer, called instantiation layer, is used to implement generic entities defined in the abstraction layer into concrete entities. Thus, actants are instantiated by actors and situations by scenes. This mechanics of instantiation allows to create several actors from a single actant model and allows the multiple inheritance (an actor implements the behavior of several actants). We define the instantiation layer by the following tuple (A cr , S c ) with A cr is a set of actors and S c is a set of scenes.

The actor implements the role of one or more actant(s). Multiple inheritance, shown in Figure 3, allows the designer to specialize an actor according to the behavior of the different actants it implements.

Supervising the model

The dynamic layer defines the execution ordering of scenes declared in the instanciation layer. Here, the scenes are encapsulated in an entity: the plot. This overcoat specifies the elements necessary for the scheduling execution of the scene. The plot is defined by the tuple (sc, G, S sup ) with sc ∈ S a scene of the instanciation layer, G a set of constraints and S sup a set of successors plots.

A constraint imposes a value to the state vector of a specific actor, before the completion of the scene. It is defined by the tuple (a, g(V a )) with a ∈ A cr s an actor of the referenced scene s and g(V a ) a constraint on the state vector of a. Figure 4: Plots representation.

We define two scenes S f loor0 and S f loor1 composed of ControllerDoor, ControllerShifting, Cabin, Door and User. Then, we define Two plots P0 and P1. P0 is composed of the scene S f loor0 , and the plot P1 is composed of the scene S f loor1 . The plot P0 is succeded by P1 and has constraints indicating that the cabin is to floor 0. The plot P1 is succeded by P0 and has constraints indicating that the cabin is to floor 1. Figure 4, represents this case.

Results

We return to our example of lift modeling. We present in Figure 5 the evolution of the number of states and transitions according to the number of floors. Give results, we see that without appropriate tools, modeling a complex system is a difficult and tedious task. The application domain of our work concerns mainly interactive experiences in museums. Our approach will be validated by the realization of games proposed by Nao robots piloted by #Telling in partner museums. With this intention, connection works with #Telling, our modeling tool, to Choregraphe, the management tool of the robot Nao, are ongoing. This connection will allow the designer to design both the architecture of the games it will offer to the museum's visitors and also the associated behaviors of the Nao robot.

Conclusion

In this paper, we have presented a model to facilitate the formal representation of complex systems. This model allows the automatic construction of systems based on simple behavior description. As an example, we have showned here the lift model. Now, we want to explore the topic of interactive experiences in museums piloted by the Nao robot. In this perspective, we wish to integrate a machine learning module to learn new behaviors for the system and dynamically add to the model. We also integrate time constraints whatsoever in the detection context or decision making (integration of the semantics of time UPPAAL [START_REF] Larsen | Uppaal in a nutshell[END_REF]

Figure 1 :

 1 Figure 1: Modeling a system in #Telling.

Figure 2 :

 2 Figure 2: System for managing a two-floors lift.

Figure 3 :

 3 Figure 3: Principle of inheritance.Figure4: Plots representation.

Figure 5 :

 5 Figure 5: Evolution of the number of states and transitions.


Damien Mondou
email: damien.mondou@univ-lr.fr

Armelle Prigent

Arnaud Revel

A dynamic scenario by remote supervision: a serious game in the museum with a Nao robot

Keywords: Robot, serious game, supervision, game design

This paper presents a new approach to designing and supervising an interactive experience. The approach is implemented by creating a serious game with a Nao robot. This game allows youth to discover the ethnographic artifacts of La Rochelle's natural history museum in a playful manner. The design phase of the game is divided into two steps. The first step defined the atomic behaviors grouped within the pattern. In the second step, the agents implementing these patterns were created; they specified the contents and behaviors to be executed on the controlled process, in our case the Nao robot. The first objective is to externalize the contents of the game (e.g. robot speech) and the real behaviors of the process (e.g. the different postures and gestures of the Nao) in a database. The second objective is to be able to define a serious game without constraints on the process piloted.

Introduction

Museums continually search for new ways to both increase their visitor count and allow visitors to discover the museum artifacts while gaining new knowledge. For several years, the serious game has demonstrated that it can playfully help users increase their understanding of a subject. The benefits of learning through play have been demonstrated [START_REF] Samuelsson | Play and learning in early childhood settings : international perspectives[END_REF][START_REF] Dietze | Playing and learning in early childhood education[END_REF]. Thus, many cultural sites have been equipped with fun features that allow visitors to find out about the collections or works of art in another manner.

For it, museum's curators may use on-screen games [START_REF] Coenen | Museus: Case study of a pervasive cultural heritage serious game[END_REF], augmented reality [START_REF] Miyashita | An augmented reality museum guide[END_REF], transmedia and virtual immersion solutions [START_REF] Carrozzino | Beyond virtual museums: Experiencing immersive virtual reality in real museums[END_REF] to allow visitors to navigate the artifacts and to learn about the cultural and artistic items at the cultural center. A possible continuation of these serious games is playing with a robot, which has been proposed for several years.

There are many advantages to interactive games with a robot. Robot-based computer vision systems can be integrated into the museum space and challenge a visitor to participate. Thus, a simple visitor can become a player for part of their visit. In addition, people can visit the museum and play without having to be equipped with a tablet, phone or others equipments which might interfere with their visit.

In collaboration with the Museum of Natural History of La Rochelle in France, we have developed an interactive experience for young visitors. This serious game allows the youth to discover, in a interesting manner, the ethnography section of the museum. This serious game is embedded in the Nao robot, that was initially developed by the French company Aldebaran (now Softbank Robotics). Nao encompasses a set of sensors (e.g. a camera, sonar, and tactile sensors) that allow it to perceive the environment. This robot is also able to interact with a person through its microphones and speakers. Thanks to a serious game, Nao is in charge of the playful discovery of the museum's artifacts.

In parallel with this experience and in the framework of a transdisciplinary study conducted with a laboratory specialized in marketing research, we studied the reactions of visitors to the presence of a robot in a cultural place. We found that, depending on the age of the visitor, the reactions differ. Children responded quicker to the robot and could be impatient waiting for the robot's response; adults were more hesitant. Thus, it is important to plan for different visitor scenarios (e.g. accounting for the individual's age).

It is important to note that scripting a game through a robot creates new challenges in design, especially when several scenarios are desired. For instance, the user can interact with the robot in various manners, which means these different interactions must be precisely orchestrated. Thus, the robot can move and gesture; see, recognize, and talk to the visitor; and wait for the visitor's responses. Another issue is that the current programming interfaces do not allow for content outsourcing, which is a challenge for the replicability of the interactive experience (e.g. in another museum).

In this paper, we offer an approach for the supervision of interactions with the robot through a high-level model to represent the different execution contexts.

We propose a formal model for the scenario, a generic supervision tool and the connection from Nao to the supervision tool (wrapper). After describing the interactive experience with Nao, developed for the museum, we will present the method for the game's modeling and dynamic supervision.

Robots in Everyday Life

Robots become more and more present in our everyday lives and allow us to simplify our daily activities. For instance, at King's College London, the receptionist is a robot named Inkha (Figure 1 (b)). Robots can also be found in supermarkets to help shoppers find different products and provide nutritional advice, such as LoweBot [START_REF]Prnewswire: Lowe's introduces lowebot -the next generation robot to enhance the home improvement shopping experience in the bay area[END_REF], Aiko Chihira [23], and Pepper [3]. Robots can also be major actors in artistic works, such as Nao [START_REF] Aspord | Pepper the humanoid robot debuts in france[END_REF] and Poppy [START_REF] Lapeyre | Poppy: a New Bio-Inspired Humanoid Robot Platform for Biped Locomotion and Physical Human-Robot Interaction[END_REF]. Artists and scientists have proposed a human-robot dance performance at the School of Moon in 2016 in order to question perceptions and representations of the body.

In this article, we are particularly interested in the presence of robots in cultural places. We have found several projects that introduce robots in museums ) is itself an interactive work and is responsible for guiding and presenting the works to the public [START_REF] Henaff | Entre art et science: Guido, un robot guide espiègle au musée d'art moderne de luxembourg[END_REF]. In France, as part of a project on the artificial esthetism of machines, the robot Berenson (Figure 1(c)) was deployed at the Quai Branly Museum. This robot behaves like an art critic, as he expresses an emotion when he sees a work. His opinion will evolve thanks to the reactions of the people around him [START_REF] Boucenna | A robot learns the facial expressions recognition and face/non-face discrimination through an imitation game[END_REF]. Furthermore, some museums, because of their architecture, are not accessible to people with a motor handicap. The Oiron castle museum in France observed this issue and, on the first floor of the museum, introduced a robot that is able to be remotely controlled by a joystick from the ground floor, which allows individuals with a handicap to visit the works that were previously inaccessible to them. This robot is called Norio (Figure 1(d)) and has been used in the museum since November 2014 [START_REF] Khlat | Norio, the robot guide of the oiron castle[END_REF].

Playing with Nao in the Museum

The scenario proposed in our experiment aims to allow the visitor (or player) to interact with the Nao robot to discover the Museum's Kanak masks collections. The robot asks the player a number of questions. This first experiment of dynamic supervision is based on an interactive quiz. With each new question, the player is required to move around the museum to find the answer and give it to the robot. Players can start a session with Nao at any time since a visual recognition algorithm allows the robot to continue the question sequence with the visitor. The first game session was completed by a purely linear development through the graphical programming tool called Choregraphe, which was delivered with Nao -and supported by Softbank Robotics -in order to pilot Nao. Choregraphe is a simple tool for combining predefined behaviors and descriptions of new behaviors, with Python language support. The pre-existing behaviors provided to Nao can be modified, since the Python code is accessible from Choregraphe. This tool offers some visual abstraction, which is then interpreted by the robot's NAOqi, the software that runs on the robot and controls it. The visual language of Choregraphe is translated through behaviors. Each behavior is defined by a name, input(s), output(s), parameter(s), and typically a Python script that contain the commands to be executed. When a signal arrives at the input, the behavior is loaded and performed. Once the output is stimulated, the box is onloaded. The entire interactive experiment in the museum was modeled and implemented through Choregraphe. The model obtained can be compared to a Petri net [START_REF] Reisig | A Primer in Petri Net Design[END_REF] where the places are behaviors (modeled by boxes) and the transitions are the links between these behaviors. While this tool has proven to be effective, it does not meet all of the researchers' expectations. For instance, Choregraphe does not make it possible to define a scenario, accounting for the space for which it was designed. The goal is to be able to deploy this type of experience in different museums with minimal processing effort. In order for this experience to be adaptable to various museums, the contents of the experiment must also be modified. Though the interactions are relatively simple and the sequence with a player contains only three questions, the possible modifications of the dialogues and, the content or the re-scheduling of the interactions proved to be laborious and hazardous when they intervened shortly before a session with the public. The final limitation concerns the temporality of the experience. We wish to be able to apply a duration period to a particular event in the scenario, such as a time limit on how long the visitor has to answer the question posed by the robot.

Modeling and Dynamic Supervision of the Game

These different limitations led the researchers to propose a new architecture allowing to take into account the activity's temporality, to manage external contents and to facilitate the deployment of the same scenario in another museum. Softbank Robotics proposed a software development kit (SDK) in C++ and Python to control Nao. Thus, we used the Python SDK in our approach. The first step consisted of developing a wrapper which would allow dialogue to occur between the robot and the supervision engine. Therefore, the robot's sequence consisted of waiting for a command that was supplied through a server (i.e. an order corresponding to a module programmed in Nao that was triggered by the supervision engine). The set of these orders (programming module) found their match in the model we created. This modeling method then considered different entities corresponding to the various possible states of Nao based on the sequence of the quiz, including waiting, "hey, approach", facial recognition, and learning the face. These entities were then grouped to define the execution contexts. The architecture of our solution, which allows for the design ans supervision of an interactive experiment (here, the Nao robot) is shown in the figure 5. As shown in figure 5, in the first step, the museum's curator and process' expert define the contents (e.g. the text of presentation of the works and quiz) and the executable behaviors (e.g. postures and gestures) respectively and then insert them into the database. The museum's curator can then design the interactive experience through the model's editor. The curator uses the contents present in the database to construct its scenario, associating the robot's behavior and speech and obtaining a specification file in XML format (Figure 7). This file is then used to generate the supervision file which contains the scenario modeled by timed automata as the input of the supervision tool. This tool, described in the following section, will then pilot the robot thanks to the scenario designed by the curator.

A Dynamic Supervision Approach

The final objective of our work is proposing a platform that allows for dynamic adaptation to the user and that permits the supervision of the activity, taking into account the content, interactivity, time, and space. Indeed, designing an interactive experience that fully corresponds to a user is tricky. A way of managing the quality of the experience is adjusting the content to the user's context. In this case, the management of the activity is based on an a priori modeling approach called top-down, as management have been used in web adaptation [START_REF] Wang | ADAM: An adaptive multimedia content description mechanism and its application in web-based learning[END_REF][START_REF] De Virgilio | AML: A modeling language for designing adaptive web applications[END_REF] and in a video game adaptation framework [START_REF] Liapis | Adaptive game level creation through rank-based interactive evolution[END_REF][START_REF] Magerko | Building an interactive drama architecture[END_REF][START_REF] Louchart | Emergent narrative, requirements and high-level architecture p[END_REF].

We propose a formal model of the game's execution based on two layers of modeling. The behaviors of the entities are modeled by input/output finite state machines, and the objective is to leave a significant possibility of choice to the user while guaranteeing the quality of the narrative framework. A first approach of dynamic supervision has been proposed in [START_REF] Rempulski | Adaptive Storytelling Based On Model-Checking Approaches[END_REF][START_REF] Rempulski | Synthèse dynamique de superviseur pour l'exécution adaptative d'applications interactives[END_REF], and having given rise to a supervision framework called #Telling. We propose an extension of this work that facilitate the control allows content outsourcing and time constraints representation. Thus, #Telling, whose modeling is divided into three layers, can supervise the activity based on the execution scenes. Although this framework's effectiveness has been proven, it does not allow for the temporal dimension to be taken into account, in either the definition of the behavior or in the transition from one situation to another. Finally, content management is not supported. We propose a new model that is able to address these issues and simplify the modeling phase of the experiment using the two-layer model, which is described in the next section.

Two-Layers Model

Formal models have been proven to be effective for controlling interactive experiments. Petri nets are often used to model and verify asynchronous activities, particularly serious games [START_REF] Araújo | Modeling Games with Petri Nets[END_REF][START_REF] Natkin | A Petri Net Model for the Analysis of The Ordering of Actions in Computer Games[END_REF]. Linear logic approaches have been used to represent ressources consumption [START_REF] Champagnat | Adaptative execution of game: Unfolding a correct story[END_REF]. In our approach, we use timed I/O finite state machines networks, which are more suited to represent synchronous systems with time constraints. Modeling an interactive experience is divided into two parts:

-We first describe the experience in an abstract manner, by defining the reusable entities (e.g. behaviors and patterns), modeled by timed automata. This step creates the declarative layer ;

-By instantiating patterns into agents, which are grouped into scheduled execution contexts, we define the implementation layer.

The process of creating an interactive system is illustrated in Figure 6.

Fig. 6. Two-layer approach for interactive modeling with content management

Declarative layer The declarative layer is the layer in which we define the generic entities of the modeled system, namely the atomic behaviors that can be executed. These behaviors are associated with declarative variables (e.g. integers, strings or Boolean) and channels, which are signals that allow several behaviors to be synchronized. The behaviors are then grouped into patterns that represent a set of entity specific behaviors that can be reused by the multiple inheritance principle.

Implementation layer

The implementation layer is the layer where the designer defines the agents, that can instantiate the behaviors of several patterns and aggregate atomic behaviors not present in the instantiated patterns. This principle of multiple inheritance allows the designer to reuse the patterns defined in the declarative layer as many times as necessary without needing to redefine the patterns. When the designer is defining the agents, for each behavior they specify the content or action to be performed on the process. These agents are then linked in execution contexts representing the specific context in which agents interact with each other.

Example of the Model for the Robot in Museums

We used our two-layer model to pilot the Nao robot in the natural history museum. We now present examples of behaviors for the implementation of the serious game embedded in the robot. In the declarative layer, we defined two behaviors, including "say" and "animate". Our scenario contains several phases in which the robot had to make a speech while being animated. We combined these two behaviors in an "animatedSay" pattern. This pattern can be reused as many times as necessary in the implementation layer.

For example, we wanted to define a "speechAwait" agent who would be responsible for attracting visitors. This agent would implement the previously defined "animatedSay" pattern. When defining the agent, the designer would perform a specification of the "say" and "animate" behaviors.

Thus, according to Figure 7, the module with ID number 673 in the database is associated with the "say" behavior and corresponds to the speech module programmed in Nao. With this behavior, we associated the content with ID number 9, which represents the speech uttered by the robot. Speed speech and language parameters had to be entered.

The interactive experience thus scripted was modeled by timed automata. We then obtained a supervisory file, as the input of our supervision tool.

Dynamic Supervision

This section introduces the dynamic supervision of the interactive experience. Since the interactive experience has been modeled, our supervision tool was responsible for running the experience and invoking it remotely in the Nao robot. The aim of our platform was to dissociate the modeling and the supervision of the activity. It was then possible to use the same model to control different processes, provided one develops a specific client for each process. A sequence diagram of the supervision is detailled in Figure 8.

This supervision tool uses the specification file previously generated as an input and loads the defined context graph (Figure 9). The transition from one context to another is completed by receiving signals (e.g. errorDetection, wait, detectUser, noGame and confirmGame) from a source context. The transition can also be done via global variables to which we can apply guards and updates, like an automaton. Thus, we define four contexts:

-Waiting: The robot goes into the rest position and waits until it detects the presence of a visitor. If a detection problem occurs, the context re-executes with the signal errorDetection. Otherwise, the supervision tool changes to the Explain context; -Explain: At this step, the serious game is presented and the robot asks the visitor if they want to play; -Disappoint: The visitor left or does not want to play. Nao expresses disappointment; Each context is defined as a timed automaton, and each transition resembles a command to be executed on the process. An example of the context "Waiting" is shown in Figure 10.

This serious game is executed on the Nao robot. We use the Python SDK provided by Softbank Robotics to control the robot through a client developed for this purpose. Each controlled process must possess its own client in order to interpret the data received from the server. The client links the supervision tool and the controlled process. Nao receives orders from the supervision tool and translates them into a language that is understandable by the robot.

Conclusion and Future Work

This paper presented a supervision model for interactive experiences. The modeling was divided into two steps. The first step defined the atomic behaviors grouped within the pattern. In the second step, the agents implementing these patterns were created; they specified the contents and behaviors to be executed on the controlled process (the Nao robot). Our contribution lies in two main points:

-A simplified construction of the scenario based on a two-layer model that helped with the modularity, reuse and automatic construction of the entities; -The external content management. Conventional design tools (like Choregraphe) do not allow this management. The modeling and adaptation of an experiment from one museum to another would have been laborious tasks. Thanks to our approach, the contents were managed externally. Our supervision tool was then in charge of recovering the contents in the database to control the process.

With the exception of the editor for designing the supervision's input file (which was thus designed manually), which is under development, all of these features were implemented. To test this approach, we modeled a simple serious game with the Nao robot. The validation of our model allows us today to consider the design of a more complex game. In the long run, we aim to combine this top-down approach with a bottom up approach [START_REF] Spronck | Adaptive game AI with dynamic scripting[END_REF][START_REF] Kop | Evolutionary Dynamic Scripting : Adaptation of Expert Rule Bases for Serious Games[END_REF] in order to integrate a relevance loop. Thus, due to the observations made during the execution of the activity and the machine learning process, we aim to be able to modify the a priori model by adding or removing behaviors. The machine learning process will allow the experience to be adaptated to the actual behavior of the end user, which is nearly impossible to predict during the design. Finally, we want to extend our model to the management of the locations where the different contexts of the scenario are executed; this outreach will allow us to take advantage of the visitors' real-time geolocation thanks to the e-beacon technology. It will also be possible to choose the dialogues and behaviors of the robot according to the observed displacements of the visitor.

Fig. 1 .

 1 Fig. 1. Experiences with robots in museums

Fig. 2 .Fig. 3 .

 23 Fig. 2. Nao in the La Rochelle museum, France

Fig. 4 .

 4 Fig. 4. Choregraphe programming for the game

Fig. 5 .

 5 Fig. 5. Architecture of the design and supervision of an interactive experience

Fig. 7 .

 7 Fig. 7. Scenario specification in XML format

Fig. 8 .

 8 Fig. 8. Supervision sequence diagram

Fig. 9 .

 9 Fig. 9. Context graph of the serious game


Frédéric Muttin

Claude Adés

Philippe Cousin

Philippe Pallu

La Barrière

Non-linear membrane finite-element analysis for lightweight structure enveloppe design

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


Stéphanie Noirpoudre

(/en/) Forum (https://forum.poppy-project.org) Photos (https://www.flickr.com/photos/poppy-project/albums) Documentation (http://docs.poppy-project.org/en/) Technologies (/en/technologies/) About (/en/about/) Blog (/en/archives/)

A day to build and program your robot! Théo (https://twitter.com/theosegonds) and Stéphanie (https://twitter.com/Sblackpowder) from Poppy Education team from Inria (https://flowers.inria.fr/) were at CERN (https://home.cern/fr/about) near Geneva to host a workshop on the construction and programming of the robotic arm Poppy Ergo Jr (https://www.poppy-project.org/en/robots/poppy-ergo-jr) as part of the Coding Pi Science Event (https://codezlascience.web.cern.ch/csd/). This educational event was organized by the CERN Micro Club, and CERN IdeaSquare (in partnership with Google Education and EU Code Week) around three scientific kits based upon the Raspberry Pi (https://www.raspberrypi.org/), a mini-computer to initiate in sciences and in computing.

In addition to the Poppy Ergo Jr (https://www.poppy-project.org/en/robots/poppy-ergo-jr) robotic arm, participants could also discover 2 other scientific kits:

POPPY ERGO JR WORKSHOP AT CERN

The Muon Hunter Cosmic Ray Detector kit (http://www.muonhunter.com/), designed as a partnership between Mr Mihaly Vadai and members of the CERN Micro Club.

The Programmable Wifi car GianoP (https://github.com/cmcrobotics/drivar), invented in partnership with the campus La Chataîgneraie, for the International School of Geneva.

By the way, we recommend this great article published on the Raspberry Pi blog written by William Bell (https://twitter.com/WilliamHBell), describing well the event and the technologies: CERN coding PI science event (https://www.raspberrypi.org/blog/cern-coding-pi-science-event/).

Here is a small report of what happened concerning the Poppy Ergo Jr robot, followed by a feedback on the workshop and the list of the resources that were used.

On Friday evening: discovering Poppy Ergo Jr

The Coding Pi Science days started with the presentation of the three scientific kits. We gave a quick overview of Poppy Ergo Jr: its story, its features and its applications.

(slides are in french but english speakers said they understood thanks to images and videos ;-))

Slide 1

This conference was a good appetizer and allowed us to exchange with very motivated participants! Saturday: a day to build and program their robot 7 groups of students with teachers and/or parents, of all ages, levels and backgrounds were there! After a brief introduction of the day -and a bit of sweating due the Swiss Customs not wanting to let the ordered robots go through :-)-, each group was given one kit. The workshop then began.

Théo and Stéphanie were there to coach and guide the groups and answer all their questions! The morning With the help of the facilitators, the first mission was to assemble the Poppy Ergo Jr robot using the documentation (https://docs.poppy-project.org/en/assembly-guides/ergo-jr/index.html). The goal? Success of the various stages (prepare the Raspberry Pi, configure the motors, assemble the robot parts using rivets…) without get mixed up! Jules built his robot super fast. Maybe a little too much: some parts were upside down! Never mind! Building and deconstructing is part of robotics :-)

In the end, all groups did very well (thanks to the younger ones :p) and finished in time for lunch!

The afternoon

Once the robots were built, the groups were ready to start their second mission: animate the robot.

Some have programmed with the visual language Snap! (similar to Scratch) and others in Python.

Jade programming the worm dance in Snap! (see the result in video (https://youtu.be/BTx-b0MQMKg))

Without having received any special instructions, the groups gave free rein to their creativity by drawing their inspiration from the pedagogical booklet, from the Jupyter Notebooks tutorials, and from their own imagination. Some choose to build Christmas tree robot, while others built a ball thrower. A robot even danced the samba! Guillaume Delille, a senior year student at the Jeanne d'Arc de Gex high school, had to present this day to his class.

He made this video which allows to relive the workshop: (https://github.com/poppy-project) (https://twitter.com/poppy_project) (https://facebook.com/poppycommunity) (https://www.flickr.com/photos/poppyproject/albums) (https://www.youtube.com/c/PoppyProjectOrgVideos)


Guillaume Bury
email: guillaume.bury@inria.fr

mSAT:AnOCamlSATSolver

mSAT : a SAT solving library in OCaml. It solves the satisfibility of propositional clauses. It is Modular : the user provides the theory. And it produces formal proofs.

Introduction

Propagation If there exists a clause C = C ∨ a, where C is false in the partial model, then add a → to the partial model, and record C as the reason for a.

Decision Take an atom a that is not yet in the partial model, and add a → to the model.

Conflict A conflict is a clause C that is false in the current partial model.

Analyze Perform resolution between the analyzed clause and the reason behind the propagation of its most recently assigned litteral, until the analyzed clause is suitable for backumping.

Backjump A clause is suitable for backjumping if its most recently assigned litteral a is a decision. We can then backtrack to before the decision, and add the analyzed clause to the solver, which will then enable to propagate a → ⊥.

SMT Formulas using first-order theories can be handled using a theory. Each formula propagated or decided is sent to the theory, which then has the duty to check whether the conjunction of all formulas seen so far is satisfiable, if not, it should return a theory tautology (as a clause), that is not satisfied in the current partial model.

Conflict Driven Clause Learning

Other Solvers

Theory Interface

Each clause records its "history" which is the clauses used during analyzing Minimal impact on proof search (already done to compute unsat-core) Sufficient to rebuild the whole resolution tree A proof is a clause and proof nodes are expanded on demand → no memory issue Enables various proof outputs :

• Dot/Graphviz (see example above)

  Are the following H1 : a = b H2 : b = c ∨ b = d hypotheses satisfiable ? H3 : a <> d H4 : a <> c ⟦b != d⟧, ⟦b != a⟧, ⟦a == d⟧ lemma T2 ⟦b == d⟧, ⟦b == c⟧ hypothesis H2 ⟦b == c⟧ ⟦b != c⟧, ⟦b != a⟧, ⟦a == c⟧ lemma T1 f, 'p) res = Sat | Unsat of 'f list * 'p type 'f slice = { start:int; length:int; get:int -> 'f } module type S = sig val backtrack : level -> unit val current_level : unit -> level val assume : formula slice -> (formula, proof) res end