Aleksander Lillienskiold

Rahaf Rahal

Paolo Robuffo Giordano

Claudio Pacchierotti

Ekrem Misimi

Human-Inspired Haptic-Enabled Learning from Prehensile Move Demonstrations

Keywords: Haptics, Grasping, Learning from Demonstration, Teleoperation, Robotics, Food handling

Research on robotic manipulation of fragile, compliant objects, such as food items, is gaining traction due to its game-changing potential within the food production and retailing sectors, currently characterized by manually-intensive and highly repetitive tasks. Food products exhibit high levels of frailness, biological variation, and complex 3D shapes and textures. For these reasons, introducing greater levels of robotic automation in the food and agricultural sectors remains an important challenge. This paper addresses this challenge by developing a humancentred, haptic-based, Learning from Demonstration (LfD) policy that enables pre-trained autonomous grasping of food items using an anthropomorphic robotic system. The policy combines data from teleoperation and direct human manipulation of objects, embodying human intent and interaction areas of significance. We evaluated the proposed solution against a recent state-ofthe-art LfD policy as well as against two standard impedance controller techniques. Results show that the proposed policy performs significantly better than the other considered techniques, leading to high grasping success rates while guaranteeing the integrity of the food at hand.

I. INTRODUCTION

A UTONOMOUS food processing and handling is gaining attention among researchers in the fields of robotics, automation, and machine learning. Reasons for this interest are three-fold: (i) compelling scientific and technological challenges linked to the handling of food, such as flexibility, frailness, friction, and high inter-object variability, (ii) increasing interest from public and private investors, and (iii) the possibility of impacting food quality and reducing waste. To address current challenges, the European Commission has recently funded the e 7-million collaborative research project "SoMa," which looks at innovative soft robotic manipulation for handling fragile objects such as fruits and vegetables [START_REF]SoMa: Soft-bodied intelligence for Manipulation[END_REF]. Similarly, Amazon's $13.7-billion acquisition of the food retailer "Whole Foods" aims to promote an automation revolution in the food delivery market. According to Bloomberg [START_REF] Soper | Amazon robots poised to revamp how whole foods runs warehouses[END_REF], Amazon will soon introduce robots in Whole Food warehouses as a cost-cutting initiative. However, not only distributors need to automate the manipulation of delicate food items. Currently, food production, harvesting, and processing continue to be dominated by labour-intensive tasks. In addition, vital global suppliers have a constant need for more efficient operations, c. Corresponding author: rahaf.rahal@irisa.fr and improved HSSEQ (Health, Safety, Security, Environment, and Quality) practices linked to their workers and the safe handling of food. To address these issues, researchers need to focus on efficient and safe methods for the autonomous handling of food while preserving their quality.

Nowadays, (purely) vision-based techniques are the most widely applied approaches for autonomous robotic grasping and manipulation, either requiring a 3D-model of the item in question or constructing models using 3D-vision information, e.g. point clouds [START_REF] Saxena | Robotic grasping of novel objects using vision[END_REF], [START_REF] Zhang | A realtime robotic grasping approach with oriented anchor box[END_REF], [START_REF] Liu | Learning to grasp familiar objects based on experience and objects shape affordance[END_REF]. Although the knowledge of an object's model may often be sufficient [START_REF] Sauser | Iterative learning of grasp adaptation through human corrections[END_REF], the lack of precise information concerning its shape and mechanical properties may significantly affect the quality of the grasping [START_REF] Namiki | Optimal grasping using visual and tactile feedback[END_REF], [START_REF] Smith | Vision-guided robotic grasping: Issues and experiments[END_REF]. An issue of major importance when handling food is its frailness, which is an even more predominant problem when objects are moving, or when they are handled and grasped during harvesting, post-harvest processes, and on production lines. A representative example is strawberry harvesting, where even the smallest excessive force can degrade and spoil the product.

Haptic sensations have been proven to play a key role in enhancing human fine manipulation [START_REF] Johansson | Roles of glabrous skin receptors and sensorimotor memory in automatic control of precision grip when lifting rougher or more slippery objects[END_REF] and precision grasping [START_REF] Westling | Factors influencing the force control during precision grip[END_REF]. In robotics, haptic feedback is widely believed to be a valuable tool in teleoperation, and it has been shown to enhance operators' performance in a wide range of robotic applications, including microrobotics [START_REF] Bolopion | A review of haptic feedback teleoperation systems for micromanipulation and microassembly[END_REF], [START_REF] Pacchierotti | Haptic feedback for microrobotics applications: a review[END_REF], [START_REF] Pacchierotti | Steering and control of miniaturized untethered soft magnetic grippers with haptic assistance[END_REF], mobile robotics [START_REF] Aggravi | Design and evaluation of a wearable haptic device for skin stretch, pressure, and vibrotactile stimuli[END_REF], needle and catheter insertion [START_REF] Salcudean | Performance measurement in scaled teleoperation for microsurgery[END_REF], [START_REF] Meli | Experimental evaluation of magnified haptic feedback for robot-assisted needle insertion and palpation[END_REF], surgical knot tying [START_REF] Moody | Objective surgical performance evaluation based on haptic feedback[END_REF], assembly [START_REF] Bolopion | A review of haptic feedback teleoperation systems for micromanipulation and microassembly[END_REF], and palpation [START_REF] Pacchierotti | Cutaneous feedback of fingertip deformation and vibration for palpation in robotic surgery[END_REF], [START_REF] Meli | Experimental evaluation of magnified haptic feedback for robot-assisted needle insertion and palpation[END_REF], [START_REF] Chinello | A modular wearable finger interface for cutaneous and kinesthetic interaction: control and evaluation[END_REF]. The benefits of haptic feedback in this scenario include greater manipulation and perception accuracy, as well as lower levels of peak and mean force applied to food objects, thus lowering the impact on the food due to their handling.

A promising approach to autonomous grasping via robotic manipulators is Learning from Demonstration (LfD) [START_REF] Billard | Learning from humans[END_REF]. This technique involves a robot learning a target policy from examples, or demonstrations, provided by an experienced human operator. LfD uses recorded datasets in the form of state-action pairs to derive policies that reproduce target behaviours. This methodology is in stark contrast to other learning techniques, such as Reinforcement Learning, where robots learn from direct self experience. The use of LfD to teach robots how to grasp is quite popular among researchers who make use of visual and/or haptic information to demonstrate tasks by means of teleoperation [START_REF] Misimi | Robotic handling of compliant food objects by robust learning from demonstration[END_REF], [START_REF] Kormushev | Imitation learning of positional and force skills demonstrated via kinesthetic teaching and haptic input[END_REF], [START_REF] Kukliński | Teleoperation for learning by demonstration: Data glove versus object manipulation for intuitive robot control[END_REF], [START_REF] Evrard | Teaching physical collaborative tasks: object-lifting case study with a humanoid[END_REF], [START_REF] Zeestraten | Programming by demonstration for shared control with an application in teleoperation[END_REF] or direct interaction [START_REF] Lin | Learning grasping force from demonstration[END_REF], [START_REF] Kormushev | Upperbody kinesthetic teaching of a free-standing humanoid robot[END_REF], [START_REF] Schou | Human-robot interface for instructing industrial tasks using kinesthetic teaching[END_REF]. However, all of the aforementioned works involve human operators driving robots using non-intuitive and somewhat basic master interfaces such as teach pendants, non-haptic joysticks, single-point haptic interfaces, or by directly moving the robots around. It is our belief that, in order for robots to learn correctly from humans how to grasp challenging, compliant, and fragile objects, it is necessary to provide an intuitive and natural tool for controlling the slave manipulators. In other words, we believe that by achieving a high degree of dexterity and telepresence, human operators will be able to approach and grasp target objects in the same way as they would do if grasping barehanded.

II. CONTRIBUTION AND MOTIVATION

This paper presents a human-centered, haptic-based, LfD approach for teaching autonomous robotic systems the action of grasping delicate, fragile, and compliant food items.

First, five human subjects were asked to grasp five food items barehanded, recording the contact area between the users' hand and the objects' surface using paint transfer and machine vision techniques (see Sec. III-A and Fig. 1b). Paint-transfer approaches have already been used to detect contact areas when humans grasp objects [START_REF] Knoop | Handshakiness: Benchmarking for human-robot hand interactions[END_REF]. However, to the best of our knowledge, this is the first time that this approach is used to learn an LfD policy. This first step enables us to study how humans grasp the considered food items when they are endowed with maximum dexterity and feedback. However, these data alone are not sufficient to design an autonomous grasping policy for a robotic manipulator, which has significantly lower sensing and actuation capabilities than a human. For this reason, afterwards, we conducted teleoperated prehensile move experiments involving the same food object types (see Sec. III-B). All relevant data on the grasping motion and exchanged forces were recorded. To achieve high levels of dexterity and telepresence, we devised a haptic-enabled high-degrees-of-freedom robotic teleoperation system, shown in Fig. 3a.

By using both direct interaction and teleoperation data, we then devised four Support Vector Regression (SVR) algorithms based on LfD policies, enabling a robotic manipulator to autonomously grasp a set of representative food items.

Finally, we validated our autonomous grasping policies by carrying out 2310 autonomous robotic grasping tasks on seven representative food items, not limited to those used during the training. We compared the proposed policies to each other, as well as, to a recently published LfD-based approach [START_REF] Misimi | Robotic handling of compliant food objects by robust learning from demonstration[END_REF] and two standard impedance controllers. Misimi et al. [START_REF] Misimi | Robotic handling of compliant food objects by robust learning from demonstration[END_REF] combines RGB-D images and tactile data to learn the required pose of the gripper, the gripper finger configuration, and the exerted forces. However, unlike our approach, it neither uses information derived from direct human interaction nor data supplied by high-dexterity haptic-enabled teleoperation.

