Gavin Kemp

Genoveva Vargas-Solar

Parisa Catarina Ferreira Da Silva

Catarina Ferreira

Da Silva

Parisa Ghodous

Christine Collet

Aggregating and Managing Big Realtime Data in the Cloud -Application to Intelligent Transport for Smart Cities

Keywords: ITS, Big Data, Cloud Services, NoSQL

published or not. The documents may come   L'archive ouverte pluridisciplinaire

INTRODUCTION

During the last five years, the problem of providing intelligent real time data management using cloud computing technologies has attracted more and more attention from both academic researchers, e.g. P.

Valduriez team in France [START_REF] Gulisano | StreamCloud: An elastic and scalable data streaming system[END_REF], Freddy Lecue's work at Ireland IBM Research Lab [START_REF] Lecue | STAR-CITY[END_REF], Big Data Initiative CSAIL Laboratory in MIT, USA, Cyrus Shahabi's team University of Southern California in USA [START_REF] Demiryurek | TransDec:A Spatiotemporal Query Processing Framework for Transportation Systems[END_REF]) and industrial practitioners like Google Big Query, IBM, Thales. They mostly concentrate on modelling stream traffic flow, yet they barely combine different data flows with other big data to provide new intelligent transport services (ITS). ITS apply technology for integrating computers, electronics, satellites and sensors for making every transport mode (road, rail, air, water) more efficient, safe, and energy saving. ITS effectiveness relies on the prompt processing of the acquired transport-related information for reacting to congestion, dangerous situations, and, in general, optimizing the circulation of people and goods.

Integration, storage and analysis of huge data collections must be adapted to support ITS for providing solutions that can improve citizens' lifestyle and safety.

In order to address these challenges it is important to consider that big data introduce aspects to consider according to its properties described by the 5V's model [START_REF] Jagadish | Improved Design of Communication Platform of Distributed Traffic Information Systems Based on SOA[END_REF]): Volume, Velocity, Variety, Veracity, Value.

Volume and velocity (i.e., continuous production of new data) have an important impact in the way data is collected, archived and continuously processed. Transport data are generated at high speed by arrays of sensors or multiple events produced by devices and transport media (buses, cars, bikes, trains, etc.). This data need to be processed in real-time, near real-time or in batch, or as streams. Important decisions must be made in order to use distributed storage support that can maintain theses data collections in apply on them analysis cycles. Collected data, involved in transport scenarios, can be very heterogeneous in terms of formats and models (unstructured, semi-structured and structured) and content. Data variety imposes new requirements to data storage and database design that should dynamically adapt to the data format, in particular scaling up and down. ITS and associated applications aim at adding value to collected data. Adding value to big data depends on the events they represent and the type of processing operations applied for extracting such value (i.e., stochastic, probabilistic, regular or random). Adding value to data, given the degree of volume and variety, can require important computing, storage and memory resources. Value can be related to quality of big data (veracity) concerning (1) data consistency related to its associated statistical reliability; (2) data provenance and trust defined by data origin, collection and processing methods, including trusted infrastructure and facility.

Processing and managing big data, given the volume and veracity and given the greedy algorithms that are sometimes applied to it, for example, giving value and making it useful for applications, requires enabling infrastructures. Cloud architectures provide unlimited resources that can support big data management and exploitation. The essential characteristics of the cloud lie in ondemand self-service, broad network access, resource pooling, rapid elasticity and measured services [START_REF] Grance | The NIST Definition of Cloud Computing Recommendations of the National Institute of Standards and Technology[END_REF]. These characteristics make it possible to design and implement services to deal with big data management and exploitation using cloud resources to support applications such as ITS.

The objective of our work is to manage and aggregate cloud services for managing big data and assist decision making for transport systems. Thus this paper presents our approach for developing data storage, data cleaning and data integration services to make an efficient decision support system. Our services will implement algorithms and strategies that consume storage and computing resources of the cloud. For this reason, appropriate consumption models will guide their use.

The remainder of the paper is organized as follows. Section 2 describes work related to ours. Section 3 introduces our approach for managing transport big data on the cloud for supporting intelligent transport systems applications. Section 4 presents a case study of the application that validates our approach. Finally, Section 5 concludes the paper and discusses future work.

RELATED WORK

This section focus on big data transport projects, namely to optimize taxi usage, and on big data infrastructures and applications for transport data events.

Transdec [START_REF] Demiryurek | TransDec:A Spatiotemporal Query Processing Framework for Transportation Systems[END_REF]) is a project of the University of California to create a big data infrastructure adapted to transport. It's built on three tiers comparable to the MVC (Model, View, Controller) model for transport data. The presentation tier, based on Google TM Map, provides an interface to create the queries and expose the result, the query interface provides standard queries for the presentation tier and a data tier is spatiotemporal database built with sensor data and traffic data. This work provides an interesting query system taking into account the dynamic nature of town data and providing time relevant results in realtime. Urban insight [START_REF] Artikis | Self-Adaptive Event Recognition for Intelligent Transport Management[END_REF]) is a European project studying European town planning. In Dublin they are working event detection through big data, in particular on an accident detection system using video stream for CCTV (Closed Circuit Television) and crowdsourcing. Using data analysis they detect anomalies in the traffic and identify if it's an accident or not. When there is an ambiguity they rely on crowdsourcing to get further information. The RITA [START_REF] Thompson | RITA[END_REF] project in the United States is trying to identify new sources of data provided by connected infrastructure and connected vehicles. They work to propose more data sources usable for transport analysis. [START_REF] Jagadish | Improved Design of Communication Platform of Distributed Traffic Information Systems Based on SOA[END_REF]) propose a service-oriented model to encompass the data heterogeneity of several Chinese towns. Each town maintains its data and a service that allows other towns to understand their data. These services are aggregated to provide a global data sharing service. These papers propose methodologies to acknowledge data veracity and integrate heterogeneous data into one query system. An interesting line to work on would be to produce predictions based on this data to build interesting decision support systems. [START_REF] Jagadish | Improved Design of Communication Platform of Distributed Traffic Information Systems Based on SOA[END_REF] propose a big data infrastructure based on five steps: data acquisition, data cleaning and information extraction, data integration and aggregation, big data analysis and data interpretation. [START_REF] Chen | High performance integrated spatial big data analytics[END_REF]) use Hadoopgis to get information on demographic composition and health from spatial data. [START_REF] Lin | Scaling big data mining infrastructure : The twitter Experience[END_REF] present their experience on twitter to extract information from log information. They concluded that an efficient big data infrastructure is a balancing speed of development, ease of analysis, flexibility and scalability. Proposing a big data infrastructure on the cloud will make developing big data infrastructures more accessible to small businesses for several reasons: little initial investment, ease of development throw Service-Oriented Architecture (SOA) and using services developed by specialist of each service. [START_REF] Yuan | T-finder: A recommender system for finding passengers and vacant taxis[END_REF], [START_REF] Ge | An energy-efficient mobile recommender system[END_REF], [START_REF] Lee | Taxi Dispatch System Based on Current Demands and Real-Time Traffic Conditions[END_REF]) worked a transport project to help taxi companies optimize their taxi usage. They work on optimising the odds of a client needing a taxi to meet an empty taxi, optimizing travel time from taxi to clients, based on historical data collected from running taxis. Using knowledge from experienced taxi drivers, they built a mapping of the odds of passenger presence at collection points and direct the taxis based on that map. These research works don't use real-time data thus making it complicated to make accurate predictions and react to unexpected events. They also use data limited to GPS and taxi usage, whereas other data sources could be accessed and used.

The state of the art reveals a limited use of predictions from big data analytics for transportoriented systems. The heavy storage and processing infrastructures needed for big data and the current available data-oriented cloud services make possible the continuous access and processing of real time events to gain constant awareness, produce big databased decision support systems, which can help take immediate informed actions.

MANAGING TRANSPORT BIG DATA IN SMART CITIES

Consider the scenario where a taxi company needs to embed decision support in electric vehicles, to help their global optimal management. The company uses electric vehicles that implement a decision cycle to reach their destination while ensuring optimal recharging, through mobile recharging units. The decision making cycle aims at ensuring vehicles availability both temporally and spatially; and service continuity by avoiding congestion areas, accidents and other exceptional events. The taxis and mobile devices of users are equipped with video camera and location trackers that can emit the location of the taxis and people. For this purpose, we need data on the position of the vehicles and their energies levels, have a mechanism to communicate unexpected events and have usage and location of the mobile recharging station.

Figure 1 shows the services that this application relies on. These services concern data acquisition and cleaning and information extraction in one side of the spectrum, and on the other side big data analysis, integration and aggregation services, and decision-making support:  Data acquisition service: hardware and infrastructure services that transfer, to NoSQL data stores adapted to the format of the data, the data acquired by the vehicles, users, and sensors deployed in cities (e.g. roads, streets, public spaces).  Information extraction and cleaning service:

receives the data from the data acquisition services. At this level information is extracted from the unstructured data (e.g. video stream).  Integration and aggregation services: combines different types of data (e.g. video, sensor, weather data) formatting the data into a standard form to make simpler querying.  Big data analysis service: to process collected data and have a comprehensive vision of it. For instance, identifying value trends of different measures within data or classifying data according to its values. The consumption of taxis during rush hours in commercial zones of a city when it rains. Keep track the on-going situation of traffic in the town and predict future bottlenecks in specific zones.  Decision support service exports an end user application exposing information on, for instance, the town transport systems and on new destinations to the taxi drivers, and information regarding the best moments in which a taxi should search for energy or events where clients may need a taxy transportation.

Figure 1: Big Data as a Service.

In order to let these services work in the best conditions, it is necessary to propose an approach for integrating and aggregating collected data and correlate it with data streaming from other data providers. Indeed, data must be cleaned to complete them and remove heterogeneity and then prepared (stored on disk, memory or cache) to support decision-making actions. This paper proposes a data store as a service that is a horizontal support for the services described in the previous lines.

TRANSPORT DATA STORE AS A SERVICE

Figure 2 presents the general architecture of the transport data store as a service that we propose. It adopts a polyglot persistence approach that combines several NoSQL systems for providing a storage support. Profiting from the cluster-oriented architecture of these systems our store uses a multicloud cluster based storage layer, which uses tools such as Swift (openstack 2015) and Amazon S3 (Amazon 2015).

Figure 2: Data store as a service.

Our service extends an UnQL [START_REF] Buneman | UnQL: a query language and algebra for semistructured data based on structural recursion[END_REF] layer with data processing operators including joins and filters for storing and retrieving data in an homogeneous way.

Furthermore, it exploits the sharding strategies of the NoSQL [START_REF] Cattell | Scalable SQL and NoSQL data stores[END_REF]) systems for distributing and duplicating data, and ensuring availability. Shards are organized according to ranges of values of given attributes, or to hash functions and tags related to geographic zones. This induces request balancing and ensures better performance when data must be inserted and retrieved.

The service exploits also the persistence supports of clients (disk and cache) installed in mobile devices in order to distribute data processing and ensure data availability. For example, in our transport scenario, the service uses storage provided by devices used by taxis and users to process and manage data necessary for ITS services described in the previous section. In this way it avoids data transfer that can be penalizing in terms of response time and economic cost for accessing 3G or 4G networks.

