Sara Bouraine

Thierry Fraichard

Ouahiba Azouaoui

Hassen Salhi

Hassen Salhi Passively

Safe Partial Motion

Passively Safe Partial Motion Planning for Mobile Robots with Limited Field-of-Views in Unknown Dynamic Environments

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

Passively Safe Partial Motion Planning for Mobile Robots with Limited Field-of-Views in Unknown Dynamic Environments S. Bouraine † , Th. Fraichard ‡ , O. Azouaoui † and Hassen Salhi ⋆ Abstract-This paper addresses the problem of planning the motion of a mobile robot with a limited sensory field-of-view in an unknown dynamic environment. In such a situation, the upper-bounded planning time prevents from computing a complete motion to the goal, partial motion planning is in order. Besides the presence of moving obstacles whose future behaviour is unknown precludes absolute motion safety (in the sense that no collision will ever take place whatever happens) is impossible to guarantee. The stance taken herein is to settle for a weaker level of motion safety called passive motion safety: it guarantees that, if a collision takes place, the robot will be at rest. The primary contribution of this paper is PASSPMP, a partial motion planner enforcing passive motion safety. PASSPMP periodically computes a passively safe partial trajectory designed to drive the robot towards its goal state. Passive motion safety is handled using a variant of the Inevitable Collision State (ICS) concept called Braking ICS, i.e. states such that, whatever the future braking trajectory of the robot, a collision occurs before it is at rest. Simulation results demonstrate how PASSPMP operates and handles limited sensory field-of-views, occlusions and moving obstacles with unknown future behaviour. More importantly, PASSPMP is provably passively safe.

I. INTRODUCTION

Nowadays, the development of autonomous mobile robots is the key issue of several new applications from industry, public transportation to spatial and underwater exploration. Such applications take place in the real world where the term real world implies that:

1) The environment is dynamic and uncertain, it features fixed and moving obstacles whose future behaviour is unknown.

2) The robot has only a partial knowledge of its surroundings because of its sensory limitations. In order to carry out its task successfully in such situations, an autonomous mobile robot should be able to navigate around while guaranteeing its safety and that of its environment. As of now, the constraints imposed on navigation in dynamic environments are clearly established. As per [START_REF] Fraichard | Iterative motion planning and safety issue[END_REF], they can be summarized as follows:

In a dynamic environment, one has a limited time to make a motion decision, one has to reason about the future evolution of the environment and do so with an appropriate lookahead 1 .

From a motion safety point of view now, the presence of moving obstacles whose future behaviour is unknown precludes absolute motion safety (in the sense that no collision will ever take place whatever happens) is impossible to guarantee [START_REF] Fraichard | Will the driver seat ever be empty?[END_REF]. To address that issue, authors such as [START_REF] Macek | Towards safe vehicle navigation in dynamic urban scenarios[END_REF] have advocated the introduction of weaker levels of motion safety level arguing that it is better to guarantee less than to guarantee nothing. It is precisely the position we took in [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF] where it was settled for a motion safety level called passive motion safety that guarantees that, if a collision takes place, the robot will be at rest. [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF] introduced a navigation scheme called PASSAVOID for mobile robots with limited field-of-views placed in unknown dynamic environments. PASSAVOID is reactive in nature, it operates with a given time step and its purpose is to compute the control that will be applied to the robot at the next time step. [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF] formally establishes that PASSAVOID is provably passively safe.

This paper builds upon [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF] and presents an extension of PASSAVOID called PASSPMP. PASSPMP operates according to the Partial Motion Planning (PMP) principle that was introduced in [START_REF] Petti | Safe motion planning in dynamic environments[END_REF]. PMP is motion planning sheme that fulfills the constraints imposed by dynamic environments (limited decision time), and attempts to bridge the gap between reactive approaches (that computes the control to apply at the next time step) and deliberative motion planning approaches (that seeks to compute a complete motion to the goal). At each cycle, PMP expands a search tree rooted at the current state of the robot and when the time available is over, PMP extracts from the tree the best partial motion towards the goal computed so far. The process is repeated until the goal is reached. PASSPMP is based upon the Rapidlyexploring Random Tree (RRT) algorithm [START_REF] Lavalle | Randomized kinodynamic planning[END_REF]. PASSPMP can handle limited field-of-views, occlusions and unknown future behavior of the obstacles. Because, it is PMP-based, PASSPMP has more insights than PASSAVOID. However, similarly to PASSAVOID, PASSPMP is provably passively safe.

The paper is organized as follows. In Section II, an overview of the most relevant works is presented. Section III explains the passive motion safety concept that must be guaranteed by PASSPMP which is later described in Section IV. Finally, the simulation results are given in Section V.

II. RELATED WORKS

Motion safety have been analyzed thanks to the Inevitable Collision States (ICS) concept developed in [START_REF] Fraichard | Inevitable collision states. a step towards safer robots?[END_REF]. An ICS is a state for which, no matter what the future trajectory of the robot is, a collision eventually occurs. The key to motion safety is clearly to stay away from ICS. However characterizing the ICS set corresponding to a given current situation is in general challenging since it requires information about the future evolution of the environment with a possibly infinite lookahead. In light of the ICS concept, it appears that, although the robotics literature is rich in works concerned with collision avoidance and safe navigation, most of them do not offer an explicit formulation of the safety guarantee they provide or the conditions under which they must operate [START_REF] Fraichard | A short paper about motion safety[END_REF]. Among them, the most interesting are those that acknowledge the difficulty of getting a meaningful characterization of the ICS set in real-world situation. To cope with that issue, these approaches relies upon a relaxation of the ICS concept: they seek to guarantee that the robot can only be in states where it is possible to execute an evasive trajectory, e.g. a braking manoeuvre for a car or a circling manoeuvre for a plane. Example of this kind of approaches can be found in [START_REF] Hsu | Randomized kinodynamic motion planning with moving obstacles[END_REF], [START_REF] Petti | Safe motion planning in dynamic environments[END_REF], [START_REF] Bekris | Greedy but safe replanning under kinodynamic constraints[END_REF], [START_REF] Seder | Dynamic window based approach to mobile robot motion control in the presence of moving obstacles[END_REF].

In order to address the uncertainty that prevails in the real-world, in particular the uncertainty concerning the future behaviour of the moving obstacles, probabilistic version of the ICS concept have been proposed, e.g. [START_REF] Althoff | Probabilistic collision state checker for crowded environments[END_REF] and [START_REF] Bautin | Inevitable collision states: a probabilistic perspective[END_REF]. Such approaches are interesting but they do not allow strict motion safety guarantee, they allow instead to minimize the risk.

Concerning sensory limitations, there are only a few research works taking them into account. For instance, the occlusion problem, i.e. the existence of regions that are hidden by other obstacles, is addressed in a coarse manner in [START_REF] Sadou | Occlusion in obstacle detection for safe navigation[END_REF] and in a more principled manner in [START_REF] Chung | Safe navigation of a mobile robot considering visibility of environment[END_REF]. The occlusion and the limited field-of-view problems are addressed in [START_REF] Fraichard | Inevitable collision states. a step towards safer robots?[END_REF] and [START_REF] Madhava Krishna | Safe proactive plans and their execution[END_REF]. [START_REF] Fraichard | Inevitable collision states. a step towards safer robots?[END_REF] addresses the case of a mobile robot moving in a static environment; its approach is general and ICS-based. While [START_REF] Madhava Krishna | Safe proactive plans and their execution[END_REF] considers dynamic environments, it does so primarily with a path-velocity decomposition perspective [START_REF] Kant | Toward efficient trajectory planning: the pathvelocity decomposition[END_REF].

PASSPMP, the contribution of this paper is an extension of PASSAVOID [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF]. PASSPMP deals with limited field-of-views, occlusions and unknown future behavior of the obstacles. Because, it is PMP-based, PASSPMP is not purely reactive, it has more insights. However, similarly to PASSAVOID, PASSPMP is provably passively safe.

