Mamoun Gharbi

Raphaël Lallement

Rachid Alami

Combining Symbolic and Geometric Planning to synthesize human-aware plans: toward more efficient combined search

We are combining symbolic and geometric planning to synthesize human-aware plans in order to deal with the complex and highly intricate planning problems induced by Human-Robot collaborative object manipulation.

In this paper, we summarize our previous contributionsrefining symbolic actions at geometric level, during the symbolic planning, in order to assess their feasibility and computing the geometric side effects-, then we present the current contributions meant to tighten the cooperation between the symbolic planning and the geometric planning: the symbolic planner helps the geometric one by providing it with constraints and domain-expert knowledge making the geometric planner more efficient, and the geometric planner helps the symbolic one to find the best plan based on social costs computed at geometric level.

We also propose different examples, highlighting the interest of such cooperation between the planners in simulation and on our PR2 robot.

I. INTRODUCTION

We are developing a symbolic-geometric planner in the context of fetch & carry and collaborative human-robot object manipulation [START_REF] Alami | On human models for collaborative robots[END_REF]. Besides, we would like the planner to be used in the context of situated dialogue [START_REF] Warnier | When the robot puts itself in your shoes. managing and exploiting human and robot beliefs[END_REF], [START_REF] Lemaignan | Grounding the interaction: Anchoring situated discourse in everyday human-robot interaction[END_REF]. We argue that such a context is very challenging and opens interesting and "subtle" issues to the Combined Task and Motion Planning problems.

In such a context and perhaps more than in standard robotic manipulation problems (the block world problem and its robotics variants, for instance), there is a need for a more sophisticated reasoning since actions and motions are far more intricate, and the contexts in which they are performed, as well as how they have to be performed, can induce complex and highly interdependent decisions.

The planner should be able to synthesize plans for every agent, while taking into account the intricacy induced by having them sharing the same space and task. One difficulty comes from our intention to reason and consider affordances and perspective taking from both human and robot sides and, based on this, to produce collaborative actions where every agent has to act.

Fig. 1 shows an example of such a problem, where a robot needs to take decisions and computes plans in a human populated space. The bottom part corresponds to a plan automatically synthesised by our planner (containing *This work was conducted within the EU SAPHARI project funded by the E.C. division FP7-IST under contract ICT-287513.

1 CNRS, LAAS, 7 avenue du colonel Roche, F-31400 Toulouse, France firstname.lastname at laas.fr

2 Univ de Toulouse, INSA, LAAS, F-31400 Toulouse, France 3 Univ de Toulouse, LAAS, F-31400 Toulouse, France Fig. 1. The robot needs to bring two processed objects to the green human.

A processed object O1 is available at A, and two unprocessed objects O2 and O3 are available at B and C (the blue human can process them). To pick O2 the robot needs to move out the orange box, and to reach O3 the robot needs to navigate behind the red human. Our planner is able to find a solution to this problem while taking into account humans preferences, affordances and comfort. The bottom figure shows the solution plan.

both the action sequence for every agent and the geometric information needed, such as the trajectories, the grasps, and the object placements). The plan takes also into account a number of human-aware constraints such as minimising the humans efforts or avoiding to disturb them. In a multi-agent, human-aware context, the action effects and their costs cannot be computed at symbolic level, especially while taking into account the human comfort and preferences [START_REF] Sisbot | A human-aware manipulation planner[END_REF]: the interleaving between symbolic and geometric planning becomes mandatory.

This paper reports on the extensions of a planner we have already presented in [START_REF] Silva | Towards combining HTN planning and geometric task planning[END_REF], [START_REF] Silva | A new approach to combined symbolic-geometric backtracking in the context of human-robot interaction[END_REF]. We provide details on how the ramification problem is tackled and present a number of extensions specially dedicated to the improvement of the plan search: (1) a set of high level geometric constraints, (2) the ability to encode domain-expert knowledge at both levels, (3) well-informed cost estimation of actions and (4) the ability of the geometric planner to provide several instantiations of the same action. This permits to address more challenging problems and to integrate human-aware planning considerations.

II. RELATED WORK

Merging symbolic and geometric planning is a growing field that has been a focus to a number of researchers over the few last years. Various approaches are pursued, some are similar to our previous work, such as [START_REF] Plaku | Sampling-based motion and symbolic action planning with geometric and differential constraints[END_REF] where the Fig. 2. A snapshot of the planner during the planning process. This plan is a "multi-stream" plan: human and robot actions. The robot has to place an object so the human can paint it and then the robot will transfer it to another place. The plan is built incrementally: the symbolic plan is maintained by the HTN planner while its geometric counterpart -the geometric plan-, the geometric refinement of some actions (the others are purely symbolic), is maintained by the geometric planner. When an action preconditions are not respected (Paint here), the HTN planner backtracks to the previous backtracking point, (the refinement of Place here) and tries alternatives to this action (the different refinements of Place in the geometric planner layer). The preconditions can be purely symbolic or computed by the geometry (predicates such as is on, is Reachable by) which enable us to tackle the ramification problem. The planner tries 3 different action instantiations (called alternatives) before finding the right object placement that will allow the human to paint it. authors guide the search at geometric level with the symbolic planning. Others focus on different aspects, such as [START_REF] Nedunuri | Smt-based synthesis of integrated task and motion plans from plan outlines[END_REF], where the authors construct a graph (the nodes are robots positions linked to feasible actions at task level, and the edges are collision free paths) and use a Satisfiability Modulo Theories to find a path in it. Similarly, [START_REF] Garrett | Ffrob: An efficient heuristic for task and motion planning[END_REF] also builds a graph representing different configurations reachable by the robot and the FastForward algorithm is used to find a solution.

In [START_REF] Dornhege | Lazy evaluation and subsumption caching for search-based integrated task and motion planning[END_REF] and [START_REF] Dornhege | Integrating task and motion planning using semantic attachments[END_REF], the authors use semantic attachments, which are external procedures called by the task planner to assess the feasibility of an action at the geometric level (e.g. if a collision free path exists between two positions). [START_REF] Karlsson | Combining task and path planning for a humanoid twoarm robotic system[END_REF] extends this approach by adding a geometric backtracking: in order to assess an action feasibility, the geometric planner can change the choices made for the previous actions without acknowledging the symbolic planner.

In [START_REF] Kaelbling | Hierarchical task and motion planning in the now[END_REF], the authors use a goal driven task planner that enables calls to external procedures during the planning phase. In case of failure, this procedure provides a reason to the planner which enables it to find an alternative plan. Using failure reasoning to guide task planning is also stressed out in [START_REF] Erdem | Combining high-level causal reasoning with low-level geometric reasoning and motion planning for robotic manipulation[END_REF] where a causal reasoner is used to find a plan, then a motion planner tries to solve the underlying motion problem, and if the latter fails, a constraint is added to the symbolic domain and the causal reasoner tries to find a new plan. [START_REF] Srivastava | Combined task and motion planning through an extensible plannerindependent interface layer[END_REF] uses off-the-shelf planners and formulates a representational abstraction enabling to combine them: each action in the symbolic plan can have multiple instantiations at geometric level corresponding to the different geometrical choices.

