Jacky Akoka
email: jacky.akoka@lecnam.net

Isabelle Comyn- Wattiau

Stéphane Lamassé
email: stephane.lamasse@univ-paris1.fr

Cédric Du Mouza
email: dumouza@cnam.fr

Modeling Historical Social Networks Databases

Historical social networks are analyzed using prosopographical methods. Prosopography is a branch of historical research that focuses on the identification of social networks that appear in historical sources. It aims to represent and to interpret historical data, sourced from texts. Conceptual modeling imparts the capability to process these large data sets. This paper outlines a conceptual approach to designing a prosopographical database encompassing uncertainty. Our contribution is threefold: i) a generic certaintybased prosopographical conceptual model; ii) two meta-models with a mapping between them; iii) an illustrative example generating a customized prosopographical relational model. Unlike past approaches, our design process helps us to integrate disparate points of view as expressed in the prosopography community. We apply our approach to the prosopographical database Studium Parisiense dedicated to members of Paris schools and university between the twelfth and sixteenth centuries. This instantiation validates the usefulness of our approach.

Introduction

Prosopography is a domain of digital humanities related to the inquiry into the common characteristics of a group of historical actors by means of a collective study of their lives [START_REF] Stone | Prosopography[END_REF]. It relies generally on a database containing information related to persons from a specific milieu defined chronologically and geographically [START_REF] Bulst | Medieval lives and the historian: studies in medieval prosopography[END_REF]. Its purpose is to collect and analyze data describing the individual lives of the historical actors under consideration, targeting mainly their common characteristics. Historians generally study large groups of individuals poorly documented. They fill in manually for each actor a record with all information they have regarding the milestones of his/her life, the places he/she visited, the people he/she met, his/her production, etc, according to a schema they decide for their prosopographical database. The reliability and the quality of the source material (demographic, economic, administrative, religious, family archives, etc.) is crucial. Moreover, historians are confronted with the relative scarcity of source material. Representing the time and the uncertainty dimensions related to people, locations, factoids, and source material constitutes another problem. Prosopography deals with information which is often incomplete, imprecise, and contradictory. Therefore, there is a need to develop data models accommodating all types of uncertainty including the one characterizing the dating phenomena.

There exist several models representing prosopographical data. The most common model is that of the factoid [START_REF] Pasin | Factoid-based prosopography and computer ontologies: towards an integrated approach[END_REF]. Prosopography of Anglo-Saxon England (PASE) is based on a factoid model in which statements about persons, possessions and places are derived from sources [START_REF] Pasin | Factoid-based prosopography and computer ontologies: towards an integrated approach[END_REF]. Another example of project based on the factoid model is the Roman Republic [START_REF] Figueira | Modelling a Prosopography for the Roman Republic[END_REF]. Most existing digital prosopography projects use relational databases. However, to the best of our knowledge, no prosopographical project uses conceptual modeling to derive the associated relational model, which considerably limits the ability of merging or querying different prosopographical databases. The aim of this paper is to present an approach allowing us to build a generic certainty-based prosopographical conceptual model which serves as a basis for the instantiation of contextualized conceptual and relational models of prosopographical databases such as PASE and Studium Parisiense [5].

We begin in Section 2 by identifying structured elements of prosopographical models and databases. We then present and discuss our approach in Section 3. Section 4 is dedicated to the application of the approach to the Studium Parisiense prosopography. We conclude in Section 5 and present future research directions. Our contribution is threefold: i) a generic certainty-based prosopographical conceptual model; ii) two meta-models with a mapping between them; iii) an illustrative example generating a customized prosopographical relational model.

Prosopographical Concepts: A State of the Art

There are many prosopographical databases such as PASE, Studium Parisiense, prosopography of the Byzantine Empire, China Biographical Database Project, The Making of Charlemagne's Europe, and Paradox of Medieval Scotland [START_REF] Bradley | Annotation and Ontology in most Humanities research: accommodating a more informal interpretation context[END_REF]. Prosopography analyzes information on sets of individuals in the context of historical societies. Central to any prosopographical project are the concepts of event, time, and uncertainty.

Modeling life stories of a group of persons can be performed using the event-based approach [START_REF] Westermann | Toward a common event model for multimedia applications[END_REF]. In an event, a person can take different roles. Events are linked to other events, persons, places, time periods, and documents. [START_REF] Shaw | Event representation in temporal and geographic context[END_REF] distinguishes different types of events, supporting both discrete and continuous events, and expressing various temporal aspects of events. Event times are generally specified as date ranges and have time-spans with durations. Most of the standards mentioned by [START_REF] Shaw | Event representation in temporal and geographic context[END_REF] enable the association of events with location terms, including geographical place names. Events play the role of linking persons to places and times. Individual events can be linked to multiple documents and vice-versa. Several ontologies describing events have been proposed [START_REF] Liu | Towards A Spatiotemporal Event-Oriented Ontology[END_REF]. Our work is inspired by the recognized and successfully used in several contexts event model [START_REF] Raimond | The Event Ontology[END_REF] since it focuses on the main concepts of interest in prosopographical projects.

Any historian faces the problem of representing temporal data. Time can be the source of vagueness and/or uncertainty. Temporal database research [START_REF] Gregersen | Temporal Entity-Relationship models-a survey[END_REF] consider two types of data: "instant" and "interval" [START_REF]Geographic information-Temporal schema[END_REF]. Allen [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] proposes a time model based on time intervals. A number of temporal relationship types are based on Allen's temporal logic [START_REF] Grüninger | The Time Ontology of Allen's Interval Algebra[END_REF]. Very few research works offer support for modeling relative times. The GENTECH model [START_REF] Gentech | Genealogical data model: A comprehensive data model for genealogical research and analysis[END_REF] supports the creation of conflicting temporal relationships expressing different points of view. Some databases integrate data temporal aspect by relying on a temporal version of SQL (TSQL2) [START_REF] Snodgrass | The TSQL2 temporal query language[END_REF]. The time model in AROM-ST [START_REF] Moisuc | Spatiotemporal Knowledge Representation in AROM-ST. Innovative Soft[END_REF] offers several time types including instant, interval, multiInstant, and multiInterval types. The importance of time considerations in ontologies was initiated by the semantic web community [START_REF] Bry | Reasoning on the semantic web: beyond ontology languages and reasoners[END_REF]. A variety of approaches have been proposed to represent temporal information in RDF [START_REF] Manola | RDF primer, W3C recommendation[END_REF] and OWL [START_REF] Mcguinness | OWL web ontology language overview[END_REF]. Several approaches have been proposed for time modeling using the ER conceptual model [START_REF] Gregersen | Temporal Entity-Relationship models-a survey[END_REF]. In our approach, we selected the AROM-ST model because of its generality.