III. PASSIVE MOTION SAFETY

Generally, absolute motion safety is impossible to guarantee in dynamic environments given the unknown future behavior of moving objects and with a robot having a limited field-of-view (presence of occlusions, unseen objects, etc.). These harsh constraints impose an alternative solution which is to settle for weaker level of motion safety by guaranteeing at least, if a collision takes place the robot will be at rest. This form of motion safety is dubbed passive motion safety.

Introducing this level of motion safety gives a relaxation to the original ICS concept of [START_REF] Fraichard | Inevitable collision states. a step towards safer robots?[END_REF] namely the braking ICS concept introduced in [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF]. A braking ICS (denoted ICS b ) is a state for which no matter what the future trajectory of the robot is, a collision takes place before the robot is at rest. With duality to passive motion safety concept, a state which is braking ICS-free is passively safe (p-safe).

In [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF], an efficient Braking ICS-Checker (called ICS b -CHECK) was designed, it checks whether a given state trajectory is braking ICS or not (i.e. p-safe or not) for a given model of the future. This algorithm is used in the passively safe planner (PASSPMP) (presented in §IV) guaranteeing the generation of p-safe partial trajectories.

However, Braking ICS is defined given an appropriate look-ahead (time horizon) because motion safety guarantee requires to reason about the future evolution of the environment. For absolute motion safety, the lookahead is infinite which is impossible to verify unless the environment is a priori known. But for passive motion safety a finite lookahead called time horizon should be set.

If T h is a valid lookahead, then computing ICS b requires to consider the model of the future up to this time.

This notion of lookahead will step in PASSPMP cycles, where an updated model of the future is required.

IV. PASSIVELY SAFE PLANNING

In this paper, the aim is to build a passively safe trajectory from an initial state to a given goal, verifying both safety criterion and best convergence towards the goal. The proposed method uses a replanning process that interleaves planning with execution so that the robot may compute partial plans leading to a passively safe partial motion planner. This planner is developed for a mobile robot A with a limited field-of-view placed in an unknown dynamic environment. A's motion is governed by differential equations of the form:

ṡ = f (s, u) (1)
where s ∈ S is the state of A, ṡ its time derivative and u ∈ U a control. S and U are respectively the state space and the control space of A.

This planner aims to drive A from its initial position until it reaches the goal guaranteeing passive motion safety no matter what happens in the environment. In other words, it guarantees two conditions:

1) If a collision takes place, it is guaranteed that A will be at rest when it occurs (passive safety). 2) A chooses the optimal trajectory to reach the goal. To summarize, our purpose is to design a passively safe navigation scheme based on a PMP and guaranteeing passive safety. To do so, a number of points must be verified:

• Kinematic and dynamic constraints of the robot.

• Reasoning about the future.

• React for a time horizon.

• Passive safety guarantee (based on ICS b -CHECK).

• Drive A to the goal.

A. Partial Motion Planning (PMP) Principle

Robot navigation requires the interleaving of sensing, decision-making and execution. In an unknown and dynamic environment, it is necessary to continuously sense the environment and regularly update the world model upon which navigational decisions are made. Likewise, the decisionmaking module must be called frequently and has a finite The set of these trajectories drives the robot to the goal. Irrespective of how the decision-making module works, the bottom line is that a trajectory must be available at each decision-making cycle.

The timeline of the decision-making process of A is illustrated in Fig. 1. At time t 0 , A is in state s 0 , it is currently executing a trajectory Π 0 that will drive it to the state s 1 at time t 1 , the next cycle time. Let W(t 0 ) denotes the world model which is available at time t 0 . During the time interval [t 0 , t 1 ], the decision-making module has to compute the trajectory Π 1 that will be executed during the next cycle time [t 1 , t 2 ]. At time t 1 , the process is repeated based on W(t 1 ), the updated model of the environment, and so forth.

From a passive motion safety perspective, the braking ICS concept brings to light two things: the first one is that, it is not sufficient to consider that all the trajectories Π i are collision-free; they must be braking ICS-free meaning that, at each time instant, A must always be in a state which is not a braking ICS (if a collision occurs, the robot is at rest). The second one is that, braking ICS-ness is always defined wrt the used world model (in particular the model of the future).

Regarding PMP process above, it should be noted that Π 1 is computed using the world model W(t 0 ). It can be computed so as to be braking ICS-free but if at time t 1 (when the updated world model W(t 1 ) is available), s 2 turns out to be a braking ICS wrt W(t 1 ), collision occurs. This remark highlights the fact that reasoning about the future evolution of the environment is critical when it comes to motion safety in dynamic environments. Therefore, reasoning about a limited time horizon (lookahead) (T h ) during which safety is guaranteed, is required. In this case, the world model W(t 0 ) will be valid during the time interval

