K Madhava Krishna

R Alami

T Simeon

Safe Proactive Plans and their Execution

We present in this paper a methodology for computing the maximum velocity profile over a trajectory planned for a mobile robot. Environment and robot dynamics as well as the constraints of the robot sensors determine the profile. The planned profile is indicative of maximum speeds that can be possessed by the robot along its path without colliding with any of the mobile objects that could intercept its future trajectory. The mobile objects could be arbitrary in number and the only information available regarding them is their maximum possible velocity. The velocity profile also enables to deform planned trajectories for better trajectory time. The methodology has been adopted for holonomic and non-holonomic motion planners. An extension of the approach to an online real-time scheme that modifies and adapts the path as well as velocities to changes in the environment such that both safety and execution time are not compromised is also presented for the holonomic case. Simulation and experimental results demonstrate the efficacy of this methodology.

Introduction

Several strategies exist for planning collision free paths in an environment whose model is known [START_REF] Latombe | Robot Motion Planning[END_REF]. However during execution, parameters such as robot and environment dynamics, sensory capacities need to be incorporated for safe navigation. This is especially so if the robot navigates in an area where there are other mobile objects such as humans. For example in Figure 1, the robot would require to slow down as it approaches the doorway, in anticipation of mobile objects to emerge from there, even if it does not intend to make a turn through the doorway.

A possible means to tackle the above problem at the execution stage is to always navigate the robot at very low speeds. In fact, reactive schemes such as the nearness diagram approach [START_REF] Minguez | Nearness diagram navigation. a new real-time collision avoidance approach[END_REF] operate the robot at minimal velocities throughout the navigation. However incorporating the computation of a velocity profile at the planning stage would circumvent not only the problem of conservative velocities throughout navigation but would also allow for a modification of the trajectory to achieve lower time (Fig. 2). We present in this paper a novel pro-active strategy that incorporates robot and environment dynamics as well as sensory constraints into a collision free motion plan. By pro-active we mean that the robot is always in a state of expectation regarding the possibility of a mobile object impinging onto its path from regions invisible to its sensor. This pro-active state is reflected in the velocity profile of the robot, which guarantees that in the worst case scenario, the robot will not collide with any of the moving objects that can interfere with its path. The ability of the algorithm to compute a-priori velocities for the entire trajectory accounting for moving objects moving in arbitrary directions is the essential novelty of this effort.

Figure 2: A longer path can be faster due to higher speed.