With reference to related published work [START_REF] Misimi | Robotic handling of compliant food objects by robust learning from demonstration[END_REF], [START_REF] Hyttinen | Learning the tactile signatures of prototypical object parts for robust part-based grasping of novel objects[END_REF], [START_REF] Luo | Robotic tactile perception of object properties: A review[END_REF], [START_REF] Stachowsky | A slip detection and correction strategy for precision robot grasping[END_REF], [START_REF] Gemici | Learning haptic representation for manipulating deformable food objects[END_REF], our study heavily focuses on human input. By providing an intuitive and rich interface to control the slave robot, we enabled human operators to carry out the tasks naturally and intuitively, close to what they would do with their own hands. To the best of our knowledge, this is the first time an LfD approach is applied to enable autonomous grasping by making use of both (i) rich haptic-endowed teleoperation data and (ii) the mapping of direct hand interaction. Moreover, this is also the first time that such an approach is used for grasping raw food items. Our approach combines teleoperation data with real human interaction to build a robust learning policy based on LfD. This policy enables a continuous understanding of the interactions taking place between the human and the robot during a grasping sequence.

We have focused our research and validation on food items because they are excellent examples of 3D compliant objects that should not be degraded during manipulation. Robotic manipulation of 3D compliant objects is indeed a research field that still requires significant research input to achieve a robust manipulation of such objects.

III. GRASPING-DATA GATHERING

This Section provides details on the two data gathering experiments we carried out with the aim of building our LfD policies. In both cases, we asked our subjects to grasp the five different food items shown in Fig. 1a: an aubergine, a bell pepper, a lettuce, a navel orange, and a beef tomato. These items were selected as representative examples of 3D compliant objects because of their difference in size, shape, texture, and compliance properties, and as representatives of the most common fruits and vegetables consumed in global food markets. According to the Food and Agriculture Organization of the United Nations (FAO), tomatoes are one of the most cultivated fruits in the world, with more than 180M metric tonnes produced every year. Aubergines and oranges are also very popular, with 50M metric tonnes produced every year, bell peppers reach 35M metric tonnes, and lettuce 25M metric tonnes. Another important constraint for our choice of produce was the payload of our robotic system, which is only able to carry up to 2 kg. Employing a different robot could of course enlarge the set of food objects we are able to handle. However, it is important to highlight that our machine learning approach can easily be trained to handle any other type of compliant food objects, regardless of the robotic system being employed A video of these experiments is available as supplemental material and at https://youtu.be/0LaDPbGwZlw. Table I summarizes the main symbols and variables used in the paper.

A. Direct grasping by hand

Five subjects (four male and one female) were asked to grasp the five sample objects barehanded. Our objective was to understand how humans grasp objects when they are endowed with maximum dexterity and feedback (i.e. during direct hand interaction). Inspired by the work of Knopp et al. [START_REF] Knoop | Handshakiness: Benchmarking for human-robot hand interactions[END_REF] and Kamakura et al. [START_REF] Kamakura | Patterns of static prehension in normal hands[END_REF], we used a paint-transfer approach to identify the parts of the hand that are employed the most during this grasping.

Task and data gathering-Subjects were comfortably seated in front of a table. The experimenter placed the first object on the table and covered it in non-toxic water paint. Subjects were asked to grasp and lift the object as if they were moving it from one table to another. Then, they were asked to release the object and show their palm to a camera, which recorded the paint-transfer patterns (see Fig. 1a). Finally, subjects washed their hands and a new object was prepared for grasping. Each subject grasped each object ten times, yielding 50 grasps per subject, 50 grasps per object, and 250 paint-transfer trials in total.

Heat-map generation-Images of paint-transfer patterns were taken using a Grasshopper 3 camera (FLIR Systems, Canada), and the contact area was segmented using standard background subtraction and light intensity filtering. We then mapped the resulting contact area and constructed a heat-map using Thin-Plate Spline interpolation [START_REF] Menesatti | Rgb color calibration for quantitative image analysis: the 3d thin-plate spline warping approach[END_REF]. A heat-map is a graphical representation of individual values contained within a 2D matrix represented by colours. Brighter colours indicate higher levels of accumulated contact, identifying which parts of the hand most used by the subjects when grasping the object in question. Establishing a human-grasp signature inferring innate sensor contact importance. An example of data derived from this heat-mapping process is shown in Fig. 2. Heat-map data are used in Sec. IV as a basis for our human-inspired LfD grasping policy.

B. Teleoperated grasping by an expert operator

Although the heat-map data are interesting, they are not sufficient on their own to define an autonomous grasping policy for a robotic manipulator. For this reason, we gathered additional data from 250 teleoperated grasping trials (50 grasps per food item) using our target robotic system as the slave of a haptic-enabled bilateral teleoperation system, shown in Fig. 3a. The master interface is composed of a 9-degrees-of-freedom (9-DoF) haptic hand exoskeleton (H-Glove by Haption, France), attached to a 6-DoF grounded haptic interface (Virtuose 6D by Haption, France). The slave system is composed of a 7-DoF robotic manipulator (Panda by Franka Emika, Germany), endowed with a 4-DoF 3-fingered robotic hand equipped with matrix pressure sensors on all fingers (ReFlex TakkTile by Right-Hand-Robotics, USA). This integrated system enables a human operator to grasp and manipulate compliant objects while receiving compelling haptic feedback of the forces applied by the slave system.

Teleoperation of the 7-DoF robotic manipulator-To achieve high motion fidelity, we mapped the velocity of the grounded haptic interface to that of the slave robotic endeffector, using an approach similar to that employed in [START_REF] Abi-Farraj | A haptic shared-control architecture for guided multi-target robotic grasping[END_REF], [START_REF] Rahal | Caring about the human operator: haptic shared control for enhanced user comfort in robotic telemanipulation[END_REF]. Let x m = (p m , R m ) ∈ R 3 × SO(3) be the pose of the master interface end-effector, and

x s = (p s , R s ) ∈ R 3 ×SO(3)
the pose of the slave end-effector, both expressed w.r.t. a common world frame W (see Fig. 3a). The velocity of the slave robot [v s ω s ] T is then calculated as a function of the master's velocity [v m ω m ] T and the difference between the desired and current pose of the robot, i.e.

v s ω s = v m ω m + λ p s,d -p s R s s θu s,d , ( 1
)
where λ is a gain parameter, and p s,d the desired robot position derived from the current position of the haptic device, p s,d = (p m -p m0 )+p s0 , with p m0 and p s0 as the initial poses of the master and slave, respectively. Similarly, to establish orientation, s θu s,d is the angle-axis representation of the relative rotation between the desired and current orientation of the slave, i.e. s R s,d = s0 R T s m0 R m , where s0 R s and m0 R m define the current orientation of the slave and master, respectively, w.r.t their orientation at the start of a given experiment. Thus, the first term of (1) ensures an adequate responsiveness of the system, while the second prevents drifts.

Of course, there are other ways we can map the motion of the human operator into that of the slave robot [START_REF] Yuan | Flexible telemanipulation based handy robot teaching on tape masking with complex geometry[END_REF], [START_REF] Bimbo | Teleoperation in cluttered environments using wearable haptic feedback[END_REF], [START_REF] Selvaggio | Haptic-based shared-control methods for a dual-arm system[END_REF]. In this work, we chose a direct and straightforward way to control the robotic manipulator, as one of our hypotheses states that a human-like natural control can improve the quality of recorded data and, thus, of the learning policies.

Teleoperation of the 4-DoF robotic hand-To control the robotic hand, we mapped the positions of the exoskeleton fingers to the positions of the slave's robotic fingers.

The robotic hand has four active DoF: one DoF for each finger's metacarpophalangeal (MCP) joint, and one to control the abduction of the two neighbouring fingers (see Fig. 3a). These fingers were chosen to correspond with the index and middle finger of the exoskeleton, together with an opposing thumb. The position command θ ri for the MCP joint in a robotic finger i is proportional to the recorded position θ ei of the MCP joint in the corresponding exoskeleton finger:

θ ri = k i θ ei + θ ri,s , (2)
where k i is a proportional gain, and θ ri,s is a safety offset, ensuring that the commanded position value is always within safe intervals.

Haptic feedback-The robotic hand is endowed with six matrix pressure sensors (TakkTile, USA), located on the proximal and distal phalanges of the three fingers. Force feedback at the MCP joint of the exoskeleton, τ M CP,i , is computed by summing the pressure stimuli registered by sensors located at the proximal and distal phalanges in the corresponding slave fingers. At the proximal-interphalangeal (PIP) joint, forces τ P IP,i are computed only from pressure stimuli on sensors located on the slave's distal phalanx. The total force feedback is computed as:

τ i = τ M CP,i τ P IP,i = u i m pro,i + m dis,i m dis,i , (3)
where u i is a proportional gain, and m pro,i and m dis,i are average pressures recorded on the proximal and distal phalanges of the slave finger i, respectively. Each finger of the master exoskeleton is modeled as a gravitycompensated mechanical system with two active joints (MCP and PIP, see Fig. 3a), with force feedback τ i . This approach enables the human operator to feel, on each finger, the forces exerted by the robotic hand on the environment.

Task and data collection-An expert operator used the teleoperation system for grasping and lifting the same five food items described in Sec. III-A and shown in Fig. 1a. Each item was placed on a table in front of the slave robot and lifted 50 times as part of a total of 250 trials (see Fig. 3a). To enable the operator to view the environment, the master interface was placed one metre in front of slave robot's workspace. For each trial, both the pose of the slave system and the forces exerted on the food items were saved. At the end of each task, the operator rated the quality of the grasp on a continuous scale from 0 (worst) to 4 (best). Zero (0) indicates that the operator was not able to grasp the object in the first place, while 4 means that the object was held firmly during the entire grasp sequence (see Table II). This information was used to select the successful demonstration examples for training the LfD policy. The majority of the grasps were rated between 3 and 4. We also asked the expert operator to rate the quality of the food items after each grasp on a scale from 0 (worst) to 4 (best), carefully looking for bruises, cuts, changes in shape, and any other sign of degradation (see Table II). The operator was gentle when handling the produce, resulting in a consistent quality rating of 4, reflecting the rich feedback and dexterity capabilities of the employed haptic teleoperation system. In comparison, Misimi et al. [START_REF] Misimi | Robotic handling of compliant food objects by robust learning from demonstration[END_REF] provided no haptic feedback during their teleoperation trials, and operators reported that it was very challenging to not damage the items when not receiving any tactile information.