The authors in [START_REF] Lagriffoul | Constraint propagation on interval bounds for dealing with geometric backtracking[END_REF] compute a task-plan, and use interval bounds which are constraints on object/robot positions to prune out geometric choices. Another approach, proposed in [START_REF] Lozano-Pérez | A constraint-based method for solving sequential manipulation planning problems[END_REF], is to formalise the problem as geometric constraints between agents and objects, and to use a Constraint Satisfaction Problem solver to find the solution.

III. SYMBOLIC-GEOMETRIC PLANNING

PROBLEM We define a problem combining the symbolic and geometric planning as the 6-tuple D s , D g , S s0 , S g0 , g, E where D s stands for the symbolic domain, containing all the symbolic tasks, while D g is the geometric domain that contains all the geometric actions. S s0 and S g0 are respectively the symbolic and the geometric initial states (they represent the SAME world state). g refers to the goal to achieve and E represents all the elements of the environment: the agents, the pieces of furniture, the objects and so on; they are called entities. The agents are treated as first-order entities since they correspond to robots and humans for which it will be necessary to compute motions. Entities are referred to, on both systems, with the same name to keep the correspondence. Their representation changes depending on the planner: at the symbolic level, attributes are associated to an entity in the form of predicates, whereas at the geometric level the same entity is described by its shape and its configuration space.

The geometric reasoning system is able to compute spatial relations between entities, such as between objects (in, ontop-of, ...) or between agents and objects (visibility, reachability, ...) [START_REF] Sisbot | Situation assessment for humanrobot interactive object manipulation[END_REF]. This can be related to well known need to deal with the anchoring problem in order to fill the gap between the levels [START_REF] Daoutis | Cooperative knowledge based perceptual anchoring[END_REF]. Those relations are named "Shared Literals" (as in [START_REF] Silva | A new approach to combined symbolic-geometric backtracking in the context of human-robot interaction[END_REF]) since they are generated by the geometric level and exploited by the symbolic planner.

The solution to this kind of problem is a set of feasible actions, where an action is defined by the agents and their motions. The different actions are sequenced thanks to causal links -computed at the symbolic level from the HTN hierarchy-forming the plan.

IV. ALGORITHMS AND EXTENSIONS

A. Previous algorithms

We have proposed various contributions to the problem of combining symbolic and geometric reasoning in order to produce pertinent and feasible robot plans.

In Asymov [START_REF] Cambon | A robot task planner that merges symbolic and geometric reasoning[END_REF], [START_REF] Gravot | asymov: a planner that deals with intricate symbolic and geometric problems[END_REF] we essentially proposed a principled way to link the two planners thanks to a geometric level able to tackle the so-called "manipulation planning problem" [START_REF] Latombe | Robot Motion Planning[END_REF] and that allows to explicitly take into account the topological changes occurring in the configuration space, when a robot grabs or releases an object. Asymov provided a well founded translation of pick and place actions (and similar actions) into 'transit' and 'transfer' motion planning requests even in multi-object and multi-robot contexts.

More recently we focused on a complementary approach [START_REF] Silva | Towards combining HTN planning and geometric task planning[END_REF], [START_REF] Silva | A new approach to combined symbolic-geometric backtracking in the context of human-robot interaction[END_REF]: exploiting the capacity of the Hierarchical Task Network (HTN) [START_REF] Nau | Automated Planning: Theory & Practice[END_REF] techniques to encode domain knowledge and developing a geometric planner capable of planning actions with several levels of abstractions, opening to more elaborate action instantiations. Such a combination provides several key features: a clean interface which corresponds to the anchoring problem and allows to better exhibit and master the links between the incremental processes of producing the symbolic plan and its geometric counterpart.

In [START_REF] Silva | Towards combining HTN planning and geometric task planning[END_REF] we presented a geometric backtracking algorithm which allows to reconsider the previous geometric choices by trying various alternatives to the previously computed actions and tests the validity of these alternatives by computing their geometric effects. In [START_REF] Silva | A new approach to combined symbolic-geometric backtracking in the context of human-robot interaction[END_REF], the approach is different since the symbolic planner creates multiple instances for the same action (if a geometric refinement is needed) and backtracks on this instances, which are in fact, different geometric alternatives for the same symbolic action. If an actions is successfully refined, geometric effects, the shared literals, are computed.

The algorithm we use in this paper is presented in details in [START_REF] Silva | Towards combining HTN planning and geometric task planning[END_REF] and illustrated in fig. 2. The implementation is different: previously the link between the symbolic planner and the geometric planner was encoded directly into the symbolic domain, now a complementary module handles this link. At the geometric level, the implementation is more generic, and is able to tackle more complex problems linked to the symbolic-geometric planning problem.

B. Algorithm extension

The ramification problem occurs when all the effects of an action cannot be determined beforehand. When a motion is involved in an action, the symbolic planner cannot compute all the effects: a too-complex world model would be required. Furthermore, computing the human affordances (objects reachability, visibility and so on) makes it even more complex. Fig. 3 shows an example of this problem: the robot needs to place three objects on the table in front of it in order for the human to be able to reach the three of them at the same time. In the figure 3-C the robot places the third object, but this makes the first one no longer reachable.

In order to (partially) tackle this problem, we use the shared literals: after a geometric action is planned, we compute those literals for the new end state and send them to the symbolic layer. If some of the literals prevent a further action preconditions to apply, a backtrack is triggered and another geometric solution is requested. This process goes on until a valid plan is found, a given maximum number of geometric solutions (given by the domain expert) are tested, or no other geometric solution is available.

The problem is only partially tackled due to the discrete set of shared literals the system is able to compute: if a shared literals does not exist, the problem will not be tackled. Fig. 3. The robot can reach the three objects (the red cube, the grey book and the orange box) and needs to place them on the table, such as the three of them are reachable by the human at the same time. A is an initial geometric situation, B is a step of the planning process where the robot has already placed the red cube and the grey book reachable to the human. In C, the robot places the orange box reachable to the human, and by doing so, obstructs the human reachability to the red cube (this is computed by the geometric reasoner). Finally D shows the result of a plan found after backtracking on a number of actions. This illustrates the ramification problem.

The symbolic layer exploits the shared literals when checking the preconditions, such as most other planners of the literature. In addition to the precondition checks, we added a "goal" for the abstract tasks (methods) under the form of literals. This goal is specified in the domain and used to check if the method decomposition has effectively reached the target goal. If the goal is achieved, the resolution continues, otherwise a backtrack is triggered. This mechanism is especially useful when, during a method decomposition, one or multiple actions can break previously achieved sub-goals in this same decomposition.