[t 0 , t 1 [∪[t 1 , T h ] (with T h > t 2 )
. Consequently, it is always guaranteed that s 2 is braking ICS-free. Introducing this notion of passive motion safety in PMP process leads to the new version PASSPMP, described in next section.

B. Passively Safe PMP (PASSPMP)

PASSPMP is a partial motion planner that operates within (2) convergence towards the desired goal. This trajectory has an execution time duration δ e . However, only the part corresponding to the duration δ cycle is executed because at the end of each cycle a new computed partial trajectory is available (see Fig. 2). δ cycle should be set carefully in a way that passive safety still always guaranteed. The planning cycle has to return a decision within a bounded time, which depends upon the current model of the environment (model of the future). It is the minimum time to collision named decision time δ d . Thus, the time cycle must be always lower than this decision time:

δ cycle < δ d (2)
Assuming that A is equipped with range sensors such as laser telemeters or range cameras, it can only perceive a subset of the workspace WS; this subset is A's field-of-view; its shape is arbitrary and its range is 360 • . It represents the region of WS which is free of objects at the sensing time while the remaining regions of WS represent the space where there might be objects that can be fixed or moving, seen or unseen.

Motion safety requires reasoning about the future motion of the objects in the environment. As it is assumed that A cannot distinguish between fixed and moving objects (every object observed is treated as a potentially moving object) and that it has no information about their future behavior, the model of the future used herein is conservative: given an upper-bound on the velocity of the objects, every point in the region outside the field-of-view is modeled as a disc that grows as time passes, i.e. a cone in spacetime. However, as time passes the region of WS occupied by this growing discs grows too. This is why, the model of the future may be valid up to a finite time; hence an appropriate time horizon (T h ) should be set.

The braking ICS concept considers braking trajectories ũb of finite duration t b , with t b the braking time of ũb (braking trajectory definition is given in [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF]). t b is the ratio of the robot's linear velocity and its maximum linear acceleration.

For an arbitrary subset E of the whole set of possible braking trajectories, a finite time horizon T h exists:

T h = max ũb ∈E {t b } (3)
For motion safety guarantee, it suffices to consider the model of the future up to time T h . This time denotes how far into the future, objects behavior has been modeled and predicted.

As the executed trajectory during the current PASSPMP's cycle is based on the previous PASSPMP's cycle result, the decision time δ d cannot exceed the time horizon (otherwise A would run out of a valid plan for the next execution cycle). However, there is no lower bound for the decision time, it depends on the complexity of the motion planning exploration itself. In fact, we set:

δ d << T h (4)
Besides, to guarantee that the executed trajectory is still valid, the following condition must be verified:

δ d + δ e ≤ T h (5)
where δ e is the execution time. As a conclusion, PASSPMP cycle is set as a fixed period of time in order to regularly get an update of the environment. Given equations 2 and 5, and knowing that the world model W is valid during the time interval [t k , t k+1 ] ∪ [t k+1 , T h ] (with T h > t k+2 and T h > 2δ cycle ), the following condition could be set to guarantee passive motion safety:

δ cycle < min(δ d , 1 2 T h ) (6)
This condition guarantees that the time horizon is still valid for both trajectory planning and execution. All the above conditions are important for safety guarantee in the PASSPMP process. However, guarantying passive motion safety requires proving that a collision will never occur while A is moving. Thus, it must be proved that, at each time cycle PASSPMP would always find a partial trajectory that is p-safe. To that end, some properties are required and henceforth introduced in what follow. Let first define what is a p-safe state.

Def. 1 (P-Safe State): A state s 0 is passively safe or psafe (it is not a braking ICS) if it exists at least one braking trajectory ũb starting at s 0 which is collision-free until A stops.

Property 1 (P-Safe trajectory): For a given state trajectory Π between s 0 and s j , if [START_REF] Fraichard | Iterative motion planning and safety issue[END_REF] the state trajectory between s 0 and s j is collision-free (with respect to the conservative model of the future) and (2) s j is p-safe, then the states belonging to Π are p-safe, therefore, Π is p-safe.

Proof: At first, we define a state s i , with 0 < i < j belonging to a state trajectory between s 0 and s j , Let assume that: (1) s 2 is p-safe, i.e. it exists at least one braking trajectory starting at s 2 which is collision-free until A has stopped. (2) s 1 is not p-safe, i.e. whatever existing braking trajectories, collision occurs (no collision-free braking trajectory). However, as the state trajectory between s 0 and s j is collision-free and there exists a braking trajectory for the state s 2 , starting from s 1 , A can brake down without a collision occurs. Therefore, s 1 is p-safe: contradiction with (2).

Property 2 (Passive Safety Guarantee): If the state s 0 is p-safe then there exists at least one p-safe state trajectory that drives A through states that are also p-safe.

Proof: According to definition 1, if s 0 is p-safe then there exists at least one braking trajectory ũb (between s 0 and s j ) which is collision-free until A stops. At the state s j , A is at rest then s j is p-safe. Applying property 1, since the braking trajectory ũb is collision-free and s j is p-safe, ũb is henceforth p-safe and every state of this trajectory is also p-safe. Let ũb is a special case of possible trajectories, then it is proved that there exists a p-safe trajectory.

Property 2 allows designing a version of PASSPMP that is passively safe i.e. at each planning cycle, it is guaranteed that PASSPMP can plan a p-safe partial trajectory to be executed in next cycle. It is an iterative process, repeated until A reaches its goal.

Algorithm 1 describes PASSPMP behavior in a k cycle.

Algorithm 1 PASSPMP.

Input: Model of the future W(t k , T h ), goal s g , partial trajectory Π k to execute. Output: The selected partial trajectory Π k+1 to execute in cycle k + 1.

1: TREE=EXPLORE STATE TIME(W(t k , T h ),s k+1 ); // Explore the state time space of A, t ∈ [t k+1 , t k+2 ] 2: Π k+1 =SELECT BEST PTRAJ(TREE,s g ); //Select the best partial trajectory.

Algorithm 1 takes as input the model of the future W(t k , T h ) which is available at time t k and valid up to time T h (i.e. sufficient to plan the partial trajectory Π k+1 during the current cycle k and to execute it during the next cycle k + 1). The algorithm takes also as input the goal to reach, and the partial trajectory computed in the previous cycle k -1 to be executed during the current cycle. PASSPMP algorithm operates by first exploring the state time space of A (with t ∈ [t k+1 , t k+2 ]) through the function EXPLORE STATE TIME (line #1 of the algorithm). To do so, a diffusion technique is used, by extending a tree rooted at the state s(t k+1 ) (with t k+1 = t k + δ cycle ). For reason of simplicity and facility of adaptation to a partial concept, the adopted technique is inspired from RRT proposed in [START_REF] Lavalle | Randomized kinodynamic planning[END_REF]. As passive safety must be a criterion in trajectories selection, the state time space is explored using what we called p-safe RRT (which is detailed below). During this step, the set of partial trajectories are computed and then defined with respect to passive safety guarantee (based on ICS b -CHECK algorithm [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF]). In step #2 of the algorithm, the function SELECT BEST PTRAJ selects the best partial trajectory verifying passive safety criterion and convergence towards the goal.

The algorithm is repeated iteratively until reaching the goal (s g ).

1) p-safe RRT: In order to explore different possible trajectories, a tree is grown in the state time space of A using RRT [START_REF] Lavalle | Randomized kinodynamic planning[END_REF], where nodes represent robot states that are related with trajectory primitives. In PASSPMP concept, the expansion is done passively safe, hence the new version of RRT algorithm namely p-safe RRT algorithm (given in algorithm 2). This algorithm describes the function EXPLORE STATE TIME of PASSPMP algorithm (algorithm 1). It aims to expand the tree given the model of the future (future behavior of moving objects) and an initialized tree rooted at the initial state of the cycle to plan (s k+1 ). An exhaustive search based expansion method is used. Each node is expanded according to a selected control space sampling set (line #7) using the function EX-PANSION WITH SAFETY CHECK (line #5). This function extends a node (state) s i with a control u j generating a new trajectory primitive that is checked for passive safety. Based on property 2, it is guaranteed that if s k+1 is psafe, there exists always a p-safe partial trajectory. As s k+1 belongs to previous p-safe partial trajectory (from previous PASSPMP cycle), s k+1 is p-safe thus there exists always a p-safe partial trajectory until A reaches its goal. Using property 1, it is guaranteed that a trajectory primitive δΠ new = {s i , ..., s new } is p-safe if δΠ new is collisionfree and s new is p-safe. The state is checked to be p-safe or not using BRAKING ICS CHECK function (line #21 of algorithm 2), which is based on ICS b -CHECK algorithm [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF]. If property 1 is verified, the corresponding trajectory primitive (δΠ new ) and expanded node (s new ) are added to the tree (lines #24 and #25 of algorithm 2). In case of no p-safe trajectory primitive is found for a given node s i , the function GENERATE BRAKING TRAJ looks for a collision-free braking trajectory to guarantee that the robot will be at rest if a collision could occur. As the node s i is p-safe it is guaranteed that it exists at least one braking trajectory ũ starting at s i which is collision-free until A has stopped (verifying passive motion safety property established in [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF]).

2) Trajectory selection: In algorithm 1 (PASSPMP algorithm), the function SELECT BEST PTRAJ selects from the expanded tree (using algorithm 2) the best partial trajectory during the planning cycles. This selection is based on two conditions: (1) The passive motion safety of the partial trajectory. (2) Convergence towards the goal: a weighted cost function is computed based on a distance metric and time cost. Thus, the selected partial trajectory could be passively safe at first. Using algorithm 2, a p-safe partial trajectory is a concatenation of p-safe trajectory primitives. Doing so, many partial trajectory possibilities are available. To settle Algorithm 2 p-safe RRT algorithm. Input: Model of the future W(t k , T h ), s k+1 (from Π k ), δ cycle (with δ cycle < min(δ d , T h /2)), initialize the tree: TREE = {s 0 , ..., s m } ∪ {δΠ 0 , ..., δΠ m-1 } (corresponding set of nodes and set of trajectory primitives). Output: TREE.

f g (s k+2 ) = w d ||s k+2 -s g || + w t ∆T Π (7)
The function f g determines the best partial trajectory Π k+1 i.e. the optimal in distance and in time with respect to the goal. It depends on the Euclidean distance between the trajectory final state (s k+2 ) and the goal state (s g ) associated to a distance weighting factor w d (minimizing distance to the goal). Besides, this function depends on the trajectory cumulative time (∆T Π ) associated to a time cost weighting factor w t (minimizing time to the goal).

V. SIMULATION RESULTS

To demonstrate and validate PASSPMP's passive motion safety, it has been implemented and tested in simulation on a scenario handling moving obstacles with unknown future behavior, for a mobile robot with a limited field-of-view. The partial motion can be described as a concatenation of several geometrical primitives.

The model of A is that of a standard car-like vehicle with two fixed rear wheels and two orientable front wheels. A state of A is a 5-tuple s = (x, y, θ, v, ξ) with (x, y) the coordinates of the rear axle midpoint, θ the orientation of A, v the linear velocity of A, and ξ the orientation of the front wheels (steering angle). A control of A is a couple u = (u α , u ξ ) with u α the linear acceleration of the rear wheels and u ξ the steering angle velocity. Let L denote the wheelbase of A. The motion of A is governed by the following differential equations:

      ẋ ẏ θ v ξ       =       v cos θ v sin θ v tan ξ/L 0 0       +       0 0 0 1 0       u α +       0 0 0 0 1       u ξ (8) with |v| ≤ v max , |ξ| ≤ ξ max , |u α | ≤ u αmax and |u ξ | ≤ u ξmax .
Simulation scenario features 22 objects moving arbitrarily in a 2D workspace. Their motion is unaffected by the other objects.

Fig. 3a shows an example of p-safe RRT construction for the first PASSPMP cycle. The tree is extended through the set of controls defined by a constant maximum linear acceleration u α = u αmax and a constant steering angle velocity |u ξ | ≤ u ξmax (namely, the control sets: [u α , -u ξ ], [u α , 0], [u α , u ξ ]). It is checked for passive motion safety using ICS b -CHECK algorithm (line #7 of algorithm 2). As illustrated in Fig. 3a, trajectory primitives represented in blue are p-safe, while those represented in cyan are not p-safe. The tree is extended in a way that each node is extended with at least one p-safe trajectory primitive. In case of no p-safe trajectory primitive is found, the node is extended with a collision free braking trajectory (lines #9 and #10 of algorithm 2) to guarantee that the robot stops before collision occurs (passive motion safety guarantee). Hence, among a set of possible braking trajectories, 21 in this example, (represented in black), the selected braking trajectory is the one that is collision-free and closest to the goal (represented in magenta). During a planning cycle, the best partial trajectory is selected given the two conditions:

(1) Passive motion safety of the partial trajectory and (2) the optimal both in distance and in time with respect to the goal (line #2 of algorithm 1). In case of the grown tree of Fig. 3a, the selected partial trajectory is represented in green (see Fig. 3b). To reach the goal in a passively safe manner, PASSPMP drives the robot following a set of concatenated partial trajectories (computed at different cycles). Fig. 4 shows grown trees along PASSPMP cycles until A reaches the goal.

The obtained results are also illustrated in a short film provided as a multimedia attachment to this paper. The corresponding velocity evolution of A is depicted in Fig. 5, where A exhibits the following behavior: 1) A increases its velocity until it reaches the maximum value. PASSPMP keeps A moving in p-safe manner (no collision occurs). 2) at the end of the first cycle, even if A could move without risk of collision, it gradually reduces its velocity (until v = 14ms -1 ). This is due to the limited field-of-view of A: as unseen objects are considered (the presence possibility of an object forces A to brake down until it stops in order to keep A in p-safe state (if collision occurs A will be at rest). 3) at next cycle, a new plan is considered using a new update of the world model. A stops reducing its velocity and rises it again until the maximum value and maintains it.Once again it brake down (passive motion guarantee) until v ≃ 3ms -1 (always due to the limited field-of-view consideration). 4) during the last cycle, A reaches the goal. It selects a collision-free braking trajectory that drives A to the closest state to the goal with a zero velocity (A stops) (see Fig. 4). In the course of several runs, these experiments have demonstrated the capability of PASSPMP to drive the robot to a predefined goal when enforcing passive motion safety.

VI. CONCLUSION AND FUTURE WORK

This paper has addressed the problem of planning the motion of a mobile robot with a limited sensory field-ofview in an unknown dynamic environment. A passively safe motion planner called PASSPMP has been presented: it is a partial motion planner enforcing passive motion safety. PASSPMP periodically computes a passively safe partial trajectory designed to drive the robot towards its goal state. Passive motion safety is enforced thanks to a variant of the Inevitable Collision State (ICS) concept called Braking ICS, i.e. states such that, whatever the future braking trajectory of the robot, a collision occurs before it is at rest. Simulation results have demonstrated how PASSPMP operates and handles limited sensory field-of-views, occlusions and moving obstacles with unknown future behaviour. PASSPMP works better than PASSAVOID, its purely reactive counterpart that was presented in [START_REF] Bouraine | Provably safe navigation for mobile robots with limited field-of-views in dynamic environments[END_REF] however the analysis of the convergence towards the goal of PASSAVOID remains to be done. It could also be interesting to explore more sophisticated levels of motion safety such as the passive friendly motion safety mentioned in [START_REF] Macek | Towards safe vehicle navigation in dynamic urban scenarios[END_REF]: it guarantees that, if a collision takes place, the robot will be at rest and the colliding object could have the time to stop or avoid the collision (if it wants to).

Fig. 1 :

 1 Fig. 1: Timeline of the decision-making and execution processes in a partial motion planner.

Fig. 2 :

 2 Fig. 2: PASSPMP process.

Fig. 3 :

 3 Fig. 3: p-safe RRT at work: (a) p-safe RRT construction during one PASSPMP cycle (b) corresponding selected partial trajectory (in green). The robot A is the disc at the center, the moving discs in blue are objects and the red mark is the goal to reach by A .

Fig. 4 :

 4 Fig. 4: p-safe RRTs corresponding to different PASSPMP cycles (left) and the overall selected trajectory represented in green (right).

Fig. 5 :

 5 Fig. 5: Velocity profile of A.

1 :

 1 while t < δ cycle do δΠ new ← GENERATE TRAJ PRIM(s i , u j ) 19: //δΠ new = {s i , ..., s f } 20: s new = s f ; 21: if BRAKING ICS CHECK(s new ,W) = False then

	2:	//set of tree nodes
	3:	for i=0 to m do
	4:	//Select the control space sampling set U
	5:	Sample U ❀ U = {u 1 . . . u n }
	6:	Forall u j ∈ U do
	7:	(s new , δΠ new )	←	EXPAN-
		SION WITH SAFETY CHECK(s i , u j , W, TREE);
	8:	end
	9:	if s new = ∅ then
	10:	GENERATE BRAKING TRAJ();
	11:	end if
	12:	end for
	13:	return TREE
	14: end while
	15:
	16: Procedure EXPANSION WITH SAFETY CHECK
		(s i ,u j ,W, TREE)
	17: //Check p-safety
	18: 22:	//s new is p-safe
	23:	if δΠ new is collision-free then
	24:	TREE = TREE ∪ s new ;
	25:	TREE = TREE ∪ δΠ new ;
	26:	return s new ,δΠ new
	27:	end if
	28: end if
	29: EndProcedure
	which p-safe partial trajectory (between s k+1 and s k+2 )
	could be selected, a weighted cost function is computed. It
	is expressed as follows:

† CDTA (DZ); ‡ INRIA, CNRS-LIG and Grenoble Univ. (FR); ⋆ Blida Univ. (DZ).[START_REF] Fraichard | Iterative motion planning and safety issue[END_REF] The lookahead, a.k.a. time horizon, is how far into the future the reasoning is done.


Thierry Fraichard

Rémi Paulin

Patrick Reignier

Human-Robot Motion: An Attention-Based Navigation Approach

Mobile robot companions are service robots that are mobile and designed to share our living space. For such robots, mobility is essential and their coexistence with humans adds new aspects to the mobility issue: the first one is to obtain appropriate motion and the second one is interaction through motion. We encapsulate these two aspects in the term Human-Robot Motion (HRM) with reference to Human-Robot Interaction. The long-term issue is to design robot companions whose motions, while remaining safe, are deemed appropriate from a human point of view. This is the key to the acceptance of such systems in our daily lives. The primary purpose of this paper is to explore how the psychological concept of attention can be taken into account in HRM. To that end, we build upon an existing model of attention that computes an attention matrix that describes how the attention of each person is distributed among the different elements, persons and objects, of his/her environment. Using the attention matrix, we propose the novel concept of attention field that can be viewed as an attention predictor. Using different case studies, we show how the attention matrix and the attention field can be used in HRM.

I. INTRODUCTION

A. Background and Motivations

Manufacturing robots have long dominated the robotics market but recently, we have witnessed the growth of the service robotics sector. Service robots come in a multitude of forms and their application areas are numerous, e.g. cleaning, inspection, rescue and security, entertainment, handicap assistance, transportation, logistics. Of particular interest to us are the service robots designed to share our living space (both professional and domestic) and to have varying degrees of interaction with us humans. Henceforth such service robots will be called robot companions.

Among the various types of robot companions that exist, we will focus on those similar to Care-O-Bot (Fig. 1a). Such robots are respectable in size (about the size of a person) and are designed to move in environments that can be large. Let's call them mobile robot companions. They differ from robot companions like Reeti that are smaller and basically static (Fig. 1b). shorter but it is not appropriate. (b) Attention vs activity: although P 1 's current activity is being on the phone, part of her attention may be directed towards P 2 , the TV set or the robot R. Suppose now that R moves towards P 2 in a way that hides the TV from P 1 . Such a behaviour would not be appropriate should P 1 be actually paying attention to the TV.

For mobile robot companions, mobility is an essential problem: they must be able to move freely in their environment. To that end, they have to address all the standard problems pertaining to autonomous motion, e.g. world modelling, localization, motion planning, motion control. However, the coexistence in the same environment of robots and humans adds a novel dimension to the mobility issue. For standard mobile robots, mobility usually boils down to computing motions that are both safe and optimal in some sense, e.g. traveled distance. However, people are not regular obstacles that can be treated like pieces of furniture. There is a set of social and cultural rules that governs how a person moves among his/her peers, e.g. Fig. 2a. Besides the motion of a person is largely influenced by the set of non-verbal cues, e.g. velocity, gaze direction, that can be sent by the other persons (and vice versa). In other words, motion constitutes a form of non-verbal interaction. At the end of the day, two aspects emerge vis-à-vis the mobility of a robot companion: the first one is to obtain appropriate motion and the second one is interaction through motion. We will encapsulate these two aspects in the term Human-Robot Motion (HRM) with reference to Human-Robot Interaction. The long-term issue is to design robot companions whose motions, while remaining safe, are deemed appropriate from a human point of view. This is the key to the acceptance of such systems in our daily lives.

B. Related Works and Contributions

Although mobile robots have actually shared the human living space as early as 1997 [START_REF] Burgard | The interactive museum tour-guide robot[END_REF], it is only around 2005 that the appropriate motion issue has surfaced and that human factors have been investigated and explicitly taken into account for motion purposes [START_REF] Althaus | Navigation for human-robot interaction tasks[END_REF]. The review of the literature on this topic shows that most of the approaches proposed so far rely upon the definition of so-called social spaces, i.e. regions in the environment that, for different reasons, people consider as psychologically theirs [START_REF] Lindner | Towards a formalization of social spaces for socially aware robots[END_REF]. Such social spaces are primarily characterized using either the position of the person, e.g. "Personal space" [START_REF] Hall | A system for the notation of proxemic behaviour[END_REF], or the activity he is currently engaged in, e.g. "Interaction Space" [START_REF] Kendon | Spacing and orientation in co-present interaction[END_REF] and "Activity Space" [START_REF] Lindner | Towards a formalization of social spaces for socially aware robots[END_REF]. The interaction/activity spaces are broadly defined by the convex hull of the person at hand and the people or the objects he interacts with. In this framework, human detection and human activity recognition are central in the definition of said social spaces (which explains why activity recognition has grown into an important area of research especially in computer vision [START_REF] Aggarwal | Human activity analysis: A review[END_REF], [START_REF] Bulling | A tutorial on human activity recognition using body-worn inertial sensors[END_REF]). Having characterized the social spaces corresponding to the current situation, the most common approach in HRM is then to define costmaps on such social spaces: the higher the cost, the less desirable it is for the robot to be at the corresponding position. The costmaps are ultimately used for motion planning and navigation purposes, e.g. [START_REF] Sisbot | A human aware mobile robot motion planner[END_REF], [START_REF] Shi | Human-aware robot motion planning with velocity constraints[END_REF], [START_REF] Scandolo | An anthropomorphic navigation scheme for dynamic scenarios[END_REF].

Such approaches are obviously relevant but we believe that an analysis of the situation based solely on the activities of the persons present may be too limited. Consider for instance the situation depicted in Fig. 2b. It involves two persons, one robot companion, a TV set and a phone. Let us focus on person P 1 and assume that she is currently on the phone. Besides the personal space centered around P 1 , her current activity would yield an activity space in the form of the convex hull of P 1 and the phone. Both the personal space and the activity space attached to P 1 should be avoided by the others. However it is important to note that the fact that P 1 is currently on the phone does not mean that she is not paying attention to the TV set, the person P 2 or the robot R. Suppose now that the task of R is to deliver a message to P 2 . If R relies on social space-based navigation only, it may very well decide to move in a way that hides the TV from P 1 . Such a behaviour would not be appropriate should P 1 be actually paying attention to the TV. This simple example is meant to illustrate that there is much more to the cognitive state of a person than what is implied by his/her current activity and that a person is generally paying attention to more than one element of his/her environment (irrespective of his/her current activity).

The primary purpose of this paper is precisely to explore how the psychological concept of attention can be taken into account in HRM in order to obtain autonomous navigation schemes for mobile robot companions that yield better appropriate motions. To that end, we build upon a computational model of attention that was earlier proposed in [START_REF] Maisonnasse | Attentional model for perceiving social context in intelligent environments[END_REF]. This attention model was initially developed in the context of ambient applications and pervasive systems. Its purpose was to estimate how attention was shared between the different users and the components of a "smart environment". The output of this model is an attention matrix that describes how the attention of each person is distributed among the different elements, persons and objects, of his/her environment. Using the attention matrix, we propose the novel concept of attention field that can be viewed as an attention predictor. Using different case studies, we show how the attention matrix and the attention field can be used in HRM.

C. Outline of the Paper

To begin with, the main concepts related to the psychological concept of attention are briefly introduced in section II. Then, section III outlines the attention model originally proposed in [START_REF] Maisonnasse | Attentional model for perceiving social context in intelligent environments[END_REF] and that is used throughout the paper. Section IV describes the implementation details of the model while section V illustrates via three case studies how the attention matrix and the attention field can be used in HRM.

II. ATTENTION

Attention is one of the most intensely studied topics in psychology and cognitive neuroscience and the point of this section is not to cover all the works and theories that have been proposed over the years. Its more modest purpose is to introduce the different psychological concepts that are later used in the paper in relation to the attention model that we use.

Attention, which has also been referred to as the allocation of processing resources [START_REF] Anderson | Cognitive Psychology and Its Implications[END_REF], is the cognitive process that enables humans to selectively concentrate on one or several aspects of their environment while ignoring others. It can be described as a filter, preventing us from being overwhelmed by all the surrounding sensory data. It selects only few of them to maintain the current activity and resist disruptions. This selection is constantly renegotiated. If the situation changes, attention can shift in response to new events, e.g. sudden noise, dimming light. Attention is generally defined as the combination of two components:

• The endogenous (aka internal) component is considered to be voluntary and based on our current activity. It is the intentional allocation of attentional resources to a predetermined element (object or person) of the environment: that is the intention. • The exogenous (aka external) component is considered to be reflexive and automatic and is caused by sudden changes in the environment: that is the distraction. The distraction capacity of an element is related to its salience (also called saliency). It is the state or quality by which it stands out of its neighbours. Salience and distraction should always be interpreted through one's sensory capabilities. A loud noise for instance will not distract a deaf person.

As mentioned above, attention is the combination of its endogenous and exogenous components. It filters the sensory information coming from the environment. This filtering process can be modeled using two complementary dimensions:

• The selective dimension corresponds to the spotlight metaphor [START_REF] James | The Principles of Psychology[END_REF]. It considers that attention is oriented in a given direction in space. This model promotes the sensory information provided by the elements around this main direction, ignoring partially [START_REF] Treisman | Strategies and models of selective attention[END_REF] or totally [START_REF] Broadbent | Perception and communication[END_REF] the elements in the periphery depending on the attention focus. Broadly speaking, the attention focus is the size of the region around the attention direction wherein elements can potentially receive attentional resources.

• The intensive dimension corresponds to the limited resource metaphor. Attention is a reservoir containing a finite amount of attentional resources [START_REF] Kahneman | Attention and effort[END_REF]. The attention is the energy needed for a cognitive task. Each person, depending of his/her own skill and the invested effort, will consume more or less attentional resources for each task. This reservoir model captures the ability to perform tasks in parallel (as long as there is enough energy in the reservoir for all of them).

III. ATTENTIONAL MODEL

In 2006, [START_REF] Maisonnasse | Attentional model for perceiving social context in intelligent environments[END_REF] proposed a computational model of attention that was later detailed in [START_REF] Maisonnasse | Estimation des relations attentionnelles dans un environnement intelligent[END_REF]. As mentioned earlier, this attentional model, henceforth called AM, was initially developed in the context of ambient applications and pervasive systems. Its purpose was to estimate how attention was shared between the different users and the components of a "smart environment". In a situation involving a set of persons and relevant environmental objects, AM can compute the attention matrix that characterizes how the attention of each person is distributed among the different elements, persons and objects, of the environment. The purpose of this section is to outline the key principles underlying the definition of AM. A more detailed presentation of AM is found in Section IV. The reader is referred to [START_REF] Maisonnasse | Estimation des relations attentionnelles dans un environnement intelligent[END_REF] for a complete presentation of AM.

A. AM Principle

The main feature of AM is that it is a global attentional model that takes into account both the activity of a person and the influence of his/her environment. On the one hand, the observation of the activity that a person is currently engaged in (along with other clues whenever available) defines the endogenous factor vis-a-vis the attention of the person. On the other hand, the identification of the salient elements of the environment, persons and objects, defines the exogenous factors vis-a-vis the attention of the person. AM combines these factors in a coherent way. It uses a mathematical model inspired from Newton's gravitation law from physics.

Newton's well known gravitation law states that any two bodies in the universe attract each other with a force that is directly proportional to the product of their masses and inversely proportional to the square of the distance between them. On the other hand, Newton's second law of motion states that the net force applied to an object is proportional to its acceleration. The consequence of these laws is that the trajectory of a body is deflected in the presence of another object. Shifting from physics to attention, the analogy could be formulated as follows:

• An object with an initial velocity and a null net force follows a straight trajectory. It takes a non null acceleration for the object to modify its trajectory and the higher the initial velocity, the more important the acceleration should be in order to significantly modify the initial trajectory. The initial velocity can be interpreted as the resistance to distraction, i.e. the endogenous component of attention. In AM, it is modeled as a vector, the intention vector henceforth denoted Ĩ. • The trajectory of an object is modified by its acceleration which is in turn proportional to the sum of the gravitation forces exerted by neighboring objects. Said acceleration can be interpreted as the distraction, i.e. the exogenous component of attention where the mass of each neighboring object represents its distraction capability, i.e. its salience. In AM, it is modeled as a vector, the distraction vector henceforth denoted D.

B. Attention Vector

Each person in the environment has his/her corresponding intention and distraction vectors. Ĩ is typically the output of a human activity recognition module [START_REF] Aggarwal | Human activity analysis: A review[END_REF], [START_REF] Bulling | A tutorial on human activity recognition using body-worn inertial sensors[END_REF]. As far as D is concerned, it is a function of the distraction of the different elements, other persons and objects, that surround the person considered. The distraction of an element is a function of its salience that can be estimated using for instance visual salience computation techniques [START_REF] Frintrop | Computational visual attention systems and their cognitive foundations: A survey[END_REF], [START_REF] Kimura | Computational models of human visual attention and their implementations: A survey[END_REF]. Both Ĩ and D are two-or three-dimensional vectors depending on the dimensionality of the environment considered. Finally, attention is modeled in AM as a two-or three-dimensional vector, the attention vector henceforth denoted à that combines both the endogenous and exogenous components of attention. à is the result of the competition between intention and distraction:

à = f a ( Ĩ, D) (1)

C. Attentional Resources Allocation

The attention vector à is central to AM. Its direction corresponds to the main direction of attention of the person considered, and its magnitude is used to determine both the amount of attentional resources available and the attention focus, i.e. the size of the region around the attention direction wherein elements can potentially receive attentional resources. At this point, it remains to allocate the attentional resources of the person considered to the elements within his/her attention focus. For a given element, person or object, of the environment, this is achieved by taking into account the azimuth of the element with respect to Ã, its distance and its salience.

D. Attention Matrix

The output of AM is an attention matrix henceforth denoted M. Each column of M is associated with an element, person or object, of the environment while each line of M is associated with a person. Table I depicts an example of attention matrix for a situation involving 5 elements: 2 persons (P 1 and P 2 ), and 3 objects (O 1 , O 2 and O 3 ). The content of each cell, denoted m ji , represents the amount of attention given by the person j to the element i. Note that each line of M represents how the attention of the corresponding person is spread among the different elements of the environment whereas each column represents the attention paid by the different persons to the corresponding element.

IV. ATTENTIONAL MODEL IMPLEMENTATION

The purpose of this section is to detail how AM is actually implemented. For the sake of simplicity, we have considered two-dimensional environments (the extension to the threedimensional case is straightforward). Again, the reader is referred to [START_REF] Maisonnasse | Estimation des relations attentionnelles dans un environnement intelligent[END_REF] for more details.

A. Notations

Let W denote the environment considered and R the robot at hand. The workspace W ⇢ IR 2 is populated by a set of e elements E i ,i =1 ...e. These elements are either persons, P j ,j =1 ...p or objects O k ,k =1 ...o. Unlike objects, persons have senses that provide them with information about their environment. Two sensory modalities have been considered in this work: vision and hearing. In this respect, every element has a salience, i.e. a capacity to distract a person. It will be distinguished between visual and auditory salience. Each element E i is thus characterized by the following attributes:

• Its pose, i.e. its position and orientation in W: q i = (x i ,y i , ✓ i ). • Its geometric shape which is denoted by E i (q i ): it is the closed region of W which is occupied by E i when it is in pose q i . • Its visual and auditory saliences respectively denoted sal visual i and sal audio i . They are both scalar values that represent the intrinsic capacity of an element to distract (irrespective of any sensing capability).

• Its visual and auditory field-of-distractions respectively denoted FoD visual i and FoD audio i . FoD mod i is a mapping from IR 2 ⇥S 1 ⇥W to IR . FoD mod i (q i ,x,y) characterizes the distraction capacity at a given position (x, y) for the sensory modality mod of E i when it is at pose q i . In addition, a person P j has the following attributes:

• His/her visual and auditory field-of-perception respectively denoted FoP visual j and FoP audio j . FoP mod j is a mapping from IR 2 ⇥ S 1 ⇥ W to IR . FoP mod j (q j ,x,y) characterizes the perception capacity at a given position (x, y) for the sensory modality mod of P j when he is at pose q j . • His/her intention Ĩj . It is henceforth assumed that Ĩj is constantly estimated thanks to a human activity recognition module [START_REF] Aggarwal | Human activity analysis: A review[END_REF], [START_REF] Bulling | A tutorial on human activity recognition using body-worn inertial sensors[END_REF]. Examples of field-of-distractions and field-of-perceptions are presented in Section V-A.

B. Computing the Distraction

As per (1), the first step in order to compute the attention vector of a person P j is to compute his/her distraction vector Dj . As mentioned earlier, Dj is a function of the distraction capacities of the different elements, other persons and objects, that surround P j . Let Dij denote the distraction vector that characterizes the distraction caused by the element E i on P j . Dij depends on the salience and field-of-distraction of element E i and the field-of-perception of P j . In line with the gravitation analogy, Dij is a vector pointing from P j to E i whose norm is computed as follows:

k Dij k = X mod sal mod i FoD mod i (q i ,x j ,y j )FoP mod j (q j ,x i ,y i )
(2) and Dj is the sum of the distractions of each element surrounding P j :

Dj = X i6 =j Dij (3)

C. Computing the Attention

Both Ĩj and Dj are now available for a given person P j , it is therefore possible to compute his/her attention Ãj as follows:

Ãj = f a ( Ĩ, D)= Ĩj + e -↵k Ĩj k Dj (4)
With ↵ a weighing factor. The exponential term is introduced to weaken the contribution of the distraction when the person is very focused and therefore less sensitive to external distractions (a determined person is hard to distract).

D. Allocating the Attention

The attention vector Ãj is used to determine both the amount of attentional resources available and the attention focus, i.e. the size of the region around the attention direction wherein elements, persons or objects, can potentially receive attentional resources. In AM, the amount of attentional resources denoted AR j is computed as follows:

AR j = tanh(k Ãj k) (5)
To capture the fact that the attention is primarily allocated to elements that are within the attention focus of a person, AM uses a function that determines the amount of attention given the incidence angle between the attention vector Ãj and the line passing through the person and the element at hand: the higher ↵, the lower the amount of attention received. This function denoted f focus j is defined as:

f focus j (↵)=AR j e -↵ 2 /2σ 2 (6)
with ↵ the incidence angle and σ the standard deviation of a Gaussian function. It represents the size of the attention focus:

σ = ⇡(1 -AR j ) (7)
For a given person P j , it is now possible to compute the amount of attentional resources he/she gives to a given element E i (and therefore to fill in the corresponding cell m ji in the attention matrix M. It is done by ordering the set of elements {E i },i 6 = j by increasing order of incidence angle ↵ i . Then each element in the order of the list is allocated an amount of attention equal to:

m ji = f focus j (↵ i )k Dij k/k Ãi k ( 8
)
This amount is deducted from AR j , the total amount of attentional resources that P j has. The process stops when AR j becomes zero.

V. ATTENTION MODEL AND HUMAN-ROBOT MOTION

The purpose of this section is to demonstrate how attention can be used to address Human-Robot Motion problems. To that end, three case studies aimed at illustrating different ways to use the attention model AM presented earlier are considered. Details concerning the set up used in all the case studies are given first.

A. Set Up Description

The case studies covered in the next sections concern twodimensional scenarios with one robot, up to two persons and up to two different objects: a TV and a phone. As far as their geometric shape is concerned, they are all modeled as disks for the sake of simplicity. The robot and the persons have both visual and auditory sensory modalities. Let us therefore see how the field-of-distractions and the field-of-perceptions are defined for these elements.

1) Field-of-Distractions: For the phone and the robot, the auditory field-of-distraction is assumed to be isotropic, centered at the elements' position (the noise source so to speak), and decreasing quadratically with the distance to the noise source. FoD audio i , the auditory field-of-distraction for the element E i is formally defined as:

FoD audio i (q i ,x,y)= 1 (x -x i ) 2 +(y -y i ) 2 = 1 d i (x, y) 2 (9)
The same definition applies to the visual field-of-distraction for the phone and the robot. However things are different for the TV and the persons. In this case, it is assumed that the distraction, both visual and auditory, is maximum when one is directly facing the TV screen/person's face, and that it decreases with the distance to the TV screen/person's face and the incidence angle with the normal to the TV screen/person's face. This can be modeled as follows:

FoD visual i (q i ,x,y)= 1 d i (x, y) 2 f visual i (↵) (10)
FoD audio i (q i ,x,y)= 1 d i (x, y) 2 f audio i (↵) ( 11
)
where ↵ is the incidence angle between the normal to the TV screen/person's face at pose q i and the line passing through (x i ,y i ) and (x, y). f mod i is the function that determines the amount of distraction given the incidence angle. It is based on the Euler Beta function (other functions could be used, e.g. Gaussian). An example of field-of-distraction for a TV is depicted in Fig. 3a.

2) Field-of-Perceptions: The persons and the robot have visual and auditory sensing capabilities that are characterized by their field-of-perceptions. As far as hearing is concerned, the auditory field-of-perception FoP audio j is assumed to be isotropic. As far as vision is concerned, the visual field-ofperception FoP visual j is defined similarly to (10) (without the quadratic decrease) with an incidence angle now defined with respect to the gaze direction. An example of field-ofperception for a person is depicted in Fig. 3b. The purpose of this case study is to show how the attention matrix M that is computed at regular intervals by AM can be used by the robot R in order to better understand the current situation and plan its next action accordingly. Let us begin by illustrating the type of information that AM brings. Fig. 4a depicts a scenario with a person P 1 , a TV O 1 and the robot R (the Person-TV-Robot scenario). It is assumed that the person is currently watching the TV (this is his current activity). his intention Ĩ1 is represented by the yellow vector pointing towards O 1 in Fig. 4a. The two white vectors represent the distractions Di1 caused to the person by the robot and the TV respectively (the corresponding visual and auditory saliences are given in Table II). The red vector is the attention Ã1 that has been computed by AM, the corresponding attention matrix M is given in Table III. As expected, most of the person's attention is given to the TV.