As is always the case, planned paths and profiles need constant modification at the execution stage due to changes in the environment. For example a profile and path that was planned for an environment with a closed doorway needs to be modified during realtime if the doorway is found open. Also addressed in this article the problem portrayed in Figure 3. Given an initial trajectory planned for a particular environment how does the robot modify its trajectory while new objects (not necessarily intersecting the robot's 1 trajectory) are introduced into the environment such that the basic philosophy of ensuring safety as well as reducing time lengths of the path continue to be respected. Simulation and experimental results are presented to indicate the efficacy of the scheme. In [START_REF] Alami | On the influence of sensor capacities and environment dynamics onto collision-free motion plans[END_REF] we had reported how the maximum velocity profiles can be computed for any generic planner and in [START_REF] Madhava Krishna | Moving safely but not slowly -reactively adapting paths for better trajectory times[END_REF] we presented initial simulation and experimental results of the reactive version of [START_REF] Alami | On the influence of sensor capacities and environment dynamics onto collision-free motion plans[END_REF]. Related work can be cited in the areas of modifying global plans using sensory data obtained during execution for overcoming uncertainty accumulated during motions [START_REF] Bouilly | A numerical technique for planning motion strategies of a mobile robot in presence of uncertainty[END_REF] and those that try to bridge the gap between planning and uncertainty [START_REF] Lazanas | Motion planning with uncertainty: a landmark approach[END_REF] or planning and control [START_REF] Khatib | Indoor navigation with uncertainty using sensorbased motions[END_REF] [START_REF] Alvarez | Accounting for mobile robot dynamics in sensorbased motion planning: experimental results[END_REF]. The velocity obstacle concept [START_REF] Schiller | Motion planning in dynamic environments: Obstacles moving along arbitrary trajectories[END_REF][5] bears resemblance to the current endeavor in that they involve selection of a robot velocity that avoids any number of moving objects. The difference is that in the present approach the only information about the mobile object available is the bound on velocity. The direction of motion and the actual velocities are not known during computation of the velocity profile. The work of Stachniss [START_REF] Stachniss | An integrated approach to goal-directed obstacle avoidance under dynamic constraints for dynamic environments[END_REF] also involves considering the robot's pose and velocities at the planning phase. A path is determined in the (x, y) space and a subgoal is chosen. A sequence of linear and angular velocities, (v, w), is furnished till the subgoal is reached. In [START_REF] Roy | Motion planning through policy search[END_REF] a policy search approach is presented that projects a low dimensional intermediate plan to a higher dimensional space where the orientation and velocity are included. As a result better motion plans are generated that enable better execution of the plan by the robot. The current effort has similarities to [START_REF] Roy | Motion planning through policy search[END_REF], at the planning level but also extends it to a suitable reactive level in the presence of new obstacles encountered during execution. Similarly the dynamic window approach [START_REF] Fox | The Dynamic Window Approach to Collision Avoidance[END_REF] and the global dynamic window method of Brock et.al. [START_REF] Brock | High Speed Navigation using the Global Dynamic Window Approach[END_REF] both incorporate the dynamics and the kinematics of the robot for a reactive collision avoidance system. Incorporating the dynamics and searching in the space of velocities overcome the problems of purely geomet-ric methods. However these methods do not speak of modifying the path in order to reduce its time-length and the dynamics of the environment does not affect the computation of the velocity profile, which places our approach as different from those mentioned above.

Problem Definition

The following problems are addressed in the paper, given: Problem 1: Given a robot's path τ (s) computed by a standard planner [START_REF] Latombe | Robot Motion Planning[END_REF], determine the maximal velocity profile v τ (s) such that, considering the constraints imposed by its dynamics, the robot can stop before collision occurs with any of the mobile objects that could emerge from regions not visible to the robot at position s ∈ τ (s). For example the velocity profile dictates that the robot in Figure 1 slow down near the doorway in expectation of mobile objects from the other side. We call M P = (τ (s), v τ (s)) a robust motion plan. The velocity profile allows us to define the time T (τ ) required for the robust execution of path τ :

• A robot R
T (τ ) = L 0 ds v τ (s)
Problem 2: Modify the planned trajectory such that the overall trajectory time T (τ ) is reduced. For example, the path of Figure 2, albeit longer than the one of Figure 1 is traversed in a shorter time.

Problem 3 Adapt the path and velocities reactively in the presence of new objects not a part of the original workspace such that the criteria of safe velocities and reduced time of path continue to be respected. This is illustrated in Figure 3.

From path to robust motion plan

The procedure for computing the maximum velocity profile v τ (s) delineated in Sections 3.1, 3.2 and 3.3 addresses the first problem. The constraints imposed by the environment on the robot's velocity are due to two categories of mobile objects. The first category consists of mobile objects that could appear from anywhere outside the boundary of the visibility circle C vis . The second category involves mobile objects that could emerge from shadows created in C vis due to stationary objects. No obstacles in C vis In the simple case where the robot's position is such that no static obstacle lies inside C vis , a moving object may appear (at time t = 0) anywhere on C vis 's boundary (Fig. 4). Let V rb denote the maximum possible robot velocity due to a mobile object at the boundary. At time t 0 = v rb /a -m (i.e., when the robot is stopped), the distance crossed by the object is d obj (v rb ) ≤ v ob v rb /a -m . Avoiding any potential collision imposes that R vis ≥ d rb (v rb ) + d obj (v rb ), where d rb = v 2 rb /2a -m . The condition relates v rb to the sensor's range R vis as:

Velocity constraints due to the environment

C vis v(0) = v rob 0 v(t )=0 d obj d rob v obj v(t)= v -a t rob m v rob
v rb = -v ob + v 2 ob + 2a -m R vis (1)
Influence of shadowing corners Static obstacles lying inside C vis may create shadows (e.g., see the grey region of Figure 5) which contain mobile objects. The worst-case situation occurs when the mobile object remains unseen until it arrives at the shadowing corner of a polygonal obstacle. Since the mobile object's motion direction is not known it is best modeled for a worst case scenario as an expanding circular wave of radius v ob t centered at (d, θ)

(X(t) -d cos θ) 2 + (Y (t) -d sin θ) 2 = v 2 ob t 2
Let us first consider that the robot's path τ is a straight segment. Considering that the intersections between the circular wave and the robot's segment path, should never reach the robot before it stops at time t 0 = v rs /a -m yields the following velocity constraint:

v 4 rsv -4(a -m d cos θ + v 2 ob )v 2 rsv + 4a 2 -m d 2 ≥ 0 (2)
Here v rsv is the maximum possible robot velocity due to the shadowing vertex under consideration. The solution of Eq. 2 gives v rsv , as a function of (d, θ). This solution only exists under the condition v ob > a -m d(1 -cos θ), i.e., when the object's velocity v ob is sufficiently high to interfere with the robot's halting path. Otherwise, the shadowing corner does not constrain the robot's velocity which can be set to v rm , the maximum bound on robot's velocity.

Similar reasoning can be applied to the case where the robot traverses a circular arc path of radius ρ. This case however leads to a nonlinear equation that needs to be solved numerically to derive the maximal velocity [START_REF] Cruzel | Planification de mouvements sous contraintes de perception[END_REF]. The expression that needs to be solved for computing the maximum velocity at a given point on a circular arc is of the form :

((v 2 rsv v 2 ob )/a 2 -m ) + 2ρ 2 cos(v 2 ob /2a -m ρ)+ 2dρ sin((v 2 ob /2a -m ρ) -θ) = d 2 + 2ρ 2 -2dρ sin θ (3)

Computing the shadowing corners

The problem of determining the set of shadowing corners needed for the velocity computation in Section 3.1 is the problem of extracting those vertices of the polygonal obstacle to which a ray emitted from the robot's center is tangential (Figure 6). The set of shadowing corners can be easily extracted from an algorithm that outputs the visibility polygon [START_REF] Suri | Worst-case optimal algorithms for constructing visibility polygons with holes[END_REF] as a sorted list of vertices.

Computing the velocity profile v τ (s)

While the methodology for computing the maximum velocity profile delineated here is essentially for a holonomic path, its extension to the non-holonomic case is not very difficult.

1. A holonomic path τ , consisting of a sequence of straight line segments ab, bc, cd (Fig. 7) is deformed into a sequence of straight lines and clothoids to ensure continuity of velocities at the bends [START_REF] Fleury | Primitives for smoothing mobile robot trajectories[END_REF]. The maximum deviation from an endpoint to its clothoidal arc (depicted as e in Figure 7) is dependent on the nearest distance to an object from the endpoint under consideration. 2. The linear velocity along a clothoid is a constant and the maximum possible linear velocity considering robot dynamics alone is calculated for each of the clothoidal arc a1b0, b1c0 according to [START_REF] Fleury | Primitives for smoothing mobile robot trajectories[END_REF] and is represented as v c (a1), v c (b1). 3. The straight segment aa1 is discretized into M equally spaced points, excluding the endpoints of the segment, viz. a and a1. We denote the first such point as a 1 and the last such point as a M . The point of entry into the clothoid, viz. a1 is also denoted as a M +1 . 4. For each of the N points, a i , the steps 4a to 4e are repeated. 4a Maximum possible velocity that a robot could have such that it can come to a halt before colliding with objects that enter into the robot's field of vision from the boundary is computed as v rb (a i ) according to Equation 1. 4b Velocity of the robot due to stationary obstacles inside the robot's field of vision that create shadows is computed as v rsv (a i ) according to Equation 2. The minimum of all the velocities due to such vertices is found and denoted as v rs (a i ). 4c The maximum possible velocity of the robot at a i due to environment is then computed as

v re (a i ) = min(v rb (a i ), v rs (a i )) (4)
4d Velocity of the robot at a i due to its own dynamics is given by

v rd (a i ) = v 2 r (a i-1 ) + 2a m s(a i , a i-1 ) (5)
The above equation is computed if v re (a i ) > v r (a i-1 ). Here s(a i , a i-1 ) represents the distance between the points a i and a i-1 . a m represents the maximum acceleration of the robot. 4e The eventual velocity at a i is given by

v r (a i ) = min(v rd (a i ), v re (a i ), v rm ) (6)
Here v rm represents the maximum robot velocity permissible due to servo motor constants. 5. The velocity at the endpoint a1 is computed as v r (a1) = min(v r (a1), v c (a1)) and this would be the linear velocity with which the robot would traverse the clothoid. 6. Steps 6a and 6b are performed by going backwards on each of the N points from a N to a 1 . 6a If v r (a i ) > v r (a i+1 ) then the modified maximum possible velocity at a i is computed as

v rd (a i ) = v 2 r (a i+1 ) + 2a -m s(a i , a i+1 ) (7)
6b Finally the maximum safe velocity at a i is given as v r (a i ) = min(v r (a i ), v rd (a i )). 7. Repeat steps 3 to 6 for all the remaining straight segments to obtain the maximal velocity profile over a given trajectory τ as v τ (s) = {v r (a), v r (a 1 ), ..., v r (a N ), v r (a1), v r (b 1 ), ..., v r (d)}.

Modifying planned trajectory for lower time

The knowledge of the maximum velocity profile over a trajectory is utilized to tackle the problem posed in Section 2 of reducing the overall trajectory time of the path. The procedure for reducing trajectory time at the planning stage involves random deformation of the planned path and evaluating time along this path. The modified path becomes the new trajectory if time along it is less than along the original trajectory. The process is continued till over a finite number of attempts no further minimization of trajectory time is possible. Prior to delineating the algorithm it is to be noted that the set of all collision free space of the workspace is denoted as C f ree and the current trajectory of the robot as τ c (s). A point of discretization on a trajectory discretized into N parts is denoted as p(s i ), i ∈ {1, 2, ..., N }. The corresponding configuration of the robot at those points is denoted by q(s i ). The algorithm is given as Algorithm 1.

Algorithm 1 Globally reducing trajectory time

1: N try ← 0 2: while N try < N attempts do 3:

Discretize current trajectory τ c (s) into N p parts where N p is selected based on minimum discretization distance between two points.

4:

Set f lag ← 0 5:

for i = 1 to N p do 6:
Compute minimum velocity at s i due to shadowing vertices as v rmin (s i )

7: if v rmin (s i ) < v rm then 8:
Find a configuration q(s p ) ∈ C f ree and s p / ∈ τ c (s k ), k ∈ {1, ..., N p } such that q(s p ) is reachable from q(s i ).

9:

Find a point s r on the remaining part of the trajectory, s r ∈ τ c (s j ); i < j ≤ N p such that q(s r ) is reachable from q(s p ).

10:

Form a new trajectory through s i , s p , s q and denote it as τ n (s)

11: if T (τ n ) < T (τ c ) then 12:
discretize τ n into N q points. end if 22: end while

Step 8 of the algorithm is carried out by searching for a collision free configuration which would displace the path away from the shadowing vertex responsible for the lowest velocity at s i . Step 11 adapts the displaced path as the new current path if its trajectory time is less than the current path. N attempts , is the number of unsuccessful attempts at minimizing trajectory time before the algorithm halts.

Remembering Sensor Information

The computation of the velocity profile at a given point on the robot's trajectory incorporates the robot's field of vision at that point. This field can change appreciably between two successive instances of computation. For example in Figure 8 the robot at position a has full field of vision of the corridor that is transverse to the robot's trajectory. However at position b the robot is blind to the zone shown in darker shade of gray. Hence it needs to slow down as it moves further down to c since it envisages the possibility of a moving object approaching it from the corners of the stationary objects. These corners are the starting areas of the robot's blindzone at b. However, if the robot could remember the earlier scene it could use this when computing its velocity profile during execution of the planned path. In such a case, if the robot did not see any moving objects in close proximity at a it can make use of this information at b to have a velocity profile from b that is greater than the one computed in the absence of such information. Figure 8 shows (in darker shade) the zone remembered by the robot. The contour of the remembered area represents the blindzone of the robot at b, from where mobile objects can emanate. The area in lighter shade of gray is the visibility polygon for the robot at b. With the passage of time the frontier of the remembered area shrinks due to the advancement of the imagined mobile objects from the initial frontier. The details of this scheme are given below.

Remembering is fruitful when a non-shadowing vertex begins to cast a shadow thereby hiding regions which were previously visible. The set of all ver- tices that are currently visible, shadowing and were at some prior instant visible, non-shadowing is denoted by V sns. For every vertex ve ∈ V sns a corresponding vertex is associated and called the blind vertex. The blind vertices are of three categories explained in Figure 9 where the vertex a, non-shadowing for the robot at p becomes shadowing when the robot is at q. Correspondingly the vertex c of the triangular obstacle which was visible and shadowing when the robot was at p becomes invisible when the robot moves to q. Simultaneously one of the other end-points of a, viz. b, would also become inevitably invisible at q. Vertices like b fall in the second category. If b was already outside C vis at p the intersection of C vis with the segment ab, namely o is identified as the third category of blind vertex. The set of all such vertices is denoted by V bs. These vertices are advanced by a distance v ob ∆t where ∆t is the time taken by the robot between p and q to new virtual locations along the line that connects those vertices to a. At q the velocity is computed due to the closest of the vertices in the set V bs at their virtual locations instead of a, which is otherwise the vertex for which equation( 2) is computed.. Such a trend continues till the distance between the robot to the closest hypothetical vertex is less than the actual distance of the robot to a.

The remembering part of the algorithm is given in algorithm 2. The set of all visible shadowing vertices is denoted by V sh.

From Plan to Execution

The velocity profile, v τ (s), is a sequence of maximum velocities calculated at discretized locations along the trajectory τ (s). The locations at which the velocity profile at the execution stage is computed are not the same locations as where the profile was computed during planning, due to odometric and motor if v e ∈ V sns then Compute velocity due to the virtual vertex v bc through Equation 29:

else 10:

Compute velocity due to the actual vertex v e through Equation 211:

end if 12:
end if 13: end for constraints. Moreover, if there are changes in the environment it entails modifying the trajectory and hence the velocities. During execution it is computationally expensive to compute the profile for the entire remaining trajectory, hence the profile is computed for the next finite distance, given by, d saf e = d max + nd samp , where d max = v 2 rm /(2 * a -m ), represents the distance required by the robot to come to a halt while it moves with the maximum permissible velocity afforded by motor constants. And d samp = v rm t samp is the maximum possible distance that the robot can move between two successive samples (time instants) of transmitting motion commands, where time between two samples is t samp .

The main issue here is what should be the distance over which the velocity profile needs to be computed during execution such that it is safe. A velocity command is not considered safe if it is less than the current velocity and not attainable within the next sample. The velocity is constrained by the environment as well as robot's own dynamics and hence their roles are studied below.

Effect of Environment Mobile objects that can emerge from corners in a head-on direction cause the greatest change in velocity over two samples. Figure 10 shows one such situation, where the rectangular object casts a shadow and is susceptible to hide mobile objects. Let the current velocity of the robot at a due to the object be v 1 . Let the velocity at a distance, s, from a, at b (Fig. 10) due to the object be v 2 . The velocities at a and b are given by

v a = -v ob + v 2 ob + 2a -m d ( 8
)
v b = -v ob + v 2 ob + 2a -m (d -s) (9) Hence v 2 a -v 2 b = 2a -m s+ 2v ob ( v 2 ob + 2a -m (d -s) -v 2 ob + 2a -m d) (10)
Evidently the second term on the right hand side of Equation 10 is negative, since the second square root term is more positive than the first. Hence

v 2 a -v 2 b ≤ 2a -m s.
Therefore the velocity at b, v b can be attained from the velocity at a, v a under maximum deceleration, d m , irrespective of the maximum velocity of the mobile object or the robot's own motor constraints. This was intuitively expected since the robot's velocity at any location is the maximum possible velocity that guarantees immobility before collision; its velocity at a subsequent location permitted by the environment would be greater than or equal to the velocity at the same location obtained under maximum deceleration from the previous location. In other words for safeness of velocity going purely by environmental considerations it would suffice to calculate the velocity, for the next sampling distance alone, for without loss of generality, d = d samp .

Effect of robot's dynamics

The robot needs to respect the velocity constraints imposed while nearing the clothoidal arcs and eventually while coming to the target. The robot can reach zero velocity from its maximum velocity over a distance of d max , computed before. Hence d max + d samp represents the safe distance over which the velocities need to be computed.

Online path adaptation for better trajectory time

The third of the problems outlined in Section 2 is tackled here. During navigation the robot in general comes across objects hitherto not a part of the map.

The robot reacts to these new objects in line with the basic philosophy of safety as well as time reduced paths. The adaptation proceeds by finding locations over a finite portion of the future trajectory where drops in velocity occur and pushing the trajectory away from those vertices of the objects that caused these drops to areas in free space where higher velocities are possible. A search is made through the newly found locations of higher velocities for a time reduced path.

Generalized Procedure The generalized procedure for adapting the path in the presence of new objects is delineated through Figure 11. 1. On the trajectory segment that is currently traversed, AB in Figure 11, enumerate the vertices of objects that reduce the velocity of the robot. 2. The positions are found on AB where the influence of vertices is likely to be maximal. 3. These positions are pushed by distances d p = k(v l -v r ), where v l and v r are the velocities at that location on the path due to the most influential vertices on the left and right of the path. These new locations are denoted as p1, p2, p3, p4 (Fig. 11) and maintained as a list provided the velocity at the new locations is higher than the original ones. p6 is the farthest point on the robot's trajectory visible from its current location at A. 4. On this set of locations A, p1, p2, p3, p4, p5, p6 starting from the current location at A, find a trajectory sequence shorter in time than the current sequence of A, B, p6 if it exists. 5. The steps 1 to 4 are repeated until the robot reaches the target.

It should be noted that when a collision with an object is detected, a collision free location is first found that connects the current location with another location on the original trajectory and this new collision free path is further adapted for a time-reduced path if it exists. Also note that while the velocities are computed over a distance d saf e , that part of the remaining trajectory that is visible from the current location is considered for adapting to a better time-length.

Planning Results and Analysis

In this section the results of incorporating the velocity profile computation as a consequence of considering robot and environment dynamics and sensor capacities at the planning stage and the subsequent adaptation of paths to better time of trajectory is analyzed. Figure 12 shows the path computed by a typical holonomic planner [START_REF] Latombe | Robot Motion Planning[END_REF] and its corresponding velocity profile. The velocity corresponding to the robot's location on the trajectory (shown as a small circle) is marked by a straight line labeled m on the profile. The dark star-shaped polygon centered at the robot depicts the visibility of the robot at that instant and is called the visibility polygon. The figure is a snapshot of the instant when the robot begins to decelerate to a velocity less than half the current velocity as it closes down on the vertex a marked in the figure. Evidently from the visibility polygon the vertex a casts a shadow and the closer the robot gets to it, the slower the velocity must be.

Figure 13 is the time reduced counterpart of Figure 12. The snapshot is once again at a location close to vertex a. Staying away from a permits nearly maximum velocity. The dip observed in the profile due to vertex a is negligible. Similarly staying away from other vertices such as b allows for a trajectory time of 21.79s compared to 26.30s for Figure 12. Mod- ification of the trajectory for shorter time proceeds along the lines of Section 3.4. For the two examples discussed, the robot's maximum acceleration and deceleration was fixed at 1m/s 2 , maximum velocity at 1m/s and the sensor range at 7m. The maximum bound on the object's velocities was 1.5m/s.

Figures 14 and15 depict the planned trajectory and velocity profiles before and after reduction of trajectory time for our laboratory environment. The time reduced trajectory is shorter by more than 8 seconds as it widens its field of view by moving away from the bends while turning around them.

Effect of remembering on trajectory time

Figure 16 shows an environment with four corridors named 1, 2, 3 and 4 with planned path obtained by minimizing time. It also portrays the robot's field of vision as it enters corridor 3. The velocity profile for the above path is shown in Figure 17. The location of the robot corresponding to its location in Figure 16 is shown through the vertical line. The locations of the robot as it decelerates when its field of view of each of the corridors vanishes is also marked with the respective numbers on the profile. Though the path of Figure 16 is minimized in time its velocity profile still shows decelerations in the vicinity of the corridors. This is due to the phenomenon discussed in Section 3.5 where the robot becomes blind to many parts of the environment it had seen at the preceding instant. Figure 18 shows the robot's field of vision at an instant after the one shown in figure 16. There is a marked decrease in its field of vision at the latter instant that results in the robot reducing its velocity in anticipation of moving objects from the blindzones depicted in the velocity profile. 6 Experimental Results

Velocity profiles

In this section the velocity profiles obtained during the planning and execution stages are compared in the absence of any new objects during execution. Figure 20 shows a simple planned trajectory and the corresponding velocity profile for our lab environment. Some of the obstacles are filled in gray and others are shown as segments (in gray). The robot is shown as a small circle and the star shaped polygon in black represents the field of vision of the robot at that location. The vertical line, marked m in the velocity profile represents the velocity of the robot corresponding to its position on the trajectory. The profile shows a subsequent drop in velocity, a consequent of robot getting closer to region marked, d, to which it is blind.

Figure 21 compares the planned and executed (in simulation) velocity profile. The executed trajectory tallied to a time of 12.28s in comparison with 12.25s for the planned profile. These figures illustrate that the executed profiles and execution times are close to the planned profiles and times while there are no changes in the environment.

Figures 23 and24 show the execution by the Nomad XR4000 (Fig. 22) of paths computed by a standard planner. Figure 23

Online adaptation of paths for better trajectory time

This section presents results of the algorithm in the presence of newly added objects that affect the velocities of the robot in real-time. Figure 26 shows a path where the robot avoids the two new segments S1 and S2 intersecting the original planned trajectory but does not adapt its path for better time. The velocity profile for the same is shown in Figure 27. Figure 28 is the counterpart of Figure 29 where the robot adapts its path to a better time-length reactively. The big dips in the velocity profile of Figure 27

Conclusions and Scope

A proactive safe planning algorithm and its reactive version that facilitates real-time execution has been presented. The proactive nature of the algo- rithm stems from the computed velocity profile, v τ (s), that guarantees immobility of the robot before collision with any of the possible mobiles that could interfere its future trajectory from regions blind to its sensor. The proactivity does not however come at the cost of robot's velocity or trajectory time. The knowledge of v τ (s) computed over the trajectory τ (s) further facilitates reduction of the over all trajectory time T (τ ) by adaptation of the initially planned path. Analysis of the scheme at the planning stage depict that the robot can have a velocity profile that achieves its maximum possible velocity for a sustained duration without many dips provided it stays away from doorways and narrow passages along its path. Remembering of previous scenes also enhances the robot's performance through reduced trajectory time and a more uniform velocity profile.

A reactive extension of the scheme that facilitates real-time simulation and implementation is also presented. The scheme maintains the underlying philosophy of computing safe velocities and modification of paths for better trajectory time. Simulation and experimental results at real-time corroborate our earlier results obtained at the planning stage (that by keeping away from vertices of objects that could hide mobiles the robot could move at higher velocities and obtain better time-lengths) and thus the efficacy of overall strategy is vindicated. The minimum distance over which the velocities need to be computed on the remaining trajectory during real-time such that the computed velocities are safe is theoretically established. This avoids repetitive computation of velocities over the entire remaining trajectory for every motion command, thereby reducing computational intensity and facilitating for real-time implementation. The methodology could be useful in the context of personal robots moving in areas where interference with mobile humans especially aged ones are generally expected.

Immediate scope of this work involves in incorporating the memory phenomena at the reactive level such that higher speeds are possible. The methodology needs to be validated in the presence of mobile objects that actually impinge on the path from blindzones with a provision for the robot to avoid the objects without halting, continuing to respect safety considerations as well as minimizing trajectory time.

Figure 1 :

 1 Figure 1: A safe robot has to slow down while approaching the doorway

Figure 3 :

 3 Figure 3: How does the robot adapt its path in the presence of new segments (a, b) and (c, d) while maintaining safe velocities?

  modelled as a disc and equipped with an omnidirectional sensor having a limited range R vis . We call C vis the visibility circle, centered at robot's position with radius R vis . The paths of R are sequences of straight segments or straight segments connected with circular arcs of radius ρ in case of a non-holonomic robot. The robot's motion is subject to dynamic constraints simply modelled by a bounded linear velocity v ∈ [0, v rm ] and a bounded acceleration a ∈ [-a -m , a m ]. The maximum possible deceleration a -m need not equal the maximum acceleration a m . • A workspace cluttered by static polygonal obstacles O i . The static obstacles can hide possible mobile objects whose motions are not predictable; the only information is their bounded velocity v ob .

Figure 4 :

 4 Figure 4: Mobile objects may appear anywhere on Cvis's contour.

Figure 5 :

 5 Figure 5: Mobile objects may also appear from the shadows of static obstacles

Figure 6 :

 6 Figure 6: Shadowing corners: among the three vertices of V(p), only s2 and s3 create shadows (the line going through s1 is not tangent to the left obstacle).

Figure 7 :

 7 Figure 7: A holonomic path deformed into a sequence of straight segments and clothoidal arcs.

Figure 8 :

 8 Figure 8: Memorization of previous scenes

Figure 9 :

 9 Figure 9: Three categories of blind vertices.

Algorithm 2

 2 Remembering effects on velocity 1: for each vertex v e ∈ V sh do 2:

3 : 4 :v b by v ob ∆t 5 : end for 6 : 7 :

 34567 for each vertex v b ∈ V bs associated with v e do Advance Denote the distance from the robot's current location, s c , to the closest of all advanced vertices, v bc as d cvb if d(s c , v e ) < d cvb then 8:

Figure 10 :

 10 Figure 10: Effect of an obstacle on the robot's velocity, possibly hiding mobiles objets at locations a and b.

Figure 11 :

 11 Figure 11: A trajectory in the presence of new objects. The points marked with crosses represent locations through which a path is searched for reduced time of trajectory.

Figure 12 :

 12 Figure 12: Path computed by a typical planner and its velocity profile shown on the top. The robot's velocity corresponding to its location on the trajectory is shown by a vertical line on the profile and labeled as m.

Figure 13 :

 13 Figure 13: Path obtained after adaptation to reduced time-length.

Figure 14 :

 14 Figure 14: Planned trajectory before adaptation to a reduced time.

Figure 15 :

 15 Figure 15: Time reduced trajectory at planning stage.

Figure 16 :

 16 Figure 16: Robot's field of view as it enters corridor 3.

Figure 17 :

 17 Figure 17: Velocity profile for the Figure 16. Corresponding position of the robot shown in vertical line. Decelerations near the corridors are also marked with the same numbers.

Figure 18 :

 18 Figure 18: Robot's field of vision at an instant that immediately follows the instance of Figure 16.

Figure 19 :

 19 Figure 19: Velocity profile obtained after incorporation of memory

Figure 20 :

 20 Figure 20: A simple planned trajectory and its velocity profile.

  Figure 21: The planned and executed velocity profile in simulation. The ordinate measures velocity in m/s and abscissa time in seconds.

Figure 22 :

 22 Figure 22: The Nomad XR4000 used in our experiments at LAAS.

Figure 23 :

 23 Figure 23: Execution of the original planned path.

Figure 24 :

 24 Figure 24: Execution of the time-reduced path.

  are filtered in Figure29considerably as the robot avoids the obstacles with larger separation. The time reduced execution tallied to 10.9s while the unreduced version was executed in 12.5s. The trajectory time at planning was 7.9s. The above graphs are those obtained in simulation.

Figure 25 :

 25 Figure 25: The top profile corresponds to the path executed in Figure 23 and the bottom to Figure 24. The planned and executed velocity profile in simulation. The ordinate measures velocity in m/s and abscissa time in seconds.

Figure 26 :

 26 Figure 26: A simulated execution in the presence of two new segments S1 and S2 along with the corresponding velocity profile. The path is not adapted to better timelength. Start and goal locations marked as S and T .

Figure 30

 30 Figure 30 shows the unreduced executed path by the XR4000 Nomadic robot in our laboratory at LAAS. The obstacles in the original map are shown by black lines, while the segments perceived by the SICK laser are shown in lighter shades of gray. Some of these segments get mapped to the ones in the map and the others are considered new segments. This is done by a segment based localization algorithm. The segments of concern here are those which form a box shaped obstacle marked B in Figure 30. The vertex d of this

Figure 27 :

 27 Figure 27: Velocity profile for the execution of Figure 26.

Figure 28 :

 28 Figure 28: Path of Figure 26 adapted to better timelength.

Figure 29 :

 29 Figure 29: Velocity profile for the execution of Figure 28.

Figure 30 :

 30 Figure 30: Unreduced path executed by the Nomad XR4000. The vertex d of the new box shaped object B forces a slow down near it.

Figure 31 :

 31 Figure 31: Time reduced path executed by the Nomad XR4000.Increasing linear and angular separation from vertex d facilitates a higher speed.

Figure 32 :

 32 Figure 32: Velocity profile for the path executed by the Nomad in Figure 31. The planned and executed velocity profile in simulation. The ordinate measures velocity in m/s and abscissa time in seconds.

Acknowledgments

The work described in this paper was conducted within the EU Integrated Project COGNIRON ("The Cognitive Companion") and was funded by the European Commission Division FP6-IST Future and Emerging Technologies under Contract FP6-002020 and by the French National Program ROBEA.


Jim Mainprice

E Akin Sisbot

Thierry Siméon

Rachid Alami

Planning Safe and Legible Hand-over Motions for Human-Robot Interaction

Human-Robot interaction brings new challenges to motion planning. The human, who is generally considered as an obstacle for the robot, needs to be considered as a separate entity that has a position, a posture, a field of view and an activity. These properties can be represented as new constraints to the motion generation mechanisms.

In this paper we present three human related constraints to the motion planning for object hand over scenarios. We also describe a new planning method to consider these constraints. The resulting system automatically computes where the object should be transferred to the human, and the motion of the whole robot considering human's comfort.

I. INTRODUCTION

Human safety becomes more and more crucial with robots entering in our daily lives. Robots and humans working together in cooperation can accomplish more sophisticated tasks beneficing from the combined power and precision of the robot and of the reasoning and problem solving power of the human. This symbiotic relationship will bring new problems and challenges to the robotics research.

Clearly, in an environment where robots and humans work together, robot behaviors need to take explicitly into account the presence of humans. The physical hardware as well as software components of the robot need to be designed by considering human's safety [START_REF] Alami | Safe and dependable physical human-robot interaction in anthropic domains: State of the art and challenges[END_REF] [START_REF] Nonaka | Evaluation of human sense of security for coexisting robots using virtual reality. 1st report: evaluation of pick and place motion of humanoid robots[END_REF]. Besides ensuring safety in robot hardware with compliant designs [START_REF] Zinn | Playing it safe [human-friendly robots[END_REF] [START_REF] Bicchi | Fast and soft arm tactics: Dealing with the safety-performance trade-off in robot arms design and control[END_REF], the motions of the robot need to be "planned" in a "human-aware" way.

The need for considering the human presence in motion plans has been established through several user studies (e.g. [START_REF] Yoda | Basic study on avoidance motions for human behaviors[END_REF][6] [START_REF]Evaluation of passing distance for social robots[END_REF]). In particular, for manipulation tasks such as object fetch-and-carry, studies have shown the importance of approach directions [START_REF] Dautenhahn | How may i serve you?: a robot companion approaching a seated person in a helping context[END_REF], human-robot distances [START_REF] Yamaoka | How close?: model of proximity control for information-presenting robots[END_REF] and the simultaneous motion of robot parts [START_REF] Yamaoka | How close?: model of proximity control for information-presenting robots[END_REF]. Koay et al. [START_REF] Koay | Exploratory study of a robot approaching a person in the context of handling over an object[END_REF] conducted a detailed user study investigating the spatial relation between a human and a robot in an object handover task. This study has provided a number of metrics and has underlined the importance of coordinating robot lower and upper body motions.

In previous work [START_REF] Sisbot | Spatial reasoning for human-robot interaction[END_REF][12], we have presented a motion planner that explicitly takes into account human-robot constraints (e.g. their relative distance, the human's field of view and posture) to synthesize navigation and manipulation motions. This planner was based on human-robot user studies [10][13], as well as on existing human-human space sharing theories [START_REF] Hall | The Hidden Dimension[END_REF]. The proposed method was the first one to investigate a "planning" approach to the problem of CNRS ; LAAS ; 7 avenue du Colonel Roche, F-31077 Toulouse, France. Université de Toulouse ; UPS, INSA, INP, ISAE, LAAS, F-31077 Toulouse, France. lastname@laas.fr Fig. 1. An example scenario of a Human-Robot object hand-over task human-robot intelligent space sharing. HRI constraints were represented through cost functions depending respectively on the human kinematic model, field of view and accessibility. This representation of the problem led to costmaps defined over the workspace. Motion planning was solved using grid search techniques for planning object motions, and inverse kinematics to adapt the robot to follow the object path. While this approach is sufficient in an uncluttered environment where strong workspace constraints are absent, it may fail in a highly constraint scenario.

In this paper we present refinements of the previous costmap representations and their use by more sophisticated sampling-based planning methods.

The paper is organized as follows. Section II presents the motivation that led to model the HRI constraints as costmaps. Each criterion is detailed and its impact on the output trajectory is sketched in an object hand-over scenario. Section III describes a planning method and an optimization method adapted to costmaps. Section IV presents the results of the complete planner by combining the elementary costmaps in a unified framework. Finally, Section V concludes the paper by discussing the results and giving perspectives.

II. MOTION IN HUMAN PRESENCE

The presence of humans in the robot workspace brings new constraints to navigation and manipulation planning because of the close physical interaction with the human.

In our previous work [START_REF] Sisbot | Spatial reasoning for human-robot interaction[END_REF][12], we have presented a navigation and manipulation planner that considers a number of HRI constraints. Planning with these constraints results in a safe, legible and socially acceptable robot behavior. In this work, three of these constraints, namely safety, visibility and arm comfort, have been taken into account and refined. These constraints can be considered as examples of a broad variety of Human-Robot Interaction properties that can be taken be considered in the design of robot's reasoning capabilities.

We model these interaction constraints as costmaps attached to the human partner and which evaluate the surrounding space. A cost function represents each constraint by evaluating the quality of 3D points in the workspace of the human. These costmaps are then used in the planning method to generate complete robot motion plans.

A. Distance Constraint

The first constraint, called distance constraint, mainly focuses on ensuring the safety of the interaction by controlling the distance between the hand of the robot and the human. This property is represented by a costmap evaluating the risk to place over the hand of the robot at a given position.

The goal of this costmsp is to push the robot sufficiently far to avoid any collision risks. However in situations requiring close interaction (e.g. handing over an object), the robot has to approach the person whom it wants to interact with. Therefore, the distance between the robot and the human is neither uniform nor fixed and depends on the interaction. The feeling of safety is highly dependent on the humans personality, his physical capabilities and his actual states; for example, safety differs highly in a sitting position compared to standing. When the human is sitting, his mobility is reduced and he tends to have a low tolerance to the robot getting close. On the contrary, when standing up he has a higher mobility, thus allowing the robot to come closer.

The distance costmap is a human centered Gaussian in which each point of the workspace has a cost inversely proportional to the distance to the human. Therefore the farther a point is situated from the human, the lesser its cost will be until some maximal distance at which it becomes null. Figure 2 illustrates the Distance costmap around the human's torso. As seen in this figure, costs become less important when going farther from the human.

As distance costs grow when approaching to the human, planning a motion according to this function will result on a motion where the robot tries to stay as far as possible to the human. Figure 3 illustrates the effect of this property on the robot motions. Given an initial position (Fig. 3(a)) and a final position (Fig. 3(c)), the figure compares a path computed using a standard planner not considering HRI constraints (Fig. 3(b)) with a path generated by our planner (see section III) taking into account the distance costs (Fig. 3(d)). From a pure safety point of view, the resulting new path pushes the robot farther from the human and causes a safer behavior.

B. Visibility constraint

The second constraint aims to maintain the robot as visible as possible to the human. Humans, who have the robot in their field of view, generally feel more comfortable. This property is represented by costs, called Visibility costmap, Fig. 2. The Distance constraint is modeled by a spherical costmap. For a better illustration the sphere is cut horizontally. Red points having the highest costs and green points the lowest, this function evaluates a position around the human according to the distance between the robot and the human's torso. evaluating a 3D point around the human according to its place in human's field of view. This function generates a costmap around the human representing the effort required by the human to get the robot in his field of view. Figure 4 shows an example of visibility costmap. The greater the effort of the human is required to see a point, the greater the cost of that point will be. Fig. 4. The Visibility property and its representation as a costmap. The greater the effort of the human is required to see a point, the greater the cost of that point will be.

If we generate a path for the hand of the robot considering the visibility costs, the resulting path will be as visible as possible to the human. Such a path is illustrated in figure 5 along with a comparison to a path planned with RRT method.

C. Comfort costraint

The third constraint represents the comfort of the human. An important property to consider for evaluating a point in the environment is its level of accessibility. Depending on the position of the human hand, the position of the object can be hard, or impossible to reach. For a robot that interacts with a person this property is crucial to take into account, especially in object hand over scenarios, since the interaction should be comfortable and not physically challenging for the human.

We represent this property with a costmap modeling how much effort the human does to reach a certain point in the environment. A point around the range of human arm is reached by Generalized Inverse Kinematics algorithm [START_REF] Yamane | Natural motion animation through constraining and deconstraining at will[END_REF], [START_REF] Baerlocher | An inverse kinematics architecture enforcing an arbitrary number of strict priority levels[END_REF] by moving the arm and the torso of the human. The resulting posture is then evaluated by its comfort [START_REF] Katayama | Optimization principle determines human arm postures and "comfort[END_REF]. The comfort is estimated with two functions. The first function computes a joint angle distance from a resting posture to the actual posture and the second one considers the potential energy of the arm by measuring the height of the arm and forearm. A weighted sum is applied to merge both cost functions and to compute the final comfort cost of the posture. These cost functions favor comfortable and natural posture.

Figure 6 illustrates examples of reaching postures ordered by their comfort levels from left to right. The difference of comfort is clearly visible between the leftmost image where the human reaches a point around his hand, and the rightmost image where the human forces his kinematic structure to reach a point near his back. The comfort constraint is used to generate robot motions where the end effector maintains the object at positions as comfortable as possible for human grasp. Figure 8 illustrates the effect of this constraint in the motions of the robot. Given an initial (Fig. 8(a)) and a goal (Fig. 8(c)) configuration, a comparison is given between a motion planned by a standard planner (Fig. 8(b)) and a motion planned by taking into account the comfort constraint (Fig. 8(d)). In the latter case, the robot moves the object in a way that the human has always the possibility to reach the object in a comfortable way.

III. PLANNING HAND OVER MOTIONS

A. Computing a transfer point

For object hand over tasks, an important property to consider is the place where the object will be passed from the robot to the human. This point needs to be chosen by considering all the properties presented above in order to be safe, visible and comfortable.

In order to compute the most suitable place for the object transfer, namely Object Transfer Point, a weighted sum of all three costmaps is calculated. This new costmap evaluates the points around the human according to their distance, visibility and reachability to the human. A search to find the less costly point in this costmap, considering feasibility with respect to obstacles and robot kinematics, is used to generate the Object Transfer Point, the place where the robot will carry the object.

B. Planning on configuration space

1) Path planning: Several approaches have been proposed to extend sampling-based algorithms for computing goodquality paths with respect to cost functions. In particular, RRT variants [START_REF] Ettlin | Randomised Rough-Terrain Robot Motion Planning[END_REF], [START_REF] Urmson | Approaches for heuristically biasing RRT growth[END_REF], [START_REF] Diankov | Randomized statistical path planning[END_REF] have been introduced in the context of field robotics. In this work, we apply a more general algorithm, called T-RRT [START_REF] Jaillet | Sampling-based path planning on configuration-space costmaps[END_REF], briefly explained below. This section also presents a new method for local optimization of the solution through a post-processing phase that can handle a general cost function defined over the configuration space [START_REF] Mainprice | Planning human-aware motions using a sampling-based costmap planner[END_REF].

As the constraints described in section II are represented by costmaps, they are perfectly suitable for the T-RRT planning algorithm. Distance, visibility and comfort costmaps are merged together with a weighted sum as follows:

c(h, q) = N i=1 w i c i (h, F K(q)),
where q is a configuration and FK the robot's forward kinematics function.

The T-RRT algorithm [START_REF] Jaillet | Sampling-based path planning on configuration-space costmaps[END_REF] takes advantage of the performance of two methods. First, it benefits from the exploratory strength of RRT-like planners resulting from their expansion bias toward large Voronoi regions of the space. Additionally, it integrates features of stochastic optimization methods, which apply transition tests to accept or reject potential states. It makes the search follow valleys and saddle points of the cost-space in order to compute low-cost solution paths (see Figure 9). This planning process leads to solution paths with low value of the integral of cost regarding the input costmap landscape.

Similarly to the Extend version of the basic RRT algorithm [START_REF] Lavalle | Rapidly-exploring random trees: Progress and prospects[END_REF], a configuration is randomly sampled. It yields both the nearest tree node to be extended, and the extension direction. This stage also integrates collision detections in the presence of binary obstacles. Thus, if the new portion of the path leads to a collision, a null configuration is returned and the extension fails independently of the associated costs. This extension process ensures the bias toward unexplored free regions of the space. In the second stage irrelevant configurations regarding the search of low cost paths are filtered using a transition test similar to the one used in stochastic optimization methodsbefore inserting a new configuration in the tree. 2) Local optimization: In order to optimize paths generated by the motion planner, we employ an extension of the shortcut method. This extension is similar to the original approach, but the cost of the path is tested together with collisions and kinematic constraints.