Uncertainty is defined as "a general concept that reflects our lack of sureness about something or some-one" [START_REF]Risk Analysis and Uncertainty in Flood Damage Reduction Studies[END_REF]. Uncertainty reflects a lack of confidence in an object, in an event or in a person. A survey about theories and practices in handling uncertainty can be found in [START_REF] Li | Dealing with Uncertainty: A Survey of Theories and Practices[END_REF]. There exist many uncertainty classifications [START_REF] Thunnissen | Uncertainty classification for the design and development of complex systems[END_REF]. In the URREF ontology [START_REF] Costa | Towards Unbiased Evaluation of Uncertainty Reasoning: The URREF Ontology[END_REF], uncertainty encompasses a variety of aspects including ambiguity, incompleteness, vagueness, randomness, and inconsistency. Ambiguity arises when the information lacks complete semantics. Incompleteness reflects a lack of information. Vagueness arises when a situation is characterized by an incomplete knowledge of the facts and events under consideration. Randomness expresses the lack of pattern or predictability in events. Finally, inconsistency arises when two or more information cannot be true at the same time. These uncertainties may be supported by different uncertainty models or theories, such as probability theory, possibility theory, fuzzy sets, etc. [START_REF] Roblot | Cardinality Constraints with Probabilistic Intervals[END_REF]. A review of the literature on fuzzy conceptual modeling and databases is presented in [START_REF] Galindo | Fuzzy Databases: Modeling, Design and Implementation, Idea Group[END_REF][START_REF] Ma | A Literature Overview of Fuzzy Conceptual Data Modeling[END_REF]. In our approach, we use the URREF ontology which seems to be the most appropriate for representing the uncertainty that characterizes prosopographical data.

Concepts such as event, time, and uncertainty are central to our modeling approach described in the next section.

Our Approach

Our methodology consists of three main steps. The first one is dedicated to building a generic certaintybased prosopographical conceptual model. Then we proceed to its customization leading to a specific prosopographical project. Finally, we automatically convert the resulting conceptual model into a prosopographical relational database.

Building a generic prosopographical conceptual model

We first proceeded to requirements gathering which encompasses the following tasks: interviewing historians, browsing through prosopographical databases, analyzing the factoid models, and studying the literature on time and uncertainty modeling. Then, we chose to capitalize on the factoid model by putting emphasis on a limited number of concepts named factoid objects, such as Person, Place, Factoid, and Source. Time is an important dimension too. Moreover, all the information is tainted with uncertainty. A factoid may be considered as an event taken in a broad sense including all the facts that characterize individuals. For example, a publication is also an event. The choice to generalize the event into a factoid enables a compact model. However, it led us to define the factoid with a larger number of dimensions. For instance, the fact that an event impacts an object allows us to cover the publication written by an author, the purchase of a property, the dowry at a wedding, Fig. 1 The generic conceptual prosopographical model etc. Our model also supports a multi-level hierarchy of concepts. For example, Places, Sources, Persons, and Factoids are generalized to one or more levels. The factoids are grouped recursively into types of factoids (FactoidType), like in PASE where the confession is an event of Christian piety, itself a religious act. The resulting generic prosopographical conceptual model is presented below (Fig. 1).

One difficulty of prosopographical research lies in onomastics, i.e. the need to identify the people that may be known by different names, each one associated with an uncertainty degree. People are also generally linked to groups. Our model supports the ambiguity attached to names as well as the concept of groups (GroupP).

Most relationships between concepts are typed. For example, the type of impact between an event and an object allows us to specify that, during a barter event, an object is transferred and an object is granted in exchange. Between factoids, the Linkedto relationship is used to define dependencies between events such as precedes, provokes, and so on. The Role of a Person in a Factoid is an entity since the same person can sometimes play more than one role in the same event.

The representation of time integrates discrete time (Instant), continuous time (Interval), and their composition. It is adapted from the AROM-ST model [START_REF] Moisuc | Spatiotemporal Knowledge Representation in AROM-ST. Innovative Soft[END_REF].

Finally, our generic conceptual model integrates the management of uncertain information in four forms: incomplete data leading to null values, ambiguous information due to linguistic terms (e.g. about, probably, not far from, etc.), vague information (membership degree, importance degree, etc.) [START_REF] Galindo | Representation of fuzzy knowledge in relational databases[END_REF], and inconsistent assertions. In our model, certainty is a representation of the degree of reliability of the information to which it is attached. Generally, it takes its value in the interval [0, 1]. In certain cases, these values are: near, around, close to, in the vicinity of, not far from, a few kilometers from, etc. When it characterizes the timing of an event, certainty can take the values of: around, before, well before, shortly after, and so on. Moreover, Time and Place are connected. For example, Flanders belonged to France at one time but not always. This led us to introduce the ternary relationship IsLocated between Place, Zone, and Time. Similarly, factoid types are linked to the Time entity. We manage the contradictory assertions by associating each source with a confidence degree associated to its reputation.

Customizing the generic prosopographical conceptual model

The customization process to any particular prosopographical database requires the following steps:

Step 1. Model pruning. Each prosopographical project concentrates on some specific features, implying a pruning of all the irrelevant parts of the model. As an example, Studium Parisiense does not consider links between factoids.

Step 2. Model refinement. The objective of this step is to facilitate data updating and to reduce quality issues. Each prosopographical project refers to basic assumptions and authority lists. Based on them, the database designer, with the help of historians, lists the possible values for each meaningful concept, enabling a precise definition of attribute domains. As an example, the Role entity may be characterized by a closed set of values. In PASE, it takes a number of values such as apostate, apostle, disciple, fugitive, etc. Moreover, for each hierarchy, the database designer has to set the number of hierarchy levels, the type of hierarchy (one-to-many or many-to-many), and the list of possible values for each level. As an illustration, PASE project includes a 3-level hierarchy of factoids whose first level contains the five following categories: 1) acts of crime, law-breaking/violence, 2) legal/governmental/administrative acts and legitimate use of violence, 3) life-events/social and economic acts and relations, 4) power-taking and power-leaving, and 5) religious/ecclesiastical acts. Finally, in some cases, the customizing process encompasses the addition of specific attributes to some concepts. As an illustration, ethnicity is an important information in PASE project.

Step 3. Temporal model management. Depending on the timeline of the prosopographical project, we have to associate each Time entity (Instant, Interval, etc.) with a specific grain. In Studium Parisiense, the time grain is the year whereas, in PASE, the dates are subdivisions of centuries (early, middle, and late).