B. Case Study #1: Using the Attention Matrix

P 1 RO 1 P 1 - 0.02 0.61

TABLE III:

The attention matrix M for the scenario depicted in Fig. 4a.

Let us now extend the previous scenario by adding a phone O 2 in the environment (Fig. 4b). The phone is an interesting element whose salience depends on whether it is ringing or not. The corresponding visual and auditory saliences are given in Table IV. Let us assume now that the task of the robot R is to deliver a message to the person P 1 . R is slowly approaching P 1 while constantly monitoring where P 1 's attention is. As R gets closer to P 1 , the attention that P 1 is paying to R increases: compare for instance the situation corresponding to Figs. 4a and5a. As per the attention matrix of Table V (silent case), it can be seen that the attention given to R by P 1 is very much increased now that R is close to P 1 : it increased from 0.02 to 0.70. All things being equal, if the phone rings, things change drastically and most of the attention of P 1 is now given to the phone: compare Figs. 5a and5b, and the attention matrices of Table V. The attention given to R by P 1 drops from 0.70 to 0.09. In such a situation, the appropriate reaction for R is to standby and wait politely until P 1 has picked up the phone. R could later decide to resume its approach as soon as P 1 is once again paying attention to R (when the phone conversation is over). In this respect, it can be seen how taking into account attention allows to anticipate the future activity of the person, i.e. picking up the phone, and yields a more appropriate behavior. As simple as these scenarios are, they illustrate how the knowledge of the current global attentional situation (embodied in the attention matrix which is constantly updated) can be used to adapt the behaviour of the robot. The next two case studies will illustrate another way to use AM, namely as an attention predictor. The purpose of this case study is to demonstrate how AM can be used to predict potential attentional situations and to use that knowledge in order to decide what the robot will do depending on its current task. Fig. 6 depicts a scenario featuring two persons, P 1 and P 2 , and a robot R. The two persons are currently engaged in a conversation (this is their current activity). Their intentions Ĩ1 and Ĩ2 are respectively modeled by the two yellow vectors in Fig. 6, they point at each other. The corresponding visual and auditory saliences are given in Table VI. Let us assume that the task of R is to deliver a message to P 1 while minimizing the disturbance caused to the other persons. To achieve this task, the appropriate behavior for R should be to move to a position where it can (1) attract the attention of P 1 , and