The shared literals are also used as constraints set by the symbolic layer when refining an action in the geometry. Then the constraints serve as supplementary goals to the action and drive the geometric search since they forbid some solutions. A constraint is a literal that must be true in the action geometric end state, for instance Object.ReachableBy == Human.

To better understand how constraints might be efficient in our context, a little reminder of the algorithm to find an action solution is needed: first it finds a position for the object, then, it finds a configuration for the agent, using inverse kinematic, and finally, it looks for a trajectory between the agent current state and this configuration.

For the constraints to be useful, they are tested as soon as possible: if it is constraints over the object position, they are tested before calling the inverse kinematic, if it is about the agent configuration, they are tested before the motion planning. Using the constraints enables to save computation time as they are tested before the computation is finished.

This constraints, when added to the symbolic domain, consist on a domain knowledge able to drive the geometric search. Another useful domain knowledge is the virtual actions. Virtual actions are simple, fast computing actions, used to test if a future action might be possible. Those actions do not ensure the infeasibility of the future actions, but, if they succeed, ensure their feasibility.

The example presented later in this paper (subsection V-B) concerns a virtualPlace1 . This action places a virtual object2 on a support to test if it fits. In this case, any items this virtual object may contain will fit on the support.

The last contribution of this paper, is the cost usage: the symbolic planner uses cost-driven search [START_REF] Lallement | Hatp: An htn planner for robotics[END_REF], moreover each action has a cost function given by the domain expert. However, the geometric planner as it computes the actual trajectory, has a better cost estimation and can provide the symbolic planner with precise costs representing different parameters such as the energy needed, the time to or social rules (e.g. avoiding navigation behind humans [START_REF] Sisbot | A human aware mobile robot motion planner[END_REF]).

V. EXAMPLES & RESULTS

In this section, we present different examples involving at least a human and a robot (the PR2), where a standard twolayer planning architecture would not be able to solve the problem or would not find the best solution. The experiments were run on a quad-core Intel Core i7 processor and 8GB of RAM, running Ubuntu 14.04.

A. Exploiting reachability computation to enrich reasoning about pick & place

This example shows the interest of having a backtracking algorithm, different levels of abstraction in the geometric planner, constraints, symbolic goals and how our system handles the ramification problem. Fig. 3-A shows a geometric initial situation S g0 . The robot needs to place the three objects (the red cube, the grey book and the orange box) on the table in front of it, reachable by the human (at the same time, in the end of the task).

The shared literals used in this example are ReachableBy (which objects are reachable to each agent) and IsOn (which object is on which one). The available geometric actions in D g are pick, place, placeR and placeRC. placeR is an action where the robot places an object ReachableBy the target agent (the human here). placeRC is similar to it but adds constraints to the action: the constraints are for the objects already placed on the table to still be ReachableBy the same target agent once the action is performed.

The highest-level task in the symbolic domain D s is PlaceObjects and is composed of the succession of three Fig. 4. The same experiment as in fig. 3 described in section V-A was held on the PR2 robot (the robot needs to place the three objects accessible to the human). The environment was set, then a plan (both at symbolic and geometric level) was computed by our algorithm and finally executed (the execution part is not a contribution of this paper).

Transport tasks followed by a Validate action. The Transport method contains a Pick action, then a Place and finally a CheckReachable. The goal of the latter is to check if the object involved in Transport is reachable by the human. The Validate action is similar but does the reachability test for all the objects the robot should place and is used as a goal test. The objects placement order is given to the planner.

There are four variants of PlaceObjects: the first is presented above, the second, PlaceObjectsR, where PlaceR is called instead of Place, the third, PlaceObjectsRC, uses PlaceRC instead of Place. The set of objects to specify in this function is the list of the previously placed objects, which prevent this action from breaking the predicates Object.ReachableBy == targetAgent tested in Check-Reachable and Validate. Finally the fourth, PlaceObjectsR-Goal, which is similar to PlaceObjectsR (the second variant) but where the goal of each method is specified such that it must keep the previously-placed objects reachable in addition to make the newly-placed object reachable.

Table I shows a clear difference between the domains using Place, PlaceR, PlaceRGoal and PlaceRC. In the first case, the action CheckReachable preconditions are rarely met, resulting in a high number of alternatives computed and a long computation time (∼15min). When PlaceR is used, the number of alternatives computed decreases significantly: the geometric planner directly places the objects reachable by the human. Placing a new object may change the reachability of the previously placed objects, -the ramification problem depicted in fig. 3-, the constraints enforcement in PlaceRC prevents this behaviour, greatly reducing the number of alternatives needed and the computation time. PlaceRGoal gives better results than PlaceR, the ramification problem is detected sooner enabling a faster recovery: for instance when the second object (the grey book) is placed, if it breaks the reachability of the first one (red cube) the PlaceR variant will only detect it at the final Validate while the goal enforcement ensures an earlier detection. However PlaceRC gives better results as it prevents the ramification problem from occurring.

This example is based on backtracking, shared literals and abstract actions. [START_REF] Cambon | A robot task planner that merges symbolic and geometric reasoning[END_REF] and [START_REF] Karlsson | Combining task and path planning for a humanoid twoarm robotic system[END_REF] can reproduce the first results (placeR and placeRC) while [START_REF] Lagriffoul | Constraint propagation on interval bounds for dealing with geometric backtracking[END_REF] and [START_REF] Garrett | Ffrob: An efficient heuristic for task and motion planning[END_REF], due to their constraint based approaches, can reproduce the latest ones (under the condition of adding the human-aware predicates).

This experiment (with slightly different items, but with the same problems) was held on the actual robot (PR2) as well, A B Fig. 5. The robot has to place the three books on the table in front of it. This table is cluttered by other objects, making it impossible to place more than one or two books. Case A shows an initial situation while B shows the VirtualPlace test made on the table to assess if there is enough space for placing all the books on the table. fig. 4 shows key pictures of the execution and the attached video shows the whole plan execution.

B. Using domain-expert knowledge to drive the search

This example shows how it is possible using the combination of a symbolic and a geometric planner to implement a common-sense heuristic. When one tries to place several objects close one to the others, it tries to find a surface or to free a surface (if needed) where it is possible to put an "imaginary" (we call it virtual), big object that represents the volume to be occupied by the full set of objects. Fig. 5-A shows an initial geometric states S g0 . The robot needs to place the three books in front of the human, but the table is cluttered with other objects. The available geometric actions in D g are pick and place.