Step 4. Linguistic terms management. Prosopographical databases rely on sources containing natural language descriptions. Thus, in particular for dates and places, there is a need to check a sample of representative sources for extracting fuzzy expressions, such as: around, about, probably, etc. and mapping linguistic terms to an evaluation of their value, i.e., around may take the value less than 20 km.

Step 5. Fuzzy attribute elicitation. For each attribute of the model, we check with historians whether this attribute is fuzzy and, as the case may be, its type of vagueness among the five categories: membership, importance, fulfillment, possibility, uncertainty, as defined by [START_REF] Galindo | Representation of fuzzy knowledge in relational databases[END_REF]. As an example, kinship in Studium Parisiense is sometimes fuzzy.

Step 6. Fuzzy object elicitation. The generic prosopographical model contains only one uncertain entity (Factoid) and many uncertain relationships (Be-longsTo, Participate, etc.). For each certainty found in the generic model, we check whether it should be maintained, and, if so, define its type of vagueness. As an example, in Studium Parisiense, people belong to different groups: student, master, graduate, etc. This information is often uncertain.

At the end of this customization step, the conceptual model is annotated for a specific prosopographical project.

Mapping the customized conceptual model to a relational database

To carry out this step automatically, we adopted a model-driven approach. To this end, we have defined: a) an Extended Entity Relationship (EER) conceptual meta-model incorporating uncertainty, b) a relational meta-model incorporating uncertainty, and c) a set of mapping rules from conceptual to relational metamodels. Due to the presence of vagueness in the resulting conceptual model, standard mapping rules do not apply, requiring the following approach. Fig. 2 The EER meta-model incorporating uncertainty

The EER conceptual meta-model incorporating uncertainty

The EER meta-model encompasses the standard concepts of entity and association (Fig. 2). They form a partition of the set of objects of the conceptual model. They are characterized by attributes. For entities, a subset of these attributes constitutes an identifier (to simplify, we consider here that an entity has only one identifier). Some attributes may be fuzzy, requiring specific relational mappings. We have improved the expressiveness of the model by allowing fuzzy attributes to cover different types of vagueness across different ranges of values. Therefore, in the meta-model, we associate with Attribute values four relationships corresponding to four different modalities: (i) an attribute value can be linked to a linguistic term. For example, 1530 is a value of the Year attribute. This value can be associated with a linguistic term of the temporal type such as "around", which can have a meaning: "in an interval centered on this value" and a degree of inaccuracy: 10%, which makes it possible to calculate the interval around 1530; (ii) an attribute value may be similar to another one. For example, the kinship "elder brother" is similar to the kinship "brother" with a similarity that can be quantified; (iii) an attribute value can be qualified by a trapezoidal function. As an example, "young" is defined over the trapezoid (20, 30, 40, 50) that represents four successive x-axis values such that a medieval clergyman is undoubtedly "young" between 30 and 40 years old, possibly "young" between 20 and 30 or between 40 and 50 years old); (iv) an attribute value is defined with a degree with respect to a type of vagueness (membership, importance, possibility, etc.).

A relational meta-model incorporating uncertainty

Similarly, the relational meta-model contains the standard relational schema concepts: Relation, Column, Columnset (aggregates columns to define candidate keys) (Fig. 3).

Four relation subtypes are added to represent the concepts related to uncertainty: (i) Vagueness type that will become a relational table listing all the types of uncertainty represented in the database; (ii) the Degree table which, in the same way, will contain all the degrees of uncertainty or inaccuracy associated with either the objects (entities or relations) or the attributes of the prosopographical model; (iii) the Linguistic term table which contains the linguistic terms describing the uncertainties (probably, perhaps, not impossible, probably, etc.) or the inaccuracies (close to, around, near, etc.); (iv) the Trapezoid_description table contains all trapezoidal type coordinates to represent possibilistic elements.

Fig. 3 The relational meta-model with uncertainty

A set of mapping rules from conceptual to relational meta-models

Beyond the standard rules mapping the EER model to the relational model by means of meta-models, we defined special rules dedicated to the mapping of uncertain information. In particular, in order to incorpo-rate the vagueness in the relational database, we generate the specific tables containing the corresponding elements. Thus, if a fuzzy attribute is defined, for each of its fuzzy values represented by a trapeze, there will be a row in the table Trapezoid_description. Table 1 summarizes the mapping between the two metamodels at the concept level. For space reasons, we cannot provide the reader with the whole set of rules. In this section we provide a generic prosopographical model and its mapping to a relational meta-model which allows to model any prosopographical databases with uncertainty management. We illustrate in the following how our generic model can be derived to a specific prosopographical project to demonstrate its feasibility and usefulness.

Illustrative example: Application to Studium Parisiense

Our research is part of a project funded by the French National Research Agency and related to several prosopographical contexts. We illustrate our approach on the Studium Parisiense project aiming at creating an online biographical-bibliographic database describing members of Paris' schools and university from the twelfth century until the end of the Middle Age. The project currently totals more than 16,000 records, of which almost 9,000 are already online using an XML format.

Customizing the generic model to the context of Studium

Applying Step 1 of our approach leads to the deletion of (i) the entities Publication, CompositeTime, Multi_Instant, Multi_Interval, (ii) the relationships In, BelongsTo, Comp, Composed_of, LinkedTo, PartOf, Includes, Subset, (iii) some attributes such as value (entity Object), duration (entity Factoid), quantity (relationship Impact), etc. Notice that we also added some attributes, such as language (entity Object) and social class of origin (entity Person).

The application of Step 2 allows us to define all the authority lists. Among them, let's mention: (i) the list of role labels: per se, author, grantee, etc., (ii) the list of factoid types: birth, death, activity, origin, university or studium attended, ecclesiastical position, functions with the pope, etc. We also set the different hierarchy types and levels. As an illustration, a factoid is not defined for Studium by an N-N relationship but by a purely hierarchical set of types with only two levels. For instance, functions with the pope (first level) is part of ecclesiastical position (top level) characterizing the career of Alexander de Kininmund who was Prosecutor of Thomas de Fingask, Bishop of Caithness at the Curia in Avignon in 1348.

Step 3 allows us to define the time unit, here year. Even if years are provided in sources, they are often qualified by a linguistic term describing the uncertainty level.

During Step 4, parsing a significant sample of XML files (in which many fields are expressed in natural language), we collected a consequent list of linguistic terms representing an uncertainty level of the information mentioned (e.g. nothing should allow us to know, probably, it is not impossible that, perhaps, unlikely). We met the team of historians in charge of for Studium Parisiense and asked them to validate this list and to enrich it with a numeric scale.