C. Case Study #2: Introducing the Attention Field

(2) minimize the distraction caused to P 2 . To that end, R must be able to estimate the attention that the persons will pay to it depending on its position (x, y). It is easily done using AM in order to compute the attentional matrix M x,y for every possible positions of R in W. Table VII gives the general form of M x,y . By doing so, it becomes possible to compute a so-called attention field for each person. Let F j denote the attention field for the person P j , it is a mapping from W to IR that gives the amount of attention that P j is paying to R when it is at position (x, y). This mapping is readily obtained from M x,y , it is the value contained in the cell m j3 . the warmer the color, the higher the amount of attention given by P 1 to R. It integrates the visual and auditory perception capabilities of P 1 . Note in particular how the occlusion of P 1 's field-of-view by P 2 impacts the field. Because of the symmetry in P 1 and P 2 's situations, the attention field F 2 for P 2 would be very similar (F 1 rotated by 180 degrees).

Once the attention fields F j are available, it becomes possible to use them to address the task at hand: attracting P 1 's attention while disturbing P 2 as little as possible. This task can be formulated as a multiobjective optimization problem, i.e. maximizing P 1 's attention and minimizing P 2 's attention. In this case, a simple weighted sum can be used to compute a field F opt defined as:

F opt = F 1 -F 2 ( 12
)
F opt is depicted in Fig. 7b. It should be interpreted as follows: the warmer the color, the better the solution to the multiobjective optimization problem at hand. F opt confirms the intuition that the best way to attract P 1 's attention while disturbing P 2 as little as possible is to be in the red region of Fig. 7b, i.e. a region where R is almost facing P 1 while remaining outside the field-of-view of P 2 . F opt can readily be used to drive R's behavior (the next case study will show how to actually do that). Fig. 8 The previous case study has shown how the attention field can be used to determine where the robot should go to achieve a given task. The purpose of this case study is to illustrate how the attention field can be used for motion planning purposes, i.e. to actually determine how the robot should move. To that end, the Person-TV-Robot scenario introduced in the first case study is used. The person is watching the TV (yellow vector pointing towards O 1 in Fig. 8a). The visual and auditory saliences are given in Table II).