In this scenario the top-level task, GiveCollection, has two decompositions and, to decide which one to use, it tries a virtualPlace with a virtual object. If the virtual object can be placed, it means that there should be enough room to directly the task PutObjects. This task is recursive and is called once for all objects in order to Transport them. (Transport is defined as the sequence of a Pick and a Place actions.) In the case where the virtual object can not be placed, the task CleanTable is called before using the PutObjects. CleanTable is also recursive and iterates through all objects on the goal table and stops when either the virtualPlace succeeds or all objects are removed. If the robot can not carry out this task (no space to place or no grasp for the objects) the human will help out.

In order to have a reference value, we have created a version of this domain where the virtualPlace is not used to choose whether to CleanTable or not, neither to stop the recursive call to CleanTable (which then stops only when all objects are moved away). Table II shows the two domains (with and without the virtual test). When virtualPlace is used, the planner tries to place a virtual object corresponding to the set of books, on the table (fig. 5-B) and if no space is found, calls CleanTable before PutObjects, otherwise it directly calls PutObjects. In the other case, the planner will try to place the books on the table, and will probably succeed to place one or two, but the space is limited, and the third book will not have enough space. Hence, the planner will backtrack several times over the Transport task before finally trying another decomposition (CleanTable), this implies to try several decompositions, refine and compute a lot of alternatives before finding the first valid plan. The significant time spent on useless backtracks can be seen in table II. On the other hand, with the virtualPlace, a first valid plan is found sooner since it realises that it is necessary to free the table before putting the objects, yet it may use few alternatives to correctly refine CleanTable or PutObjects.

In this example, the aim was to remove objects in the target area only when necessary, this has been of interest in [START_REF] Dornhege | Integrating task and motion planning using semantic attachments[END_REF], [START_REF] Kaelbling | Hierarchical task and motion planning in the now[END_REF], [START_REF] Lozano-Pérez | A constraint-based method for solving sequential manipulation planning problems[END_REF].

C. Reconsidering the object choices based on the plan cost

This example shows how the geometry can guide and/or help the symbolic planner to find the best plan based on its quality. Number of research focuses on qualifying a geometric action, especially in a human-aware context. We use [START_REF] Sisbot | A human aware mobile robot motion planner[END_REF] in order to compute a cost for the robot navigation action, integrating the path length, the distance between the path and the humans and the length of the path passing closely behind the humans.

Fig. 6 shows two initial situations S g0 and their solutions (the blue lines). The difficulty consist on choosing the right object (between the two similar and available ones) to bring to the human. This choice should take into account the comfort of every human in the environment.

The available geometric actions in D g are pick, place and goto, which is a navigation action where the search space is the set of positions within range of the target object.

The domain starts with the task GiveObject that randomly chooses an object: this is a backtracking point and since all the plans are computed in order to find the best, all objects are tested. It decomposes into Take and MakeReachable methods. The first method has two decompositions depending on whether the robot can Pick or has to first GotoObject before being able to Pick. The choice is based on a reachability test. The MakeReachable task again takes in account the reachability of the table to place the object on: it relies on Place but also has a second decomposition where it first uses GotoTable before the Place.

This example can be solved using a symbolic planner only, but our approach enables the planner to choose the best solution among all the possible plans while taking into account the geometric world and some specific social rules.

[15] describes an example close to this one, where the robot needs to choose between multiple symbolic plans and the best one based on a geometric computation of the cost.

Fig. 1 shows a variation of this example (The attached video shows a symbolic-geometric search in this domain, and the plan found for it), where there are more actions and interactions. The green human is waiting for two processed objects to be delivered, and there are two unprocessed objects A B Fig. 6. The green human asks the robot to bring him an object. Two similar objects are available in the environment, and the robot needs to choose the one to bring to the human, depending on the environment (here the presence or not of the blue human). When the blue human is absent, the shortest path is chosen. When he is near the table, choosing this path makes the robot navigate behind him, thus the robot chooses the other object which is farther but, by doing this, it respects the human comfort. and a processed one in the environment. The blue human is able to process the objects. The difficulties in this example are the followings: (1) to reach the unprocessed object at B, the robot needs to move the orange box, (2) to navigate to the unprocessed object at C, the robot goes behind the red human, (3) the planner needs to choose between the two unprocessed object based on cost evaluation, (4) the choice between the processed and unprocessed object can be done only by the symbolic planner.

The planner chooses for the robot to first bring the processed object to the green human (smaller number of actions), then, goes and get the unprocessed object at B after moving the orange box (as it is less disturbing for the red human) and brings it to the green human after the blue human has processed it.

VI. CONCLUSION

We have presented in this paper different improvements to a previously published algorithm, concerning the combination of symbolic and geometric planning in the context of human robot collaboration. We have provided details on how we handle the ramification problem by computing the actions side-effects and using the shared literals. We have also presented these improvements: (1) using shared literals as constraints to guide the geometric planner, (2) Adding requests to the geometric planner to asses the feasibility of future actions, (3) estimating accurately the action cost based on social rules and (4) using different alternatives of a geometric action for the same symbolic task.

In order to support these improvements, we implemented them on pick & place examples, however they can be used in other domains. In order to achieve this, new domain specific knowledge should be added, such as new shared literals, new cost computations and/or new virtual actions, but their usage would be similar.

We believe that this framework will provide latitude for even more improvements and for devising more elaborate techniques to reduce computation time and focus on the more promising alternatives. For instance, a way to extend our work would be to choose a backtracking point using information from both the geometric and symbolic contexts. As of now, the maximum allowed number of alternatives is fixed by the domain expert, while it could be computed or learned from the geometric and symbolic contexts.

TABLE I RESULTS

 I FOR THE PICK & PLACE EXAMPLE.

	30 runs(time in s)	Place	PlaceR	PlaceRGoal	PlaceRC
	Mean time(stdev)	44.3(6.1) 27(3.6)	23(2.7)	16.2(1.8)
	Nb tasks tried	67.5	11.6	9.7	8.6
	Nb alternatives	59.6	3.8	2.5	1.6

italic is used for the symbolic layer, bold is used for the geometric layer.

an object that can contain other objects, and that can be ignored by the collision checking when needed. The virtual objects are given to the system, each virtual object correspond to a set of objects it can contain.


Emmanuel Ferreira
email: emmanuel.ferreira@univ-avignon.fr

Grégoire Milliez
email: gregoire.milliez@laas.fr

Fabrice Lefèvre
email: fabrice.lefevre@univ-avignon.fr

Rachid Alami
email: rachid.alami@laas.fr

Users' Belief Awareness in Reinforcement Learning-based Situated Human-Robot Dialogue Management