Finally, for each grasping repetition, we also registered the angle of approach, any significant synergy between the fingers, and the forces applied by the robotic hand on the object. The design of the robotic hand lead to most grasps being precision ball (enveloping) grasps [START_REF] Napier | The prehensile movements of the human hand[END_REF]. This type of grasp enabled the operator to receive haptic feedback to all the three fingers of the exoskeleton.

TABLE II

Scales used in the evaluation of the teleoperated prehensile move and the quality of the food after the move, inspired from [START_REF] Pettersson | A hygienically designed force gripper for flexible handling of variable and easily damaged natural food products[END_REF], [START_REF] Barrett | Color, flavor, texture, and nutritional quality of fresh-cut fruits and vegetables: desirable levels, instrumental and sensory measurement, and the effects of processing[END_REF]. Scale runs continuously from 0 (worst) to 4 (best), enabling the operator to select values between those indicated below. Learning a task from scratch can be very challenging, even for humans. A good strategy for learning how to perform a brand new task is to be provided with a set of instructions by an expert, followed by a practical demonstration [START_REF]Learning from demonstration[END_REF]. Indeed, most forms of machine learning (ML) applied in robotics are based on supervised learning (SL), typically using manually-crafted features as key to learning sought-after policies [START_REF] Misimi | Robotic handling of compliant food objects by robust learning from demonstration[END_REF], [START_REF] Argall | A survey of robot learning from demonstration[END_REF]. Unsupervised learning methods, such as (deep) reinforcement learning, achieve objective functions by enabling learning agents to autonomously define actions that maximize specific reward functions [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF]. Van Hoof et al. [START_REF] Van Hoof | Learning robot inhand manipulation with tactile features[END_REF] illustrate such an approach with their tactile in-hand manipulation skills derived from reinforcement learning with tactile feedback. However, as SL can reduce the number of trials needed for sufficient implementation, i.e. also reducing food waste compared to a self-training algorithm, we opted for an LfD approach.

Prehensile move Food items

In this study, the prediction of a time-varying sequence of grasping features during the grasping task was performed using Support Vector Regression (SVR) time series. In addition, we tested the SVRs' response to the weighting of selected variables, and demonstrate how the imposition of human-inspired interaction indicators (heat-map weights) affects performance. SVR is one of the most powerful and popular machine learning techniques to deal with non-linear prediction problems. It has a strict, well understood mathematical description, and it is widely used in various applications. Compared to recent NNbased methods, SVR is significantly less data-greedy, meaning that it does not require huge amounts of training data-sets to develop prediction models. Moreover, SVR is very robust to local minima problems. These aspects led us to choose SVR as the machine learning method for this application.

A detailed description of the proposed three variants of SVR techniques is given in the following subsections. Fig. 4 summarizes the process of generating these policies from the acquired data.

A. Standard SVR

Let g pos = [x s , y s , z s , q s T ] ∈ R 3 × H represent the pose of the robotic gripper, where q s is a unit quaternion. Each robotic finger has nine tactile sensors, five on its proximal phalanx and four on the distal. Let f prs ∈ R 27 be the vector containing all these tactile readings, f mot ∈ R 4 the position of the motors in the robotic hand, and f ang ∈ R 7 the joint angles of the exoskeleton. We can now define s ∈ S ⊆ R 3 × H × R 27 × R 4 × R 7 as an observed (demonstrated) robotic grasping action performed by a human teacher for a given object. Furthermore, let a ∈ A ⊆ R 3 × H × R 4 be the corresponding action-state, which consists of a gripper pose and motor positions. We define the set of n demonstrations as ordered pairs D = {(s, a) i : ∀i ∈ I n , s ∈ S, a ∈ A}. The goal is to instruct a policy function Π 0 (s; θ) : S → A, which is parameterized by θ ∈ R d , using the set of human demonstrations. Let l : A × A → R be a loss function between two action-states and Π : S → A a robotic grasp policy demonstrated by a human. The objective is to find the parameterization θ that minimizes the expected loss across a set of human demonstrations, i.e. ∀(s, a) ∈ D :

arg min θ E[l(Π 0 (s; θ), Π (s))]. (4)

B. SVR with time-series

For the implementation of an LfD policy based on SVR modelling, we used Vapnik's E-insensitive time-series [START_REF] Müller | Predicting time series with support vector machines[END_REF], where the aim is to identify a policy Π 0 by minimization of an E-function. In our case, this function is defined as

l E (s, a) = d k=1 l Ek (s k , a k ). (5)
An SVR with time-series was chosen to generate a policy able to predict grasping actions in the form of action vectors with use of memory,

âi (t + ∆ t ) = f (a i (t -α), a i (t -β), a i (t -γ), . . . ), ( 6
)
where âi is the predicted value of the action vector a i derived from its discrete grasping time-series values, and α = 0, β = 2, γ = 5 are selected time-steps brought into the prediction equation, i.e. action predictions use current time sequence t together with shifted time sequences (t -2) and (t -5) as data input.

We organized and subdivided the data into predefined grasping stages: approach, grasp, lift, placement, and release (see [START_REF] Misimi | Gribbot-robotic 3d vision-guided harvesting of chicken fillets[END_REF], [START_REF] Lippiello | Position-based visual servoing in industrial multirobot cells using a hybrid camera configuration[END_REF] for details). Then, we shifted g pos to make it relative to the position of the grasped object prior to finally normalizing all the data.

C. SVR with heat-map weighting

We used heat-maps to represent action vector predictions by weighting the predicted tactile finger data using objectspecific values generated by the heat-maps themselves. For a given object, we found little variability among the ten grasps performed by each subject (i.e. grasp practitioner). Although we registered a difference in heat-maps between subjects, this was negligible compared to the much larger differences identified between objects (i.e. the produce). Fig. 2 shows that the distal parts of the fingers experienced the most contact, whilst proximal parts yielded higher inter-object variation. As expected, the palm was more active in subjects with smaller hands, and when grasping larger objects such as the aubergine. However, since the RHR hand is not equipped with sensors on the palm, we did not use the palmar heat-map data.

In practice, we weighted each column of the sensor action vector (a for f prs ∈ R 27 ) with its respective heat-map values, represented by the matrix H:

a k ij = H k j • a k ij , (7)
where k is the object type, i the sequence (row) values, and j a feature of the action vector. As mentioned above, this heat-map weighting was performed only on the sensor-covered area of the RHR hand, i.e., the RHR's sensor placements were overlaid to the generic human hand heat-map generated during direct grasping. The human hand heat-map was thereby segmented into parcels which were averaged to create the matrix H (see also Fig. 4). This procedure enabled us to create a map of human-weighted grasp actions. It privileges the activation of specific tactile sensors according to the areas of the hand most used by the operator during direct interaction with the objects. Of course, this mapping approach only works if the structure of the slave system resembles that of the human hand. Moreover, the more human-like the slave system is, the better we expect this mapping to perform.

V. EXPERIMENTAL EVALUATION

This section presents the experimental evaluation of our LfD policy for autonomous grasping of compliant food. The execution-validation stage, conducted after the LfD-ML policy is learned, is illustrated on the right-hand side of Fig. 4.

A. Setup

The setup is comprised of the same slave system described in Sec. III-B and illustrated on the right-hand side of Fig. 3b, i.e. an RHR hand attached to a Panda manipulator. However, in this case, the slave robot is autonomously controlled by the learned LfD-ML policies and no human is involved in the loop. Feedback data derived from the RHR and the manipulator, such as tactile forces, joint positions, and velocity are continuously provided to the controller. The environment involves seven types of food objects: five (aubergine, bell pepper, lettuce, navel orange, and beef tomato) from the same categories used during training, and two (tangerine and plume tomato) which were not used in the training phase. These two latter objects are significantly different in size, approximately 50% smaller than the navel orange and beef tomato, respectively.

Food items were placed at a designated location within the robot's reachable working space. The location was carefully marked to ensure repeatability. The robot was placed in a starting position above the food item in question. Then, the grasping, lifting, and placement sequences were generated entirely from the autonomous LfD policy under consideration. While here we only focus on the interaction phase, in the future we also plan to consider the approaching phase by using, e.g., visual-servoing techniques to automatically reach the object from any position.

B. Grasping policies

We carried out grasping experiments taking into account (i) standard human-in-the-loop teleoperation, (ii) standard SVR, (iii-v) three variants of our SVR-based policies, (vi) a recentlypublished haptic LfD approach, and (vii-viii) two standard impedance controllers:

(i) Human teleoperation (no automation). This approach considers the ground truth grasping data recorded during human teleoperation with the haptic interface (see Sec. III-B). No machine learning is involved here. (ii) SVR. This approach uses normalized data (i.e. forces, positions, velocities) as input and directly maps them into grasping actions through a standard Support Vector Regression algorithm (see Sec. IV-A). (iii) SVR-W (weighted as in [START_REF] Misimi | Robotic handling of compliant food objects by robust learning from demonstration[END_REF]). This approach is similar to the SVR above, but it privileges specific RHR sensor data as a mean of improving on the previous algorithm. The weighting is done as in the work of [START_REF] Misimi | Robotic handling of compliant food objects by robust learning from demonstration[END_REF], not using any human direct grasping data (i.e. the heat-maps). (iv) SVR-WH (weighted using heat-maps). This approach is similar to the SVR-W above, but it weights RHR sensor data according to our human-generated heat-maps (see Secs. IV-A and IV-C). (v) SVR-WHT (weighted using both heat-maps and timeseries). Same as SVR-WH, but this approach takes into account the temporal variation in the finger configuration and sensor pressure during the grasping sequence (see Secs. IV-A, IV-B, and IV-C). (vi) Misimi et al. [START_REF] Misimi | Robotic handling of compliant food objects by robust learning from demonstration[END_REF] (state-of-the-art). This approach is a recent learning policy for autonomous grasping, published in 2018. It uses data derived from human teleoperation and tactile sensors on a robotic hand. It differs from our approach because it uses a simple non-haptic joystick during the teleoperation demonstrations, and it does not consider any human direct grasping information when weighting the tactile data. (vii) Impedance controller (gentle grasp). This approach implements a standard impedance controller. The robotic hand increases the grasping force until the average force sensed by the tactile sensors reaches a set threshold. We set this threshold to the average value recorded during trials with haptic teleoperation. (viii) Impedance controller (strong grasp). This approach is the same as (vii), but the threshold is here set to twice the average value recorded during trials with haptic teleoperation. Fig. 5 summarizes the internal relative weights applied in these policies, illustrating how the different sensory input is valued.