This method reduces the length of the input path while improving its quality, and usually converges rapidly to a local minimum (Figure 10).

IV. EXAMPLE & RESULTS

By taking into account the three constraints, the overall system is able to generate comfortable object transfer positions, and to compute a visible, safe and comfortable robot paths to move the object to this hand over position. Figure 11 shows a kitchen scenario as a complete illustration by using all above mentioned models and methods.

In this example, the robot is holding a glass in its hand while the human is sitting and looking at his left (human gaze direction is illustrated with a blue line in figure 11(a)). The goal of the robot is to hand over the object. The final position of the object (Object transfer point) is automatically computed by the planner. As the three constraints are considered during this computation, the resulting position is already safe, visible and comfortable to reach by the human, and will be used as the target configuration (Fig. 11(b)).

Figure 11(b) illustrates a path generated by a classical motion planner. The robot follows a direct path without considering any constraints on human. On the other hand, the solution obtained by our human-aware planner has interesting properties (Fig. 11(c)): all along the path, the robot stays sufficiently far from the human and avoids penetrating his safety bubble; the path deviates towards human's gaze direction to ensure the visibility of the object; and for the last part of the path the object is comfortaby reachable to the human.

V. CONCLUSION

In this paper we have presented three constraints that increase the quality of the human-robot interaction in motion planning level. Each one of these constraints, namely Distance, Visibility and Comfort, represents an important property related to the position, kinematics and field of view of the human. A planning method and a transfer point generation method is also presented and the results of the overall system is illustrated by an example.