Step 5 generates the list of fuzzy attributes which is very limited in Studium. Among them, let us mention the kinship attribute characterizing ParentOf links between Persons. The peculiarity of this attribute led us to build a table linking two by two all the possible values of kinship and to characterize the links by a similarity measure. As an example, brother and elder brother are very similar.

Finally, Step 6 required more effort to qualify the uncertainty feature and the vagueness type of each entity and/or relationship. For instance, relationship OccurredAt comes often with linguistic terms listed in Step 4. Regarding the relationship TookPlaceAt, the vagueness type uncertainty applies whereas importance better qualifies the reputation of Source.

For space reasons, we cannot present the final conceptual model. As it can be seen in the different steps, the involvement of historians is crucial to the success of this customization process.

Generating the relational schema

Firing the mapping rules described above, we obtain the following customized relational schema. The following two queries shed the light on the opportunities offered by the resulting Studium database. The first query compares two individual careers as follows: Who studied canon law in Paris at the same time as Petru de Quercu and then got an ecclesiastic position?

This query shows how we succeed in capturing the uncertainty of the different data (factoids, places, times, etc.), and in managing linguistic terms with vagueness interpretation and the onomastics. The corresponding SQL query is:

The evaluation of this query on the Studium dataset returns the following results (extract). The second query looks for more complex career patterns and takes into account sources reputation (evaluated by historians): Who are the Italian living in the fourteenth or fifteenth century who studied a PhD This query illustrates how we take into account the source reputation when evaluating a query related to the hierarchy of locations or of factoid types. The evaluation of this query on the Studium dataset returns the following results (extract). Observe that the different confidence and reputation scores are set by experts who filled in the database. This illustrative example validates the ability of the generic model to be customized to a specific prosopographical project like Studium Parisiense as well as the usefulness of this representation to deal with certainty issues.

Conclusion and future research

This paper proposes a modelling approach to certainty-based prosopographical databases. It consists of three successive steps: building a generic certaintybased prosopographical conceptual model, customizing this generic conceptual model to a specific prosopographical project, and mapping the customized conceptual model to a relational database. Our contribution encompasses a generic conceptual model, two meta-models including uncertainty features, and a set of mapping rules. We illustrate the application of the approach with the Studium Parisiense prosopographical database and we propose two SQL queries demonstrating the ability of the approach to go beyond previous approaches. Observe that our approach is not dedicated to the sole History field but can also be deployed in other contexts using prosopographical approaches like societal studies, biology, tourism, etc. Future research will confront our generic certaintybased conceptual model with more prosopographical projects in order to ensure its completeness. Since prosopography can be seen as a social network accommodating different uncertainty relationships of people, place, events and time periods which can be handled using probabilistic or fuzzy social networking approaches, we also plan to map our generic conceptu-al model to a graph database in order to efficiently perform complex graph queries.

Table 1 .

 1 Mapping the meta-models An example of a rule is described below. It deals with the case where an attribute A linked to O (O may be either an entity or a relationship) contains fuzzy values defined with trapezoid functions.

	Conceptual meta-model	Relational meta-model
	Object	Attribute	Object	Attribute
	Attribute	attribute_id, attribute_name Column	column_id, column_name
	qualifies	degree id, degree value	Degree	degree id, degree value
	measures	degree id, degree value	Degree	degree id, degree value
	Object	object_id, object_name	Relation	relation_id, relation_name
	describes	trapeze1, trapeze2, trapeze3, trapeze4	Trapezoid description	trapez1, trapez2, trapez3, trapez4
	Vagueness type	vagueness type description vagueness type id	Vagueness type	vagueness type description vagueness type id
	Attribute value attribute value id, value	Column value	Column value id, value
	Attribute	ISA between Fuzzy attribute and Attribute	Column	fuzzy Y_N
	similar_to	similarity	similar_to	similarity
		linguistic term id, label, term		linguisTerm id, label, term
	Linguistic term	type, meaning, imprecision	Linguistic term	type, meaning, imprecision
		degree		degree
	Object	object id	Columnset	columnset_id
	involved in	cardinality	Column Relation	column_name relation_name

Acknowledgements

This research has been partly funded by a national French grant (ANR Daphne 17-CE28-0013-01.)

degree in Bologna after studies in Paris, according to sources with a reputation greater than 0.5.


Jules Waldhart

Aurélie Clodic

Rachid Alami

Reasoning on Shared Visual Perspective to Improve Route Directions

We claim that the activity consisting in providing route directions can be best dealt with as a joint task involving the contribution not only of the robot as a direction provider but also of the human as listener. Moreover, we claim that in some cases, both the robot and the human should move to reach a different perspective of the environment which allows the explanations to be more efficient. As a first step toward implementing such a system, we propose the SVP (Shared Visual Perspective) planner which searches for the right placements both for the robot and the human to enable the visual perspective sharing needed for providing route direction and which makes the choice of the best landmark when several are available. The shared perspective is chosen taking into account not only the visibility of the landmarks, but the whole guiding task.

I. INTRODUCTION

When one asks a direction to an employee in charge of providing information to visitors of a public place, said employee will most likely point a direction and give some instructions to reach your destination ("This way, take the first street on your left,..."). In trivial cases, she/he will point directly at the destination ("It is just here"). In some other interesting cases however, the employee may move and take you to a position where she/he can show you some (previously hidden) landmark ("It is just behind this corner"), thus simplifying the directions and easing your task. This is the case for our robot in the example shown in Fig. 1. These scenarios of a robotic guide could be summarized as follows:

• an interactive robot, placed near an information desk in a public space, is available to provide information and route directions • it can move a little (say several meters around its base) in order to place itself and ask its human addressee to move with it in order for both of them to reach a configuration where it can point to one (or several) landmark(s) and utter route direction information • the robot is not intended to accompany the persons to their destination but to help way-finding. This scenario is similar to the one proposed in [START_REF] Kanda | A Communication Robot in a Shopping Mall[END_REF], but with a major difference: the robot is able to compute a placement for both participants, the human and the robot which offers a perspective that is more pertinent to provide route direction anchored on visible landmarks.

We will show the pertinence of choosing and reaching a different shared perspective for the route explanation by *The research leading to these results has received funding from the European Unions H2020 programme under grant agreement No. 688147, MuMMER http://mummer-project.eu/ 1 Authors are with LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France firstname.name at laas.fr (c) Robot asked the human to move a little and also placed itself such as the sign is visible to both and it can point at it. means of a few -yet significant -examples. In those examples, the robot autonomously computed a location, went there with the human and provided route directions supported by deictic gestures. We will present the core decisional component, the Shared Visual Perspective (SVP) Planner, that computes the locations (2D positions of both human and robot) to reach. The SVP Planner has been integrated in a larger system that allows the effective achievement of the full guiding task on a real robot, but this is not in the scope of this paper, neither are the complete task design details; we focus here on the SVP planner and its pertinence.