D. Case Study #3: Motion Planning using Attention Fields

Two different tasks are assigned to the robot R: the first one is to deliver a message to P 1 (Deliver task). The second one is to reach a goal G while disturbing P 1 as little as possible (Goto task). For both tasks, the attention field F 1 for P 1 is used. F 1 is depicted in Fig. 8b. At this point, it is interesting to look at the relationship between our attention model and the standard social space model. The Person-TV-Robot scenario would yield two social spaces: (1) a personal space centered around the person, and (2) an activity space in the form of the convex hull of P 1 and the TV. Note how the red region of F 1 encompasses these social spaces. To address the Deliver task, the behavior of R is driven using a simple gradient descent based on F 1 . The idea is to move towards P 1 so as to smoothly increase the attention that P 1 is paying to R (hence the gradient descent). The resulting motion is depicted in Fig. 9a. Note how R ends up approaching P 1 with an incidence angle of about 45 degrees. Such a behavior is coherent with the experimental results presented in [START_REF] Dautenhahn | How may i serve you? a robot companion approaching a seated person in a helping context[END_REF] that establish that this is the best way to approach a person politely without causing discomfort. This behaviour has been confirmed for arbitrary start poses.

Addressing the Goto task requires motion planning capabilities. A Dijkstra algorithm is used to compute the optimal path between the current position of R and the goal. In our case, the optimality criterion is to minimize the total sum of the attention paid by P 1 to R along the path. A resulting path is depicted in Fig. 9b. Note how R passes behind the person so as not to disturb him (with respect to his visual and auditory modalities). Note also that, had R's behavior been driven based solely on the social spaces, it would have passed above the TV since it would yield the shortest path towards the goal. Doing so, it would have distracted P 1 more. As simple as this example is, it illustrates the interest of taking attention into account.