Others can have a different perception of the world than ours. Understanding this divergence is an ability, known as perspective taking in developmental psychology, that humans exploit in daily social interactions. A recent trend in robotics aims at endowing robots with similar mental mechanisms. The goal then is to enable them to naturally and efficiently plan tasks and communicate about them. In this paper we address this challenge extending a state-of-the-art goal-oriented dialogue management framework, the Hidden Information State (HIS). The new version makes use of the robot's awareness of the users' belief in a reinforcement learning-based situated dialogue management optimisation procedure. Thus the proposed solution enables the system to cope with the communication ambiguities due to noisy channel but also with the possible misunderstandings due to some divergence among the beliefs of the robot and its interlocutor in a Human-Robot Interaction (HRI) context. We show the relevance of the approach by comparing different handcrafted and learnt dialogue policies with and without divergent belief reasoning in an in-house Pick-Place-Carry scenario by mean of user trials in a simulated 3D environment.

Introduction

When robots and humans share a common environment, previous works have shown how much enhancing the robot's perspective taking and intention detection abilities improves its understanding of the situation, and leads to more appropriate and efficient task planning and interaction strategies [START_REF] Breazeal | Using perspective taking to learn from ambiguous demonstrations[END_REF][START_REF] Breazeal | An embodied cognition approach to mindreading skills for socially intelligent robots[END_REF][START_REF] Milliez | A framework for endowing interactive robot with reasoning capabilities about perspective-taking and belief management[END_REF]. As part of the theory of mind, perspective taking is a widely studied ability in developmental literature. This broad term encompasses 1) perceptual perspective taking, whereby human can understand that other people see the world differently, and 2) conceptual perspective taking, whereby humans can go further and attribute thoughts and feelings to other people [START_REF] Baron-Cohen | Does the autistic child have a 'theory of mind[END_REF]. Tversky and al. [START_REF] Tversky | Why do speakers mix perspectives?[END_REF] explain to what extent switching between perspectives rather than staying in an egocentric position can improve the overall dialogue efficiency in a situated context. Therefore, to make robots more socially competent, some research aims to endow robots with this ability. Among others, Breazeal et al. [START_REF] Breazeal | Using perspective taking to learn from ambiguous demonstrations[END_REF] present a learning algorithm that takes into account information about a teacher's visual perspective in order to learn specific coloured buttons activation/deactivation patterns, and Trafton et al. [START_REF] Trafton | Enabling effective human-robot interaction using perspective-taking in robots[END_REF] use both visual and spatial perspective taking to find out the referent indicated by a human partner. In the present study, we specifically focus on a false belief task as part of the conceptual perspective taking. Formulated in [START_REF] Wimmer | Beliefs about beliefs: Representation and constraining function of wrong beliefs in young children's understanding of deception[END_REF], this kind of task requires the ability to recognize that others can have beliefs about the world that differ from the observable reality. Breazal et al. [START_REF] Breazeal | An embodied cognition approach to mindreading skills for socially intelligent robots[END_REF] proposed one of the first human-robot implementation and proposed some more advanced goal recognition skills relying on this false belief detection. In [START_REF] Milliez | A framework for endowing interactive robot with reasoning capabilities about perspective-taking and belief management[END_REF], a Spatial Reasoning and Knowledge component (SPARK) is presented to manage separate models for agent belief state and used to pass the Sally and Anne test [START_REF] Baron-Cohen | Does the autistic child have a 'theory of mind[END_REF] on a robotic platform. This test is a standard instance of false belief task where an agent has to guess the belief state of an other agent with a divergent belief mind state. The divergence in this case arises from modifications of the environment which one agent is unaware of and which are not directly observable, for instance displacement of objects hidden to this agent (behind another object for instance).

Considering this, to favour the human intention understanding and improve the overall dialogue strategy, we take benefit of the divergent belief management into the multimodal situated dialogue management problem. To do so, we rely on the Partially Observable Markov Decision Process (POMDP) framework. This latter is becoming a reference in the Spoken Dialogue System (SDS) field [START_REF] Young | The hidden information state model: A practical framework for pomdp-based spoken dialogue management[END_REF][START_REF] Thomson | Bayesian update of dialogue state: A pomdp framework for spoken dialogue systems[END_REF][START_REF] Pinault | Unsupervised clustering of probability distributions of semantic graphs for pomdp based spoken dialogue systems with summary space[END_REF] as well as in HRI context [START_REF] Roy | Spoken dialogue management using probabilistic reasoning[END_REF][START_REF] Lucignano | A dialogue system for multimodal humanrobot interaction[END_REF][START_REF] Milliez | Simulating human robot interaction for dialogue learning[END_REF], due to its capacity to explicitly handle parts of the inherent uncertainty of the information which the system (the robot) has to deal with (erroneous speech recognizer, falsely recognised gestures, etc.). In the POMDP setup, the agent maintains a distribution over possible dialogue states, the belief state, all along the dialogue course and interacts with its perceived environment using a Reinforcement Learning (RL) algorithm so as to maximise some expected cumulative discounted reward [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]. So our goal here is to introduce the divergence notion into the belief state tracking and add some means to deal with it in the control part.

The remainder of the paper is organised as follows. Section 2 gives some details about how an agent knowledge model can be maintained in a robotic system; in Section 3 our extension of a state-of-art goal-oriented POMDP dialogue management framework, the Hidden Information State (HIS), is presented to take into account users' beliefs state; in Section 4 the proposed Pick-Place-Carry false belief scenario used to exemplify the benefit of both taking account of the perspective taking ability and its integration in a machine learning scheme is introduced. In the same section, the current system architecture and the experimental setup employed are given. The user trial results obtained with a learnt and an handcrafted belief-aware system are compared in Section 5 with systems lacking perspective taking ability. Finally, in Section 6 we discuss some conclusions and give some perspectives.

Agent knowledge management

As mentioned in the introduction, the spatial reasoning framework SPARK is used for situation assessment and spatial reasoning. We will briefly recap here how it works, for further details please refer to [START_REF] Milliez | A framework for endowing interactive robot with reasoning capabilities about perspective-taking and belief management[END_REF]. In our system, the robot collects data about three different entities to virtually model its environment: objects, humans and proprioceptions (its own position, posture, etc.). Concerning objects, a model of the environment is loaded at startup to obtain the positions of static objects (e.g. walls, furnitures, etc.). Other objects (e.g. mug, tape, etc.) are considered as movable. Their positions are gathered using the robot's stereo vision. Posture sensors, such as Kinect, are used to obtain the position of humans. These perception data allow the system to use the generated virtual model for further spatial-temporal reasoning. As an example, the system can reason on why an object is not perceived any more by a participant and decide to keep its last known position if it recognizes a situation of occlusion, or remove the object from its model if there is none. Figure 1 (a) shows a field experiment with the virtual environment built by the system from the perception data collected and enriched by the spatial reasoner. The latter component is also used to generate facts about the objects relative position and agents' affordances. The relative position such as isIn, isNextTo, isOn are used for multimodal dialogue management as a way to solve referents in users' utterances, but also for a more natural dialogue description of the objects position in the robot's responses. Agents' affordances come from their ability to perceive and reach objects. The robot is calculating its own capability of perception according to the actual data it gets from the object position and recognition modules. For reachability, the robot computes if it is able to reach the object with its grasping joints.