An important aspect of the interaction to take into account in our perspectives is the motions of the human partner. While planning for itself, the robot can also plan for the human in order to find cooperative solutions involving the robot and the human moving together. This will allow us to generate plans where the human contributes, thus opening the door to a wider solution set.

  (a) Initial Robot Position (b) Motion generated by a standard method. (c) Target Robot Position (d) Motion generated by taking into account Distance cost.

Fig. 3 .

 3 Fig. 3. A comparison between a motion generated by a standard planner and another one generated by considering the Distance constraint. With the help of this costmap the robot moves the object sufficiently far from the human while going to the desired position.

  (a) Initial Robot Position (b) Motion generated by a standard method. (c) Target Robot Position (d) Motion generated by taking into account Visibility cost.

Fig. 5 .

 5 Fig.5. A comparison between a motion generated by a standard planner and another one generated by considering the Visibility cost. The center of human's field of view is illustrated with the blue line. With the help of this cost function the robot moves the object in a way that it stays as visible as possible to the human. Meanwhile the standard planning method generates a direct yet "risky" motion without considering where the human is looking at.

Fig. 6 .

 6 Fig. 6. Reaching postures for the human ordered from a comfortable (left) to a less comfortable (right) position.

Figure 7

 7 Figure 7 illustrates a costmap built around the human representing the comfort of human's left arm. As the energy increases, the effort also increases to reach higher positions. The positions requiring a minimal effort are evaluated as