Our approach differs from previous contributions and systems concerning robot guides. From the first museum guides [START_REF] Burgard | The museum tour-guide robot RHINO[END_REF], [START_REF] Clodic | Rackham: An interactive robot-guide[END_REF], [START_REF] Siegwart | Robox at expo.02: A large-scale installation of personal robots[END_REF] to more recent robot guides in large areas [START_REF] Kümmerle | A navigation system for robots operating in crowded urban environments[END_REF], [START_REF] Bauer | The autonomous city explorer project[END_REF], [START_REF] Triebel | SPENCER: A Socially Aware Service Robot for Passenger Guidance and Help in Busy Airports[END_REF], the focus was more to open the road or accompany a person or a group until they reach a final destination. Here the problem is different, the robot is not authorized to move too far from its base and its role is to provide route information using gesture and speech.

While a number of issues have been studied and proposed to build and evaluate direction-giving robot behaviors, very little has been done when the robot and the human are placed in a way where they cannot see the landmark. Indeed most of the existing work assume that they are already placed in a favorable position and, if the human is not correctly placed, they assume that she/he will adjust.

In this task, not only the robot action needs to be taken into account but also an action to be achieved by the human since they will create a mental model of the route, interpret the information, search for it in the environment, etc... [START_REF] Allen | Principles and practices for communicating route knowledge[END_REF]. This is why, we can consider that it is typically a humanrobot joint task [START_REF] Sebanz | Joint Action: Bodies and Minds Moving Together[END_REF], [START_REF] Lemaignan | Artificial cognition for social human-robot interaction: An implementation[END_REF], [START_REF] Clodic | Key elements for human-robot joint action[END_REF] where the robot needs to have the abilities to estimate the perspective of the human, and to elaborate a shared plan involving the human and the robot that will allow to place both of them in a desired perspective.

We focus here on the selection of a shared visual perspective for providing route directions, but this work is part of an overall project that aims to implement and evaluate a complete system for the guiding task. This involves the development of a number of other components such as a human perception system [START_REF] Duffner | Track creation and deletion framework for long-term online multiface tracking[END_REF], a human-aware reactive motion planner [START_REF] Khambhaita | Viewing Robot Navigation in Human Environment as a Cooperative Activity[END_REF], a Human-Robot joint action supervision [START_REF] Devin | An implemented theory of mind to improve human-robot shared plans execution[END_REF] and the associated dialogue [START_REF] Papaioannou | Hybrid chat and task dialogue for more engaging HRI using reinforcement learning[END_REF].

II. RELATED WORK

We review here some contributions related to the tasks of guiding, providing route directions and pointing. Both human cognition studies and robotic or system implementations are briefly discussed.

Landmarks selection

Landmarks are used to support route description, and it is not enough to use them, one must choose them accordingly [START_REF] Nothegger | Selection of Salient Features for Route Directions[END_REF], [START_REF] Clark | Common ground at the understanding of demonstrative reference[END_REF], [START_REF] Daniel | Testing the Value of Route Directions Through Navigational Performance[END_REF]. The criteria for choosing landmarks are related to semantic properties, perception salience and the appeal to context [START_REF] Clark | Common ground at the understanding of demonstrative reference[END_REF]. Also studies show the importance and relevance of propositions connecting landmarks and the actions to take (like "at the parking lot, turn right") [START_REF] Daniel | Testing the Value of Route Directions Through Navigational Performance[END_REF]. [START_REF] Allen | Principles and practices for communicating route knowledge[END_REF] proposes "best practices" for the choice of route direction based first on a temporospatial ordering of the statements and then on the use of shared knowledge to convey common ground during the interaction.

Pointing

In situated dialog, physical signals intended to direct the addressee attention to an element of the environment can be sorted into two classes: "directing-to" and "placing-for" [START_REF] Clark | Coordinating with each other in a material world[END_REF]. In [START_REF] Sauppé | Robot deictics: How gesture and context shape referential communication[END_REF] a study is conducted to highlight the rich design space for deictic gestures and the necessity to adapt them to physical, environmental, and task contexts. Another key aspect for the synthesis of the robot pointing gestures is their legibility [START_REF] Holladay | Legible robot pointing[END_REF]. Interesting studies have been done in the analysis of gestures accompanying verbal route directions [START_REF] Allen | Gestures accompanying verbal route directions: Do they point to a new avenue for examining spatial representations?[END_REF].

Pointing can also be seen as a joint-action where the guide has to verify that the visitor has successfully looked at the pointed direction or object, through gaze analysis and dialogue.

Placements to share visual perspective

Beyond extending one's arm, pointing at an object may require repositioning the agents to facilitate the perspective sharing and communication between the visitor and the guide [START_REF] Alibali | Gesture in Spatial Cognition: Expressing, Communicating, and Thinking About Spatial Information[END_REF], [START_REF] Fu | Effects of Communication Methods on Communication Patterns and Performance in a Remote Spatial Orientation Task[END_REF], [START_REF] Kelly | Perception of shared visual space: Establishing common ground in real and virtual environments[END_REF].

[26] provides a pertinent analysis of the stages to a successful pointing gesture. They mention the need for the viewer to be able to see both the gesture and the referent as well as the necessity of holding the gesture until coming to mutual agreement with the observer about what is being pointed at.

The consideration of the point of view of the observer by the speaker is discussed in [START_REF] Alibali | Gesture in Spatial Cognition: Expressing, Communicating, and Thinking About Spatial Information[END_REF] and in [START_REF] Fu | Effects of Communication Methods on Communication Patterns and Performance in a Remote Spatial Orientation Task[END_REF]. In [START_REF] Kelly | Perception of shared visual space: Establishing common ground in real and virtual environments[END_REF] the importance and role of the "Shared visual space" is stressed.

Concerning issues linked to placement planning, there are substantial results on planning sensor placement (e.g. [START_REF] Chen | Automatic sensor placement for model-based robot vision[END_REF]) as well as planning the robot position to let it share the human visual perspective [START_REF] Marin-Urias | Towards shared attention through geometric reasoning for Human Robot Interaction[END_REF] but we have found no contribution on planning shared perspective for both the human and the robot i.e. searching for a reachable placement of both partners.