C. Autonomous Grasping Task

The task consisted in autonomously grasping seven types of food items using the learning policies cited above. We considered five food items (aubergine, bell pepper, lettuce, navel orange, and beef tomato) coming from the same categories of objects used during training, and two objects (tangerine and plume tomato) significantly different in size.

From the 50 teleoperated grasps per produce (see Sec. III-B), it was possible to tailor our four grasping policies, (ii-v), for each produce used in Sec. III-B, e.g. aubergine-trained SVR-WHT, pepper-trained SVR-WHT, lettuce-trained SVR-WHT, etc. This process yielded a total of 4 policies × 5 (trained) objects = 20 tailored policies. Each (trained) produce was grasped 30 times with its tailored policies. E.g., when grasping the aubergine, we used the four learning policies ii-v trained with data registered during the teleoperation of aubergines. To grasp the two food items whose category was not considered during training (tangerine and plume tomato), we used the four policies trained on navel orange and beef tomato, respectively. This task yielded 30 grasps × 7 produce × 4 policies = 840 grasps. For comparison, we also carried out the same task using the three standard controllers (vi-viii), yielding 30 grasps × 7 produce × 3 policies = 630 additional grasps.

In addition to the above grasping repetitions, we also wanted to study the adaptability of the proposed approach for different objects. To do so, we ran a second set of trials, using tailored Fig. 6. Success rate of grasping tasks. Results are based on 30 grasp attempts per condition per food item. Autonomous grasping using LfD was implemented for a variety of SVRs. SVR with heat-map and time-series inputs had the best accuracy. We compared our approach to a recent state-of-the-art LfD from 2018, and two impedance controller techniques. Grasping variations and their abbreviations are described in Sec. V-B. SVR-WHT policies to grasp produce different than the one it was designed for. We only considered SVR-WHT policies because we expect them to be most effective. To avoid repeating grasps already considered in our first set of trials, each tailored policy only grasped the items it was not designed for, e.g., aubergine-trained SVR-WHT was used to autonomously grasp all items but aubergine. Each food item was grasped 30 times per policy, yielding 30 grasps × 6 produce × 5 tailored SVR-WHT = 900 grasps.

In total, we carried out 2370 autonomous grasping actions.

D. Results and Discussion

Fig. 6 shows the average success rate for autonomous grasping actions for the different food items and policies. On the left-hand side, we can find the results of the first set of trials, which uses the four autonomous policies to grasp the seven objects. In this case, each policy was tailored for each food item, using data coming from grasping trials on the considered object only. For comparison, we also included success rates from (i)-human teleoperation, (vi)-Misimi et al., and (vii,viii)-the two impedance controllers. On the right-hand side, we can find the results of the second set of trials, using SVR-WHT policies trained on objects different than the one they grasped in the testing phase.

The left-hand side of Fig. 6 shows that, among the SVRbased approaches implemented, the SVR-weighted policy using heat-map and time-series data (SVR-WHT) was the one with the highest levels of accuracy. This confirmed our original hypothesis: the addition of real human-interaction elements to the grasping policies increases the overall accuracy, which peaked at 100% for SVR-WHT with all food items. We recall that this result was validated by 30 trial runs for each approach and food item. Both heat-map-based approaches (iv-v) outperformed Misimi et al. in all cases, performing on average 35% better. For SVR-WHT vs. Misimi et al., a related-samples Wilcoxon-signed-rank-test showed a significant difference in the performance (z = 1.997 and p = 0.046). Considering [START_REF] Misimi | Robotic handling of compliant food objects by robust learning from demonstration[END_REF] uses tactile sensing and a recent LfD approach (work published in 2018), this result strongly supports our hypothesis that combining direct hand interaction and high-dexterity haptic teleoperation is a winning technique (these are the two main differences between our work and [START_REF] Misimi | Robotic handling of compliant food objects by robust learning from demonstration[END_REF]). For further comparison, we also included two standard impedance controllers. In this case, the robotic hand grasps until a certain threshold force is reached. We considered as thresholds one and two times the average force registered by the hand sensors during the teleoperation trials. The first approach (gentle grasp) did not damage the food, but it failed to successfully grasp the objects. On the other hand, the second approach (strong grasp) showed very good grasping performance. However, the high force applied severely damaged the considered food (see the red triangles in Fig. 6). Although impedance control could provide acceptable results through fine tuning (i.e. finding a custom force threshold for each item), we believe that LfD provides a more effective (and elegant) solution. Indeed, a simple force threshold approach still requires a significant amount of work from the human user, who needs to program the robot for each different set of objects, defeating the main purpose of our work: efficient non-programmatic automation for food processing.

After these first results, we carried out additional trials to study the adaptability of our approaches for other objects. In these trials, we used SVR-WHT to grasp food items different than the one used for the training, e.g. an SVR-WHT trained on the aubergine was used for grasping all other objects. The large difference between our food items enables us to evaluate the adaptability of our SVR algorithms to different situations. As mentioned above, five objects were in the same category as those used during training (aubergine, bell pepper, lettuce, orange, and beef tomato), while two were much smaller (tangerine and plum tomato). The results on the right-hand side of Fig. 6 suggest that we cannot grasp heavy objects with an SVR policy trained with lighter ones, e.g. a policy trained using lettuce data fails to grasp an aubergine. the opposite often works quite well, e.g. a policy trained using aubergine data succeeds at grasping the lettuce. Of course, in general, results show that grasping objects using policies trained on other objects only works to a certain extent. As expected, as the difference between the target object and the training one increases, the success rate decreases. This degradation happens faster when grasping heavy objects with policies trained on lighter ones. However, even though it is possible to grasp lighter items (e.g. lettuce) using policies trained on heavier ones (e.g. aubergine), the higher force applied may risk to damage the object.

Finally, Fig. 6 shows that success rates for tangerines and plum tomatoes are quite low in respect to the others, demonstrating that our approach struggles to handle objects significantly smaller than those used during the training. As we are using both the positions and forces of the robotic fingers to learn our policies (see Fig. 5), this is an expected behaviour. In fact, while the combination of these two prevents the hand from squeezing items too hard, it also limits the capability of grasping objects with internally varying sizes (i.e. fruits or vegetables grown with higher ecological diversity). Results show that, if we had the opportunity to training LfD policies for each and every specific type of produce, this combined approach of finger position and tactile force sensing works well (see the high performance on the first five food objects Fig. 6). On the other hand, if we plan to autonomously grasp objects where size and shape span a wider range (i.e. produces is less uniformed/higher diversity) we need to make further adjustments, such as using finger force only. However, finger positions seem important and leaving this information out might not be viable, in regards to damages. Our grasps have all been made blindly, picking up a produce at position X. Adding further information about the produce through machine vision could be one way to unify finger positioning and variations size and shape.

It is also interesting to notice that the success rate for the teleoperation trials is not as high as one might expect (between 0.46 and 0.68). A grasping task was deemed successful only when the user was able to successfully grasp, lift, and move the object. Often the operator was able to grasp and lift the object, but then it slipped during transport. Upon asking, the operator said that it was not easy to always maintain the right amount of force needed for a robust grasp, as she was afraid of damaging the produce.

VI. CONCLUSION AND FUTURE WORK

In this paper, we have proposed a novel human-inspired, haptic-enabled learning policy designed to handle compliant food items, originating from the agricultural automation domain. We selected soft food objects because they represent an important example of 3D-compliant object manipulation in robotics, which remains poorly researched due to many manipulation challenges.

The paper presents four LfD learning policies that, after training, were capable of gently and autonomously grasping a representative set of compliant produce such as aubergines, bell peppers, lettuces, oranges, and tomatoes. We compared the four different variants of our LfD approach by carrying out a total of 2370 autonomous grasping actions of compliant food objects. The best proposed approach combines (a) data collected during demonstrations using a haptic-enabled high-dexterity teleoperation interface, and (b) heat-map knowledge acquired from humans directly grasping the items in question. Results indicated that the use of tactile data, weighted according to experience gathered during direct interaction trials, yielded the best performance. We also compared our approach with a recent LfD method for grasping compliant objects and two standard impedance controllers. Results showed that our approach performed better, proving our hypothesis-that to properly learn from humans how to grasp challenging, compliant, and fragile objects, it is beneficial to carry out the demonstrations using an intuitive and natural tool for controlling the slave manipulator.

Another key aspect of our approach is the inspiration from direct human grasping actions, represented in the LfD model by the use of heat-maps as an input variable, privileging and activating the "right" sensors on the robotic hand.

The proposed approach has a vast range of potential applications in the agricultural and food sectors, as well as in other industries that deal with compliant and fragile objects and where a knowledge of the applied tactile forces is crucial to achieving successful grasping actions. Our work contributes to a better understanding of the input required during the development of grasping ML policies. Furthermore, our aim was to make a contribution to the topic of LfD through teleoperation, by highlighting (a) the necessity of improved operator interaction by means of high-fidelity highdexterity interfaces, and (b) the importance of combining these teleoperation data with barehanded prehensile movements. These results have the potential to advance the capabilities of robotic interaction, combining human puppetry with inherent intentions. We also believe that in the future, a more intuitive interaction system with strong learning capabilities can even void the need of expert human operators pre-training the robots. If the interface is intuitive enough, anyone able to carry out the target task will be able to also train the robot, allowing for an easier deployment.

In future work, we plan to keep improving our teleoperation system. It is of paramount importance to keep providing human operators with intuitive and natural approaches to control the slave manipulator. The more naturally a human operator carries out a task, the more useful the data will be, enabling effective and true learning of the task in question.