Our data store service provides a global access to clusters providing NoSQL and relational support, and enables applications designers to configure their resources provision and non-functional properties according to given requirements and cloud subscriptions. An application defines the data structures that must persist in the UML eclipse plugin and then the tool Model2Roo (https://code.google.com/p/model2roo/) generates the necessary bindings to interact with different NoSQL stores. The application designer according to a profiling phase executed using the QDB benchmark (https://github.com/qdb-io) chooses the NoSQL stores.

Designing transport data collections

The data collections "Evènement routier temps reel", "Etat du trafic temps reel", "Borne Criter", "Tronçon Web Criter", "Trafic historique", "plan Lyon", "Aménagement cyclable", "Caméra Web Criter" and "Station Velo'v", provided by the project Grand Lyon (GrandLyon 2015), are sought and stored by our service in order to be able to correlate collected data with data describing the city and its infrastructures (parks, roads, commercial zones, river). This data is highly heterogeneous in format, information and update rates. There are images in JPG, JSON, XML, and PDF formats. The data is also updated at varying rates going from yearly updates to real-time data passing by daily and minutely updates. GPS and location data in devices and vehicles are seen by our service as continuous data that can be correlated to other collected data useful for performing some decision making requests, such as which is the closest taxi (considering distance and time) to a client?, according to traffic and taxi-energy level, which are the possible destinations it can accept? Data are sharded by our service to perform this type of requests that require computing resources. Our service uses a MongoDB cluster to store these data.

Data stemming from social networks particularly Twitter and Waze of taxi users are collected and stored in NeO4J. This collection provides a real-time view of the traffic, road and zones status and events. Data are sharded thanks to our storage service locally on mobile devices and on NeO4J instances deployed in the cloud.

Making global transport decisions

We conducted an experimental validation of our transport data store as a service for the scenario we described in Section 3. The experiment implements a polyglot multi-database that contains data collected from the French city Lyon. These data are retrieved by applications and infrastructure integrated by the project Grand Lyon. We then implement some important operations of the decision making cycle of the scenario (see Figure 3). The decision making cycle consists in:

 Collecting data streams from taxis and users that are mobile data providers evolving in Lyon and feeding the data store service.  Computing recommendations, such as taxy itineraries and battery charging, according to the traffic status.

Figure 3 UML sequence diagram of the decision making process.

We focus particularly in three operations that use the transport data storage as a service approach, which are dissemination of events, optimization of energy recharging and scaling taxi provision of exceptional situations. We describe this use cases in the following sections.

Disseminating events

The applications deployed in taxis and users can be used for disseminating exceptional situation events, for example, unexpected dangers (Figure 4). In our scenario a pedestrian is about to cross the road. "Vehicle A" is arriving in the same place but has no line of sight. "Vehicle B" in the area "sees" the pedestrian. The video stream from "Vehicle B" is analysed by the "Information extraction and cleaning services" and compared with topological information of the area. The pedestrian detection information is stored on a NoSQL database. As the vehicle comes in the area, the vehicle computer will make query to that database informing on potential dangers and then notifies the driver of the danger. Depending on the nature of the danger the data store will make decisions on how long to keep that information and during which period it will reexecute the dissemination to taxis getting close to the zone.

Optimising battery recharging

Part of the objective of taxi companies is use only electric vehicles. Unfortunately the lack of data makes it complicated to make good strategic solutions on the locations of the recharging stations that are also mobile (Figure 5). Using UnQL queries, the historical data stored in the NoSQL databases is periodically uploaded into a Hadoop [START_REF] Zikopoulos | Understanding big data[END_REF] based application designed to extract information to build a classification model and regression model for the real time data. Using this model and real-time data the system will make predictions on the location of taxi users and the traffic. As decision makers take decisions, this information is feed into the model to help the decision maker optimise the number of operational taxi, the location of these taxis and the location of the recharging stations by exposing the consequence previous similar decisions had.

CONCLUSION

This paper proposes a transport data store as a service that implements a distributed storage approach. Our approach uses NoSQL systems deployed in a multi-cloud setting and makes sharding decisions for ensuring data availability.

The transport data store service is validated in a scalable and adaptable ITS for electric vehicles using big data analytics on the cloud. This provides a global view of current status of town transport, helps making accurate strategic decisions, and insures maximum security to the vehicles and their occupants.

For the time being our storage service concentrates in improving design issues with respect to NoSQL support. We are currently measuring performance with respect to different sizes of data collections. We have noticed that NoSQL provides reasonable response times once an indexing phase has been completed. We are willing to study the use of indexing criteria and provide strategies for dealing with continuous data. These issues concern our future work.

Figure 4 :

 4 Figure 4: Disseminating exceptional events.

Figure 5 :

 5 Figure 5: Optimising battery recharging.

ACKNOWLEDGEMENT

We thank the Région Rhône-Alpes who finances the thesis work of Gavin Kemp by means of the ARC 7 programme (http://www.arc7-territoiresmobilites.rhonealpes.fr/), as well as the competitiveness cluster LUTB Transport & Mobility Systems, in particularly Mr. Pascal Nief, Mr. Timothée David and Mr. Philippe Gache for putting us in contact with local companies and projects to gather use case scenarios for our work.


Nadine Glas
email: glas@telecom-paristech.fr

Ken Prepin
email: ken.prepin@priceminister.com

Catherine Pelachaud
email: pelachaud@telecom-paristech.fr

Engagement driven Topic Selection for an Information-Giving Agent

We propose a model for conversational agents to select the topic of interaction in agent-initiated information-giving chat. By taking into account the agent's dynamically updated perception of the user's engagement, the agent's own preferences and its associations between topics, the agent tries to select the topic that maximises the agent and user's combined engagement. The model offers engagement driven dialogue management on the topic level.

Introduction

Conversational agents often employ a strict taskoriented dialogue structure in order to achieve the particular task for which they are built. Chat-based systems on the other hand, allow for less rigid interaction but the agent has less control of the topic of the interaction. Some applications however, ask for dialogue that falls in between these categories: Where there is not a clear task to achieve and where the interaction is not completely open either, but where there is freedom of topic choice within a certain domain. We are interested in the latter category, more specifically in interaction that is not task-driven but instead driven by social variables of the interaction. In this work, we present a topic selection model for a conversational agent, driven by the social variable engagement.

By taking into account the agent's perceived (detected) level of user engagement as well as the agent's own preferences and associations in the selection of a topic, we do not consider the dialogue merely from a user-oriented system point of view, but consider the agent as an interaction participant with human-like features that contributes to the interaction from its own point of view. In Section 4 we will detail the exact interpretation of these variables.

We consider engagement as "the value that a participant in an interaction attributes to the goal of being together with the other participant(s) and of continuing the interaction" [START_REF] Poggi | Mind, hands, face and body: a goal and belief view of multimodal communication[END_REF]. In order to favour the user's engagement level previous research manipulated the agent's non-verbal behaviour including gaze [START_REF] Peters | Direction of attention perception for conversation initiation in virtual environments[END_REF], gestures [START_REF] Sidner | An architecture for engagement in collaborative conversations between a robot and humans[END_REF], postures [START_REF] Peters | Direction of attention perception for conversation initiation in virtual environments[END_REF] and facial displays [START_REF] Bohus | Models for multiparty engagement in open-world dialog[END_REF], as well as the agent's verbal behaviour including the form [START_REF] Glas | Politeness versus Perceived Engagement: an Experimental Study[END_REF] and prosody [START_REF] Mary | Enhancing human-computer interaction with embodied conversational agents[END_REF] of its dialogue strategies. As mentioned above, certain interaction types however, also allow for an adaptation regarding the content of the agent's dialogue strategies. In this work we focus on the latter, by proposing a model where the agent initiates discussion topics that are adapted to the user.

In the following section we will first further specify the type of interaction and topic we are looking at. In Section 3 we present related work and in Section 4 we introduce the variables that will be taken into account in the topic selection model. In Section 5 we present the topic selection model itself. In Section 6 we discuss its configurations and in 7 its implementation. Section 8 concludes our findings.

Information-Giving Chat

The work we describe in this paper is conducted in the context of the French project 'Avatar 1:1' that aims at developing a human-sized virtual agent playing the role of a visitor in a museum. The agent's task is to engage human users in one-toone face-to-face interaction about the museum and some of its art objects with the objective to give the visitors information about these subjects. The choice of the exact subject is secondary: what matters is that some amount of cultural information is transferred. We refer to this type of interaction as an information-giving chat (as opposed to information-seeking chat [START_REF] Stede | Information-seeking chat: Dialogues driven by topic-structure[END_REF]). Just as information-seeking chat [START_REF] Stede | Information-seeking chat: Dialogues driven by topic-structure[END_REF], information-giving chat is distinguished by its more exploratory and less task-oriented nature, while still being more structured than general free conversation.

The information-giving chat that is modelled in this particular project is agent-initiated in order to increase the likelihood of understanding the user's contributions. Due to the limitations of our natural language understanding module it is also the agent who introduces (initiates) the topics in the interaction.

The notion of topic in interactions can mean different things [START_REF] Brown | Discourse Analysis[END_REF]. We define topic from a discourse perspective as what is being talked about in a conversation [START_REF] Brown | Discourse Analysis[END_REF]. In the context of the informationgiving chat defined above, each topic refers to the discussion phase of an artwork in the museum (O'Donnell et al., 2001). Each topic is thus associated to a fragment of conversation (similar to Macias-Galinde et al. (2012)) consisting of at least 1 pair of agent-user turns. Subtopics are subfragments of these larger conversation fragments and discuss a particular aspect of the artwork. For example, the artist of the artwork or the historical period during which it was created.

Related Work

Some previously built virtual agent systems give their users the opportunity to directly select or reject the topics of interaction [START_REF] Bickmore | Relational agents improve engagement and learning in science museum visitors[END_REF][START_REF] Kopp | A conversational agent as museum guide-design and evaluation of a real-world application[END_REF], thereby adapting the content of the interaction to the user. However, these systems only offer the user a choice for certain information. They do not present a conversational virtual agent than can select interaction topics itself based on dynamic social variables in the interaction.

In order for the agent to be able to select appropriate interaction topics itself, it needs to dispose of a domain knowledge representation mapping to the possible discussion topics. Several dialogue systems dispose of some kind of representation of domain knowledge, developed for various modules such as natural language understanding [START_REF] Milward | Ontology-based dialogue systems[END_REF], topic tracking [START_REF] Carlson | Generic and domain-specific aspects of the Waxholm NLP and dialog modules[END_REF][START_REF] Jokinen | Constructive Interaction for Talking about Interesting Topics[END_REF], question-answering [START_REF] Agostaro | A conversational agent based on a conceptual interpretation of a data driven semantic space[END_REF], response generation [START_REF] Pilato | A modular architecture for adaptive ChatBots[END_REF], sur-face realization [START_REF] Milward | Ontology-based dialogue systems[END_REF], and the selection or generation of dialogue topics (Chakrabory et al., 2007;[START_REF] Macias-Galindo | Coherent topic transition in a conversational agent[END_REF][START_REF] Stede | Information-seeking chat: Dialogues driven by topic-structure[END_REF]. We are interested in the latter where domain knowledge is organised as in such a way that it represents (potential) interaction topics.

The topic representations can be divided in specific task-oriented models (Chakrabory et al., 2007) and non task-oriented models. As information-giving chat has a less task-oriented structure (Section 2) we focus on the latter category. In this category [START_REF] Macias-Galindo | Coherent topic transition in a conversational agent[END_REF] use a semantic relatedness mechanism to transition between conversational snippets in an agent that engages in chatty dialogue, and [START_REF] Stede | Information-seeking chat: Dialogues driven by topic-structure[END_REF] use an ontology-like topic structure that makes the agent produce coherent topic follow-ups in information-seeking chat. However, these systems do not take into account the user's engagement during the different discussion phases (topics). They are merely oriented towards dialogue coherence and are therefore not sufficient for an optimisation of engagement by topic selection. [START_REF] Song | Topic control in a free conversation system[END_REF] and [START_REF] Adam | Flexible conversation management in an engaging virtual character[END_REF] do take into account the user's interests or engagement level in that they decide when the agent should switch topic. The systems are in charge of the timing of a topic change. The new topics are then respectively extracted from the web or a topic structure. For the selection of the topics themselves the user's engagement or preferences are not taken into account.

By using some concepts of the models described above, we aim at building a topic structure in the agent's mind to retrieve dynamically, during human-agent information-giving chat, engaging interaction topics. Opposite to existing topic selection systems that have focused exclusively on dialogue coherence, our topics will be generated from an agent perspective: The topic structure is representing a part of the agent's knowledge, which is located within the agent's mind, and the agent's objective is to constantly favour engagement. As such the topic selection will include human-like features by taking into account the agent's dynamically updated perception of the user's engagement, the agent's preferences and the agent's associations with respect to the current topic of conversation. In the section below we de-fine these variables.

Variables for Topic Selection

In order to select engaging discussion topics, the agent needs to be able to predict the user's engagement level during the discussion of sofar unaddressed topics (objects). For this we need to know if there are any underlying observable preferences that can help the agent collect indications with regard to its prediction of the user's engagement. We interpret a preference as "a relatively stable evaluative judgement in the sense of liking or disliking a stimulus" [START_REF] Scherer | What are emotions? And how can they be measured?[END_REF]. Since a topic of conversation in our interaction setting corresponds to the discussion of a particular artwork, we verified by means of a perceptive study if there exists a relation between the user's engagement level during the discussion of an artwork with a virtual agent, and the user's preference for the physical artwork that is discussed. Below we shortly describe this study (for details see [START_REF] Glas | User Engagement and Preferences in Information-Given Chat with Virtual Agents[END_REF]).

User Preferences and Engagement:

Perceptive Study

We simulated a small museum in our laboratory by hanging photos of existing artworks on the walls. The artworks were chosen as to vary in style and type of affect they might evoke. When the participant finished observing the artworks in a first room, the visit continued in the next room where the participant talked with Leonard, introduced as a virtual character who also visits the museum. In the interaction Leonard discussed the different artworks from the museum in a random order.

After the interaction we presented the participants a questionnaire in which we asked indirectly for the user's engagement level during the different discussion phases, corresponding to each separate discussion around a museum object. We also asked for the user's preferences of the physical artworks.

Analyses of the data collected from 33 participants (13 female, aged 19-58) regarding the randomly discussed artworks have shown amongst others that the user's preference for a museum object is significantly, positively correlated with the user's engagement (wanting to to be together with Leonard p < 0.001, ⌧ = 0.50; wanting to continue the interaction p < 0.001, ⌧ = 0.52) during the discussion of this object with a virtual agent.

From this finding we can derive that the user's preference for a physical object gives a direct indication of the user's engagement level during the discussion of this object (schematised in Figure 1). This makes that the characteristics (i.e. attributes) of a physical object can help the agent predict the user's future engagement level for the discussion of the object (further discussed in Section 4.3).

The agent can then use its predicted level of user engagement for every object discussion to select an engaging topic of conversation.

Agent Preferences and Engagement

To represent human-like features in an agent that plays a museum visitor, the agent needs to have its own preferences for the artworks as well, as representing agent preferences is fundamental for any agent model [START_REF] Casali | A graded BDI agent model to represent and reason about preferences[END_REF]. Besides, the preference representation of the agent can be used to express (consistent) agent appreciations, which has shown to significantly favour the user's engagement [START_REF] Campano | I like this painting too: When an ECA Shares Appreciations to Engage Users[END_REF]. Following the correlation we found above (Section 4.1, Figure 1) an agent likes to talk most about its preferred topics as those maximise its own engagement. However, the agent we model also wants to engage the user. The agent thus tries to optimise the engagement level of both the user and the agent itself (from here onwards indicated as combined engagement). To achieve this, for each (sub)topic (object and characteristic) that can be addressed the agent calculates an expected (predicted) level of combined engagement and selects the one with the highest score as the next topic of discussion. In this way, the agent selects a new topic of conversation based on a combination of the agent's own preferences for the artworks and its prediction of the user's level of engagement during the discussion of the artworks. Figure 2 shows this relation.

Associations between Topics

A last human-like variable that needs to be represented when the agent selects a topic of conversation in information-giving chat are its own associations between topics. This is needed since events that share meaning or physical similarity become Figure 2: The agent's prediction for the level of combined engagement during the discussion of an object depends on several variables. associated in the mind [START_REF] Dellarosa | The psychological appeal of connectionism[END_REF]. Activation of one unit activates others to which it is linked, the degree of activation depending on the strength of association [START_REF] Dellarosa | The psychological appeal of connectionism[END_REF]. The discussion of one topic can thus be associated with other topics in the agent's mind by means of similarities or shared meanings between the topics. In the context of information-giving chat about museum objects each topic is revolving around an artwork. The topics can thus be associated in the agent's mind by similarities between the physical artworks. For example, an abstract painting by Piet Mondriaan may be associated with other abstract paintings, and/or with other works by Piet Mondriaan. In the topic selection model we will therefore represent the agent's associations by similarity scores between every pair of physical objects underlying two topics.

The associations (based on object similarities) allow the agent to make predictions about the user's engagement during sofar unaddressed topics: When the user has a certain engagement level during the discussion of the current topic (and thereby a related preference towards the current object under discussion (Section 4.1)), similar conversation topics are expected to have similar levels of user preference and are thus expected to lead to similar levels of user engagement (Figure 1). The topic selection model described in the following Section ensures that when the agent's predicted user engagement level for an associated topic is high enough (in combination with the agent's own preferences) it is a potential new topic of conversation, triggered by the agent's associations.

Topic Selection Model

In the spirit of [START_REF] Stede | Information-seeking chat: Dialogues driven by topic-structure[END_REF] we define an ontology-like model of domain knowl-edge holding the conceptual knowledge and dialogue history. The model is part of the agent's knowledge and dynamically enriched with information representing the variables described above (Section 4).

The topics all consist of artwork discussions and are therefore not hierarchically ordered but represented in a non-directed graph {Obj, Sim} (e.g. Figure 3) where each node represents an object among N objects: {Obj i , i 2 [1 N ]}. Each object node contains the object's name (corresponding to a topic) and its characteristics (attributes) that map to the topic's subtopics (see Section 2):

{Char n (Obj i ), n 2 [1 C], i 2 [1 N ]},
where C is the number of characteristics for any object Obj i . All the topics are connected to each other by similarity scores: {Sim(Obj i , Obj j ), i, j 2 [1 N, i 6 = j]} (ranging from 0 to 1), which are responsible for the possible associations of the agent. Likewise, all the subtopics (characteristics of the objects) are connected to each other: {Sim(Char n (Obj i , Obj j ), i, j 2 [1 N, i 6 = j]}. For every object and characteristic the agent has its own preferences:

{P ref a (Obj i ), P ref a (Char n (Obj i )
), a = agent}, where 0 corresponds to no liking and 1 to a maximum liking, following the definition in Section 4. The agent also has for every object and characteristic a continuously updated predicted level of the user's engagement during the discussion of these objects and characteristics at time t + 1: {Eng ⇤ u (t + 1, Obj i ), Eng ⇤ u (t + 1, Char n (Obj i )), u = user}, where 0 refers to the minimum level of engagement to continue an interaction and 1 refers to the maximum level of engagement.

The latter two variables lead to a continuously updated predicted level of combined (user and agent) engagement by the agent for each object and characteristic for time t + 1: {Eng ⇤ u+a (t + 1, Obj i ), Eng ⇤ u+a (Char n (t + 1, Obj i )}, ranging from 0 to 1. See Figure 3 for a graphical representation of the topic structure that incorporates all the variables of the (sub)topics.

For 8Obj i , i 2 [1 N ] the agent's predicted level of combined engagement at time t + 1 (described in Section 4.1) during the discussion of any Obj i is:

Eng ⇤ a+u (t + 1, Obj i ) = w(t) • P ref a (Obj i )+ (1 w(t)) • Eng ⇤ u (t + 1, Obj i ) (1)
n (Obj i ))) is: Eng ⇤ u (t + 1, Obj i ) = Eng obs u (t, Obj j ) • Sim(Obj j , Obj i )+ Eng ⇤ u (t, Obj i ) • (1 Sim(Obj j , Obj i )) (2)
Where Obj i 6 = Obj j and Eng obs u (t, Obj j ) is the agent's observed level of user engagement during the discussion of Obj j at time t.

Initial State

The initial state of the topic structure used for the agent's topic selection contains all the objects and characteristics that are known to the agent. For these entities dialogue fragments have been created. For 8Obj i , i 2 [1 N ] and 8Char n (Obj i ),

n 2 [1 C], i 2 [1 N
] the agent's preferences and similarity scores can be initialised at any value between 0 and 1. In case we want agent associations that correspond to observable objective similarities between objects, theoretically defined similarity measures (e.g. Mazuel and Saboutret, 2008) can be used. In the latter case the similarity score between objects can be derived directly from the similarity scores of their characteristics. We further initialise for 8Obj

i , i 2 [1 N ] : Eng ⇤ u (t 0 + 1, Obj i ) = P ref a (Obj i ) and w(t 0 ) = 1 (3)
The same holds 8Char

n (Obj i ), n 2 [1 C], i 2 [1 N ] (replacing Obj i by Char n (Obj i ))
). This makes that for time t 0 + 1 the predicted user engagement of every object and characteristic equal the agent's preferences. However, this assumption is only used as a starting point for future predictions of the user's engagement that will be based on observed user behaviour (Equation 2). At the start of the interaction (t 0 ), the agent only takes into account its own preferences, indicated by w(t 0 ) = 1. The first topic the agent introduces in the interaction is the one for which it predicts the highest level of combined engagement at time t 0 + 1:

max{Eng ⇤ a+u (t 0 + 1, Obj 1 n )} (4)
The agent introduces one by one the subtopics of this first topic for which:

{Eng ⇤ a+u (t 0 + 1, Char n (Obj i ))} > e (5)
Where e is a threshold for the minimum level of predicted mutual engagement level that the agent finds acceptable for the interaction. For example the agent can decide to only talk about the subtopics that are predicted to lead to half the maximum level of engagement, setting e to 0.5.

Updating

A new topic is selected when either: 1) The current topic is finished, meaning that the conversational fragment has been uttered completely. Or 2) the detected level of user engagement during an interval I within the discussion phase of an object is below a threshold z. The description of the user engagement detection method itself lies outside the scope of this paper. The required length of I and level of z, which determine when the user's engagement level (detected by the agent) should lead to a topic switch, will be studied in future work.

At any time t, just before selecting a new topic of interaction the agent first updates the weights in the topic structure with information that is gathered during the previous discussion phases. In the rest of this section we describe how.

For 8Obj i , i 2 [1 N ] that are part of the dialogue history (already discussed topics) we set:

Eng ⇤ u (t + 1, (Obj i )) = 0 and w(t) = 0 (6) Similarly for 8Char n (Obj i ), n 2 [1 C], i 2 [1 N ]
that are part of the dialogue history. This implies that the agent makes the assumption that once a topic has been addressed the user does not want to address it again. The agent values this over its own preferences (w(t) = 0). This simplification makes that the system shall not discuss a topic twice.

8Obj i , i 2 [1 N ] and 8Char n (Obj i ), n 2 [1 C], i 2 [1 N ]
that are not in the dialogue history the agent's prediction for the user's engagement at time t + 1: Eng ⇤ u (t + 1, Obj i ), as well as the agent's prediction for the agent and user's combined engagement level at time t + 1: Eng ⇤ a+u (t + 1, Obj i ) are updated by Equation 1 and Equation 2. This is done by entering the agent's detected (observed) overall level of user engagement during the discussion phases of the lastly discussed object and each of its characteristics (at time t): Eng obs u (t, Obj j ) and Eng obs u (Char k (t, Obj j )). This update makes sure that the agent's observed user engagement level influences the predicted (user and combined) engagement levels for the objects and characteristics that the agent associates with the previously discussed (sub)topics. As mentioned before, the detection method of the user's engagement level lies outside the scope of this paper.

In circumstances where a detection of the user's engagement is not possible Equation 1 and Equation 2 can be updated by entering the user's explicitly uttered preferences for the lastly discussed object and characteristics at the place of respectively Eng obs u (t, Obj j ) and Eng obs u (Char k (t, Obj j )). This follows from the finding that a user's preference is directly related to the user's engagement (Section 4.1).

Topic Selection

Whenever a new topic needs to be introduced (see previous section) it is selected in the same way as the first topic of the interaction:

max{Eng ⇤ a+u (t + 1, Obj 1 n )} (7)
In this way, the agent tries to optimise the combined engagement. The selected subtopics of this topic are, like the first subtopics of the interaction, those where:

{Eng ⇤ a+u (t + 1, Char n (Obj o ))} > e (8)

Example

For the sake of clarity, in this Section we demonstrate the working of the topic selection model with a small example topic structure shown in Figure 4. In this example the agent knows about the 4 topics (objects) that are listed in Table 1.

Figure 4 shows how the variables for each topic can evolve over time t 0 2 during an interaction. Due to space limitations we limit this example to the calculation and selection of topics. The calculation of the weights of the subtopics occurs in exactly the same manner. Only the ultimate selection of subtopics differs slightly as described in Section 5.3. The values of the variables for each topic at time t 0 represent the initial state. Given that at this moment Eng⇤ a+u is the highest for Obj j , this topic is the first to be selected for discussion. When the agent then perceives a minimum level of user engagement during the discussion of this topic, the updated variables (t 1 ) lead to the selection of object Obj l as next object, which has nothing in common with the former object. To show the opposite extreme situation, during the discussion of object Obj l the agent perceives a maximum level of user engagement, leading to the selection of Obj k as next topic, staying close to the characteristics of the former object. Of course Figure 4 is only a limited example and not sufficient to illustrate the full potential of the tradeoff between agent and user oriented variables in the selection of a topic.

Topic Selection Configurations

As described in Section 5.2 the preference, engagement and similarity weights in the topic structure can be initialized at any value ranging from 0 to 1. The freedom of initialising these variables as desired allows for different configurations. The initialisation of the agent's preferences, for instance, can reflect different types of agents (as recommended by [START_REF] Amgoud | Agent dialogues with conflicting preferences[END_REF]) but can also be initialised, for example, at values that are close to the users' preferences in previous interactions. The agent's preferences for the objects can be directly related to the sum of its preferences for the characteristics of the object or not. It is also possible to attribute more importance to the preference for one characteristic than to another. The same holds for the similarity values. For example, to model an agent that is particularly focused on history, the similarity and preference weights of the characteristic "period" may have a larger impact on the similarities and preference of the entire object than the other characteristics of the object. The initialisation of the graph can be simplified with the help of a museum catalogue that already lists the objects and their characteristics.

The topic selection model can be easily ex-tended to other domains that can be structured similarly as museum objects. This means that the agent needs to have its preferences for the different topics and can associate the topics to each other by means of similarity scores. Selecting subtopics as described in Section 5 is only possible if the topics' characteristics (attributes) can be defined.

Implementation and Dialogue Management

For the management of the multimodal behaviour of the agent we use the hierarchical task network Disco for Games [START_REF] Rich | Using collaborative discourse theory to partially automate dialogue tree authoring[END_REF] that calls prescripted FML files, which are files that specify the communicative intent of an agent's behaviour and include the agent's speech [START_REF] Heylen | The next step towards a function markup language[END_REF]. As Disco is developed for task-oriented interactions it offers a fixed, scripted order of task execution where agent contributions and user responses alternate. As mentioned in Section 2, in our project each (sub)topic is associated to a scripted fragment of conversation, consisting of 1 or multiple pairs of agent-user turns. Within such a conversation fragment we can thus directly use the Disco structure. The agent executes the tasks that consist of talking about the object while the local responses of the user drive the dialogue further in the network.

In between (sub)topics it is different. In information-giving-chat we cannot foresee, and thus predefine, the topics and their order of discussion as they are selected by the agent during the interaction. Therefore, at any time a topic switch is required, we overwrite the fixed task structure proposed by Disco by calling from an external module the appropriate tasks that map to the selected (sub)topics. The external module is the topic selection module of the agent. In this way we continuously paste in real time dialogue parts to the ongoing conversation. This procedure makes that local dialogue management is controlled by Disco and topic management is controlled by the external topic selection module, thereby adding flexibility to the existing task-oriented system, resulting in a more adaptive and dynamic dialogue. The agent's topic selection module could be connected to any other task and/or dialogue system as well.

Conclusion and Future Work

In this work we have proposed an engagement driven topic selection model for an informationgiving agent. The model avoids the need for any pre-entered information of the user. Instead, it dynamically adapts the interaction by taking into account the agent's dynamically updated perception of the user's level of engagement, the agent's own preferences and its associations. In this way, the interaction can be adapted to any user. The model's configurations also allow for different types of agents. By connecting the topic selection model to existing task-oriented systems we proposed a way to construct a dynamic interaction where the agent continuously pastes in real time dialogue parts ((sub)topics) to the ongoing conversation.

In the future we would like to perform a perceptive study to evaluate the topic selection model in human-agent interaction. However, for this we first need to plan some additional research.

First, we will study the different ways of switching topic on a dialogue generation level. Even when two consecutive topics have no characteristics in common, the agent needs to present the new topic in a natural way in the conversation without loosing the dialogue coherence [START_REF] Stephen | Pragmatics[END_REF]. Strategies that we will consider to achieve this include transition utterances by the agent that make the agent's associations explicit, transition utterances that recommend interesting (e.g. similar/opposite) artworks to the user, and transition utterances that refer to the artworks' locations within the museum.

Further, before evaluating the topic selection module in interaction with users, we will also have a closer look at the timing of topic transitions. We noted that a topic switch is needed, amongst others, when the current topic leads to a very low user engagement during a certain time interval. We will need to determine the exact interval of the engagement detection that is required and thereby determine the timing of a possible topic transition.

Possible extensions to the topic selection model we would like to explore in the future include the option of coming back to previously addressed topics, considering agent preferences that may change during the interaction and dealing with similar information-giving conversational fragments for different topics.

Figure 1 :

 1 Figure 1: A human's preference and engagement.

Figure 3 :

 3 Figure 3: The graph representing an example of a topic structure in the agent's mind at a time t. Each circle represents a topic (object) where Obj j is the current object under discussion.

Figure 4 :

 4 Figure 4: Example of the evolution of the weights in the topic structure over time t 0 2 . In this example, at each t, w = 0.5.

Acknowledgments

We would like to thank Charles Rich for his help with Disco. This research is partially funded by the French national project Avatar 1:1, ANR MOCA, and the Labex SMART (ANR-11-LABX-65) supported by French state funds managed by the ANR, within the Investissements d'Avenir program under reference ANR-11-IDEX-0004-02.


Nadine Glas
email: glas@telecom-paristech.fr

Catherine Pelachaud
email: pelachaud@telecom-paristech.fr

Topic Transition Strategies for an Information-Giving Agent

We have explored how a conversational agent can introduce a selected topic in an ongoing non-task oriented interaction with a user, where the selected topic has little to do with the current topic. Based on the reasoning process of the agent we have constructed a set of transition strategies to introduce the new topic. We tested the effects of each of these strategies on the perception of the dialogue and the agent.

Introduction

The choice of the dialogue topics that an agent initiates in non-task oriented human-agent interaction is important for several aspects of the interaction such as the coherence of the interaction [START_REF] Macias-Galindo | Coherent topic transition in a conversational agent[END_REF] and the user's engagement (Glas and Pelachaud, 2015). Multiple efforts are oriented towards the selection of the appropriate topic at a specific point in the interaction. However, how the selected topic can or should be introduced by the agent has not been given much consideration in non-task oriented dialogue.

In this work we will explore the latter aspect by looking at utterances that may be used to initiate a transition from one topic to another. We shall call these utterances transition strategies. By comparing a selection of transition strategies we try to answer two questions: 1) What strategies have the potential of keeping/making the dialogue coherent? And 2) what effect do the use of the different transition strategies have on the perception of the conversational agent? The answers to these questions will serve to automatically generate agent strategies to connect one topic to another in non-task oriented dialogue.