A preliminary study [START_REF] Belhassein | Human-human guidance study[END_REF] focuses on the way a guide and a visitor place themselves and possibly move during the explanation of a route in the context of a large mall.

Route direction

In this activity, the guide gives indications on how to reach the desired destination, mostly through dialogue, but this can be improved by some gestures. Once the route directions have been successfully communicated to the visitors, they can navigate to their destination.

The synthesis of a combination of speech and gesture in order to achieve deictic reference has been discussed in [START_REF] Brooks | Working with robots and objects: Revisiting deictic reference for achieving spatial common ground[END_REF]. [START_REF] Okuno | Providing route directions: Design of robot's utterance, gesture, and timing[END_REF] proposes a model for a robot that generates route directions by integrating three crucial elements: utterances, gestures, and timing.

III. THE SVP PLANNER

The problem addressed here is related to several modalities: speech, gestures (including deictic) and navigation. These modalities are deeply connected, in the sense that they support each other: speech describes a navigation path; gestures improve speech by anchoring it to landmarks or describing actions; navigating closer to the destination simplifies the speech and may allow different (better) deictic gestures. Altogether, route directions are improved by pointing at pertinent landmarks. The guide can take the visitors to a location where said landmarks are "sufficiently" visible from their (shared) perspective.

All in all, there is a continuity of solutions between providing route directions from the starting point to guiding the visitor to his destination, including guiding only to a good perspective where to provide route directions.

The task as we address it is the sequence: 1) guiding -physically accompanying-the visitor to some place; 2) pointing at a landmark;

3) providing route directions -based on the pointed landmark; 4) reaching the destination (visitor only); in that order, but with each step being optional. The SVP planner solves the problem of finding a position for visitor and the guide where a pointing of some landmark(s) can be performed. The landmarks to point at is dependent on the task. It is important to notice that all of these steps are taken into account by the SVP planner to evaluate the task solution as a whole 1 .

A. Model

Our approach relies on a variety of information about the environment and the agents, either symbolic, physical, or on mental states. Provided with these data, the SVP planner can be potentially adapted to any situation where a robot has to provide route directions and to point at landmarks, like streets, museums, malls, offices, university campuses...

1) Physical Environment Model:

The environment needs to be represented in three dimensions, its accuracy influences the pertinence of the visibility computations and navigation planning. All the obstacles to navigation or sight (occlusion) must be represented. The model must discriminate landmarks from each other and from other objects or obstacles to allow the computation of a specific landmark visibility. In our implementation, we represent the environment (including landmarks) using 3D meshes, visibility of objects is computed with OpenGL (similar to what is used by [START_REF] Marin-Urias | Towards shared attention through geometric reasoning for Human Robot Interaction[END_REF]).

2) Symbolic Environment Model: The SVP planner needs information at symbolic level, mostly about landmarks. The SVP planner takes as input a list of landmarks that could suit the destination. Each landmark is associated to a scalar representing the duration of the utterance of the route direction based on this landmark. [START_REF] Morales | Building a Model of the Environment from a Route Perspective for Human-Robot Interaction[END_REF] presents an environment model built for providing route directions that can be suitable to our approach. A similar system is being developed within our team that computes route directions and provides the pertinent landmarks to use and their evaluation.

3) Human Model (visitor): We want the guide to adapt to different human visitor capabilities, so the system is accessible and does not discriminate certain persons by ignoring their specificities, and also adapt to a range of use cases. Our system can make use of the following information to adapt the solutions:

• height of the subject eyes, to compute its perspective accordingly; • visual acuity to enforce the use of more visible and salient landmarks; • navigation speed, to compute plan duration and give more important penalties to long routes; • urgency to reach the place (to balance the importance of plan duration over other criteria). These attributes are taken as input here but we believe they can be acquired and/or inferred through dialogue and perception (e.g. persons with a stroller or loaded shopping cart, persons in a wheelchair or with crutches are usually slower than average; a person in a hurry may express it verbally or through body attitude), or updated on failure recovery 2 .

4) Robot Model (guide):

The robotic guide may be able to navigate, in which case the planner can take as input a maximal distance the robot can run from its initial position. We use a speed estimation to compute plan duration. Our approach can indirectly take into consideration capacities of the robot by tuning some related parameters: accuracy of the pointing gesture and gaze estimation, dialogue capacities (inducing a higher cost of dialogue-based tasks).

5) Domain Parameters: Some parameters may depend on the given domain where the robot is deployed. The guide may be allotted a limited amount of time to serve each visitor, or on the contrary be expected to help each visitor as much as possible, i.e. provide the maximum effort to solve a request once it has been asked to the guide.

B. Evaluating the Solutions

The decision is based on estimation and comparison of the possible solutions to the task. The solution evaluation has to take into account:

• chances of success (the simpler the indications the higher is the probability that the human will remember them and reach the destination); • visitor effort and task duration;

• domain objectives -serving as much visitors as possible vs. providing the best quality of service for the served individuals. 1) Placements to share visual perspective: When pointing at an object, the guide objective is that the visitor identifies it unambiguously. To achieve this, it may be helpful to (1) reduce the difference of perspective, by getting the two agents almost aligned with the object. Stress is put on the alignment when the object is difficult to distinguish because it is small in the field of view. A secondary objective for the guide is to (2) relieve the visitor from some physical or mental effort by placing itself between the visitors and the destination, so they don't have to turn their head around to successively look at the pointing arm or gaze and in the pointed direction. A last objective on the pointing position is (3) for the guide to be able to monitor the visitor gaze, and speak to them; but the guide also needs to enforce pointing with gaze, so it should be able to look at the visitor and at the chosen landmark.

These properties are estimated by building a triangle whose vertices are the visitor, guide and pointed object centers, as represented in Fig. 2. The three angles (see Fig. 2b) denote the above mentioned properties of the pointing position. Angle (a 1 ) at the pointed object vertex correspond to the difference between the perspectives of the agents. Angle (a 2 ) at the visitor vertex reflects how much they have to move to switch from looking at the guide being pointing and the pointed object; it also indicates if the guide sees the visitor's face when they look at the landmark, allowing gaze detection or not. The third angle (a 3 ) is for the guide to look at the object and the visitor. In the presented results, the SVP planner is configured to get a 2 ≈ a 3 and minimize a 1 .

2) Guiding: The joint navigation step is evaluated considering the distance run while guiding, and the duration of the guiding step thanks to the speed estimations provided as input. When a guiding step is necessary, the solution evaluation is penalized by a constant value that represents the time needed to ask the visitor to move and explain what she/he should do.