Toward this objective, we plan to design a new multisensory bi-manual teleoperation system that will provide a wide range of haptic feedback features (kinesthetic, contact pressure, skin stretch and vibratory), and to extend the range of tasks that the robotic system can perform. We will also consider other ways to map the motion of the human operator into that of the robotic manipulator, so as to understand how different mapping techniques can affect the performance of the learning policies. Another important point to further study is the type and amount of information we need during the training, especially to understand what is most important when it comes to grasping objects with a different size than those used during the training. For this reason, it will be fundamental to also extend the evaluation to a wider range of compliant objects. Furthermore, our technique for heat-mapping, though functional for our small scale, should get a simpler and faster interface in future works. Sundaram et al. [START_REF] Sundaram | Learning the signatures of the human grasp using a scalable tactile glove[END_REF] could be one avenue to explore with a promising technique for collection of digital heat-maps and human-object-interaction signatures, when their interface becomes available for research use. Another point to highlight is that an advanced master interface such as that used here is rather expensive (around $110,000). However, it is important to bear in mind that the master interface is only used in the first part of the learning phase. Once the LfD policy is trained, only the slave manipulator is required. For this reason, the effective cost is significantly lower as it spreads over the total number of autonomous grasps carried out using this approach. Finally, we also plan to extend the range of learning techniques considered, e.g., deep learning, ensemble learning, and the range of objects, e.g., industrial 3D compliant objects, smaller/larger and more fragile food items such as raspberries, strawberries, and fish (whole and fillets). We will also compare all performance metrics using principled statistical approaches, such as repeatedmeasures ANOVA.

Fig. 1 .

 1 Fig. 1. Food items and Heat-map capturing.a) The five food objects used in the experiments: average circumference 290 mm, height 75 mm. b) Heat-map generation set-up. A laptop connected to a camera, a lighting system, water paint with a brush for application, and a cloth for wiping the subject's hand after each trial.

Fig. 2 .

 2 Fig. 2. Example of a heat-map generation (aubergine). The intensity of the RGB-image is extracted, converted to binary, then mapped to a generic hand using Thin-Plate spline interpolation, creating an intensity image for accumulated binary images. Active areas in the hand change with different objects.

  Symbol Definition/Description * m , * s related to the master or slave, respectively xm , xs end-effector pose pm , ps end-effector position Rm , Rs end-effector orientation W world coordinate system vm , vs end-effector linear velocity ωm , ωs end-effector rotational velocity * MCP , * P IP related to the fingers' metacarpophalangeal joint and proximal-interphalangeal joint, respectively θr i angular command to the MCP robotic joint i θe i angular value of the MCP exoskeleton joint i τ M CP,i , τ P IP,i haptic feedback applied to finger i mpro,i, m dis,i average pressure on the proximal and distal phalanges of the robot finger i, respectively gpos pose of the gripper fprs tactile readings from the robotic hand's pressure sensors fmot position of the motors of the robotic hand fang joint angles of the exoskeleton s observed robotic grasping action performed by the human teacher a action-state, including gripper pose and motor positions α, β, γ discrete time-series steps H k j heat-map values gathered during direct hand interaction for object k and action vector feature j

Fig. 3 .

 3 Fig. 3. Teleoperation set-up and control design. (a) The human operator teleoperates the slave system to grasp a tomato. (b) Master-slave control: [xs, ys, zs, qs T ] T are the end-effector coordinates defining the pose of the RHR hand. The difference between the previous and current master position is used to evaluate the velocity command, which is then sent to the slave manipulator. RHR finger movements are proportional to the positions registered by the H-Glove fingers.

Fig. 4 .

 4 Fig. 4. Generation of LfD policy from acquired data. Finger tactile values coming from the RHR-hand were weighted according to heat-map data when generating the human-inspired LfD-policy. Temporal variation was captured by implementing time-series, where n previous values for the robot pose, finger configuration, and tactile stimuli were applied to the generation of predictions.

4 -Complete prehensile move 4 -

 4 No visible modifications 3 -Slips close to the landing 3 -Small, localized, light marks 2 -Slips mid-way 2 -Mid-sized, spread marks 1 -Slips right after lift-off 1 -Bruises, small tears in skin 0 -Robotic hand fails to clutch, action aborted 0 -Heavy bruises, spread marks and tears in skin IV. MACHINE LEARNING

Fig. 5 .

 5 Fig. 5. Weighting for each algorithm: How these values relate to each other defines the SVRs work-space. Comparison of SVR weights gives an understanding of how they differ and relate to action inputs. For the abbreviations, see Sec. V-B.

TABLE I

 I List of main symbols and variables.

ACKNOWLEDGMENTS

We would like to express our appreciation for the financial support given by Research Council of Norway via iProcess (255596) and GentleMAN (299757). We also wish to acknowledge the help provided through our two laboratories: MAROLA at SINTEF Ocean and the RAINBOW team at IRISA/Inria Rennes. Finally, we are particularly grateful for the assistance given by Elling Ruud Øye and Martin von Heimburg (SINTEF Ocean AS) for helping in the vision collection and learning trials, respectively.


Alin Bostan
email: alin.bostan@inria.fr

Antonio Jiménez-Pastor

On the exponential generating function of labelled trees Sur la série génératrice des arbres étiquetés

Keywords: Combinatorics, generating functions, differential equations. 2020 Mathematics Subject Classification. 05A15, 12H05, 34A34

We show that the generating function of labelled trees is not D ∞ -finite.

Résumé. Nous montrons que la série génératrice des arbres étiquetés n'est pas D ∞ -finie.

Version française abrégée

Nous montrons que la série génératrice exponentielle des arbres étiquetés, T (x) = n≥1 n n-1 n! x n , n'est pas D ∞ -finie. En particulier, cela implique que, bien que T (x) vérifie des équations différentielles non-linéaires, ces dernières ne peuvent pas être « trop simples ». En particulier, T (x) n'est pas un quotient de deux fonctions D-finies (vérifiant des équations différentielles à coefficients polynomiaux), et plus généralement, T (x) ne vérifie aucune équation différentielle linéaire à coefficients des fonctions D-finies. La preuve repose ultimement sur un résultat de théorie de Galois différentielle. Plusieurs questions ouvertes sont proposées, dont une sur la nature de la série génératrice ordinaire des arbres étiquetés, n≥1 n n-1 x n .

Context and main result

A formal power series f (x) = n≥0 a n x n in C[[x]
] is called differentially finite, or simply Dfinite [START_REF] Stanley | Differentiably finite power series[END_REF], if it satisfies a linear differential equation with polynomial coefficients in C[x]. Many generating functions in combinatorics and many special functions in mathematical physics are D-finite [START_REF] Andrews | Special functions, volume 71 of Encyclopedia of Mathematics and its Applications[END_REF][START_REF] Flajolet | Analytic combinatorics[END_REF]. DD-finite series and more generally D n -finite series are larger classes of power series, recently introduced in [START_REF] Jiménez-Pastor | A computable extension for D-finite functions: DD-finite functions[END_REF]. DD-finite power series satisfy linear differential equations, whose coefficients are themselves D-finite power series. One of the simplest examples is tan(x), which is DD-finite (because it satisfies cos(x) f (x)sin(x) = 0), but is not D-finite (because it has an infinite number of complex singularities, a property which is incompatible with D-finiteness). Another basic example is the exponential generating function of the Bell numbers B n , which count partitions of {1, 2, . . . , n}, namely:

B (x) := n≥0 B n n! x n . (1)
Indeed, it is classical [9, p. 109] that B (x) = e e x -1 , therefore B (x) is DD-finite. On the other hand, B (x) is not D-finite: this can be proved either analytically (using the too fast growth of B (x) as x → ∞), or purely algebraically (using [START_REF] Singer | Algebraic relations among solutions of linear differential equations[END_REF], and the fact that the power series e x is not algebraic). More generally, given a differential ring R, the set of differentially definable functions over R, denoted by D(R), is the differential ring of formal power series satisfying linear differential equations with coefficients in R. In particular, D(C[x]) is the ring of D-finite power series, D 2

(C[x]) := D(D(C[x]
)) is the ring of DD-finite power series, and

D n (C[x]) := D(D n-1 (C[x]
)) is the ring of D n -finite power series. We say that a power series f

(x) ∈ C[[x]] is D ∞ -finite if there exists an n such that f (x) is D n -finite.
It is known [START_REF] Jiménez-Pastor | Some structural results on D n -finite functions[END_REF] that D n -finite power series form a strictly increasing sequence of sets and that any D ∞ -finite power series is differentially algebraic, in short D-algebraic, that is, it satisfies a differential equation, possibly non-linear, with polynomial coefficients in C[x]. This class, as well as its complement (of D-transcendental series), are quite well studied [START_REF] Rubel | A survey of transcendentally transcendental functions[END_REF][START_REF] Van Der Hoeven | Computing with D-algebraic power series[END_REF].

Let now (t n ) n≥0 = (0, 1, 2, 9, 64, 625, 7776, . . .) be the sequence whose general term t n counts labelled rooted trees with n nodes. It is well known that t n = n n-1 , for any n. This beautiful and non-trivial result is usually attributed to Cayley [START_REF] Cayley | A theorem on trees[END_REF], although an equivalent result had been proved earlier by Borchardt [START_REF] Borchardt | Ueber eine der Interpolation entsprechende Darstellung der Eliminations-Resultante[END_REF], and even earlier by Sylvester, see [START_REF] Biggs | Graph theory. 1736-1936[END_REF]Chapter 4]. Due to the importance of the combinatorial class of trees, and to the simplicity of the formula, Cayley's result has attracted a lot of interest over the time, and it admits several different proofs, see e.g., [15, §4] and [1, §30]. One of the more conceptual proofs goes along the following lines (see [9, §II. 5.1] for details). Let

T (x) := n≥0 t n n! x n (2)
be the exponential generating function of the sequence (t n ) n . The class T of all rooted labelled trees is definable by a symbolic equation T = Z SET(T ) reflecting their recursive definition, where Z represents the atomic class consisting of a single labelled node, and denotes the labelled product on combinatorial classes. This symbolic equation provides, by syntactic translation, an implicit equation on the level of exponential generating functions:

T (x) = x e T (x) , (3)
which can be solved using Lagrange inversion

t n = n! • [x n ]T (x) = n! • 1 n [z n-1 ](e z ) n = n n-1 . (4)
From (3), it follows easily that T (x) is D-algebraic and satisfies the non-linear equation

x(1 -T (x))T (x) = T (x),
and from there, that the sequence (t n ) n≥0 satisfies the non-linear recurrence relation

t n+1 = n + 1 n • n i =1 n i t i t n-i +1 , for all n ≥ 1.
This recurrence can also be proved using (4), by taking y = n, x = w = 1 in Abel's identity [START_REF] Jensen | Sur une identité d'Abel et sur d'autres formules analogues[END_REF] (x