Fig. 7 .

 7 Fig. 7. The arm comfort costmap for the left arm of the human.

  (a) Initial Robot Position (b) Motion generated by a standard method. (c) Target Robot Position (d) Motion generated by taking into account Comfort cost.

Fig. 8 .

 8 Fig.8. A comparison between motion generated by a standard planner and another one generated by taking into account Comfort cost. In the latter case, the robot moves the object in a way that the human has always the possibility to reach the object in a comfortable way.

Fig. 9 .

 9 Fig. 9. T-RRT constructed on a 2D costmap (left). The transition test favors the exploration of low-cost regions, resulting in good-quality paths (right).

Fig. 10 .

 10 Fig. 10. A medium-quality path in black is improved red path by the two local path-optimization methods resulting in the red path. The Shortcut method (left) converges more quickly to a local minimum, while the P erturbation method (right) is less local and tends to further improve the path.

  (a) Initial Robot Position (b) Target Robot Position (c) Motion generated by a standard method. (d) Motion generated by taking into all three cost functions.

Fig. 11 .

 11 Fig.11. A complete object hand over example scenario. The robot has the object in its hand. The human is sitting on a chair looking at his left. While the motion planned with a standard planner does not consider the presence of the human, the one planned by taking into account the three constraints generates a comfortable motion. By following this path the robot stays as visible as possible, as sufficiently far as possible and the object is comfortable to reach by the human.