3) Route Directions: The utterance of route directions to the visitor, or more ambitiously the construction of a dialogue in which the directions are given to the visitor, is likely to be a time consuming step of the task. Even more importantly, it is a critical part for the success of the task: too complex instructions will be likely to lead the visitor to get lost or simply abandon the task and find another way for reaching her/his objective, making the guide counterproductive. The duration and complexity of the route directions is directly related to the number of steps of the route [START_REF] Daniel | Testing the Value of Route Directions Through Navigational Performance[END_REF]. The guide will need to find simpler routes, use visible landmarks to simplify them, move to a place where such landmark is visible. This is illustrated in the example of Fig. 6b where the guide uses a landmark next to the door and starts its route directions from that point, hence removing one step in the route to explain (the one to reach the door from the current position). The planner will seek to choose a landmark associated to simplest possible route description

C. A Planning Request

Equipped with the data provided by the models defined section III-A, a request to SVP planner contains at least:

• initial position of the robot (guide) p g0 and the human (visitor) p v0 , • visitor's destination position p v d , • list of landmarks L and duration of the indication utterance based on each landmark (T Indic (l), ∀l ∈ L); and outputs:

• placements and orientation for both guide and visitor,

• list of visible landmarks from there. Some other parameters that are set by default can be parameterized: height of the eyes of the human; height of the eyes of the robot: those that the human consider to be the eyes of the humanoid robot, not the camera actually used for perception; speed estimations for each agent; maximal distance the robot can run from its initial position; minimal visibility score to consider a landmark visible; other parameters to tune the importance of each aspect of the task with respect to each other in the choice of the best solution (like optimizing the duration over the visibility,...).

IV. IMPLEMENTATION

The SVP planner decides where the robot and human should go to reach a good shared perspective from which efficient route directions can be given. This step is a key decision of the overall task, as the position will determine all the other steps. This is why our planner uses an objective function that encompasses all the task, rather than just evaluate the quality of the pointing and perspective. Our solution is designed to match the high coupling of all the steps of the task.

The evaluation criteria presented above are represented as cost and constraints. Constraints are inequalities that represent the validity of a solution, and costs are used to choose the best solution among the valid ones.

A. Search Space

The planner decomposes the area accessible to the guide in a two-dimensional grid, and searches for the best pair of positions

X = (p g , p v ) = ((x g , y g ), (x v , y v ))
both for the guide and visitor, expanding from the initial positions X 0 = (p g0 , p v0 ). The destination state is X d = (p g0 , p v d ) (the guide goes back to its initial position and the visitor reaches the destination).

B. Constraints

Constraints are computed for a tuple of : landmark, visitor position and guide position, that is (l, p v , p g ) or equivalently (l, X). A solution is valid only if all the constraints are respected.

a) Visibility constraint: ensures that the two agents see the landmark (hence that shared perspective and joint attention are possible) v(l, p g ) ≥ V ming and v(l, p v ) ≥ V minv b) Interaction distance constraint: interaction distance within 20% of the desired distance

(|| p v p g || -D I ) 2 < (D I • 0.2) 2
where || p v p g || = distance between the agents and D I = desired distance interaction. The value of D I relates to the proxemics theory and is intended to ensure a social interaction distance. (The 20% error is actually a parameter.)

Guide range constraint: keeps the guide within a certain distance from its initial position d g (X) < D max Guide time constraint: limit the duration of the task for the guide

T Guide (X) + T Return (X) + T Indic (l, X) < T max

C. Costs

In addition to these constraints, our implementation takes the following parameters into account:

1) Navigation Distance and Duration: To estimate the distances and duration of the navigation phase, we use a the same grid as the visibility grid. It allows to compute shortest paths with Dijkstra Algorithm.We compute the distances from three points, giving distances between these points and any point in the grid. We compute distances from p g0 , v0 and p v d , respectively providing the following path lengths for any X in the grid: distance runs by the guide d g (X) = d(p g0 , p g ); distance run by the visitor d v (X) = d(p v0 , p v ); remaining distance to reach the destination for the human

d destination (X) = d(p v (X), p v d (X)).
We compute an estimation of the joint navigation (guiding) step duration as

T Guide (X) = max(d g (X)/s g , d v (X)/s v )
where s g and s v are the respective average speed estimations of the agents and the durations

T Destination (X) = d Destination (X)/s v T Return (X) = d s (X)/s g
respectively for the human to reach the destination and for the robot to return to its base.

2) Landmarks visibility from visitor and guide placements: For each landmark l and position X we compute the visibilities of l by the guide and the visitor v(l, p g ), v(l, p v ).

To speed up the computation, each visibility score is precomputed, because it is a quite expensive step. The 3D space is sampled with a grid that holds score representing perceived size of the objects in the 360 degrees fields of view from each cell center (the values of v(l, p) for various sizes of human). Sample visibility grid (3D) are shown in Fig. 3. The visibility computation itself is done by assigning each object a unique color, rendering the 3D scene with OpenGL and counting the number of pixel of each color, from each cell of the grid. To avoid issues related to distortion, the field of view is split in section of a maximum range of 90 degrees in each direction. 3) Route direction duration regarding a landmark: For each landmark l, providing the route direction based on that landmark has a duration estimation T Indic (l).

4) Pointing Conformation: We use the three angles a i (l, X), i = [1, 2, 3] representing the pointing conformation, computed from a triangle whose vertices are robot and human eyes and the center of the landmark (see Fig. 2).

5) Cost Function: The cost function combining the parameters presented above is:

c(l, X) = (T Guide (X) + T Indic (l))(K H + K R ) + T Destination (X).K H + T Return .K R + K v .V (l, X) + 1 × 3 i=1 a i (l, X)K ai (1)
Where V (l, X) = max(0, V min -v(l, X)), K H is the weight applied to human time, K R for robot, K v is the weight applied to the visibility score, and the K ai are the weights applied to each angle of the conformation. This is the cost for a landmark and position. As we want to choose the best landmark to point at, the cost c(X) at a position X is the best of the c(l, X), that is

c(X) = min l∈L (c(l, X))
where L is the set of landmarks provided in the request.

D. Search Algorithm

Our implementation performs a search by propagation from the cell containing X 0 . The propagation is based on a set of open cells, where neighbors of previously closed cell are added, except when the closed cell break some evaluation constraints (namely, the guide range and time constraints). This prevents the algorithm to explore all the possibilities.

E. Choose the Best Route

One step further, the planner could be provided multiple alternative routes, and choose the best one based on the already existing cost. Indeed, we try to capture the whole task in this cost. So this would be achieved by simply running the planner for each route, and picking the one which provides the solution with the best cost.

V. EXAMPLES