+ y) n = n k=0 n k x(x + wk) k-1 (y -wk) n-k ,
and then by isolating the term k = n in the resulting equality.

On the other hand, it is known that the power series T (x) is not D-finite, see [START_REF] Gerhold | On some non-holonomic sequences[END_REF]Theorem 7], or [START_REF] Flajolet | On the non-holonomic character of logarithms, powers, and the nth prime function[END_REF]Theorem 2]. This raises the natural question whether T (x) is DD-finite, or D n -finite for some n ≥ 2. Our main result is that this is not the case:

Theorem 1. The power series T (x) = n≥1 n n-1 n! x n in (2) is not D ∞ -finite.
To our knowledge, this is the first explicit example of a natural combinatorial generating function which is provably D-algebraic but not D ∞ -finite. In particular, Theorem 1 implies that T (x) is not equal to the quotient of two D-finite functions, and more generally, that it does not satisfy any linear differential equation with D-finite coefficients.

Proof of the main result

Our proof of Theorem 1 builds upon the following recent result by Noordman, van der Put and Top.

Theorem 2 ( [17]). Assume that u(x)

∈ C[[x]] \ C is a solution of u = u 3 -u 2 . Then u is not D ∞ - finite.
The proof of Theorem 2 is based on two ingredients. The first one is a result by Rosenlicht [START_REF] Rosenlicht | The nonminimality of the differential closure[END_REF] stating that any set of non-constant solutions (in any differential field) of the differential equation u = u 3u 2 is algebraically independent over C (see also [START_REF] Noordman | Combinatorial autonomous first order differential equations[END_REF]Prop. 7.1]); the proof is elementary. The second one [START_REF] Noordman | Combinatorial autonomous first order differential equations[END_REF]Prop. 7.1] is that any non-constant power series solution of an autonomous first-order differential equation with this independence property cannot be D ∞ -finite; the proof is based on differential Galois theory.

Proof of Theorem 1. We will use Theorem 2 and a few facts about the (principal branch of the) Lambert W function, satisfying W (x) • e W (x) = x for all x ∈ C.

Recall [START_REF] Corless | On the Lambert W function[END_REF] that the Taylor series of W around 0 is given by

W (x) = ∞ n=1 (-n) n-1 n! x n = x -x 2 + 3 2 x 3 -8 3 x 4 + 125 24 x 5 -• • • .
In other words, our T (x) and W (x) are simply related by W (x) = -T (-x).

The function defined by this series can be extended to a holomorphic function defined on all complex numbers with a branch cut along the interval (-∞, -1 e ]; this holomorphic function defines the principal branch of the Lambert W function.

We can substitute x → e x+1 in the functional equation for W (x) obtaining then

W (e x+1 )e W (e x+1 ) = e x+1 ,
or, renaming Y (x) = W (e x+1 ), we have a new functional equation: Y (x)e Y (x)-1 = e x . From this equality it follows by logarithmic differentiation that Y (x)

• (1 + Y (x)) = Y (x). Take now U (x) := 1 1+Y (x) = 1 2 -1 8 x + 1 64 x 2 + 1 768 x 3 + • • • . We have that U (x) = -Y (x) (1 + Y (x)) 2 = -Y (x) (1 + Y (x)) 3 = U (x) 3 -U (x) 2 .
By Theorem 2, U (x) is not D ∞ -finite. By closure properties of D ∞ -finite functions (see [START_REF] Jiménez-Pastor | Some structural results on D n -finite functions[END_REF]Theorem 4] and [12, §3]), it follows that Y (x) is not D ∞ -finite either.

To conclude, note that by definition, for real x in the neighborhood of 0, we have W (x) = Y (log(x) -1), and by Theorem 10 in [START_REF] Jiménez-Pastor | Some structural results on D n -finite functions[END_REF], it follows that W (x) and T (x) are not D ∞ -finite either, proving Theorem 1.

Open questions

The class of D-finite power series is closed under Hadamard (term-wise) product. This is false for D ∞ -finite power series; for instance, Klazar showed in [START_REF] Klazar | Bell numbers, their relatives, and algebraic differential equations[END_REF] that the ordinary generating function n≥0 B n x n of the Bell numbers is not differentially algebraic, contrary to its exponential generating function [START_REF] Aigner | Proofs from The Book[END_REF], which is DD-finite.

Moreover, it was conjectured by Pak and Yeliussizov [18, Open Problem 2.4] that this is an instance of a more general phenomenon.

Conjecture 3 ( [18, Open Problem 2.4]).

If for a sequence (a n ) n≥0 both ordinary and exponential generating functions n≥0 a n x n and n≥0 a n x n n! are D-algebraic, then both are D-finite. (Equivalently, (a n ) n≥0 satisfies a linear recurrence with polynomial coefficients in n.)

This conjecture has been recently proven for large (infinite) classes of generating functions [START_REF] Bostan | Differential transcendence of Bell numbers and relatives -a Galois theoretic approach[END_REF]. However, the very natural example of the generating function for labelled trees escapes the method in [START_REF] Bostan | Differential transcendence of Bell numbers and relatives -a Galois theoretic approach[END_REF].

We therefore leave the following as an open question.

Open question 1. Is the power series n≥1 n n-1 x n D ∞ -finite? Is it at least differentially algebraic?

According to Conjecture 3, the answer should be "no" for both questions in Open question 1.

Another natural question concerns the generating function for partition numbers: which is known to be differentially algebraic [START_REF] Mian | The differential equations satisfied by certain functions[END_REF].

Open question 2. Is it true that n≥0 p n x n is not D ∞ -finite?

One may also ask for the nature of the exponential variant of the generating function for partition numbers.

Open question 3. Is the power series n≥0 p n n! x n D ∞ -finite, or at least differentially algebraic?

n≥0 p n x n := n≥1 1 1 -

 1 x n = 1 + x + 2 x 2 + 3 x 3 + 5 x 4 + 7 x 5 + 11 x 6 + • • • ,

Acknowledgements

We would like to warmly thank the referees for their careful reading and for their constructive remarks.

Funding. This research was partially funded by the Austrian Science Fund (FWF): W1214-N15, project DK15. It was also supported in part by the ANR DeRerumNatura project, grant ANR-19-CE40-0018 of the French Agence Nationale de la Recherche.

Electronic supplementary material.


Thierry Fraichard

Vivien Delsart

Navigating Dynamic Environments with Trajectory Deformation

Keywords: Mobile robots, autonomous navigation, collision avoidance, motion deformation

Path deformation is a technique that was introduced to generate robot motion wherein a nominal path, that has been computed beforehand, is continuously deformed online in response to unforeseen obstacles. In an effort to improve path deformation, this paper presents a trajectory deformation scheme. The main idea is that by incorporating the time dimension and hence information on the obstacles' future behaviour, quite a number of situations where path deformation would fail can be handled. The trajectory represented as a discrete space-time curve is subject to deformation forces both external (to avoid collision with the obstacles) and internal (to maintain trajectory feasibility and connectivity). The trajectory deformation scheme has been tested successfully on a planar robot with double integrator dynamics moving in dynamic environments.

Introduction

Where to move next? is a key question for an autonomous robotic system. This fundamental issue has been largely addressed in the past forty years. Many motion determination strategies have been proposed (see [START_REF] Lavalle | Planning Algorithms[END_REF] for a review). They can broadly be classified into deliberative versus reactive strategies: deliberative strategies aim at computing a complete motion all the way to the goal, whereas reactive strategies determine the motion to execute during the next few time-steps only. Deliberative strategies have to solve a motion planning problem. They require a model of the environment as complete as possible and their intrinsic complexity is such that it may preclude their application in dynamic environments. Reactive strategies on the other hand can operate on-line using local sensor information: they can be used in any kind of environment whether unknown, changing or dynamic, but convergence towards the goal is difficult to guaran-tee.

To bridge the gap between deliberative and reactive approaches, a complementary approach has been proposed based upon motion deformation. The principle is simple: a complete motion to the goal is computed first using a priori information. It is then passed on to the robotic system for execution. During the course of the execution, the stillto-be-executed part of the motion is continuously deformed in response to sensor information acquired on-line, thus accounting for the incompleteness and inaccuracies of the a priori world model. Deformation usually results from the application of constraints both external (imposed by the obstacles) and internal (to maintain motion feasibility and connectivity). Provided that the motion connectivity can be maintained, convergence towards the goal is achieved.

Figure 1: Path deformation problem: in response to the approach of the moving disk, the path is increasingly deformed until it snaps (like an elastic band).

The different motion deformation techniques that have been proposed [START_REF] Quinlan | Elastic bands: Connecting path planning and control[END_REF]; [START_REF] Khatib | Dynamic path modification for carlike nonholonomic mobile robots[END_REF]; [START_REF] Brock | Elastic strips: a framework for motion generation in human environments[END_REF]; [START_REF] Lamiraux | Reactive path deformation for nonholonomic mobile robots[END_REF]; [START_REF] Yang | Elastic roadmaps: Globally task-consistent motion for autonomous mobile manipulation[END_REF] all performs path deformation. In other words, what is deformed is a geometric curve, ie the sequence of positions that the robotic system is to take in order to reach its goal. The problem with path deformation techniques is that, by design, they cannot take into account the time dimension of a dynamic environment. For instance in a scenario such as the one depicted in Fig. 1, it would be more appropriate to leave the path as it is and adjust the velocity of the robotic system along the path so as to avoid collision with the moving obstacle (by slowing down or accelerating). To achieve this, it is necessary to depart from the path deformation paradigm and resort to trajectory deformation instead. A trajectory is essentially a geometric path parametrized by time. It tells us where the robotic system should be but also when and with what velocity. Unlike path deformation wherein spatial deformation only takes place, trajectory deformation features both spatial and temporal deformation meaning that the planned velocity of the robotic system can be altered thus permitting to handle gracefully situations such as the one depicted in Fig. 1.

The first trajectory deformation scheme has been proposed by one of the authors in [START_REF] Kurniawati | From path to trajectory deformation[END_REF]. It operates in two stages (collision avoidance and connectivity maintenance stages) and was geared towards manipulator arms. The contribution of this paper is a new trajectory deformation scheme, henceforth called Teddy (for Trajectory Deformer). It operates in one stage only and is designed to handle arbitrary robotic systems.