VI. ACKNOWLEDGMENTS

The research leading to these results has been partially funded by the European Community's Seventh Framework Program with DEXMART project under grant agreement no 216239, with CHRIS project under grant agreement no 215805 and with ANR Psirob AMORCES project.


Jim Mainprice

Emrah Akin Sisbot

Léonard Jaillet
email: ljaillet@iri.upc.edu

Juan Cortés

Rachid Alami

Thierry Simeon

E Akin Sisbot

Thierry Siméon

Planning human-aware motions using a sampling-based costmap planner

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

I. INTRODUCTION

In an environment where robots and humans co-exist and work together, robot motions need to explicitly take into account the presence of humans. Therefore, hardware as well as software components need to be designed by considering human's safety [START_REF] Alami | Safe and dependable physical human-robot interaction in anthropic domains: State of the art and challenges[END_REF], [START_REF] Nonaka | Evaluation of human sense of security for coexisting robots using virtual reality. 1st report: evaluation of pick and place motion of humanoid robots[END_REF]. Besides ensuring safety in robot hardware with compliant designs [START_REF] Zinn | Playing it safe [human-friendly robots[END_REF], [START_REF] Bicchi | Fast and soft arm tactics: Dealing with the safety-performance trade-off in robot arms design and control[END_REF], the motions of the robot need to be planned in a "human-aware" manner.

In previous work [START_REF] Sisbot | Spatial reasoning for human-robot interaction[END_REF], [START_REF] Emrah Akin | Human aware mobile robot motion planner[END_REF], we have presented a motion planner that explicitly takes into account human-robot constraints (e.g. their relative distance, the human's field of view and posture) to synthesize navigation and manipulation motions. This planner was based on human-robot user studies [START_REF] Koay | Exploratory study of a robot approaching a person in the context of handling over an object[END_REF], [START_REF] Cogniron | Cogniron project ra3 final deliverable[END_REF], as well as on existing human-human space sharing theories [START_REF] Hall | A system for the notation of proxemic behavior[END_REF]. The proposed method was to our knowledge the first to investigate a "planning" approach to the problem of human-robot intelligent space sharing. HRI constraints were represented through cost functions depending respectively on the human kinematic model, field of view and accessibility. This representation of the problem led to costmaps defined over the workspace. Motion planning was solved using grid search techniques for planning object motions, and generalized inverse kinematics for the robot to follow the planned object path. While this decoupled approach is sufficient in the absence of strong workspace constraints, it may fail in cluttered environments such as shown in Figure 1.

In this paper we extend the capabilities of the planner using sampling-based planning algorithms, which enable planning in the robot configuration space and permit to find human-aware motions in cluttered environments. Samplingbased path planning methods [START_REF] Choset | Principles of robot motion: theory, algorithms, and implementation[END_REF], [START_REF] Lavalle | Planning algorithms[END_REF], are able to handle complex problems in high-dimensional spaces. How-Fig. 1.

A cluttered environment such as a home provides a difficult workspace for the robot motion planning in which the human presence adds new constraints. In this paper we propose to use a sampling-based method to achieve high-dimensional optimal planning regarding cost functions designed to take explicitly the human into account. ever, they usually operate in a binary configuration space, aiming to find out feasible collision-free solutions rather than optimal paths. Moreover, due to their probabilistic nature, solution paths have generally low quality, and a post-processing phase is commonly used to improve them locally regarding specific criteria (e.g. length, clearance). The proposed method relies on the recent algorithm T-RRT [START_REF] Koay | Exploratory study of a robot approaching a person in the context of handling over an object[END_REF], which computes good-quality paths given a general costfunction defined over the robot configuration space. The solutions provided by T-RRT are further improved using local optimization methods also described in the paper. Finally, we present a refined description of the HRI constraints, in particular the "arm comfort constraint" only used in [START_REF] Sisbot | Spatial reasoning for human-robot interaction[END_REF] for computing the object transfer point of hand over tasks while considered here for planning robot motions.

The paper is organized as follows. Next section describes the model of the HRI constraints. Section III presents the path planning method. First, the T-RRT algorithm, which is used to find a first good-quality path, is briefly explained. Then, we describe post-processing methods that can be applied to further improve path quality over a configurationspace costmap. Finally, experimental results are presented to demonstrate the efficacy of the approach (Section IV).

II. HUMAN-ROBOT INTERACTIONS CONSTRAINTS

The presence of humans in a robot workspace brings new constraints to navigation and manipulation planning. In this work, several examples of important constraints have been taken into account, such as safety, visibility and arm comfort which are further detailed. These constraints have to be considered as examples of the broad variety of HRI properties that can be taken as input of our planner.

The first constraint depicted in Figure 2, called distance constraint, mainly focuses on ensuring the safety of the interaction by controlling the distance between the robot and the human. As the human can move during the trajectory execution, its position has to be modeled with high uncertainty. Moreover, it has been also shown in proxemics theory [START_REF] Hall | A system for the notation of proxemic behavior[END_REF] that violation of an intimate space radius generates a feeling of intrusion. Therefore the farther a point is situated from the human, the lesser its HRI safety cost is, until some maximum threshold at which it becomes null.

The second constraint, called visibility constraint, has the purpose of limiting the human's surprise as the robot is moving in the workspace. A human will feel less surprise if the robot stays in sight resulting in a safer and more comfortable interaction as shown in [START_REF] Emrah Akin | Human aware mobile robot motion planner[END_REF]. Thus each workspace point has a cost proportional to the angle between the gaze and its position in Cartesian space.

The third constraint, called arm comfort constraint, was introduced in [START_REF] Sisbot | Spatial reasoning for human-robot interaction[END_REF] to compute object transfer position in hand over tasks with the human. This section presents a refined description of this constraint, that is also considered by the motion planner in order to generate paths from which it is easy for the human to access an object held by the robot at any time. For this the robot must reason on humans' accessibility and kinematics. The presupposed human reaching volume can be computed using basic inverse kinematics (IK) of a human kinematic model. Then, to each valid reaching posture can be assigned a comfort cost as shown in Figure 3 by using the predictive human-posture cost function introduced in [START_REF] Marler | A new discomfort function for optimization-based posture prediction[END_REF]. In this contribution, the comfort is estimated by the sum of the three functions:

• The first function computes a joint angle distance from a resting posture q N to the actual posture where q is the configuration of the human:

f 1 = DOF i=1 w i (q i -q N i ) 2
• The second considers the potential energy of the arm which is defined by the difference of the arm and forearm heights with those of a resting posture (∆z i ) pondered by an estimation of the arm and forearm mass m i :

f 2 = 2 i=1 (m i g) 2 (∆z i ) 2
• The third penalizes configuration close to joint limits.

To each joint corresponds a minimum and a maximum limit and the distance to the closest limit (∆q i ) is taken into account in the cost function as follows:

f 3 = DOF i=1 γ i ∆q 2 i
Each constraint expressed as an elementary threedimensional costmap is combined with a weighted sum as follows:

c(h, p) = N i=1 w i c i (h, p),
where h is the human model posture and p the point of the workspace for which the cost is computed.

The planners of [START_REF] Sisbot | Spatial reasoning for human-robot interaction[END_REF], [START_REF] Emrah Akin | Human aware mobile robot motion planner[END_REF] were based on a direct search on the resulting cartesian grids to produce legible and comfortable motions using basic graph search techniques. In [START_REF] Emrah Akin | Human aware mobile robot motion planner[END_REF], navigation tasks were performed based on 2D cost grids explored by an A* algorithm. Extension to manipulation tasks [START_REF] Sisbot | Spatial reasoning for human-robot interaction[END_REF] led to cartesian grids used to compute the end effector path, assuming the computed path was feasible for the robot. While such a decoupled approach is sufficient in the absence of strong environmental constraints, it may fail in situations where the path planned for the object can not be followed by the robot because of collisions with workspace obstacles. Hence, the extension to costmaps defined over the robot configuration space is desirable.

III. PLANNING LOW COST PATHS

Instead of considering a grid on the workspace, a cost is defined for each robot configuration as:

c(h, q) = N i=1 w i c i (h, F K(q)),
where q is a configuration and FK the robot's forward kinematics function. Given the resulting configuration-space costmap, we adopt a sampling-based algorithm for computing good-quality paths. Several approaches have been introduced in former works, in particular RRT variants [START_REF] Ettlin | Randomised Rough-Terrain Robot Motion Planning[END_REF], [START_REF] Urmson | Approaches for heuristically biasing RRT growth[END_REF], [START_REF] Diankov | Randomized statistical path planning[END_REF] in the context of field robotics. In this work, we apply a more general algorithm, called T-RRT [START_REF] Jaillet | Cost based planning in general cspaces[END_REF], briefly explained below. This section also presents a new algorithm for local optimization of the solution through a post-processing phase that also handles such general cost functions.

A. Costmap exploration

The T-RRT algorithm [START_REF] Jaillet | Cost based planning in general cspaces[END_REF] takes advantage of the performance of two methods. First, it benefits from the exploratory strength of RRT-like planners resulting from their expansion bias toward large Voronoi regions of the space. Additionally, it integrates features of stochastic optimization methods, which apply transition tests to accept or reject potential states. It makes the search follow valleys and saddle points of the cost-space in order to compute low-cost solution paths (see Figure 4). Several criteria can be used to measure the quality of a path based on its parametric cost function (e.g. the maximal cost, the average cost, the integral of costs along the path, or the mechanical work). The T-RRT algorithm aims at finding paths that minimize the mechanical work criterion, but also simultaneously satisfy other quality metrics such as the integral of cost.

Algorithm 1 shows the pseudo-code of the T-RRT planner. Similarly to the Extend version of the basic RRT algorithm [START_REF] Lavalle | Rapidly-exploring random trees: Progress and prospects, Algorithmic and computational robotics: new directions: the fourth Workshop on the Algorithmic Foundations of Robotics[END_REF], a configuration q rand is randomly sampled. It yields both the nearest tree node q near to be extended, and the extension direction. The extension from q near is performed toward q rand with an increment step δ, which has to be small enough to avoid cost picks to be missed by the linear interpolation between q near and q new . This stage also integrates collision detections in the presence of binary obstacles. Thus, if the new portion of the path leads to a collision, a null configuration is returned and the extension fails independently of the associated costs. This extension process ensures the bias toward unexplored free regions of the space. The goal of the second stage is to filter irrelevant configurations regarding the search of low cost paths before inserting q new in the tree. Such filtering is performed by the TransitionTest function.

In the TransitionTest function, the probability of acceptance of a new configuration is defined by comparing its cost c j relatively to the cost c i of its parent configuration in the tree. It relies on the Metropolis criterion, commonly used in stochastic optimization methods, with a transition probability p ij defined as follows:

p ij = exp(- ∆c * ij K•T ) if ∆c * ij > 0 1 otherwise. ( 1
)
This test integrates a self-tuning method in order to automatically control its filtering strength, and thus ensures a minimal growth of the tree. Finally, the MinExpandControl function forces the planner to maintain a minimal rate of expansion toward undiscovered regions of the space. Thus, it avoids possible blocking situations during the search. For more details on T-RRT refer to [START_REF] Jaillet | Cost based planning in general cspaces[END_REF].

B. Smoothing

Traditional post-processing methods (e.g. [START_REF] Geraerts | Creating high-quality paths for motion planning[END_REF]) generally applied to reduce the length and/or to increase the clearance of a path. We investigate below the extension of path optimization techniques to the case of a general cost function. First, we present how the classic shortcut method can be extended, and secondly, we present a new method that optimizes locally the path by random perturbations.

1) Random shortcut method: The cost-space extension of the shortcut method is similar to the original approach, but the cost of the path is tested together with collisions and kinematic constraints. The method is sketched in Algorithm 2. At each iteration, the new path portion replaces the current one only if it is feasible and of lower cost.