To compute the human's affordances the robot applies its perspective taking ability. In other words, the robot has to estimate what is visible and reachable for the human according to her current position. For visibility, it computes which objects are present in a cone, emerging from human's head. If the object can be directly linked to the human's head with no obstacle and if it is in the field of the view cone, then it is assumed that the human sees the object and hence has knowledge of its true position. If an obstacle is occluding the object, then it won't be visible for the human. Concerning the reachability, a threshold of one meter is used to determine if the human can reach an object or not.

The facts generation feature allows the robot to get the information about the environment, its own affordances, and the human's affordances. In daily life, humans get the information about the environment through perception and dialogue. Using the perspective taking abilities of our robot, we can compute a model of each human's belief state according to what she perceived or what the robot has told her about the environment. Then two different models of the world are considered: one for the world state from the robot perception and reasoning and one for each human's belief state (computed by the robot according to what the human perceived). Each of these models is independent and logically consistent. In some cases, the robot and the human models of the environment can diverge. As an example, if an object O has a property P with a value A, if P's value changed to B and the human had no way to perceive it when it occurred, the robot will have the value B in its model (P(O) = B) while the human will still have the value A for the property P (P(O) = A). This value shouldn't be updated in the human model until the human is actually able to perceive this change or until the robot informs him. In our scenario, this reasoning is applied to the position property. We introduce here an example of false belief situation (fig. 1 (b)). A human sees a red book (RED BOOK) on the bedside table BT . She will then have this property in his belief state: P(RED BOOK) = BT . Now, while this human is away (has no perception of BT ), the book is swapped with an other brown one (BROWN BOOK) from the kitchen table KT . In this example, the robot explores the environment and is aware of the new position values. The human will keep this belief until she gets a new information on the current position of RED BOOK. This could come from actually seeing RED BOOK on the position KT or seeing that RED BOOK is not any more in BT (in which case the position property value will be updated to an unknown value). Another way to update this value is for the robot to explicitly inform the user of the new position.

In our system we mainly focused on position properties but this reasoning could be straightforwardly extended to other properties such as who manipulated an object, its content, temperature, etc. Obviously if this setup generalises quite easily to false beliefs about individual properties of elements of the world, more complex divergence configurations that might arise in daily interactions, for instance due to prior individual knowledge, still remain out of range and should be addressed by future complementary works.

Belief Aware Multimodal Dialogue Management

As mentioned earlier, an important aspect of the approach is to base our user belief state management on the POMDP framework [START_REF] Kaelbling | Planning and acting in partially observable stochastic domains[END_REF]. It is a generalisation of the fully-observable Markov Decision Process (MDP), that was first employed to determine an optimal mapping between situations (dialogue states) and actions for the dialogue management problem in [START_REF] Levin | Learning dialogue strategies within the markov decision process framework[END_REF]. We try hereafter to recall some of the principles of this approach pertaining to the modifications that will be introduced. More comprehensive descriptions should be sought in the cited papers. This framework maintains a probability distribution over dialogue states, called belief states, assuming the true one is unobservable. By doing so, it explicitly handles parts of the inherent uncertainty on the information conveyed inside the Dialogue Manager (DM) (e.g. error prone speech recognition and understanding processes). Thus, POMDP can be cast as a continuous space MDP. The latter is a tuple < B, A, T, R, γ > , where B is the belief state space (continuous), A is the discrete action space, T is a set of Markovian transition probabilities, R is the immediate reward function, R : B × A × B → ℜ and γ ∈ [0, 1] the discount factor (discounting long term rewards). The environment evolves at each time step t to a belief state b t and the agent picks an action a t according to a policy mapping belief states to actions, π : B → A. Then the belief state changes to b t+1 according to the Markovian transition probability b t+1 ∼ T (.|b t , a t ) and, following this, the agent received a reward r t = R(b t , a t , b t+1 ) from the environment. The overall problem of this continuous MDP is to derive an optimal policy maximising the reward expectation. Typically the averaged discounted sum over a potentially infinite horizon is used, ∑ ∞ t=0 γ t r t . Thus, for a given policy and start belief state b, this quantity is called the value function:

V π (b) = E[∑ t≥0 γ t r t |b 0 = b, π] ∈ ℜ B . V * corresponds
to the value function of any optimal policy π * . The Q-function may be defined as an alternative to the value function. It adds a degree of freedom on the first selected action, Q π (b, a) = E[∑ t≥0 γ t r t |b 0 = b, a 0 = a, π] ∈ ℜ B×A . As well as V * , Q * corresponds to the action-value function of any optimal policy π * . If it is known, an optimal policy can be directly computed by being greedy according to

Q * , π * (b) = arg max a Q * (b, a)∀b ∈ B.
However, real-world POMDP problems are often intractable due to their dimensionality (large belief state and action spaces). Among other techniques, the HIS model [START_REF] Young | The hidden information state model: A practical framework for pomdp-based spoken dialogue management[END_REF] circumvents this scaling problem for dialogue management by the use of two main principles. First, it factors the dialogue state into three components: the user goal, the dialogue history and the last user act (see Figure 2). The possible user goals are then grouped together into partitions on the assumption that all goals from the same partition are equally probable. These partitions are built using the dependencies defined in a domain-specific ontology and the information extracted all along the dialogue from both the user and the system communicative acts. In the standard HIS model, each partition is linked to matching database entities based on its static and dynamic properties that corresponds to the current state of the world (e.g. colour of an object vs spatial relations like isOn). The combination of a partition, the associated dialogue history, which corresponds here to a finite state Fig. 2: Overview of the HIS extension to take into account divergent belief. machine that keeps track of the grounding status for each convoyed piece of information (e.g. informed or grounded by the user), and a possible last user action forms a dialogue state hypothesis. A probability distribution b(hyp) over the most likely hypotheses is maintained during the dialogue and this distribution constitutes the POMDP's belief state. Second, HIS maps both the belief space (hypotheses) and the action space into a much reduced summary space where RL algorithms are tractable. The summary state space is the compound of two continuous and three discrete values. Continuous values are the probabilities of the two-first hypotheses b(hyp1) and b(hyp2) while the discrete ones, extracted from the top hypothesis, are the type of the last user act (noted last uact), a partition status (noted p-status) database matching status related to the corresponding goal and a history status (noted h-status).

Likewise system dialogue acts are simplified in a dozen of summary actions like offer, execute, explicit-confirm and request. Once the summary actions are ordered by their Q(b, a) scores in descending order by the policy, an handcrafted process checks if the best scored action is compatible with the current set of hypotheses (e.g. for the confirm summary act this compatibility test consists in checking if there is something to confirm in the top hypothesis). If they are compatible, an heuristic-based method maps this action back to the master space as the next system response. If not, the process is pursued using the next best scored summary action until a possible action is found.