Domain

This research is performed for the French project 'Avatar 1:1' that aims at developing a human-sized virtual agent in a museum. The goal of the agent is to engage human visitors in interaction about the artworks of the museum. In this informationgiving chat (Glas and Pelachaud, 2015) each artwork that is discussed is defined as a topic of the interaction. The discussion of an artwork's characteristic corresponds to a subtopic (Glas et al., 2015).

Previously, we found out that the topic of the interaction has an important influence on the user's level of engagement (Glas and Pelachaud, 2015). We had human users talk with a virtual agent that addressed several topics, correponding to different artworks. The users indicated that they were more engaged when the agent talked about artworks for which the users have a stronger preference (defined here as degree of liking) than when the agent talked about less preferred topics (Glas and Pelachaud, 2015). We are therefore working on an engagement driven topic manager that dynamically selects topics for the ongoing interaction taking into account the user's preferences (Glas et al., 2015). In the present work we are interested in agent strategies that may be used to connect the newly selected topic to the current topic of interaction. This is necessary as the topics are primarily selected according to their potential of engaging the user instead of their coherence with respect to the previous topic. Where other dialogue systems look at what topic is coherent at a specific point in the interaction (e.g. Macial-Galindo et al., 2012;[START_REF] Breuing | Let's talk topically with artificial agents! providing agents with humanlike topic awareness in everyday dialog situations[END_REF][START_REF] Wong | Flexible conversation management using a bdi agent approach[END_REF], we are looking at possible strategies to introduce a topic coherently.

Related Work

Transition Strategies in Theory

Literature about transition strategies outside taskoriented applications can be found in the domains of conversational analysis and social sci-ences, where they are studied from an observational (detection) point of view. [START_REF] Downing | Talking topically[END_REF] distinguishes two forms of introducing a topic: by means of an informative statement, and by asking a question. By informing the speaker assigns him/herself the role of topic supplier, whereas by questioning or eliciting a topic this role is offered to an interlocutor in the discourse.

Similarly, [START_REF] Button | Topic nomination and topic pursuit[END_REF] define two global ways of introducing a topic that is not related to the prior topic in a conversation: by a topic initial elicitor that is used to elicit a candidate topic from the next speaker while being mute with respect to what that topic may be, and by topic nominations that are oriented to particular newsworthy items. Two sequence types that may be used for topic nomination are itemised news enquires and news announcements. An itemised news inquiry is oriented to a recipient's newsworthy item where a news announcement is oriented to a speaker's newsworthy item.

Maynard and Zimmerman (1984) identified four topic initiation strategies in dyadic humanhuman conversations. For acquainted parties: displaying prior experience and using setting talk, and for unacquainted parties: categorisation question-answer pairs (e.g. year in school, academic major, etc.) and question-answer pairs involving activities that are related to the categories. [START_REF] Hobbs | Topic drift[END_REF] focuses on three coherence relations that he claims are responsible for most of the so-called topic drift in dialogue: parallelism, explanation and metatalk. Parallelism between two segments occur when the two segments assert propositions from which we can infer that identical properties hold of similar entities, or that similar properties hold for identical entities. An explanation occurs when one segment functions as the explanation of a previous segment and metatalk asserts a relation between some segment and the goals of the conversation.

Transition Strategies in Dialogue Systems

To our knowledge, existing dialogue systems that explicitly consider different strategies to introduce a particular topic have been developed exclusively for task oriented interaction, in particular in the form of task interruption strategies. In this context [START_REF] Mcfarlane | Comparison of four primary methods for coordinating the interruption of people in human-computer interaction[END_REF] defines four primary methods: immediate, negotiated, mediated, and scheduled interruption. [START_REF] Yang | Switching to real-time tasks in multi-tasking dialogue[END_REF] found out that dialogue partners usually use discourse markers and prosody cues to signal task switching. Guided by these works [START_REF] Heinroth | Topic switching strategies for spoken dialogue systems[END_REF] looked at 4 different task switching strategies: unassisted immediate topic shift, discourse markers combined with prosody cues, and two full sentence initialising topic shifts to produce a more natural dialogue flow and to increase the timespan the user has for task switching: explanation and negotiation strategies. The explanation strategy explains what task is about to be started and the negotiation strategy asks for permission to switch a task. They evaluated the use of these four strategies on several dimensions and found that the explanation strategy showed high scores regarding efficiency and userfriendless and supports the user to memorise the tasks. Other strategies showed advantages such as being less irritating.

Guidelines for Topic Transitions

The above mentioned research demonstrates that there does not exist one overall taxonomy of transition strategies that can be used as a recipe for transition strategy generation in non-task oriented dialogue. This lack shows the need of our own research towards transition strategies and makes us fall back to the following generally accepted ideas about topic switching: According to Clark (1996) a topic can be described as a joint project as it is jointly established during ongoing conversations. [START_REF] Svennevig | Getting acquainted in conversation: a study of initial interactions[END_REF] adds that every spoken contribution may raise new potential topics whose actual realisation depends on the co-participant's acceptance by picking up one of these topics within his or her reply. To conclude, Sacks (1971, April 5 in: Levinson, 1983:313) made an overall remark that what seems to be preferred for a topic shift is that if A has been talking about X, B should find a way to talk about Z (if Z is the subject he wants to introduce) such that X and Z can be found to be natural fellow members of some category Y. In the current work we try to collect more precise indications about how to generate transition strategies in non-task oriented dialogue. This painting was made around 1865. Period User:

Yes, I've read so too. Table 1: An example of a dialogue fragment preceding a topic switch initiated by a transition strategy.

In the experiment this dialogue fragment (translated) serves as the context of scenario 1 (Section 4.3).

the perception of the dialogue and the agent. In the subsections below we respectively discuss the steps to achieve this: the specification of the context of the transition strategies (Section 4.1), the design of the transition strategies themselves (Section 4.2), the setup of the experiment to test the set of strategies (Section 4.3), and the questionnaire that will be used for this (Section 4.4).

Context of the Transition Strategies

The strategies that have been mentioned in previous work vary with respect to the context. Some strategies work for topics that are interesting for the listener and others for those that are interesting for the speaker [START_REF] Button | Topic nomination and topic pursuit[END_REF]. Some strategies are used by acquainted parties and others by unacquainted parties [START_REF] Douglas | Topical talk, ritual and the social organization of relationships[END_REF]. Explanation strategies in the sense of [START_REF] Hobbs | Topic drift[END_REF], as well as metatalk only work for a specific set of topics. These constraints imply that the strategies that can be used to introduce a topic in a conversation depend on the relation between the current topic of the dialogue and the new topic that is to be introduced. The first step in generating transition strategies is thus to define this relation. In the context of project Avatar 1:1 (Section 2) we are looking at strategies that an agent can employ in interaction with an unacquainted user to make the transition between two discussion phases about two different artworks. In the current work we will focus on what seems the most extreme case, namely the transition between discussion phases of two very different artworks: Artworks that have nothing in common except from the fact that they are both artworks in the same museum. In this way we test if the agent's topic manager can indeed be allowed the flexibility to select any given artwork of the museum as next topic of the discussion. Such flexibility helps finding (initiating) the topic that engages the user most (Glas et al., 2015).

To be more precise, in Table 1 we give an example of a dialogue fragment that proceeds the moment at which the new topic, corresponding to a very different artwork than the one discussed, is to be introduced. As the timing of introducing a new topic may have an influence on the perception of the topic switch [START_REF] Herbert | Using language[END_REF] we limit this research to a topic switch that occurs after the conversation has addressed respectively the artist and the period of the former discussed artwork.

Design of Potential Transition Strategies

Due to the nature of the context we are dealing with, the potential transition strategies to introduce a discussion phase of another artwork are limited to the following categories from the literature: explanations in the sense of [START_REF] Heinroth | Topic switching strategies for spoken dialogue systems[END_REF], informative statements [START_REF] Downing | Talking topically[END_REF], itemised news enquires and news announcements [START_REF] Button | Topic nomination and topic pursuit[END_REF], categorisation question-answer pairs and question-answer pairs involving activities [START_REF] Douglas | Topical talk, ritual and the social organization of relationships[END_REF], and parallelism [START_REF] Hobbs | Topic drift[END_REF]. It is however not prescribed how we could generate formulations for each of these detection-based categories for the context we are looking at. We thus base the manual creation of a set of potential transition strategies that belong to one or multiple of these categories, on the general guideline by Sacks (1971, Section 3.3).

According to Sacks (1971) we need to find a way to let the former (current) and the next (selected) topic be members of some category Y. We try to do this by (indirectly) referring to an element that is used in the agent's reasoning process to talk about the next topic. The agent disposes of a knowledge base that holds information about certain artworks from the museum. From this set of artworks it selects dynamically a new topic of discussion with the goal of maximising the user's engagement level, taking into account the characteristics of the artworks (e.g. period, artist), the

Nr. Strategy

Element in Topic Manager Orientation 1. P ol(P refA(i)) == P ol(P refA(j)) Preferences Agent (i, j) Agent E.g. I also like the Balloon Dog by Jeff Koons 2.

(P refA(j) > P refA(i)) Preferences Agent (i, j) Agent E.g. Personally, I prefer the Balloon Dog by Jeff Koons 3.

AssociationA(i, j) Associations Agent (i, j) Agent E.g. This work reminds me of the Balloon Dog by Jeff Koons 4.

(P ol(P refU(i)) == +) ! (P ol(P refU(j)) == +) Preferences User (i, j) User E.g. If you like this work, maybe you also like the Balloon Dog by Jeff Koons 5.

(P refU(j) > P refA(i))? Preferences User (i, j) User E.g. Maybe you prefer the Balloon Dog by Jeff Koons.

6.

ExperienceA(i) + ExperienceA(j) i, j in Knowledge Base Agent E.g. I've also seen the Balloon Dog by Jeff Koons 7.

ExperienceU (i) + ExperienceU (j)? i, j in Knowledge Base User E.g. Have you also seen the Balloon Dog by Jeff Koons? 8. 9 (j) ^(j 6 = i) i, j in Knowledge Base Object E.g. Another artwork is the Balloon Dog by Jeff Koons 9. 9 (j) ^(Artist(j) 6 = Artist(i))

Characteristics(i, j) in Object E.g. An artwork from another artist is the Balloon Dog by Jeff Koons Knowledge Base 10. 9 (j) ^(P eriod(j) 6 = P eriod(i))

Characteristics(i, j) in Object E.g. An artwork from another period is the Balloon Dog by Jeff Koons Knowledge Base

Table 2: Potential transition strategies to connect the discussion phases of two very different artworks (translated). i is the current topic of the interaction and j is the one to be introduced. A = Agent, U = User, P ol = Polarity, P ref = Preference.

preferences of the user and the agent for an artwork (degree of liking), and the agent's associations (Glas et al., 2015). The set of potential transition strategies that we created by referring to these elements is listed in Table 2. For each of the strategies we formulated an agent utterance to realise the strategy. Strategies 9 and 10 that insist on the (in this case contrasting) characteristics of the artworks are added as a reference to the strategies that we would use for the transition between artworks that have characteristics in common (the category Y).

Experimental Setup

Inspired by the existing literature we have created a set of potential transition strategies for the context we are looking at. In order to verify if each of these strategies is suitable to be generated by the agent to switch the topic in the information-giving chat with the user we perform an empirical study. By means of an online questionnaire we test the effect that the different transition strategies have on the perception of the dialogue and the agent.

To this end we present each participant with 2 different dialogue fragments (i.e. contexts) consisting of agent utterances and simulated user in-puts (as e.g. [START_REF] Macias-Galindo | Coherent topic transition in a conversational agent[END_REF]. Each scenario is followed by 3 randomly assigned transition strategies, displayed next to each other. We do not show the utterances that may follow the transition strategies. In this way we do not show an acceptance or rejection of the topic by the user [START_REF] Herbert | Using language[END_REF][START_REF] Svennevig | Getting acquainted in conversation: a study of initial interactions[END_REF]. Directly after each of the 3 transition strategies we ask the participants to answer several questions (Section 4.4). Appendix A shows a fragment of the website for this experiment. We use a written setup to allow the participants to consider multiple strategies at the same time in the same context, enabling crosscomparison and rereading as much as desired. Besides, in this way the judgements are not disturbed by unnatural text-to-speech realisations.

As mentioned before, the dialogue fragment that represent the former topic in the context and the topic that is addressed in the transition strategies (next topic) are about very different artworks. We test 2 topic pairs for each participant (i.e. 2 different scenarios) to anticipate possible effects that are due to individual characteristics of a particular context. Scenario 1 consists of the discussion of a painting by Monet (shown in table 1) followed by transition strategies introducing a statue by Jeff Koons (listed in Table 2). Scenario 2 consists of the discussion of a painting by Mondrian followed by transition strategies introducing David, the statue by Michelangelo. The alternation of agent-user utterances, the number of utterances and the order of the subtopics are the same in both context fragments. The order in which the scenarios are presented to the participants is random. Pictures of the artworks next to the questionnaire make sure that all the participants know what the artworks look like (Appendix A).

Questionnaire

For each of the 3 selected transition strategies we ask questions on a scale from 1-9 (shown in Appendix A) (following [START_REF] Bickmore | Social dialongue with embodied conversational agents[END_REF]. The first 3 questions relate to the perception of the dialogue and serve to answer the first question we try to answer (Section 1): What strategies have the potential of keeping/making the dialogue coherent? We ask respectively if the participant finds the dialogue natural (Nakano and Ishii, 2010; [START_REF] Bickmore | Social dialongue with embodied conversational agents[END_REF], coherent [START_REF] Macias-Galindo | Coherent topic transition in a conversational agent[END_REF], and smooth [START_REF] Higashinaka | Effects of self-disclosure and empathy in human-computer dialogue[END_REF][START_REF] Yukiko | Estimating user's engagement from eye-gaze behaviors in human-agent conversations[END_REF].

The following 5 questions serve to answer our second question (Section 1): What effect do the use of the different transition strategies have on the perception of the conversational agent? We ask respectively to what extent the participants find the agent friendly, warm, fun (in French "stimulant"), competent and informed (in French "cultivé) [START_REF] Bickmore | Social dialongue with embodied conversational agents[END_REF]. These measures are related to 2 important social aspects, warmth and competence [START_REF] Susan T Fiske | Universal dimensions of social cognition: Warmth and competence[END_REF].

Results

83 subjects filled out the questionnaire: 56 female, all native speakers of French, aged 19-69. In the subsections below we show the results of the experiment specified for the two issues we are looking at: the perception of the dialogue and the perception of the agent.

Dialogue Perception

For each strategy, the perception of the dialogue has been questioned for the two scenarios and on three dimensions: naturalness, coherence, and smoothness. For each of these dimensions the results show no significant difference between the two scenarios (Kruskal-Wallis). This means that we can take the data for both scenarios together, as shown in Figures 1, 2, and3.

For all three dimensions the scores differ significantly among the strategies (Kruskal-Wallis p < 0.01). Regarding the level of naturalness and smoothness, Kruskal-Wallis multiple comparisons show that the significant differences are due to the strategies 9 and 10 that score significantly lower than some others, indicated by the horizontal brackets in the graphs. Regarding the coherence of the dialogue, strategy number 10 leads to a significantly lower level than other strategies. Only strategies 1 to 7 show a higher mean than the average level (4.5 on a scale of 9) on the dimensions of naturalness and smoothness. With respect to the level of coherence, except from strategies the 8, 9 and 10, strategy 3 also scores lower than average (mean).

As mentioned in Section 4.2 the strategies are either oriented towards the agent, the user, or the (characteristics) of the object (artwork). The strategies from the latter group lead to significantly lower levels of naturalness, coherence and smoothness in comparison to the strategies with another orientation (both scenarios, Kruskal-Wallis p < 0.01). There is no significant difference in the scoring of the strategies that are agent oriented versus the ones that are user oriented with respect to the perception of the dialogue.

Agent Perception

Questions 4 to 8 are about the way the participants of the experiment perceive the social competence [START_REF] Susan T Fiske | Universal dimensions of social cognition: Warmth and competence[END_REF] of an agent that would use the transition strategies in the context in which they are presented. The results show that between the two scenarios, the participants find the agent not significantly different with respect to its level of friendliness and knowledge ("informed") (Kruskal-Wallis). For these dimensions we can thus analyse the data for both scenarios together. Figure 4 and 5 specify the distributions of these dimensions for every strategy. The level of friendliness differs significantly among the strategies (Kruskal-Wallis p < 0.01), which is due to strategies 8, 9, and 10 (Kruskal-Wallis multiple comparisons). However, only strategy 10 scores below average for the level of friendliness (mean < 4.5). For all strategies the agent is not perceived significantly different with respect to its knowledge ("informed") and all of the strategies score above average on this dimension (mean < 4.5).

In contrast to the agent's level of friendliness and knowledge ("informed"), for the dimensions of warmth, fun and competence, some strategies are significantly differently judged among both scenarios (Kruskal-Wallis p < 0.05). both scenarios. On the dimension of warmth, strategy number 8 scores significantly higher in the second scenario (Monet-Koons) than in the first (Mondian-Michelangeloo). Together with strategy 6, strategy 8 also scores higher in the second scenario with respect to the level of fun that the participants perceived in the agent. Further, in the second scenario strategies 4 and 6 score higher on the dimension of competence than in the first scenario.

With respect to the agent's perceived level of warmth as well as fun, in scenario 1, strategies 8, 9 and 10 score significantly lower than other strategies (Kruskal-Wallis p < 0.01). In this scenario strategies 6, 8 and 10 also score below average (mean < 4.5). For scenario 2 strategy 10 scores significantly lower than other strategies (Kruskal-Wallis p < 0.01) and falls below average.

Scenario 1 shows significant differences between the scorings of the agent's perceived level of competence (Kruskal-Wallis p < 0.01). Multiple comparisons (Kruskal-Wallis) do not indicate a specific pair of strategies that is responsible for this difference. Strategy 3 is the only strategy that scores below average (mean < 4.5). In scenario 2 the strategies show no significant differences or scorings below average.

Comparing the strategies that are oriented towards the agent with those that oriented towards the user (Table 2) does not lead to a significant difference with respect to the perception of the agent (both scenarios, Kruskal-Wallis). The strategies that are not oriented towards the agent or user, but refer to the (characteristics) of the object (artwork) lead to significantly lower levels of friendliness, warmth and fun in comparison with the strategies that are oriented towards the interaction participants (both scenarios, Kruskal-Wallis p < 0.01).

Within the group of strategies that are agent or user oriented, we can make another grouping according to the element of the agent's reasoning process that is referred to: preferences (1,2,4,5), associations (3) and the presence of an artwork in the agent's knowledge base (6,7). A comparison between these groups leads to one significant re- sult: in scenario 1, strategies that use preferences score significantly higher on competence than the strategies from the other groups (Kruskal-Wallis p < 0.01, Kruskal-Wallis multiple comparisons).

Discussion

The results show that the transition strategies that insist on contrasting characteristics of the artworks such as a different artist (strategy 9) or period (strategy 10) lead to scores below average (4.5 on a scale of 9) with respect to the level of naturalness, coherence and smoothness. On the level of naturalness and smoothness the difference with the other strategies is significant. This demonstrates that even when the artist and period of the former artwork have been discussed just before the transition strategies, making transition strategies that are based on (referring back to) the earlier discussed characteristics (subtopics), does not guarantee a natural, coherent and smooth dialogue.

The fact that strategy 8, that presents another artwork as just being another artwork, scores below average on naturalness and coherence, shows that "being an artwork" is not a category that can sufficiently bind both topics ("category Y" by Sacks, 1971[START_REF] Stephen C Levinson | Pragmatics (Cambridge textbooks in linguistics[END_REF]. This can have several reasons: The transition strategy may not succeed in presenting the former and latter artwork in being natural fellow members of some category Y, in this case being an artwork. Category Y may need to be a more restrictive (distinctive) category than one to which all topics belong (all topics are artworks) in order to bind two specific topics. Or, making both topics natural fellow members of some category Y may not be sufficient in general to establish a natural and coherent dialogue.

A reason why strategy 3 that is based on the associations of the agent, scores bad on coherence but well on naturalness and smoothness may be due to the fact that the participants can find the association itself incoherent. Due to the contrasting characteristics of the artworks the participants may find it incoherent that the first artwork reminds the agent of the second. However, given that the strategy is considered natural and smooth implies that it might be a suitable strategy to connect the discussions of two similar artworks.

The same explanation can be given for the low scoring of this strategy (3) with respect to the perception of the agent's level of competence (scenario 1). When the agent associates two artworks that do not seem alike the agent is perceived less competent than average.

The strategies that lead to low scores on naturalness, coherence and smoothness of the dialogue (8, 9 and 10) also score relatively low with respect to the perception of friendliness, fun and warmth of the agent. This gives us reasons to suspect that both aspects are related: when a dialogue is not considered natural, coherent or smooth, the agent is not considered as very friendly, fun and warm.

The participants do not perceive the agent significantly more or less informed when it uses certain transition strategies instead of others. This shows that referring explicitly to the characteristics of the artworks such as its artist (9) or period (10) does not make the agent look more informed than when the strategies refer to more subjective aspects of the agent's reasoning process, such as its preferences or associations.

On the contrary, strategies that refer to the preferences of the interaction participants score significantly higher with respect to the agent's level of competence than the strategies that use other variables from the agent's reasoning process.

With respect to the consequences of the transition strategies on the perception of the dialogue the results have shown no significant difference among both scenarios. The effects on the perception of the dialogue that are discussed in this Section seem thus generalisable for the domain we are looking at (Section 4.1). However, for some transition strategies the perception of the agent is judged significantly differently among the two scenarios. For example, strategy 6, a statement of the fact that the agent has seen some other artwork, has in some contexts a negative influence on the agent's level of fun and competence, where this is not the case in other contexts. In the two scenarios that were used for this experiment the type of information, the utterance types, and the number of utterances are equal. Therefore, further research will be needed to show what exactly the underlying reason is that the same strategies lead, in a different scenario, to a difference in the perception of the agent.

Conclusion

In this work we have looked at how a selected topic of discussion can be introduced by an agent in an ongoing non-task oriented dialogue. In the context we are looking at, each topic consists of the discussion of an artwork from a museum. Inspired by social and conversational analytic literature we first constructed a set of candidate transition strategies. We then checked the consequences of each of these transition strategies on the perception of the dialogue and the agent.

We have found that the strategies that score well on all dimensions and all tested circumstances are those that ask for the experience of the user, and those that refer to the preferences of the interaction participants. Whether the preference is the agent's or the user's, and whether or not the new topic is preferred over the current one, transition strategies that integrate any type of preference maintain the coherence of the dialogue while maintaining/establishing a positive perception of the agent. The fact that certain transition strategies can connect topics about very different artworks while maintaining positive perceptions of the dialogue and the agent, shows that the agent's topic manager can indeed be allowed to select any topic required to engage the user at any moment in the conversation (Glas et al., 2015).

We plan to use the observations we obtained in this study by automatically generating appropriate transition strategies for the conversational agent whenever the topic manager initiates a topic switch. The automatic generation of the transition strategies could be performed by means of templates where the object names and characteristics can be generated from the agent's knowledge base. In the future we would like to explore the effects of the timing of the topic switch on the perception of the topic transition [START_REF] Herbert | Using language[END_REF]. Lastly, we would like to consider the agent's non-verbal behaviour with respect to topic switching. Nonverbal behaviour plays an important role in topic switching [START_REF] Kendon | Some relationships between body motion and speech[END_REF] and in the perception of verbal behaviour in general [START_REF] Sidner | Explorations in engagement for humans and robots[END_REF].

  find out what strategies a conversational agent can use to initiate topic transitions in nontask oriented dialogue we follow Heinroth et al. (2011) (Section 3.2) by testing a set of potential transition strategies with respect to their effects on Speaker Dialogue about "Luncheon on the Grass" by Claude Monet Subtopic [...] Agent: Claude Monet was a French painter. He lived his entire life at Giverny, a beautiful village north of Paris. Artist User: Yes I know. I visited Giverny last year. Agent:

Figure 1 :

 1 Figure 1: Naturalness for each strategy, p < 0.01.

Figure 2 :

 2 Figure 2: Coherence for each strategy, p < 0.01.

Figure 3 :

 3 Figure 3: Smoothness for each strategy, p < 0.01.

  Figure 6, 7 and 8 show the distribution of the results specified for both scenarios. The circled numbers indicate the strategies that are judged differently between

Figure 4 :

 4 Figure 4: Friendliness for each strategy, p < 0.01.

Figure 5 :

 5 Figure 5: Agent being informed for each strategy.

Figure 6 :

 6 Figure 6: Warmth for each strategy, p < 0.01. Between scenarios strategy 8 differs p < 0.05.

Figure 7 :

 7 Figure 7: Fun for each strategy, p < 0.01. Between scenarios strategies 6, p < 0.05, and 8, p < 0.01, differ.

Figure 8 :

 8 Figure 8: Competence for each strategy, p < 0.01 for scenario 1. Between scenarios strategies 4, p < 0.05, and 6, p < 0.01, differ.

Acknowledgements

We would like to thank Sophie Rosset and Andrew Kehler for valuable discussion, and Brice Donval and Caroline Langlet for technical support. We would also like to thank all the participants of the experiment. This research is partially funded by the French project Avatar 1:1, ANR MOCA, and the Labex SMART (ANR-11-LABX-65) supported by French state funds managed by the ANR, within the Investissements d'Avenir program under reference ANR-11-IDEX-0004-02.

Appendix A. Website for the experiment