This method reduces the length of the input path while improving its quality, and usually converges rapidly to a local minimum. However when applied to more general cost functions to be optimized, the fact that the optimization is restricted inside the convex hull defined by the set of points on the path appears to be a limiting factor. Hence, it is not sufficient to deform the path towards the low-cost valleys of the costmap.

2) Random path perturbation: The goal of this method is to avoid the path convex hull limitation. The path is iteratively deformed by moving a point q perturb randomly selected on the path in a direction determined by a random q rand q new q perturb q near1 q near2 q init q goal Fig. 5. The random path perturbation does not restrict the new path to be inside the convex hull defined by the path's set of points enabling a more global exploration of the input path neighborhood.

sample q rand This process (depicted in Figure 5) creates a deviation from the current path, The new segment replaces the current segment if it has a lower cost. Collision checking and kinematic constraints verification can be performed before or after cost comparison depending on the computational cost of both processes. The first step of this method (sketched in Algorithm 3) is to select a configuration q perturb . This selection is biased to higher cost segments. For this, path portions are sorted according to their cost, and high-cost portions have higher chances of being picked for optimization. In a second phase an extension toward a random direction q rand is performed to select a configuration q new inside the path's neighborhood.

The step parameter1 controls the amplitude of the local perturbations. First it is used to determine the distance between the two configuration named q near1 and q near2 that are selected to be both at step/2 of q perturb . It also controls the deviation of q new from the current path, chosen as a percentage of the step parameter. High values of the step parameter tend to deform strongly the path while low values tend to refine locally the solution.

This perturbation method explores more globally the path neighborhood, but usually outputs longer paths. Therefore It is complementary to the shortcut method that tends to shorten the path. Thus, in the post-processing phase, it may be suitable to use a combination of the two methods in order to obtain smooth and low-cost solutions. Also note that these methods can be used to optimize an input path resulting from the RRT search that does not take cost into account. This is illustrated in the results presented below that also compare the computational performance and path quality obtained with global T-RRT costmap planning and local path-optimization of RRT solutions.

IV. EXPERIMENTAL RESULTS

The T-RRT algorithms and the path smoothing methods have been implemented into the path planning software Move3D [START_REF] Simeon | Move3D: a generic platform for path planning[END_REF]. The experiments reported below have been performed on a 2.6GHz INTEL processor. All performance results summarized in the tables correspond to average values computed over 10 runs.

The scenario illustrates a planning problem involving torso and arm motions of the mobile Justin robot from DLR [START_REF] Ott | A humanoid two-arm system for dexterous manipulation[END_REF]. Justin hands an object to the human in a kitchen environment cluttered by ceiling lamps. The resulting motion planning problem involves 10 active DoFs that enable the robot to bend the torso while moving the arm in order to avoid the ceiling lamps. Taking into account the HRI constraints induces high-dimensional costmaps to be explored for generating a safe and legible robot motions.

In Figure 6, the three costmaps are taken separately into account during motion planning resulting in three different solutions to the same problem. Figure 6(c) illustrates the effect of the distance criterion on the robot motion. As one can see, the resulting path pushes the robot farther from the human and causes a safer behavior compared to the direct path generated by the "standard planner". Similarly in Figure 6(d), with visibility cost function, the robot moves the object in a way that it stays as visible as possible to the human. Finally considering the reachability criterion in Figure 6(e), the robot moves the object on a path that maximizes the possibility for the human to reach the object in a comfortable way.

The total planning time including post-processing and the cost of solutions before and after optimization are compared on those three costmaps in Table I. The exploration phase using either the standard RRT or T-RRT are compared while the post-processing is performed using a time limited 4 seconds phase composed of consequential runs of the perturbation and shortcut methods introduced in section III.

T-RRT planning on the first costmap improves drastically the cost of the solutions because the solution path with low integral of cost implies a large detour from the standard RRT solution. As one can see on Figure 6(d) and 6(e) low cost object translation paths on the visibility costmap and reachability constmap are geometrically closer to the standard RRT path of Figure 7(a). This explains the less significant gain found of using the cost-space planning in Table I. Finally, Table II similarly reports the results obtained when considering the combination of the three costmaps the solution obtained realizes a good compromise between the three constraints illustrated on Figure 7.

V. CONCLUSION

We have presented a novel cost-space planning approach for computing human-aware motions considering HRI constraints. The proposed T-RRT algorithm bridges the gap between low dimensional costmap planning and samplingbased motion planning. We have also described a path postprocessing technique that can be used to further improve T-RRT solutions, or for the local optimization of paths computed without considering the HRI constraints.

Future work concern the extension of the proposed framework to more general HRI constraints, better characterizing the desired properties of human-aware motions. We also expect to further validate the approach through experiments with real robot systems.

Fig. 2 .

 2 Fig. 2.The costmaps model the distance and visibility constraint by assigning to each point of the cartesian space an HRI cost. The safety cost function is inversely proportional to its distance to the human while the visibility cost function reasons about the field of view modeled by the gaze direction.

Fig. 3 .

 3 Fig. 3. Arm confront: Four poses that vary from comfortable and natural on the upper left corner to uncomfortable and uneasy postures on the lower right corner, the color gradient expresses the corresponding cost function value.

Algorithm 1 :

 1 Transition-based RRT input the configuration space CS; the cost function c : CS → R * + ; the root qinit the goal qgoal; output : the tree T ; begin T ← InitTree(qinit); while not StopCondition(T , qgoal) do qrand ← SampleConf(CS) ; qnear ← NearestNeighbor(qrand, T ); qnew ← Extend(T , qrand, qnear); if qnew = N U LL and TransitionTest(c(qnear), c(qnew), dnear-new) and MinExpandControl(T , qnear, qrand) then AddNewNode(T , qnew); AddNewEdge(T , qnear, qnew); end

Fig. 4 .

 4 Fig. 4. T-RRT constructed on a 2D costmap (left). The transition test favors the exploration of low-cost regions, resulting in good-quality paths (right).

Fig. 6 .Fig. 7 .

 67 Fig.6. Justin robot in a handover task. The workspace is cluttered by object on the table and ceiling lamps which make the a difficult motion planning problem. The three cost functions lead to three cost-spaces which can be taken separately as input of the proposed sampling-based costmap planner.

Algorithm 2 :

 2 Random Cost Shortcut

	input	: The Path P;
	output : The Path P;
	begin
	while not StopCondition() do
	(q1, q2) ← P.getTwoConfig();
	LP ←getSegment(q1, q2) ;
	if isValidAndLowerCost(LP, q1, q2) then
		P.ReplacePortion(LP, q1, q2) ;
	end
	Algorithm 3: Random Path Perturbation
	input	: The Path P;
	output : The Path P;
	begin
	while not StopCondition() do
	q

perturb ← P.shootRandConfigOnPath(); (qnear1, qnear2) ← P.getNeigh (q perturb , step); q rand ← shootRandDirection() ; qnew ← Expand(q perturb , q rand , step) ; LP1 ←getSegment (qnear1, qnew) ; LP2 ←getSegment (qnew, qnear2) ; LP ← LP1 + LP2 ; if isValidAndLowerCost(LP, qnear1, qnear2) then P.ReplacePortion (LP, qnear1, qnear2, ); end

TABLE I RUNS

 I

		ON AN ELEMENTARY COSTMAP
		Time(sec.)	Cost(Before) Cost(After)
	Dist.
	RRT	8.57	212	111
	T-RRT	13.31	45	18
	Visib.
	RRT	8.64	294	186
	T-RRT	7.05	251	176
	Reach.
	RRT	8.39	158	89
	T-RRT	15.91	117	62

TABLE II RUNS

 II

	ON THE COMBINATION OF THE 3 CONSTRAINTS
		Time(sec.)	Cost(Before) Cost(After)
	RRT	8.65	179	120
	T-RRT	16.69	82	54