The standard HIS framework can properly handle misunderstandings due to noise in the communicative channel. However, misunderstandings can also be introduced in cases where the user has false beliefs, impacting negatively her communicative acts. HIS has no dedicated mechanism to deal with such a situation and so it should react as in front of a classical uncertainty by asking the user to confirm hypotheses until the request can match the reality, although it could have be resolved since the first turn. Therefore having an appropriate mechanism should improve the quality and efficiency of the dialogue, preventing user to pursue her goal with an erroneous statement.

So, as illustrated in Figure 2 and highlighted with the orange items, we propose to extend the summary belief state with an additional status, the divergent belief status (noted d-status), and an additional summary action, inform divergent belief. The d-status is employed to trigger the presence of false belief situations by matching the top partition with user facts compiled by the system (see Sec. 2) and as such trying to highlight some divergences between the user and the robot points of view. Both the user and the robot facts (from the belief models, not to be mistaken with the belief state related to the dialogue representation) are considered as part of the dynamic knowledge resource and are maintained independently of the internal state of the system with the techniques described in Sec. 2. Here we can observe in Figure 2 that the top partition is about a book located on the bedside table. In the robot model of the world (i.e. robot facts) this book is identified as a unique entity, RED BOOK, and p-status is set to unique accordingly. However, in the user model it is identified as BROWN BOOK. This situation can be considered as divergent and p-status is set to unique too because there is one possible object that corresponds to that description in the user model. In this preliminary study d-status can only be unique or non-unique. Further studies may consider more complex cases. The new summary action is employed for appropriate resolution and removal of the divergence. The (real) communicative acts associated to this (generic) action relies on expert design. In this first version, if this action is compatible with the current hypotheses and thus picked up by the system, it explicitly informs the user of the presence and the nature of the divergence. To do so, the system uses a deny dialogue act to inform the user about the existence of a divergent point of view and let the user agree on the updated information. Consequently, the user may pursue its original goal with the correct property instead of the obsolete one. This process is also illustrated in Figure 2 when the inform divergent belief action is mapped back to the master space.

Scenario & Experimental Setup

In order to illustrate the robot's ability to deal with user's perspective, an adapted Pick-Place-Carry scenario is used as test-bed. The robot and the user are in a virtual flat with three rooms, in which there are different kinds of objects varying in terms of colour, type, and position (e.g. blue mug on the kitchen table, red book on the living room table, etc.). The user interacts with the robot using unconstrained speech (Large Vocabulary Speech Recognition) and pointing gestures to ask the robot to perform some specific object manipulation tasks (e.g. move the blue mug from the living room table to the kitchen table). The multimodal dialogue is used to solve ambiguities and to request missing information until task completion (i.e. full command execution) or failure (i.e. explicit user disengagement or wrong command execution). In this study, we specifically focus on tasks where divergent beliefs are prone to be generated as in the Sally and Anne test: a previous interaction has led the user to think that a specific object O is located at A which is out of her view, and an event has changed the object position from A to B without user's awareness. For example, a change performed by another user (or by the robot) without the presence of the first one. Thereby, if the user currently wants to perform a manipulation involving O she may do so using her own believed value (A) of the position property in her communicative act.

Concerning the simulation, the setup of [START_REF] Milliez | Simulating human robot interaction for dialogue learning[END_REF] is applied to enable a rich multimodal HRI. Thus, the open-source robotics simulator MORSE [START_REF] Echeverria | Modular open robots simulation engine: Morse[END_REF] is used which provides a realistic rendering through the Blender Game Engine, a wide range support of middleware (e.g. ROS, YARP), and proposes reliable implementations of realistic sensors and actuators which ease the integration on real robotic platforms. It also provides the operator with an immersive control of a virtual human avatar in terms of displacement, gaze, and interactions on the environment, such as object manipulation (e.g. grasp/release an object). This simulator is tightly coupled with the multimodal dialogue system, with the overall architecture given in Figure 3.

In the chosen architecture, the Google Web Speech API 1 for Automatic Speech Recognition (ASR) is combined with a custom-defined grammar parser for Spoken Language Understanding (SLU). The spatial reasoning module, SPARK, is responsible for both detecting the user gestures and generating the per-agent spatial facts (see Sec. 2) used to dynamically feed the contextual knowledge base and allowing the robot to reason over different perspectives of the world. Furthermore, we also make use of a static knowledge base containing the list of all available objects (even those not perceived) and their related static properties (e.g. color). The Gesture Recognition and Understanding (GRU) module catches the gesture-events generated by SPARK during the course of the interaction. Then, a rule-based fusion engine, close to the one presented in [START_REF] Holzapfel | Implementation and evaluation of a constraintbased multimodal fusion system for speech and 3d pointing gestures[END_REF], temporally aligns the monomodal inputs (speech and gesture) and merges them to convey the list of possible fused inputs to the POMDP-based DM, with speech considered as the primary modality.

The DM implements the extended HIS framework described in Sec. 3. For the reinforcement learning setup, the sample-efficient KTD-SARSA RL algorithm [START_REF] Daubigney | A comprehensive reinforcement learning framework for dialogue management optimization[END_REF] in combination with the Bonus Greedy exploration scheme enables online learning of dialogue strategy from scratch, as in [START_REF] Ferreira | Expert-based reward shaping and exploration scheme for boosting policy learning of dialogue management[END_REF]. A reward function is defined to penalise the DM by -1 for each dialogue turn and give it a +20 if the right command is performed at the end of the interaction, 0 otherwise. To convey the DM action back to the user, a rule-based fission module is employed that splits the high level DM decision into verbal and non-verbal actions. The robot speech outputs are generated by chaining a template-based Natural Language Generation (NLG) module, which converts the sequence of concepts into text, to a Text-To-Speech (TTS) component based on the commercial Acapela TTS system2 . A Non-verbal Behaviour Planning and Motor Control (NVBP/MC) module produces robot postures and gestures by translating the non-verbal actions into a sequence of abstract actions such as grasp, moveTo, release which are then executed in the simulated environment.