We present examples in two environments. The first example (Fig. 5) is the ground floor of a building of our lab, featuring an entry hall, offices and meeting room, and a large hall with an experimenting apartment. The main hall is around 12 by 20 meters the central apartment occupies a 9x9 meters square.

In Fig. 6 we show how the robot can make use of landmarks situated on the path to the destination and balance Fig. 6 between guiding and providing route directions. In Fig. 6a the robot is guiding the visitor to a place where the destination is visible, leading to simple route directions; whereas in Fig. 6b, we set a low speed to the robot, so the planners prefers not to guide the human, and use a landmark to indicate a waypoint for human navigation (while the robot is still able to guide the human, the planner prefers no to).

The SVP planner has been integrated to a system allowing its execution on a real robot, we have been running in-lab demonstrations, and we plan to bring it to real life situations for testing. Fig. 1 shows pictures taken during an in-lab test, and Fig. 7 shows the human initial and planned perspectives in the 3D model. The request in this case was made of only one landmark, the shop front, and the robot asks the human to move a bit to reach a perspective where he can see the destination landmark. The robot too is moving to have a similar perspective. While the robot do not need to see the object, it is important that both agents share a visual perspective for an effective pointing.

In this same environment, Fig. 8 illustrates the ability to take into account different human morphologies and adapt to their perspective when pointing at an object that can be hidden by obstacles, leading to very different solutions, in this case with a small child unable to look over a window edge.

We have been testing the system in a larger environment, a mall, where the robot can navigate only in a small area of a vast hall (Fig. 9 and10). The solution is to guide the human to a place from where he can see a landmark close to the target (as close as possible). If the robot wouldn't move, it would have to point at a landmark further away from the target (say, here, the green info panel, visible near the middle of Fig. 9 and in Fig. 10).

In these test, when the supervising component detects the human did not moved at the planned position, it requests the SVP Planner an evaluation of this position (applying the cost function to it). If it is valid, then the execution continues with that position, otherwise the guiding starts again from that position3 .

VI. CONCLUSIONS

We have shown in this paper that we can compute a place where a robot can accompany a human to provide route directions based on landmarks that would otherwise be invisible. Doing so may be pertinent when such landmark The bottom black box is the area allowed for the robot to navigate, the circle in it highlights the starting position of the experiment in Fig. 10, where the robot guides the human near the position highlighted by the white cross mark. may help improve the quality of the indications, as shown by some examples. This approach requires to consider the problem as a joint task, as we produce a shared plan where both agents need to act.

The preliminary implementation of a solver dedicated to this task, the SVP Planner, gives us a view of the requirements for implementing a system aiming at tackling this complete task, from request to execution. Our planner needs information about the route to indicate to the visitor: the path(s) it can take, and landmarks that could improve the route directions if they can be pointed at. Knowledge about the visitor goal, mental state and capacities presented in III-A.3 can be provided by dedicated tools based on dialogue and visual perception. The execution of the navigation (guiding) step is widely addressed in the literature. The pointing

  (a) Initial situation, the visitor asks for a shop. (b) Visitor's perspective at his initial position: he cannot see the sign (in the corridor).

  (d) Visitor's perspective from the planned position. He can see the sign now.

Fig. 1 :

 1 Fig. 1: In-lab demonstration. The robot has to show the circled landmark to the human; the SVP planner has found nearby positions for the human and the robot (c) from where it can be seen and pointed at.

Fig. 2 :

 2 Fig. 2: Four examples of real pointing scenarios. The person wearing a green (light) sweatshirt is the guide pointing at a landmark (two in (d)); in white are represented the triangles formed by the landmark, visitor and guide.

Fig. 3 :

 3 Fig.3: Grids representing the visibility of two landmarks in our lab building environment, at two different viewpoints height. The grids are actually three dimensional, we represent here two 2D slices of two visibility grids. Cells are cubes of 40cm sides. Lighter/yellow cells are those from where the visibility of the object is the best, while from dark/purple ones the object is hardly visible. Transparent cells correspond to the object being not visible at all. We see how the visibility measure is determined by distance and obstacles. The landmark for which the visibility is shown is highlighted by a white ellipse and arrow, the cross on the far left is the position from where the perspectives of Fig.4are taken.

  (a) Perspective from a height of 1.5m, the two highlighted landmarks are visible. (b) Picture of the same perspective from 1.5m height (zoomed). (c) Perspective from a height of 1.9m, the hanging landmark is hidden by the part of the wall above the door. (d) Picture of the perspective from 1.9m height.

Fig. 4 :

 4 Fig. 4: Two perspective taken from the position marked in Figure 3, with the same landmarks indicated by a black ellipse and arrow.

Fig. 5 :

 5 Fig.5: Overview of our lab building 3D model, with virtual signs added to serve as landmarks.

  (a) The robot indicates the restroom door (top of the picture) to the human (b) The robot points at a sign to indicate where the human should go to approach and see the restroom door (both come from the left side of the picture).

  (a) Initial human perspective in our 3D model. (b) Planned perspective in the 3D model.

Fig. 7 :

 7 Fig. 7: Perspectives in the 3D model for the example of Fig. 1

  (a) In this solution, the robot shows the bed to the human through a "window", limiting the joint navigation length.(b) With the same initial situation but with a small person (child) who cannot see the bed through the window, the robotic guide guides to get in the bed room.

Fig. 8 :

 8 Fig. 8: Two distinct solutions to the same problem caused only by a different morphology of the visitor.

Fig. 9 :

 9 Fig. 9: Bird's-eye view of the real-life mall visibility grids of the target landmark (left) and a waypoint landmark (right).The bottom black box is the area allowed for the robot to navigate, the circle in it highlights the starting position of the experiment in Fig.10, where the robot guides the human near the position highlighted by the white cross mark.

Fig. 10 :

 10 Fig. 10: Real-life mall experiment video screen-shots: (left) initial position; (right) robot pointing at the corridor, after guiding the human a few meters to reach an acceptable shared visual perspective.

individual steps are heuristically evaluated on some parameters we found pertinent (mostly time) , so that their precise design should not interfere with the planner.

The human could say "I don't see it", we would then replan with reduced acuity

Details of this implementation are out of the scope of this publication, but it appeared to be an important concern in most reviews.

gesture by itself is also addressed, along with the association of gestures with verbal route directions. These elements would work with objectives provided by the SVP planner presented in this paper: guiding destination, landmarks to point and route to indicate. Execution of the task requires dedicated supervision to articulate the various phases of the interaction and eventually recover from failures, e.g. by replaning with updated parameters. We are developing such a complete system in the scope of the MuMMER project.