VI. DISCUSSION AND CONCLUSION

We have shown in this paper that the psychological concept of attention can be used to address Human-Robot Motion (HRM) in order to obtain autonomous navigation schemes for mobile robot companions that yield better appropriate motions. We have built upon the computational attention model initially proposed in [START_REF] Maisonnasse | Attentional model for perceiving social context in intelligent environments[END_REF] that computes the attention matrix, i.e. a model of how the attention of each person is distributed among the different elements, persons and objects, of his/her environment. Through several case studies, we have demonstrated different ways to use the attention matrix in HRM. We have also introduced the novel concept of attention field and used it for navigation purposes. We believe that attention is a concept that is a beneficial complement to the social space concept that is classically used in HRM.

The next step of this work is to investigate this approach further with more complex case studies. Then, although this paper has focused on attention only, we plan to combine attention with social space concepts (in particular our earlier work on social space-based navigation in dynamic environments [START_REF] Scandolo | An anthropomorphic navigation scheme for dynamic scenarios[END_REF]). Finally, real life experiments on a real robot will be carried out and used to validate the interest of using attention to address HRM.

Fig. 1 :

 1 Fig. 1: Mobile vs fixed robot companions.

Fig. 2 :

 2 Fig. 2: (a) People are not pieces of furniture! Motion in red is definitely