In this study we intend to assess the benefit of introducing the divergent belief management into the multimodal situated dialogue management problem. Thereby, the scenarios of interest require some situations of divergent beliefs between the user and the robot. In real setup those scenarios often need a long term interaction context tracking. To bypass this time consuming process in our evaluation setup, we directly propose a corrupted goal to the user at the beginning of her interaction. So, a false belief about the location value was automatically added concerning an object not visible from the human point of view. Although the situation is artificially generated, the same behaviour can be obtained with the spatial reasoner if the robot performs an action in self-decision mode, or if another human corrupts the scene. Thereby, this setup was used to evaluate the robot's ability to deal with both classical (CLASSIC) and false belief (FB) object manipulation tasks. To do so, we compare the beliefaware learnt system performance (noted BA-LEARNT hereafter) to an handcrafted one (noted BA-HDC), and with two other similar systems with no perspective taking ability (noted LEARNT and HDC respectively). The handcrafted policies make use of expert rules based on the information provided by the summary state to pick the next action to perform (deterministic). They are not considered as the best possible handcrafted policies but as robust enough to manage correctly an interaction with real users. The learnt policies were trained in an online learning settings using a small set of 2 expert users which first performed 40 dialogues without FB tasks and 20 more as a method-specific adaptation (LEARNT with CLASSIC tasks vs BA-LEARNT with FB tasks). In former works we have shown the possibility to learn efficient policies with few tens of dialogue samples, due to expert users better tolerance to poor initial performance combined with more consistent behaviours during interactions [START_REF] Ferreira | Social signal and user adaptation in reinforcement learning-based dialogue management[END_REF].

In the evaluation setup, 10 dialogues for the four proposed system configurations (the learnt policies were configured to act greedily according to the value function) were recorded from 6 distinct subjects (2 females and 4 males, around 25yo on average) who interacted with all configurations (within-subjects study), so 240 dialogues in total. 30% of the performed dialogues involve FB tasks. No user had knowledge of the current system configurations and they were proposed in random order to avoid any prior effect. At the end of each interaction, users evaluated the system in terms of task completion with an online questionnaire. Table 1: System performance on classic (CLASSIC), false belief (FB) and all (ALL) tasks in terms of average cumulative discounted reward (Avg.R), average dialogue length in terms of system turns (Length) and average success rate (SuccR).

Results

HDC

Table 1 is populated with the performance obtained by the four system configurations discussed above considering CLASSIC and FB tasks. These results are first given in terms of mean discounted cumulative rewards (Avg.R). According to the reward function definition, this metric expresses in a single real value the two variables of improvement, namely the success rate (accuracy) and the number of turns until dialogue end (time efficiency). However, both metrics are also presented for convenience. The results in Table 1 were gathered in test condition where no exploration of the RL method is allowed. Thus, they basically consist of a mere average over the 60 performed dialogues for each method and metric.

The differences observed between the LEARNT/BA-LEARNT and the HDC/BA-HDC on the overall performance (row ALL) shows the interest of considering RL methods rather than handcrafted policies. Indeed, only 60 training dialogues are enough to outperform both handcrafted solutions. On CLASSIC tasks the performance between LEARNT and BA-LEARNT as well as between HDC and BA-HDC must be considered similar. Thus, the divergent belief resolution mechanism doesn't seem to impact the dialogue management when divergent belief situations do not appear. For BA-HDC this statement could be expected (in lack of false belief, the rules are the same as HDC). However for BA-LEARNT the tested policy is learnt and the action assignment process is optimized with an additional degree of complexity (larger state/action space than in LEARNT), so a loss could have been observed. The performances between LEARNT and BA-LEARNT and respectively between HDC and BA-HDC on FB tasks appear in favour of the BA-systems (both show a higher success rate and a slightly more time efficient dialogue management process -average gain of 1 turn). However the quantitative comparison between the system configurations is not ensured to be relevant due to the relatively high confidence interval on considered metrics (e.g. success rate confidence interval for row FB is around 0.2 for all system configurations). Two main reasons account for this status quo. First, a limited amount of observations involving the different system configurations (due to experimental cost). Second, the expected marginal gain in terms of the considered metrics. Indeed, the current system is learnt on some overall task completion and efficiency criterion. However solving divergent belief situations in a pick and place scenario can not be considered a critical factor influencing these criterion greatly but just a way to cope with an additional (not dominant) degree of uncertainty and to improve user experience and naturalness of the interaction with the embodied agent. To have better insights on what the main differences between the four dialogue strategies are we also performed a qualitative study. In this study we precisely identify the behavioural differences due to introducing a FB handling mechanism in a learning setup. Overall, it is observed that confirmation acts (e.g. confirm, offer) are more accurate and less frequent for the two learnt methods. For instance, when the learnt systems are confident on the top object manipulation hypothesis they predominantly performed the command directly rather than trying to check its validity further as in the handcrafted versions. In Table 2 two dialogue samples extracted from the evaluation dataset illustrate the differences between non-BA and BA dialogue management on the same FB task (here a red book was interchanged with a brown one). If the belief divergence problem is not explicitly taken into account (as in (a)) the DM can be constrained to deal with an additional level of misunderstanding (see (b) from R 2 to U 3 ). We can also see in (b) that the non-BA system was able to succeed FB tasks (explaining the relative high LEARNT performance on FB tasks). Indeed, if the object is clearly identified by the user (e.g. color and type) the system can release the constraint of the false position and thus is able to make an offer on (execute) the "corrected" form of the command involving the true object position. Concerning the main differences between BA-LEARNT and BA-HDC, we observed a less systematic usage of the inform divergent belief act in the learnt case. BA-LEARNT first tries to reach a high confidence on the true presence of the object involved in the belief divergence in the user goal. Furthermore, BA-LEARNT, like LEARNT, has learnt alternative mechanisms to fulfil FB tasks such as direct execution of the user command (which also avoids misunderstanding) when the convoyed piece of information seems to be sufficient to identify the object.

Conclusion

In this paper, we described how a user belief realtime tracking framework can be used along with a multimodal POMDP-based dialogue management. The evaluation of the proposed method with real users confirms that this additional information helps to achieve more efficient and natural task planning (and does not harm handling of normal situations). Our next step will be to integrate the multimodal dialogue system on the robot and carry out evaluations in real setting to uphold our claims in an fully realistic configuration.

Fig. 1 :

 1 Fig. 1: (a) Real users in front of the robot (right) and the virtual representation built by the system (left). (b) Divergent belief example with belief state.

Fig. 3

 3 Fig. 3 Architecture of the multimodal and situated dialogue system.

R 1 :

 1 Can I help you? U 1 : Bring me the book on my bedside tableR 2 :The brown book is not on the bedside table, it has been moved to the kitchen.

		R 2 : Do you want the red one?
		U 2 : No, the brown book.
		R 3 : There is no brown book in your bedroom
	U 2 : Ok, bring it to me	but there is one in the kitchen
	R 3 : I will give you the brown book that is on	U 3 : Are you sure? Well, bring me that one.
	the kitchen table	R 4 : I will give you the brown book that is on
	(a)	the kitchen table
		(b)

Table 2 :

 2 Dialogue examples with (a) and without (b) divergent belief reasoning in the case of an unknown (from the user's point of view) interchange between a red and a brown book.

https://www.google.com/intl/en/chrome/demos/speech.html

http://www.acapela-group.com/index.html

Acknowledgements This work has been partly supported by the French National Research Agency (ANR) under project reference ANR-12-CORD-0021 MaRDi.