Teddy is designed to be one component of an otherwise complete autonomous navigation architecture. A motion planning module is required to provide Teddy with the nominal trajectory to be deformed. Teddy operates periodically with a given time period. At each cycle, Teddy outputs a deformed trajectory which is passed to a motion control module that determines the actual commands for the actuators of the robotic system. The paper focuses on Teddy only. It is organised as follows: Teddy is overviewed in §2. Its application to the case of a planar robot with double integrator dynamics (subject to velocity and acceleration bounds) is detailed in §3. Experimental results are then presented in §4.

Overview of the Approach

Notations and Definitions

Let A denote a robotic system operating in a workspace W (IR 2 or IR 3 ). q ∈ C denote a configuration of A. The dynamics of A is described by a differential equation of the form:

ṡ = f (s, u)
where s ∈ S is the state of A, ṡ its time derivative and u ∈ U a control. C, S and U respectively denote the configuration space, the state space and the control space of A. Let ξ : [0, t f [-→ U denote a control input, ie a time-sequence of controls. Starting from an initial state s 0 (at time 0) and under the action of a control input ξ, the state of A at time t is denoted by s(s 0 , ξ, t). A couple (s 0 , ξ) defines a trajectory for A, ie a curve in S × T where T denotes the time dimension.

For the sake of trajectory deformation, a trajectory is discretized in a sequence of nodes. A node is a state-time, it is denoted by n i = (s i , t i ). The discrete trajectory of A is Γ 0 = {n 0 , n 1 • • • n N } with n 0 (resp. n N ) the initial (resp. final) node of the trajectory.

Trajectory Deformation Principle

Algorithm 1: Teddy.

Input: The main steps of Teddy are outlined in Algorithm 1. Teddy operates periodically with a time period of duration T c . At time t k , it takes as input the still-to-be-executed part of the trajectory Γ k = {n k , n k+1 • • • n N } and an updated model of the workspace. This model includes the position of the obstacles of W at time t k along with information about their future behaviour. Teddy then deforms Γ k in response to the updated position and future behaviour of the obstacles. At time

Γ k = {n k , n k+1 • • • n N }, Workspace model Output: Γ k+1 = {n k ′ , n k+1 ′ • • • n N ′ } Γ k+1 = ∅; 1 // Apply forces to each node foreach n i ∈ Γ k do 2 n i ′ = n i + F ext (n i ) + F int (n i ); 3 Γ k+1 = Γ k+1 ∪ n i ′ ; 4 end 5 //
t k+1 = t k + T c , Teddy outputs a deformed trajec- tory Γ k+1 = {n k ′ , n k+1 ′ • • • n N ′ } with n i ′ the up- dated node corresponding to n i .
Like a particle placed in a force field, a node is displaced in response to the application of a force which is the combination of two kind of forces: external and internal. External forces (denoted F ext ) are repulsive forces exerted by the obstacles of the environment, their purpose is to deform the trajectory in order to keep it collision-free. They are detailed in §2.3. Internal forces (denoted F int ) on the other hand are aimed at maintaining the feasibility and the connectivity of the trajectory, ie to ensure that the deformed trajectory still satisfies the dynamics of A. They are detailed in §2.4. Now, for the sake of both collision-checking and connectivity evaluation, it is desirable to maintain a regular sampling level along the trajectory. Depending on the situation, nodes are removed or added accordingly. This point is detailed in §2.5.

Finally, it is important to note that, like the path deformation scheme, the trajectory deformation scheme suffers from the following limitation: there is no guarantee that it will produce a collisionfree and connected trajectory at each time step; both schemes are heuristic by nature. Failure to produce a valid trajectory typically happens when the topology of S × T changes (when a passage is blocked for instance, like when a door is closed). At each time step, the deformed trajectory is therefore checked for collision and connectivity. Should it become invalid, a global motion planner must be invoked to compute a new nominal trajectory. Strictly speaking, the motion planner is not part of Teddy, it is not discussed here.

External Forces

External forces are repulsive forces exerted by the obstacles of the environment for collision avoidance purposes. They are derived from a potential function V ext . To explicitly take into account the future behaviour of the moving obstacles, V ext is defined in the space-time W × T (instead of S × T for efficiency reason). In a manner similar to [START_REF] Brock | Elastic strips: a framework for motion generation in human environments[END_REF], a set of points p j are selected on the body of A. Each node n i of the trajectory Γ k yield a set of control points c j i = (p j , t i ) in W × T. For a control point c j corresponding to the configuration q and the state s along the trajectory, V ext is defined as:

V ext (c j ) = k ext (d 0 -d wt (c j )) 2 if d wt (c j ) < d 0 0 otherwise
(1) where d wt (c j ) is the distance from c j to the closest obstacle in W × T. d 0 is the region of influence around the obstacles and k ext is a repulsion gain. d wt is a distance function in W × T. It is derived from the Euclidean distance by scaling the space versus the time dimension. In IR 2 for instance, the distance d wt between (x 0 , y 0 , t 0 ) and (x 1 , y 1 , t 1 ) is given by:

d wt 2 = w s 2 (x 1 -x 0 ) 2 + w s 2 (y 1 -y 0 ) 2 + w t 2 (t 1 -t 0 ) 2 (2)
with w s (resp. w t ) the spatial (resp. temporal) weight. The force resulting from this potential function acting on c j is then defined as:

F wt ext (c j ) = -∇V ext (c j ) = k ext (d 0 -d wt (c j )) d ||d|| (3)
where d is the vector between c and the closest obstacle point. Now, F wt ext has to be mapped into S × T. The forces defined in W × T by each control point c j yield a force in C × T defined as follows:

F ct ext (q, t) = r j=1 J T c j (q, t)F wt ext (c j ) (4)
where J T c j (q, t) represents the Jacobian at point c j :

J T c j (q, t) =         ∂q 1 ∂p j 1 • • • ∂q 1 ∂p j m 0 . . . . . . . . . . . . ∂q n ∂p j i • • • ∂q n ∂p j m 0 0 • • • 0 1         (5)
with m the dimension of W, p j l the l th coordinate of p j , n the dimension of C and q l the l th coordinate of q. The final mapping into S × T that yields F ext (n) = F ext (s, t) is carried out by leaving the remaining parameters of s unchanged.

Internal Forces

The external forces defined above push each node of the trajectory away from the obstacles if they are inside their influence region. Internal forces are introduced to ensure that the trajectory remains connected, ie that there exists a trajectory verifying the dynamics of A between two consecutive nodes of the trajectory. Trajectory connectivity is related to the concepts of forward and backward reachability. The set of states that are reachable from a given state s 0 are defined as (forward-reachability):

R(s 0 ) = {s f ∈ S|∃ξ, ∃t, s(s 0 , ξ, t) = s f } (6)
Likewise, the set of states from which it is possible to reach a given state s 0 are defined as (backwardreachability):

R -1 (s 0 ) = {s b ∈ S|∃ξ, ∃t, s(s b , ξ, t) = s 0 } (7)
Let n -, n and n + denote three consecutive nodes of the trajectory Γ k . Γ k is connected at n iff n ∈ R(n -) and n + ∈ R(n). In other words, n must belong to R(n -) ∩ R -1 (n + ). Now, two cases arises depending on whether the intersection R(n -) ∩ R -1 (n + ) is empty or not (if this intersection is not empty, it means that n -and n + are connected together also). The next two sections detail how the internal forces are defined in both cases.

2.4.1. Case 1: n -And n + Connected

In that case, the purpose of the internal force is to ensure that n remains within R(n -) ∩ R -1 (n + ). To that end, a virtual spring is defined between n and a selected point H belonging to R(n -) ∩ R -1 (n + ). It yields a potential function V int defined in the spacetime S × T as:

V int (n) = k int d st (n) 2 (8)
where d st (n) is the distance between n and H. It is defined in a manner similar to d wt . k int is an attraction gain.

F int (n) = -∇V int (n) = k int d st (n) d ||d|| ( 9
)
where d is the vector between n and H.

2.4.2. Case 2: n -And n + Disconnected

In that case, R(n -) ∩ R -1 (n + ) = ∅ and it is not possible to find a point H belonging to R(n -) ∩ R -1 (n + ). The solution proposed then is aimed at restoring the connectivity with n -only. To that end, H is simply selected within R(n -) and F int is defined as in §2.4.1. above.

Selecting H

Depending on whether n -and n + are connected together (ie whether R(n -) ∩ R -1 (n + ) is empty or not), H should be selected within R(n -) ∩ R -1 (n + ) or R(n -). In the former case, a natural choice for H would be the centroid of R(n -) ∩ R -1 (n + ). In the latter case, H could for instance be defined as the point of R(n -) which is the closest to n.

Other choices are possible of course but the important thing to note is that, in theory, determining H requires, in the worst case, the characterization of the three sets R(n -), R -1 (n + ) and R(n -) ∩ R -1 (n + ). Computing reachable sets for arbitrary robotic systems is a process whose complexity is dependent upon the dimensionality of the system considered and whether its dynamics is linear or not (cf [START_REF] Asarin | Recent progress in continuous and hybrid reachability analysis[END_REF]; [START_REF] Mitchell | Comparing forward and backward reachability as tools for safety analysis[END_REF]). Since Teddy has a limited time T c only to deform the trajectory, it is therefore critical that Teddy be able to compute F int (n) as efficiently as possible. To that end, it is important to exploit as much as possible the properties of the robotic system considered, and in some cases, to resort to various approximation or linearization schemes. The case study of §3. presents such an approximation scheme.

In the case where n -and n + are connected, another possibility is to compute a feasible trajectory from n -to n + and to select, say its intermediate state, to define H. Once again, it is the particulars of the robotic systems at hand that determines how the internal forces are actually computed.

Trajectory Resampling

In the course of the deformation process, the nodes of the trajectory may either move away from their neighbours or, on the contrary, move very close to them (whether it be in the spatial or the temporal dimensions). For the sake of both collision-checking and connectivity evaluation, it is desirable to maintain a regular sampling level of the trajectory Γ k . Depending on the situation, nodes are removed or added accordingly.

Let n -, n and n + denote three consecutive nodes of the trajectory Γ k . A space-time distance similar to d wt is used to compute the distance between two nodes (cf ( 2)). To begin with, if the distance between n -and n + is less than a given threshold, n is removed from Γ k . Then, the distance between n -and n is computed. If is is greater than a given threshold then a new intermediate node n i is added to Γ k . n i can be defined as the centroid of R(n -) ∩ R -1 (n). This node-adding procedure is repeated recursively for both pair of nodes (n -, n i ) and ((n i , n) (in case n -and n are really far from one another). The same node-adding procedure is repeated for the nodes n and n + .

Case Study: Double Integrator

To begin with, Teddy has been applied to the case of a 2D planar robot A with double integrator dynamics (point mass model). A state of A is characterized by (p, v) that respectively denote the 2D position and velocity of A: p = (x, y) and v = (v x , v x ). The dynamics of A is given by:

ṗ v = v a ( 10
)
where a denotes the acceleration control applied to A. |a| ≤ a max and |v| ≤ v max . As mentioned earlier in §2.4.3., one key point in the adaptation of Teddy to a particular robotic systems lies in the determination of the point H that is used to compute the internal force F int . It is important that H can be computed efficiently. Algorithm 2 outlines the way H is computed in our case. The main idea is to compute both R(n -) and R -1 (n + ) for a particular time slice only, namely the intermediate time slice t = (t +t -)/2. It is also taken advantage of the fact that, it is possible for the system (10) to compute the sets R(n -), R -1 (n + ) and R(n -) ∩ R -1 (n + ) for each spatial dimension independently.

Algorithm 2: H selection.

Input: {n -, n, n + } Output: Let us first consider how to compute R(n -) for the time slice t (henceforth denoted R(n -, t)), and for the x-dimension only, ie in the case where n -= (x -, v x -, t -). The y-dimension is dealt with similarly and so is the computation of R -1 (n + , t).

H // Check chronology if t + < t -then 1 // Select H within R(n -) H = ForwardSelect(n -, n); 2 return H; 3 end 4 // Compute intermediate time t = (t + -t -)/2; 5 // Compute R(n -) at time t F t = R(n -, t); 6 // Compute R -1 (n + ) at time t B t = R -1 (n + , t); 7 // Compute R(n -) ∩ R -1 (n + ) at time t I t = F t ∩ B t ; 8 // Is R(n -) ∩ R -1 (n + )
Computing R(n -, t)

First, the extremal positions reachable at time t from n -are computed. It is easily achieved by integrating forward (10) while applying the extremal control ±a max (until ±v x max is reached). Let p min (t) and p max (t) denote these extremal positions. Then, for a discrete set of positions p i ∈ [p min (t); p max (t)], we compute the corresponding extremal velocities min (p i , t) and v max (p i , t). Now, the convex hull of the corresponding set of position-velocity pairs yields a 2D polygonal approximation of R(n -, t). R -1 (n + , t) is computed in a similar manner.

Computing R(n -, t) ∩ R -1 (n + , t)

Both R(n -, t) and R -1 (n + , t) are represented by 2D polygons of the position-velocity space. A straightforward polygon intersection yields R(n

-, t) ∩ R -1 (n + , t). If R(n -, t) ∩ R -1 (n + , t) is not empty then its centroid is computed, it becomes H (line 10 of Algorithm 2). Selecting H within R(n -) Now, if R(n -, t) ∩ R -1 (n + , t
) is empty, H must be selected within R(n -) in order to try to maintain the connectivity between n -and n. To that end, a discrete set of time instants t j > t -is defined and the corresponding reachable sets R(n -, t j ) are computed as above. Their centroids H j are computed as well. Finally the point H j whose distance to n is minimal becomes H (lines 2 and 12 of Algorithm 2). Teddy has been implemented in C++ and tested on an Intel Pentium 4 desktop PC (3 GHz, 1 GB RAM, Linux OS). Teddy has been evaluated in different scenarios. At each time cycle, Teddy is provided with a new model of the environment under the form of a list of a fixed and moving obstacles B i ). The moving obstacles are moving randomly but the model of the future assumes they maintain a constant linear velocity. Fig. 2 illustrates in a visual manner how Teddy operates.

Experimental Results

A

F ext , F int Γ k B 1 B 2 B 3

"Cutting" Scenario

To emphasize the interest of trajectory deformation vs path deformation, a "cutting" scenario similar to the one depicted in Fig. 1 has been considered first. This scenario has been selected because it is problematic for classical path deformation schemes.

Teddy relies upon a number of parameters to operate properly: the repulsion gain k ext , the attraction gain k int and the distance functions d wt and d st . The two examples presented below have been selected to illustrate the importance of the distance function d wt on the performance of Teddy. Recall that d wt is used to determine the distance between a trajectory node and the closest obstacle in W × T (cf §2.3.). In both examples, the initial trajectory had a duration of 20s and the discrete trajectory contained 320 nodes. Teddy would run at 28Hz.

For the same scenario, two very different deformation patterns can be obtained by properly selecting the weights w s and w t in (2). The first example is obtained by giving more weight to w s thereby allowing more important spatial deformations to take place (Fig. 3). In this case, A has time to pass before the obstacle crosses its path. The path component of the trajectory is deformed downwards for safety reasons whereas the velocity component is only slightly modified.

The second example on the other hand is obtained by giving more weight to w t thereby allowing more important temporal deformations to take place (Fig. 4). In this case, A let the obstacle cross its path before proceeding. The path component of the trajectory is only slightly modified whereas the velocity component is largely deformed so as to allow A to slow down and stop in order to give way to the obstacle.

These two examples have shown the influence of the choice of the parameters in the final performance of Teddy. They have also illustrated the advantage of trajectory deformation versus path deformation.

Miscellaneous Scenarios

Afterwards, Teddy has been tested on different scenarios featuring up to 10 obstacles moving randomly (their linear velocity change at each time cycle). Three runs with different settings for the weights w s and w t are illustrated in Figs. 5 to 7. In Fig. 5, w s is the most important thereby allowing more important spatial deformations to take place. In Fig. 6, w t is the most important thereby allowing more important temporal deformations to take place. In Fig. 7, w s and w t are balanced, both spatial and temporal deformations take place. Finally, Teddy has been tested on a scenario featuring both fixed and moving obstacles (Fig. 8).

Performances of Teddy

From a complexity point of view, it grows linearly with the number of nodes and the number of obstacles. Table 1 gives the running time of one deformation cycle for different numbers of nodes and obstacles. These results shows the ability of Teddy to operates efficiently even in highly cluttered environments.

Conclusion and Future Works

The paper has presented Teddy, a trajectory deformation scheme. Given a nominal trajectory reaching a given goal, Teddy deforms it reactively in response to updated information about the environment's obstacles. Teddy can handle robotic systems with arbitrary dynamics. It has been applied to the case of a 2D double integrator system and tested in various situations. Because, Teddy explicitly takes into account information on the future behaviour of the obstacles, it is able to handle situations that are problematic for classical path deformation schemes.

In the future, it is planned to consider other robotic systems, eg differential drive/car-like vehicles, and to further optimize Teddy. Considering for instance that the knowledge about the future behaviour is less reliable in the distant future, it could be interesting to monotonically decrease the influence of the obstacles with respect to time. Last but not least, Teddy remains to be integrated within a global navigation architecture and tested on an actual robotic system. It is planned to do so on the architecture and the vehicle presented in [START_REF] Chen | A real-time autonomous navigation architecture[END_REF].

Thierry Fraichard does research on motion autonomy for vehicles with a special emphasis on safe navigation, motion planning (for nonholonomic systems in dynamic environments and in the presence of uncertainty), prediction of the future motion of moving objects, and the design of control architectures for autonomous vehicles.

Figure 2 :

 2 Figure 2: Teddy's principle visualized in a scenario involving three moving disk obstacles B i , i=1-3. The time dimension is pointing upward. The past lies below the xy-plane (the present) and the future lies above. The obstacles are moving randomly but the model of the future assumes that they maintain a constant linear velocity. The internal and external forces acting upon the nodes of the trajectory Γ k are represented by vectors.

Figure 3 :

 3 Figure 3: "Cutting" scenario (spatial deformation): A is moving from the left to the right, the obstacle is moving downwards. The top snapshots depict the path at different time instant (x × y view). The bottom snapshots depict the velocity profile at the same instants (x × t view).

Figure 4 :

 4 Figure 4: "Cutting" scenario (temporal deformation): A is moving from the left to the right, the obstacle is moving downwards. The top snapshots depict the path at different time instant (x × y view). The bottom snapshots depict the velocity profile at the same instants (x × t view).

  (a) space view, t = 0 (b) space view, t = 10 (c) space view, t = 20

Figure 5 :

 5 Figure 5: Multi-disk scenario (spatial deformation): A is moving from the bottom-left corner to the top-right corner.

  Figure 6: Multi-disk scenario (temporal deformation): A is moving from the bottom-left corner to the top-right corner.

Figure 7 :

 7 Figure 7: Multi-disk scenario (spatio-temporal deformation): A is moving from the bottom-left corner to the top-right corner.

Figure 8 :

 8 Figure 8: Maze scenario (spatio-temporal deformation): A is moving from the left to right among fixed polygonal obstacles and moving disks.

  He received a Ph.D ('92) and the Habilitation à Diriger des Recherches ('06) in Computer Science from the Institut National Polytechnique de Grenoble (INPG), France. Dr. Fraichard holds an Inria Research Associate position at the Inria Rhône-Alpes Research Center located near Grenoble. He is currently a Visiting Professor in the Autonomous Systems Lab. of the Swiss Federal Institute of Technology in Zurich, Switzerland. Vivien Delsart is currently a Ph.D student at INPG. He received a Master Degree ('07) in Computer Science from INPG for his work on trajectory deformation.

Acknowledgements

This work has been supported by the French Ministry of Defence (DGA Doctoral Grant) and by the European Commission contracts "Cybercars-2 FP6- IST-2004-028062" and "Have-It FP7-IST-2007-212154".

Contact address:

Thierry Fraichard INRIA Grenoble -Rhône-Alpes e-mail: thierry.fraichard@inria.fr