P

( a )

 a FoD visual for a TV. (b) FoP visual for a human.

Fig. 3 :

 3 Fig. 3: (a) Visual field-of-distraction for a TV whose screen is facing downward. Distraction is maximum when standing right in front of the screen. It decreases with the distance to the screen and the incidence angle with the normal to the screen, the rate of decrease obeys an Euler Beta function. (b) Visual field-of-perception of a person whose gaze direction is pointing upwards. Perception is maximum when standing right in the gaze direction. It decreases with the incidence angle with the gaze direction; the rate of decrease obeys a Gaussian function and is truncated to zero behind the person.

  Fig. 4: (a) Scenario with a person P 1 , a TV O 1 and the robot R. The person is currently watching the TV. The yellow vector is the intention, white vectors are distractions and the red vector is the attention. (b) Scenario with a person P 1 , a TV O 1 , a phone O 2 and the robot R. The person is currently watching the TV.

  Visual and auditory saliences for the Person-TV-Phone-Robot scenario. The phone salience depends on whether it is ringing or not.

  (a) Phone is silent. (b) Phone is ringing.

Fig. 5 :

 5 Fig. 5: Two similar situations for the Person-TV-Phone-Robot scenario.

Fig. 6 :

 6 Fig. 6: Scenario with two persons, P 1 and P 2 , and a robot R (Person-Person-Robot scenario).

  (a) Attention field F 1 for P 1 . (b) Solution field Fopt for the message delivering problem.

Fig. 7

 7 Fig. 7

Fig. 7a depicts F 1 ,

 1 Fig. 7a depicts F 1 , the attention field for P 1 for the Person-Person-Robot scenario. It should be interpreted as follows:the warmer the color, the higher the amount of attention given by P 1 to R. It integrates the visual and auditory perception capabilities of P 1 . Note in particular how the occlusion of P 1 's field-of-view by P 2 impacts the field. Because of the symmetry in P 1 and P 2 's situations, the attention field F 2

  (a) Person-TV-Robot scenario. (b) The attention field F 1 for P 1 .

  (a) Deliver task. (b) Goto task.

Fig. 9

 9 Fig. 9

TABLE I :

 I Example of attention matrix.

		1	P 2	O 1	O 2	O 3
	P 1	-	m 12	m 13	m 14	m 15
	P 2	m 21	-	m 23	m 24	m 25

TABLE II :

 II Visual and auditory saliences for the Person-TV-Robot scenario.

TABLE V :

 V The attention matrices M for the situations in Figs.5.

TABLE VI :

 VI Visual and auditory saliences for the Person-Person-Robot scenario.

		P 1	P 2	Rx,y
	P 1	-	m 12	m 13
	P 2	m 21	-	m 23

TABLE VII :

 VII Attention matrix Mx,y for the Person-Person-Robot scenario depending on the position of R.

This work was partially supported by the French Ministry for Education and Research, the INRIA PAL project and the FUI PRAMAD2 project.