The step parameter can be set at a certain percentage of the path length, in the experimental results, we use 10% which refines locally the path in a convenient way. The distance between qnew and q perturb is set to be at

25% of step.

VI. ACKNOWLEDGMENTS This work has been supported by the European Community's Seventh Framework Program FP7/2007-2013 "DEX-MART" under grant agreement no. 216239.


Marie-Noelle Bessagnet

Patrick Etcheverry

Annig Lacayrelle

Christophe Marquesuzaà

Landy Rajaonarivo

Philippe Roose

André Sales

Christian Sallaberry

Leveraging heterogeneous Cultural Heritage data to promote tourism

The objective of our works is to propose an open source software able to to manage data source heterogeneity and to generate other ones in order to propose context oriented and on the fly itineraries according to several criterions (time, means of transport, personal interest, current close events, etc.). In this first step, we propose a software architecture and an implementation in order to manage data source heterogeneity.

Introduction

This paper presents part of the European FEDER Project TCVPYR, which aims to promote tourism in the French Pyrenees region by leveraging elements of its cultural heritage. The TCVPYR is a multidisciplinary project involving scientists from various domains, including: computers scientists, geographers, historians and anthropologists. In order to achieve its goal, some of the TCVPYR researchers are currently collecting georeferenced cultural heritage data in different areas of the Pyrenees. This data, together with data from the local governments and the Open Data, is intended to feed a mobile application that promotes the tourism in the region. The mobile application will allow tourists, but also scientists, to access cultural heritage data in the form of points of interest (POI). Moreover, these POI are to be presented according to the user profile and the environmental context, including spatiotemporal aspects such as his current location. For example, the application may suggest to a tourist an itinerary with several POI taking into account his interests, means of locomotion, available time and mobile features (battery level, internet connexion…). All data collected in this project as well as the final application will be published as open data and open source.

The first major challenge in this project consists in managing the heterogeneity of the several different sources of data we plan to use. For example, the French government currently employs at least two different software each one with different data model (format) to storage its data. Similarly, a plethora of data models are used in the countless sources of Open Data. In order to handle this challenge, we propose a unified model that allows us to gather all this data we plan to use and to import it into a single database suitable for further exploitation.

The second major challenge is related to leverage the cultural heritage data stored in our unified database. In particular, we plan to elaborate a set of algorithms and heuristics to propose contextualized itineraries (i.e., sequences of POI to be visited) on the fly to the users of the mobile application. This recommendation must take into account the user profile, his location, his device features and also some other parameters such as available time for visiting the POI and means of transport. A recommendation must also be enriched with information extracted from open data. For example, if an exhibition is happening close to the user location, the user itinerary may be enriched with a link to a mobile ticketing service. Another important approach we plan to adopt in order to leverage the cultural heritage data is to publish it as open data. In this direction, we are currently developing a set of tools and API that will allow anyone to download our data in open popular formats (e.g., JSON, XML or CSV). Moreover, we are investigating and experimenting on the creation robots to publish our data directly on wellknown and visited open data providers such as Wikipedia and OpenStreetMap.

Related works

The contribution presented in this paper deals with patrimonial data valorization through tourism vector. As presented in [START_REF] Benhamou | Valoriser le patrimoine culturel de la France[END_REF] which highlight the close links between culture, tourism and economy, we are also positioning the cultural heritage at the service of the tourism and the attractiveness of the territory. This issue is also related to the "globalism" phenomenon addressed in papers such as (Baumann, 2002) and [START_REF] Michele | Social Smartourism: A Sustainable Development Methodology for Smart Urban Lands[END_REF]. The Social Smart Tourism project presented in (Angelaccio, 2017) aims at developing services to improve the quality of life by highlighting places and resources insufficiently known. Our project shares some common goals without directly focusing on the social aggregation aspect. [Hui et al, 2015] propose an algorithm called PERSTOUR for recommending personalized tours using POI popularity and user interest preferences, which are automatically derived from real-life travel sequences based on geotagged photos. The algorithm uses trip constraints such as time limits and the need to start and end at specific POIs. Such approach is interesting as in our proposition, available time is also an important information in order to propose an itinerary. [START_REF] Igo Ramalho Brilhante | On planning sightseeing tours with TripBuilder -Information[END_REF] propose TripBuilder, an unsupervised framework for planning personalized sightseeing tours in cities using collected and categorized POIs from Wikipedia and albums of geo-referenced photos from Flickr. Such traces give information about tourists' behaviors. Spatio-temporal information obtained from photo metadata are compared with city POIs in order to obtain a measure of personal interest for the user given her preferences and visiting time-budget is maximized. [START_REF] Colomo | Sanjay Misra -Towards a social and context-aware mobile recommendation system for tourism[END_REF] present POST-VIA 360, a platform to support the whole life-cycle of tourism loyalty after the first visit. The objective of the platform is to collect and analyse data and to propose (using positioning and bio-inspired recommender systems) relevant recommendations.

As we can see on previous works [START_REF] Fonteles | Trajectory recommendation for task accomplishment in crowdsourcinga model to favour different actors[END_REF] or [START_REF] Rajaonarivo | Inline Co-Evolution between Users and Information Presentation for Data Exploration[END_REF], many works and prototypes are now available in order to increase the value of tourism oriented data (including POI, traces) and propose context and user oriented itineraries. Unfortunately, few of them use public data and/or are freely available.

Proposal

This project is part of the European ERDF Project TCVPYR. This project is a multidisciplinary one involving geographers, historian, anthropologists and computer scientists. The objective consists in collecting data on the topic of thermal cities and increasing their value for the public. Both data and applications will be open-source. The final application will permit tourists to express some requirements and to get itinerary propositions according to the time they have, their means of transport, their personal interest and knowledge skills, etc.

In order to collect patrimonial information, researchers draw up an inventory of georeferenced cultural heritage data using two different systems: RenablLP2 and Gertrude. These two systems allow geographers to structure, to organize and to describe all the patrimonial collected data. RenablLP2 is used in the Occitanie region and Gertrude is both used in the new Aquitanian and in the Occitanie regions.

The idea is to gather and to merge all the collected data with these two systems in a same database (named TCVPYR in Figure 1) that could be used for touristic purposes (Figure 4) but also that could be shared through open data platforms (Figure 3). Even if RenablLP2 and Gertrude systems can export data in XML format, resulting exports are very different in terms of structure, data organization or information naming. In order to emphasize these heterogeneous data within applications dedicated to tourism, we designed a unified and homogeneous data model (Figure 2). This model can describe all the study objects collected from the field: buildings, furnitures and all elements related to intangible cultural heritage. Each object ("ObjetdEtude" class) has a description ("description" property), an history ("historique" property) and can be geolocated with specific geographic coordinates ("Adresse" and "Geometry" classes). Some object can also be represented by one or more images ("Illustration" class). The model allows also geographers to reference, for each object, persons ("Personne" class) related with it: the architect of a building, the sculptor of a statue and so on, according to this/her role ("Rôle" class). Of course, several objects can be interrelated ("Lien" association class): a building can be composed of several buildings, a furniture can be located in a building, etc. This model is not intended to describe all the complexity of the patrimonial domain but only the set of information that can be later exploited and highlighted within a tourist context.

Prototype

In order to leverage all the cultural heritage data merged in our unified database, we plan to develop two applications: an application dedicated to share all the collected data through open data platforms (Figure 3) and another one dedicated to tourists (Figure 4). The application dedicated to share the collected patrimonial data exploits the API developed to access the TCVPYR database. The communication layer of this application connects with the TCVPYR API in order to get the data that must be shared on open data platforms. We plan to develop several export modules, each one aiming at distributing patrimonial data on a specific open data platform such as Wikipedia or Open Street map.

We developed a first prototype wich is able to publish patrimonial data of specific patrimonial objects on Wikipedia. This component, developed in Java, queries the TCVPYR unified database and uses the JWiki API (https://github.com/fastily/jwiki) to publish each point of interest in the form of a Wikipedia article. Figure 4 shows an example of result for a patrimonial object (Champsaurei Castle) stored in the TCVPYR database. Concerning the dissemination of patrimonial data through the tourist vector, we plan to develop a classic client/server application allowing a tourist to access patrimonial data during a trip. The idea consists in providing customized data according to the user profile but also the context in which he moves (Figure 5). The client side application takes the form of a mobile application that will exploit the mobile components to get contextual information: location, battery level, internet connexion type, etc. The user will also be able to define personal preferences such as the time available to achieve his trip, his/her means of travel, preferences in terms of things to see during his/her trip… According to all this gathered information, the server side application will search for relevant patrimonial information matching with the tourist context and profile. To carry out this task the server side application relies on a recommendation engine that will exploit all the collected data concerning the user in order to search for relevant information in the TCVPYR database but also on open data platforms.

We are currently working towards implementing the technical architecture of this application and we have developed a first prototype allowing the user to access, without any filter, all the patrimonial data stored in the TCVPYR database (Figure 6). The next step will consist in designing the recommendation engine to take into account the user context and preferences in order to enhance information retrieval.

Conclusion and future work

This paper proposes a unified model, and architecture and a software solution in order to get a basic solution for further data integration. We are also proposed a tool in order to extract tourism oriented data and export them to a Wikipedia format.

The next step will now be the on the fly itinerary proposition according to the complex context (user profile, means of locomotion, time, interests, events, etc.

Acknowledgement

These work are supported by the European Regional Development Fund (ERDF). Project TCV-PYR (2017-2020), in collaboration with Occitanie-Méditerranée and Nouvelle-Aquitaine Regions.

Figure 1 :

 1 Figure 1: Patrimonial data merge process

Figure 2 :

 2 Figure 2: Unified patrimonial data model for tourist use

Figure 3 :

 3 Figure 3: Patrimonial data dissemination through open data platforms.

Figure 4 :

 4 Figure 4: An example of a patrimonial object exported to Wikipedia.

Figure 5 :

 5 Figure 5: Patrimonial data dissemination through a tourist application.

Figure 6 :

 6 Figure 6: An example of a first prototype for the tourist application.