V Padois
email: vpadois@enit.fr

J-Y Fourquet
email: fourquet@enit.fr

P Chiron
email: pchiron@enit.fr

A Mauratille

Reactive Behavior and dynamic sequencing for nonholonomic mobile manipulators

This work is devoted to planning and execution of complex missions in Robotics. It is organized around a complex mission: "Go around obstacles to the blackboard and write" for mobile manipulators that have capabilities of locomotion and manipulation. It is a simple and intuitive example of a complex mission that relies on different sensors, exhibits different operating modes and needs to switch between different feedbacks and set-points. It is focused on dynamical sequencing of control laws that ensures good transients, robustness and allows to update the mission at every transition from one mode to another. Simulation have been realized with matlab Simulink and Stateflow toolboxes and experimental validation has been developed within the G en om controller on the h 2 bis nonholonomic mobile manipulator.

I. Introduction

For many years, research community in robotics has proposed numerous solutions allowing manipulators and, more recently, mobile manipulators to solve specific tasks. In the literature, contributions concerning the motion in free space of the end-effector, whose location is denoted ξ, are clearly separated from the ones dealing with constrained motion for which contact force f is imposed together with ξ. In the first ones, it is assumed that no contact force can occur whereas the second category considers that the contact is realized from the beginning. Regarding manipulators, many modeling issues -at dynamic and kinematic level -and related control schemes can be found in reference textbooks [START_REF] Spong | Robot Dynamics and Control[END_REF], [START_REF] Sciavicco | Modelling and control of robot manipulators[END_REF], [START_REF] Khalil | Modeling, Identification and Control of Robots[END_REF]. Methods and models have also been proposed to deal with the control of mobile manipulators. Modeling issues can be found in [START_REF] Bayle | Kinematic modelling of wheeled mobile manipulators[END_REF], [START_REF] Campion | Structural Properties and Classification of Kinematic and Dynamic Models of Wheeled Mobile Robots[END_REF] and control issues are exposed in [START_REF] Umeda | Hybrid position/force control of a mobile manipulator based on cooperative task sharing[END_REF], [START_REF] Yamamoto | Control and coordination of locomotion and manipulation of a wheeled mobile manipulator[END_REF].

Thus, the approach generally adopted when considering a complex problem is to decompose it in a sequence of elementary subproblems, and then to solve independently each subproblem. This approach has the merit to permit the study of each step of the sequence in a simple way since it disregards the other steps. It is particularly suited when the environment can be adapted to the task and when this task is repetitive enough to deserve ad hoc tuning. These features are usual in an industrial framework that requires a low versatility of the robotic system. Now, new directions, both in service and manufacturing robotics, lead to embed these techniques in missions where uncertainty and variability are much more important. Wheeled locomotion, for instance, naturally produces positioning uncertainty. Environment is less calibrated and tasks are less repetitive. At the same time, it seems pertinent to build the solution from the library of classical methods by chaining them dynamically. So, it is necessary to adapt and combine existing strategies for local tasks in order to realize complex missions with good transients.

Even if the objectives of our work are more general, the work presented here is sufficiently rich to point out problems and features of a more generic complex mission in robotics. It is organized around one kind of mission: From an imposed end-effector location, a free space endeffector motion among obstacles is followed by a trajectory tracking over a surface along which a normal force is imposed, and around one kind of system: A nonholonomic mobile manipulator, kinematically redundant, built from a serial arm mounted on a wheeled mobile platform. This system is equipped with a force sensor that measures contact forces at the end-effector.

At the end of the paper, simulation illustrates how the same approach allow to follow a real-time interactively imposed end-effector motion.

We made the choice of a description based on the Hybrid Dynamical Systems formalism where switchings among a finite number of modes occur when particular events are detected. Modes are linked to different setpoints and control laws. The emphasis is made on the dynamical nature of the sequence of elementary modes and more particularly on the contact transition problem (i. e. transition from free space to constrained effector motion). This issue has been emphasized very early for manipulators [START_REF] Paul | Problems and research issues associated with the hybrid control of force and displacement[END_REF] but only a little number of authors has actually studied it (e. g. [START_REF] Mills | of robotic manipulators during general tasks execution: A discontinuous control approach[END_REF], [START_REF] Hyde | Controlling Contact Transition[END_REF], [START_REF] Walker | Impact configurations and measures for kinematically redundant and multiple armed robot systems[END_REF]). These works mainly deal with stability issues and impact modeling. Recently, Yu and Pagilla [START_REF] Yu | A Switching Control Scheme for Constrained Robot Tasks[END_REF] have presented a method that allows to cope with geometric uncertainties of the contact surface location. Doh et al. [START_REF] Doh | On hard contact force control[END_REF] have also proposed a specific control law that aims at avoiding large bounces during hard contact transitions. With regard to mobile manipulators, the contact transition problem is an emerging field of research that has not been extensively studied yet. Nonetheless, one can refer to the work of Nagatani et al. [START_REF] Nagatani | Door-opening behaviour of an autonomous mobile manipulator by sequence of action primitives[END_REF] focused on static chaining of primitives ("Open the door") but also to the work of Kang et al. [START_REF] Kang | Utilization of inertial effect in damping-based posture control of mobile manipulator[END_REF] focused on the utilization of inertial effect when controlling holonomic mobile manipulators.

II. Structuring and planning the mission

In our approach a mission is described by:

• k modes or local tasks, • a switching pattern that describes the sequencing of the local tasks.

The switching pattern can be represented using a finite state machine. States corresponds to modes and transitions are activated by events: time elapsed or detection of a sensor threshold value. Using this formal description and the mission parameters, a first off-line planning step leads to "a perfect plan" that describes the ideal temporal evolution of the variables to control (i. e. the set-points or trajectories to track) and contains the calculated threshold values and time windows needed to define the transition conditions between modes. A state machine is then instantiated with these values. During the mission, this instantiated state machine creates indicators used to switch between the different phases of the plan and among a set of control schemes. At each transition, the "perfect plan" is updated thanks to the different signals and values of the variables describing the mission (e. g. the relative situation of the end-effector in the environment frame is updated at contact time).

This update allows to cope with uncertainties due to poor parameter estimations of both the robot (drift of the platform, sensors resolution) and the environment. Thus, transition from a task to the following one occurs asynchronously but in a predictable time (or space) interval. Any large drift in the transition date or in the value of a controlled variable corresponds to an anomaly that cannot be interpreted as the result of these uncertainties and leads to a premature stop of the mission.

III. Modeling of a mobile manipulator

We consider the case of mobile manipulator composed of a mobile platform with two independent driving wheels and a serial manipulator with n b joints. Such a system is depicted on figure 2 in a planar version or on figure 1 in a 3-dimensional version. This latter is the one used for the experiments. It has velocity controlled joints with high ratio gear reduction (i. e. the torque at each joints cannot directly be controlled) and so needs to rely on kinematic control schemes. Thus, we hereafter present some kinematics modeling results regarding mobile manipulators based on Bayle et al. work [START_REF] Bayle | Kinematic modelling of wheeled mobile manipulators[END_REF], [START_REF] Bayle | Manipulability of wheeled mobile manipulation: application to motion generation[END_REF]. We also shortly introduce the inertia matrix of this kind of mobile manipulator. Indeed, we later show that a rough estimation of the parameters of this matrix can be useful for a better control of the robot during transition from free space to contact.

A. Mobile manipulator kinematics

The configuration of such a mobile manipulator is completely defined using vector q = [ q b q p ] T where q b = [ q b1 . . . q bn b ] T and q p = [ θ r θ l x Op y Op ϑ ] T respectively represents the manipulator configuration and the platform configuration. Its end-effector situation (i. e. situation of R EE = (O EE , x EE , y EE , z EE ) in R = (O, x, y, z)) can be described using a minimal set of parameters ξ = [ ξ 1 . . . ξ m ] T . ξ is expressed as a non linear function of q. Differentiating it, the relation between ξ and q is given by: ξ = J(q) q with J(q) a m × n matrix and n = n b + 5.

(1) In addition, the components of q are constrained by the nonholonomy of the platform (i. e. the wheels can not slip). Then, one can define a vector u = [ u b u p ] of independent parameters (i. e. taking the nonholonomic constraints into account) such as:

q = T (q)u. (2)
Defining J(q) as:

J(q) = J(q)T (q), (3)
equation ( 1) becomes :

ξ = J(q)u. (4)
Equation ( 4) completely describes the mobile manipulator kinematics. This model is called instantaneous posture kinematic model in [START_REF] Bayle | Modélisation et commande cinématiques des manipulateurs mobiles à roues[END_REF]. A natural choice for u ∈ R

n (n = n b + 2) is u b = q b and
u p can be chosen as [ θr θl ] T or [ v ω] T . v and ω are respectively the linear and angular velocities of the platform and when no slipping actually occurs, one can verify that:

θr θl = -1 r -b r 1 r -b r v ω . (5)
When m < n, the mobile manipulator is said to be kinematically redundant. This property provides the capability to choose a particular kinematic control vector u among those giving the prescribed end-effector velocity ξ by using the relation:

u = J(q) ξ + (I -J(q) J(q))z, (6)
where J(q) is any generalized inverse of J(q) and z any n × 1 vector.

Access to the kinematic redundancy of the system is given by the second right-hand term of equation ( 6) also called the internal motion control term since it does not provide any end-effector motion.

Remark 1: A particular set of generalized inverse of J(q) is called generalized pseudo-inverses. When m ≤ n and rank(J(q)) = m, these generalized inverse are defined as:

J(q) = M -1 x J(q) T [J(q)M -1 x J(q) T ] -1 , (7)
where M x ∈ R n×n is a positive definite symmetric matrix. Replacing J(q) by J(q) in ( 6) leads to the solution minimizing the M x -weighted euclidean norm of (u -z). For M x = I, J(q) is called the pseudo-inverse or right inverse of matrix J(q). It is usually denoted J(q) + . Detailed results and proofs regarding generalized inversion are presented in [START_REF] Doty | A theory of generalized inverses applied to Robotics[END_REF].

B. Mobile manipulator inertia

Using Lagrange's technique to derive the dynamic model of the mobile manipulator and choosing u p = [ θr θl ] T as control vector for the platform, we obtain an inertia matrix with the following structure:

A(q b ) = A p + A bp (q b ) A b/p (q b ) A p/b (q b ) A b (q b ) , (8)
where:

• A p is the platform inertia matrix which is independent of its configuration, • A b (q b ) is the manipulator inertia matrix, • A bp (q b ) is a coupling term due to the influence of the arm on the inertia of the platform, • and A b/p (q b ) and A p/b (q b ) are the coupling terms representing the influence of each subsystem motion on the other. Yamamoto has shown in [START_REF] Yamamoto | Control and coordination of locomotion and manipulation of a wheeled mobile manipulator[END_REF], using simulations, the prevalence of the effect of the platform motion on the manipulator.

C. Operational kinematic control

Operational kinematic control uses a two stages control structure. The first stage is at the actuator level. Each actuator has its own velocity control loop. In our case, these controllers are digital PID regulators. The second stage is at end-effector level. Given ξ * and ξ * desired endeffector speed and situation to track, and a positive definite weighting matrix W reg , the control vector defined by:

u = J(q) ( ξ * + W reg (ξ * -ξ)) + (I -J(q) J(q))z, (9)
ensures an asymptotic decreasing of e = ξ * -ξ toward 0.

In order to take advantage of the kinematic redundancy of the system, we can determine z such as to minimize a scalar function P(q), also called potential function. The "steepest descent" local optimization method consists in choosing q such as:

q + W grad ∇P(q) = 0, (10)
where W grad ∈ R n×n is a positive definite weighting matrix and ∇P(q) is the gradient of P(q). This choice ensures an evolution of the system configuration tending to locally minimize P(q). However, q components have to be independent which is not the case for a mobile manipulator. Thus, one have to adapt this method as done in [START_REF] Bayle | Modélisation et commande cinématiques des manipulateurs mobiles à roues[END_REF]. This adaptation leads to choose z as:

z = -T (q) + W grad ∇P(q). (11)

D. Hybrid speed / force controller

The hybrid speed / force controller is a modified version of the well known work presented in [START_REF] Raibert | Hybrid position/force control of manipulators[END_REF].

Once the contact established, the robot's end-effector cannot independently exert a displacement and a force in the same direction. One has to choose the direction to be position or speed controlled and the direction to be force controlled. n c being the unit vector normal to the environment surface at contact point, a smart choice fort the reference frame R is x = -n c . Thus, one can create a m × m diagonal selection matrix S where ones or zeros are placed on the diagonal respectively to indicate whether the component of ξ corresponding to the line in S is speed or force controlled. The control vector is then calculated as the sum of three terms:

u = u s + u f + u r , (12)
with:

u s = J(q) S ξs , (13)

u f = J(q) (I -S) ξf , (14)
u r = (I -J(q) J(q))z.

(

) 15
ξs and ξf are the control vectors whose simple versions are given by:

ξs = ξ * + W regs (ξ * -ξ), (16)
and:

ξf = W reg f (f * -f ), ( 17
)
where W regs and W reg f are two positive definite weighting matrices.

E. Use of redundancy

We expose here a set of functions to optimize using the internal motion. Many other functions may be used but these ones seem to be relevant according to the considered mission.

1) Manipulability maximization:

The manipulability notion was first introduced for manipulators (cf. [START_REF] Yoshikawa | Foundations of robotics -Analysis and Control[END_REF] for a detailed presentation of this notion) but was also extended to mobile manipulators in [START_REF] Bayle | Manipulability of wheeled mobile manipulation: application to motion generation[END_REF]. The different manipulability measures are quantitative indicators representing the ease to instantly move the end-effector in any direction. Maximizing any of these indicators tends to avoid singular configuration of the system and thus to avoid high joints speed.

2) Impact force reduction: During the transition tasks, it is interesting to re-configure the mobile manipulator using internal motion so as to give it good inertial properties. Results concerning holonomic mobile manipulators are presented in [START_REF] Kang | Utilization of inertial effect in damping-based posture control of mobile manipulator[END_REF]. The notion of impulse force F is used in [START_REF] Walker | Impact configurations and measures for kinematically redundant and multiple armed robot systems[END_REF] and is defined as:

F = lim ∆t→0 t+∆t t f (s)ds, ( 18
)
where t is the impact time. Using the dynamic model of the system (i. e. the model establishing the relation between physical effects of motion, actuating torques and contact forces at end-effector level), the magnitude F of F is expressed as:

F = -(1 + e)v T impact n c n T c C(q)n c . (19)
v T impact is defined as the linear speed of the end-effector at the impact time, e is the restitution coefficient (i. e. a physical characteristic of the contact). Using equation [START_REF] Kang | Utilization of inertial effect in damping-based posture control of mobile manipulator[END_REF], one can define the pseudo-inertia matrix of the system as:

Λ(q) = J(q)A(q b ) -1 J(q) T -1 . ( 20
)
Fig. 3. Writing on a board with a mobile manipulator Λ(q) represents the part of the system inertia having effects on the end-effector motion. C(q) is a matrix extracted from Λ(q) -1 that corresponds to linear acceleration terms in Λ(q) -1 .

To minimize F , one can:

• plan a low impact speed but uncertainties in the plan execution lead to higher values of impact speed than the planned one, • maximize, using internal motion, n T c C(q)n c which is configuration dependent. It directly acts on the inertial properties of the manipulator.

3) Collision avoidance:

Techniques to avoid obstacles have extensively been studied in the case of mobile robots. However, the problem to solve here depends on the nature of the task to perform. Is the goal to follow an obstacle (like during a writing task on the wall) or to go around an obstacle (like in free space end-effector motion). Different potential functions have been defined depending on what kind of collision avoidance is expected.

IV. Experimental system and simulation results

The "go to the blackboard and write" mission has been validated on the experimental mobile manipulator (see 3) and impact reduction has been shown experimentally.

In this paper, the focus is more on simulation results. In simulation, this mission has been realized in a robust manner with obstacles. Also, a joystick demo has been realized that allow for real-time setpoint generation. We hereafter detail the experimental and simulation frameworks and we then present some results obtained using the simulator.

A. Experimental framework

The mobile platform is actuated using two independent driving wheels (i. e. an HILARE type platform). The manipulator is a 6R serial arm called GT6A. The whole system is controlled using on board calculators equipped with the real time operating system VxWorks system and running on Motorola 68000 and Apple Power PC cards.

Localization devices such as ultrasonic sensors, a telemeter and a black and white camera are present on the system. Of course, we could use those sensors. However uncertainty associated to the kind of mission we study would still be present. So, to clearly delimit the framework of this study, we chose to rely only on the platform's odometer system, the manipulator's incremental coders and a 6-axis GIROBO force / torque sensor.

Control algorithms are implemented using G en om, a generator of software control modules developed, as well as the robot, in the RIA team of the LAAS laboratory. At actuator level, the control sampling time is 5ms (the smaller one admitted by the control modules) whereas at operational level we chose it to be either 10 or 20ms. Force sensor bandwidth is 100Hz.

B. Simulation framework

The simulator has been developed using Matlab and Simulink.

1) Robot: The robot is modeled at kinematic and dynamic level as a continuous system. Actuators (dc motors) are modeled as second order linear systems and we take into account load torques due to dynamic effects of motion or due to contact. We also take into account saturations of the actuators.

2) Sensors: Only the noise and inaccuracy of the force sensor are modeled. Force signal is sampled with a period of 10ms to reflect the effects of its limited bandwidth.

3) Contact: Contact between the end-effector and the environment is locally modeled either as a {spring // damper} system (i. e. Kelvin-Voigt visco-elastic model) or as a spring system. When running simulations, we consider that the values of the parameters characterizing the contact are unknown or poorly estimated.

4) Controllers:

Actuators' controllers are modeled as digital PID regulators whose sampling time is 5ms. The operational level controller is also implemented as a digital controller. We consider its sampling time as an off-line tunable parameter whose minimum value is 10ms.

C. Simulation results

System depicted on figure 2 is chosen for simulation. ξ is chosen as the end-effector position and u = [ θr θl qb1 qb2 ] T . The reference frame is attached to the blackboard whose surface is defined by equation x = 0. Thus, f is defined as the vector whose components are the normal and tangential force to the blackboard. Once the contact established, the normal direction is force controlled whereas the tangential direction is speed controlled. So, the selection matrix S is given by: S = 1 0 0 0 .

1) Simulation 1: go to the blackboard among obstacles and write: Here the end-effector motion is imposed and the mobile base has to avoid low obstacles reactively. There is only a local information about the location and number of obstacles. The dynamic sequencing scheme switchs automatically between indices : manipulability, obstacle avoidance, inertia, ... The imposed end-effector motion is made of the two blue straight lines and the path of the middle of the rear axle of the mobile base is depicted in red.

2) Simulation 2: interactive joystick : Here, the control scheme is used interactively since the end-effector velocity is imposed in real time. Again, the real-time imposed endeffector motion is in blue whereas the path of the middle of the rear axle of the mobile base is depicted in red. This simulation shows the robustness of the control scheme and the ability to realize totally reactive behaviour with a nonholonomic mobile manipulator. In particular, cusps or manoeuvers are automatically generated.

V. Conclusion

The aim of this study was to propose a method to obtain dynamic task sequencing for nonholonomic mobile manipulators. The method is based on the decomposition of complex mission in elementary tasks to sequence. A particular attention is paid to transition phases. A simulator, taking into account the physical system's constraints, was developed and allows to test different control structures and schemes. The obtained results show the efficiency of the proposed method. In particular, a smart use of the kinematic redundancy of the system allows to correctly control the contact transition phase. The principle of the proposed approach was validated using simulation and has been confirmed experimentaly on robot H 2 bis.

Fig. 1 .

 1 Fig. 1. H 2 bis: a 3-dimensional mobile manipulator.

Fig. 2 .

 2 Fig. 2. A planar mobile manipulator.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Go to the blackboard among obstacles and write

Acknowledgment: This work is partially supported by the French CNRS Robea program within the project Dynamic sequencing of multi-sensor based tasks for complex motions execution in mobile robotics

LGP-ENIT is a partner of the Innovative Production Machines and Systems (I PROMS) Network of Excellence funded by the European Commission under the Sixth Framwork Programme (Contract n o FP6-2002-500273-2).


Mehdi Badr

Dan Vodislav

A general top-k algorithm for web data sources

Keywords: top-k queries, web data, multi-criteria information retrieval, ranking

Several algorithms for top-k query processing over web data sources have been proposed, where sources return relevance scores for some query predicate, aggregated through a composition function. They assume specific conditions for the type of source access (sorted and/or random) and for the access cost, and propose various heuristics for choosing the next source to probe, while generally trying to refine the score of the most promising candidate. We present BreadthRefine (BR), a generic top-k algorithm, working for any combination of source access types and any cost settings. It proposes a new heuristic strategy, based on refining all the current top-k candidates, not only the best one. We present a rich panel of experiments comparing BR with state-of-the art algorithms and show that BR adapts to the specific settings of these algorithms, with lower cost.

Introduction

Data retrieval applications accorded an increasing importance these last years to ranked queries, compared to traditional boolean queries. This is, to a large extent, the consequence of the great development of web applications integrating huge volumes of heterogeneous and multimedia data: text, images, video, maps, etc. On one hand, this introduced the need for fuzzy, approximate answers, ranked by relevance, when querying such large and heterogeneous amount of data, on the other hand the new web data types came with intrinsic ranked predicates: text and image similarity, location proximity, user preferences, etc.

In this context, we address the problem of processing top-k queries over a set of web sources. A query is expressed through a set of ranked predicates over a common set of data objects. Each predicate is independently evaluated by some web source and returns a relevance score for any input object. A monotone aggregation function combines partial scores from each predicate into the final object score relative to the query. The query returns objects having the k best global scores.

Consider the example of a tourist in Paris, looking for buildings constructed around 1750, near to his current location and similar to the one he just photographed. Objects are here the buildings in Paris and the query consists of three ranked predicates: p 1 : proximity of the construction date, p 2 : spatial proximity to the current location, and p 3 : similarity with a given picture.

In SQL-like syntax, e.g. the one proposed by RankSQL [START_REF] Li | Ranksql: Query algebra and optimization for relational top-k queries[END_REF], this query could be expressed such as in Figure 1, if we consider k = 5 and a simple aggregation function based on the sum of the individual scores.

The sources that evaluate the predicates could be, for instance:

The original publication is available at www.springerlink.com select * from Building b order by proximity(b.year, 1750) + closeness(b.address, here()) + similarity(b.image, myImage) limit 5 ; S1 (S-source) S2 (SR-source) S3 (R-source) (o2, 0.4) (o3, 0.9) (o1, 0.9) (o1, 0.3) (o1, 0.2) (o2, 0.7) (o4, 0.25) (o4, 0.15) (o3, 0.8) (o3, 0.2) (o2, 0.1) (o4, 0.6) Fig. 1. Example query and sources -S 1 : a database server storing historical information about buildings (for p 1 ); -S 2 : a geographic/map service (for p 2 ); -S 3 : an image database indexing fronts of buildings in Paris (for p 3 ). Note that the ranking predicates are dependent on the query, for instance, even if S 2 always evaluates spatial proximity between an object and a reference point, this point depends on the query.

To execute such a query, one must access the web sources to get partial scores for objects. The access to the web sources during query processing has the following main properties:

-Access is limited to operations allowed by the web source interface and there is no control on the inside mechanisms. Generally, a web source may allow two kinds of access: sorted, where each access returns the next score/object in decreasing order, and/or random, where each access returns the score of a given object. We call S-sources sources with sorted access only, R-sources those with random access only, and SR-sources those with both accesses. -Accessing web sources is expensive, the cost of accessing sources dominates the cost of the other algorithm operations.

The naive approach would be to get all the partial scores for all the objects, then to compute their global scores, to order them by descending score and get the first k results. In practice, this method is very expensive and many efficient algorithms have been proposed for various cases of access types and cost settings.

Some algorithms, such as NRA [START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF] and StreamCombine [START_REF] Güntzer | Towards efficient multi-feature queries in heterogeneous environments[END_REF] consider only S-sources, while algorithms such as TA [START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF], CA [START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF] and QuickCombine [START_REF] Güntzer | Optimizing multi-feature queries for image databases[END_REF] consider only SR-sources. A third category considers specific heterogeneous access configurations, e.g. one S-source and several R-sources for Upper [START_REF] Bruno | Evaluating top-k queries over web-accessible databases[END_REF] and MPro [START_REF] Chang | Minimal probing: supporting expensive predicates for top-k queries[END_REF], or several SR-sources and several R-sources for some extensions of TA and Upper. The NC framework [START_REF] Hwang | Optimizing top-k queries for middleware access: A unified cost-based approach[END_REF] is the only approach that addresses any combination of access types. All these algorithms are further detailed in the related work section.

Cost settings considered by these algorithms fall generally into two categories: (i) no difference between the cost of sorted and random accesses (NRA, StreamCombine, TA, Quick-Combine), and (ii) random more expensive than sorted access (CA, Upper, MPro). However, other cost settings are possible, e.g. sorted more expensive than random access. Consider for instance the case of a source evaluating image similarity by using an index on disk for sorted access, but keeps image descriptors in memory; random access requires here no disk access and is faster than sorted access. Again, NC is the only attempt to adapt to any cost settings.

The general idea behind all these top-k algorithms is to maintain a list of candidate objects and the interval [L, U ] of possible global scores for each of them. At the beginning, the interval is obtained by aggregating the minimum / maximum source scores. Monotonicity of the aggregation function ensures that further source accesses will refine these intervals, by decreasing the upper bound U and increasing the lower bound L. The algorithm stops when the score of the best k candidates cannot be exceeded by the other objects.

We illustrate the behavior of such an algorithm through the example in Figure 1. Suppose S 1 is a S-source, S 2 a SR-source, S 3 a R-source; scores are presented in descending order for S/SR sources and by object id for R-sources. Individual predicate scores belong to the [0, 1] interval, so the initial global score interval is [0, 3] for all objects. Note that we consider algorithms without wild guesses, i.e. objects are not known in advance, they are 'discovered' by sorted accesses. We note candidates the set of candidates and U unseen the maximum score of objects not yet discovered. Initially, candidates = ∅ and U unseen = 3.

- Execution may continue depending on the value of k, but notice that top-k objects could be returned without knowing their exact scores and order. Most of the existing algorithms return exact scores for top-k and are iterative, i.e. return first top-1, then top-2, etc. However, in many applications the exact global score is not needed (e.g. image retrieval), but only the top-k objects with approximate ordering.

A
The difference between the top-k algorithms mentioned above consists in the heuristics proposed for the choice of the next source to probe and of the candidate to refine through random accesses. Note that all the algorithms that must select a candidate to further refine focus on the current "best" candidate.

Our goal is to propose a new generic top-k algorithm that works for any combination of source access types and cost settings, and returns the set of top-k objects, possibly without complete scoring information. This algorithm uses a new heuristic approach, that refines on all the top-k candidates, instead of favoring only the best current candidate.

The contributions of this paper may be resumed as follows: -We present BreadthRefine (BR), a new, generic top-k algorithm, able to adapt to any combination of source access types and to any cost settings. To the best of our knowledge, excepting NC [START_REF] Hwang | Optimizing top-k queries for middleware access: A unified cost-based approach[END_REF], this is the first generic top-k algorithm for web sources. Unlike NC, that mixes heuristics and sampling optimization, our algorithm is only based on a simple heuristics. -We propose a new heuristic approach, that do not focus only on the best current candidate, but considers all the top-k candidates. Our experiments show that this heuristics produces better results than the usual approach. -We report a rich experimental evaluation comparing BR to existing algorithms for various source types and cost settings, and show that BR is less expensive.

The rest of the paper is organized as follows: the next section presents related work, then Section 3 describes the BR algorithm, Section 4 reports the experiments comparing BR to existing algorithms, then we end with conclusions and future work.

Related work

Top-k query processing techniques have been largely studied in the last decade at different levels: query model, access types, implementation structures, integration in database engines [START_REF] Li | Ranksql: Query algebra and optimization for relational top-k queries[END_REF][7] [START_REF] Li | Supporting ad-hoc ranking aggregates[END_REF], etc. The survey [START_REF] Ilyas | A survey of top-k query processing techniques in relational database systems[END_REF] presents a rich overview of these various approaches. In this context, we address the problem of selection queries (no joins), for web sources with any configuration of access types and any cost settings. We do not compare with algorithms having additional information about objects in sources, e.g. the rank in BPA [START_REF] Akbarinia | Best position algorithms for top-k queries[END_REF]. Join queries are addressed e.g. by the J* [START_REF] Natsev | Supporting incremental join queries on ranked inputs[END_REF] or the Rank-Join [START_REF] Ilyas | Supporting top-k join queries in relational databases[END_REF] algorithms.

Algorithms for top-k selection queries proposed so far focus on specific access types and cost settings for the sources. They fit with the general method illustrated in the example of Section 1, i.e. maintaining a list of candidates with global score interval and accessing sources following their own heuristics.

Among the algorithms that consider only S-sources, the best known is NRA (No Random Access) [START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF]. NRA consults sources following a simple round-robin strategy, with no specific order. Such as for BR, final results may have incomplete scoring information. Efficient NRA implementations such as LARA [START_REF] Mamoulis | Efficient aggregation of ranked inputs[END_REF] that reduce the overhead of candidate updates are not relevant in our context, since we ignore this overhead compared to the access time to web sources. StreamCombine [START_REF] Güntzer | Towards efficient multi-feature queries in heterogeneous environments[END_REF] is a variant of NRA that selects at each step the next source to probe following the benefit that the source may provide. Benefit considers three factors: (i) the importance of the source in the global score (e.g. the coefficient in the aggregation function, for a weighted sum), (ii) the decrease of the source score (bigger decreases favor faster algorithm termination), and (iii) the number of candidates in the current top-k not yet seen in the source and that will consequently lower their upper bound. We adopt in BR a similar notion of benefit for sorted sources.

Algorithms that consider only SR-sources adopt a different approach: the global score of a candidate discovered through a sorted access is completely evaluated through random probes of the other sources. The consequence is that candidates have exact scores, not intervals, so there is no need to maintain a list of candidates. The termination test simply compares the score of the k-th candidate with the threshold U unseen .

TA (Threshold Algorithm) [START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF], the best known SR-source algorithm, consults sources in a way similar to NRA, following a round-robin strategy. QuickCombine [START_REF] Güntzer | Optimizing multi-feature queries for image databases[END_REF] is a variant of TA that uses the same idea as StreamCombine to select the next sorted source to probe. The benefit considers only the two first factors presented above for StreamCombine, the last one being not relevant. CA (Combined Algorithm) [START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF] is a variant of TA that considers random accesses being h times more expensive than sorted ones. It combines NRA with TA to reduce the number of random accesses by performing h sorted accesses in each source before a complete evaluation of the best candidate by random probes. We adopt in BR a similar idea for taking into account the possible difference between random and sorted costs. Many other extensions of TA have been proposed, such as TAz [START_REF] Bruno | Evaluating top-k queries over web-accessible databases[END_REF], which considers an additional set of R-sources. TAz acts as TA for the sorted accesses, but includes the R-sources in the random probe phase.

Algorithms with sorted access and controlled random probes, such as Upper [START_REF] Bruno | Evaluating top-k queries over web-accessible databases[END_REF] and MPro [START_REF] Chang | Minimal probing: supporting expensive predicates for top-k queries[END_REF], typically consider one S-source and several R-sources. The random cost exceeds the sorted cost, but is different from one R-source to another. Both Upper and MPro consider complete scoring of the final top-k result.

Upper maintains candidates following an estimated score. At each step, it considers candidate o with the highest upper score U : if U < U unseen a sorted access is performed in order to reduce U unseen , otherwise a random probe for o is done. A benefit is computed for each R-source and the best source is selected for the random probe. Two cases are considered. If o belongs to the current top-k, the benefit is the ratio between the expected decrease δ of U and the access cost. Otherwise, o has more chances to be out of the top-k and one computes the decrease ∆ of U necessary to prove that o is not a top-k object. The source benefit in this case is the ratio between min(δ, ∆) and the access cost. An extension of Upper for several SR-sources and several R-sources is presented in [START_REF] Marian | Evaluating top-k queries over web-accessible databases[END_REF] -in this case sorted access is performed in NRA manner over the SR-sources, while random access considers all the SR/R-sources not yet probed.

Like Upper, MPro considers at each step the candidate with the highest upper score and performs a random probe for it or a sorted access if U unseen is higher. But unlike Upper, MPro fixes for all the candidates the same order (schedule) for probing the R-sources. The best schedule may be determined by various methods, such as sampling optimization, proposed by the authors.

The only algorithm that aims at genericity is NC (Necessary Choices) [START_REF] Hwang | Optimizing top-k queries for middleware access: A unified cost-based approach[END_REF], an extension of MPro. Like BR, NC is generic and adapts to any source access type and cost settings. NC identifies necessary choices (i.e. accesses that are necessary at a given execution state to obtain the final result) as belonging to accesses for the current top-k upper bound candidates. NC proposes an algorithm framework that performs only necessary accesses and defines an algorithm called SR/G in this framework that computes for each S/SR-source a limit score. SR/G gives priority to sorted accesses in sources that did not reach the limit score. More precisely, the algorithm considers at each step the candidate with the highest upper score and chooses a sorted access for it, if possible (i.e. in a sorted source that did not return the object, nor reach its limit). If not possible, a random probe is selected following a fixed schedule, like for MPro. Limit scores are determined by sampling optimization and simulation.

Compared to NC, BR addresses a slightly different problem, by computing top-k objects possibly without complete scoring. Therefore necessary choices in the NC context are not relevant for BR. We do not compare in this paper BR with NC because, source sampling being not always possible, we only focus on fully heuristic-based top-k algorithms. Even if NC authors claim that sampling may replaced by estimation of the source limits, our tests indicate that NC is very sensible to the quality of this estimation. One should first define good limit estimation heuristics for NC, which is out of the scope of this paper.

The BreadthRefine algorithm

Unlike top-k algorithms presented in Section 2, the BreadthRefine (BR) algorithm covers any configuration of source access types and cost settings and proposes a new heuristic approach: refining the scores of all the top-k candidates, instead of focusing on the best one. We first present the BR data and query model, then the general BR algorithmic framework and several algorithm variants in this framework.

Data and query model

We consider a set of data objects O = {o 1 , ..., o n }, a top-k multicriteria query q over these objects, and a set of web sources S = {S 1 , ..., S m } able to evaluate the query criteria. Definition 1. Query: A top-k multi-criteria query q is defined by (i) a number of objects k to return, (ii) a set of ranked predicates (criteria) P q = {p 1 , ..., p m }, depending on the query, and (iii) a monotone score aggregation function F.

Predicates p j : O → [min j , max j ] return for any object a score in a given interval, while function F : R m → R aggregates predicate scores into a global object score. Each predicate p j is independently evaluated by source S j . Definition 2. Source: A source S j is characterized by (i) its access type (S, R or SR), and (ii) a cost per access, noted C s (S j ) for sorted and C r (S j ) for random access. The minimum and maximum scores in S j are noted min j and max j , as mentioned in Definition 1.

The set of sources S can be partitioned following the access type in three disjoint subsets, possibly empty: S = S S ∪ S R ∪ S SR .

A sorted source (of type S or SR) provides an access function getNext : S S ∪ S SR → O × R ∪ {nil} returning the next couple (o, s), where o is the object with the next score in decreasing order and s its score (if exists), or the special value nil otherwise.

A random source (of type R or SR) provides an access function getScore:(S R ∪ S SR ) × O → R returning the score of the given object in the source.

We note score(o, S j ) the score retrieved for object o in source S j . We note crtmax j the largest score that source S j could further return. For pure random sources S j ∈ S R , crtmax j = max j (constant). For sorted sources S j ∈ S S ∪ S SR , crtmax j is the score returned by the last sorted access to S j1 (initially crtmax j = max j ). L(c) = F(l 1 , ..., l m ), l j =score(c, S j ) if c consulted in S j , else l j = min j U (c) = F(u 1 , ..., u m ), u j =score(c, S j ) if c consulted in S j , else u j = crtmax j . We note L k (U k ) the k-th value in decreasing order for L(c) (U (c)) among the candidates -for less than k candidates, the value is nil.

A candidate is called viable if it still has chances to belong to the final top-k result. The viability condition for c is U (c) ≥ L k . It is simple to prove using monotonicity that once a candidate becomes non-viable, it will remain non-viable and could be removed.

We note U unseen the upper bound of the global score for any object that is not yet a candidate. Initially, U unseen = F(max 1 , ..., max m )

The BR algorithm framework The basic idea of the BR algorithm is to maintain the top-k candidates as a whole instead of looking only at the best candidate. Also, BR is able to handle any kind of source access; the choice of the access type is the central issue at each step.

Figure 2 presents the general BR framework, from which various algorithm variants may be instantiated. BR maintains a set of candidates, initially empty, and the maximum score of unseen objects, U unseen . At each step, BR first chooses the type of access to be performed. Sorted access is preferred in the following cases:

-A group of top-k candidates does not exist yet, i.e. if |candidates| < k.

-An unseen object could belong to the current upper bound top-k group, i.e. U k < U unseen .

A sorted access will decrease U unseen and eliminate unseen objects from the top-k group. -If the cost-related condition CostCondition is true. This condition enables BR to adapt to various cost settings, e.g. to force sorted accesses when random probes are expensive.

If a sorted access is decided, the BestSortedSource function chooses the best sorted source, then performs the sorted access2 . Consequently, the candidate set and U unseen are updated; the update of the candidate set consists in several actions:

-Add the object to the candidate set, if it is seen for the first time.

-Update the upper and lower bounds for all the candidates. In fact, besides the retrieved object, the update only affects the upper bound of candidates that have not been retrieved yet in the source. -Remove non-viable candidates.

In the case of a random access, the ChooseCandidate function chooses a candidate in the current top-k group. Then a random source is selected with BestRandomSource, among those not yet probed for the candidate. The source is probed and the candidate set is updated.

The algorithm ends when the candidate set is reduced to k objects (after removing nonviable candidates) and when the unseen objects cannot change anymore the final result (L k ≥ U unseen ). The result is the set of k candidates, with possibly incomplete scores.

BR algorithm variants By instantiating CostCondition, BestSortedSource, ChooseCandidate and BestRandomSource functions, one may obtain various BR algorithms. We present three variants: BR-Cost, BR-Basic and BR-First. BR-Cost is the reference BR algorithm that we propose. It refines the set of top-k candidates in a breadth-first manner and adapts to various cost settings. BR-Cost uses weighted sum aggregation function and employs source selection methods similar to existing algorithms.

-ChooseCandidate selects the least refined candidate (with the least random probes) from the current upper bound top-k group.

-CostCondition aims at reducing the number of random accesses (if more expensive than sorted ones), in a way similar to the CA algorithm. More precisely, if r is the average ratio between the cost of random and sorted accesses, then once a random probe is processed, the next one is possible only after at least r sorted accesses. -BestSortedSource selects the sorted source S j with respect to a benefit similar to the one proposed by StreamCombine [START_REF] Güntzer | Towards efficient multi-feature queries in heterogeneous environments[END_REF], i.e. B j = coef j N j δ j /C s (S j ), where coef j is the weight of S j in the aggregation function, N j the number of top-k candidates not yet seen in S j , δ j the expected decrease of the score in S j and C s (S j ) the access cost. Here N j measures the number of top-k objects that will be concerned by the decrease of the upper bound, and coef j and δ j the amount of this decrease. -BestRandomSource selects the random source with respect to a benefit B j = coef j × (crtmax j -min j )/C r (S j ). Here coef j and crtmax j -min j measure the variation of the candidate's upper/lower bound when the real score will replace the upper/lower source score.

BR-Basic is a variant of BR-Cost which does adapt to various cost settings, i.e. Cost-Condition systematically returns false. Comparing BR-Basic with BR-Cost will reveal the importance of cost adaptation.

BR-First is a variant of BR-Basic that uses the classical approach for choosing a candidate to refine, i.e. always select the best one -the highest upper bound in this case. Note that this is still a particular case of the general BR heuristics, the best candidate belonging to the top-k. Comparing BR-First with BR-Basic will measure the benefit of the new heuristics.

Experiments

In this section we report the experimental evaluation of the BR algorithms over synthetic data. We evaluate genericity and adaptivity by comparing BR with state of the art algorithms in their specific access type and cost configurations. We also measure the importance of the BR heuristics and of cost adaptivity by comparing the BR algorithms variants.

Data sets

We generate synthetic score lists for each source, each list representing the predicate scores for a given query, as values in the [0,1] interval. Sources are independent and have similar data distribution. The sorted access cost C s is the same for any source, idem for the random cost C r . We consider three variants of data distribution:

-Uniform: values are uniformly distributed.

-Gaussian: values are generated from three overlapping Gaussian bells.

-Zipfian: values are generated from a Zipf function with 1000 distinct values and Zipfian parameter z = 1.

Parameters and default settings All the experiments measure the execution cost, which is the cost of all the source accesses performed during execution. More precisely, if N s j (N r j ) is the number of sorted (random) accesses to source S j , then the cost of the algorithm is:

cost = Sj ∈S S ∪S SR N s j C s (S j ) + Sj ∈S R ∪S SR N r j C r (S j ) (1)
Each result is the average of 8 measures over different randomly generated data sources. We consider various parameters in the experiments:

-The number of objects: 10000 (default), 20000, 40000, 60000, 80000, 100000.

-The number k of returned objects: 20, 40, 50 (default), 60, 80, 100.

-The number of S-sources N s , of R-sources N r and of SR-sources N sr (default value for each one: 3). -The cost setting: C r (= 5) > C s (= 1) (default), C r = C s (= 1), C r (= 1) < C s (= 5) -Data distribution for all the sources: uniform (default), gaussian, zipfian.

Algorithms tested Experiments are grouped by source access type in three categories, in each case the set of algorithms adapted to this setting is considered:

-No R-sources: NRA and MPro.

-No S-sources: Upper, TAz and MPro.

-All the source types exist: MPro.

We adapted the MPro algorithm to cover all the cases as follows: sorted sources are combined with NRA to behave as a single S-source. SR-sources may be considered by MPro either as sorted or random, depending on the context: sorted when there are no S-sources, random when there are no R-sources. In the case of all the source types, we considered both settings (SR as sorted and SR as random) and reported the average cost. Also for random probes we considered a fully heuristic variant for MPro, in which scheduling uses the same order based on benefit as BR.

SR-sources + S-sources

We compare BR-Cost, BR-Basic and BR-First with NRA and MPro. We first vary k in two cases: C r > C s (default setting) and C r = C s . The case C r < C s is not favorable to NRA and is considered later for MPro.

Figure 3(a) presents results for C r > C s . Cost increases with k for all the algorithms, but BR-Cost is significantly less expensive than MPro and even than NRA, which does no random access. The importance of considering cost settings in BR is obvious when comparing BR-Cost with BR-Basic. Also the benefit of the BR heuristic is confirmed by BR-First which behaves worse than BR-Basic. Figure 3(b) considers the case C r = C s , where BR-Cost is the same as BR-Basic. BR-Basic/Cost is still the best, but the difference with BR-First and MPro decreases.

Next, we vary the number of objects for the default cost settings. Figure 3(c) shows that the cost increases almost proportionally for all the algorithms, so the above conclusions are unchanged.

Figure 3(d) illustrates the variation of data distribution. For uniform and gaussian distributions, BR-Cost is the best algorithm and BR-Basic outperforms BR-First. Zipfian distribution, with many identical values, is a special case, but BR-Cost still have good results. BR-Cost and NRA have almost the same cost, while differences between MPro and BR variants become insignificant.

Conclusion

In this paper we proposed BreadthRefine (BR), a generic top-k algorithm, able to adapt to any combination of source access types and to any cost settings. It adopts a new heuristic approach, by refining the scores of all the top-k candidates instead of focusing on the best one. Experiments on synthetic data clearly indicate that BR successfully adapts to various settings, with globally better execution cost than algorithms designed for that specific case. Comparison with the classical approach of favoring the best candidate shows that BR's breadth-first heuristics produces better results.

Future work will focus on the advantages of breadth-first heuristics in approximating the top-k final results.

Definition 3 .

 3 Candidates: A candidate in the algorithm is an object that has been already returned by a sorted access. For each candidate c, the algorithm maintains L(c) (U (c)), i.e. the lower (upper) bound of the global score for c. L(c) (U (c)) is computed by aggregating the scores of c in the sources where it has been already consulted, and the minimum (maximum) score in the other sources.

Fig. 3 .

 3 Fig. 3. SR + S-sources: varying k, the number of objects and the distribution

  (a) Cr > Cs (b) Cr = Cs

Fig. 4 .Fig. 5 .

 45 Fig. 4. SR + S-sources: varying |SR|/|S|

Fig. 6 .

 6 Fig. 6. SR + S + R-sources: varying k and the distribution

Figure 6 (

 6 Figure 6 (d) illustrates the impact of data distribution: BR-Cost remains globally the best, while BR-First is the worse BR variant. There is little difference between BR variants for gaussian distribution, while zipfian favors MPro compared to BR-Basic and BR-First.Figure7reports the impact of the number of objects for C r > C s (a) and C r < C s (b). In both cases, the cost augments almost proportionally for the BR variants and BR-Cost is always better than the other algorithms. We remark that MPro scales better than BR-Basic and BR-First when C r > C s and significantly worse when C r < C s , indicating that MPro makes slightly less random accesses, but much more sorted accesses than BR-Basic.

Figure 7

 7 Figure 6 (d) illustrates the impact of data distribution: BR-Cost remains globally the best, while BR-First is the worse BR variant. There is little difference between BR variants for gaussian distribution, while zipfian favors MPro compared to BR-Basic and BR-First.Figure7reports the impact of the number of objects for C r > C s (a) and C r < C s (b). In both cases, the cost augments almost proportionally for the BR variants and BR-Cost is always better than the other algorithms. We remark that MPro scales better than BR-Basic and BR-First when C r > C s and significantly worse when C r < C s , indicating that MPro makes slightly less random accesses, but much more sorted accesses than BR-Basic.

  (a) Cr > Cs (b) Cr < Cs

Fig. 7 .

 7 Fig. 7. SR + S + R-sources: varying the number of objects

  A sorted access to S 2 retrieves (o 1 , 0.2). This adds a new candidate (o 1 ), lowers U unseen to 1.6, but does not lower the maximal global score of the other candidates because o 2 and o 3 already know their S 2 scores. candidates={(o 2 , [0.5, 1.5]), (o 3 , [1.7, 2.1]), (o 1 , [0.2, 1.6])}. -The minimum global score of o 3 exceeds both U unseen (maximum global score of unseen objects) and the maximum global score of all the other candidates, we can conclude that o 3 is the best (top-1) object.

	sorted access to S 1 retrieves (o 2 , 0.4), so with one partial score known for o 2 its global
	score interval becomes [0.4, 2.4], i.e. candidates={(o 2 , [0.4, 2.4])}. Also U unseen becomes
	2.4 because further scores in S 1 cannot exceed 0.4.
	-A sorted access to S 2 retrieves (o 3 , 0.9). This adds a new candidate (o 3 ), lowers U unseen
	to 2.3 (because further S 2 scores cannot exceed 0.9), but also lowers the maximum global
	score of o 2 to 2.3, because the maximum score of S 2 is now 0.9. candidates={(o 2 , [0.4, 2.3]),
	(o 3 , [0.9, 2.3])}.
	-A random access to S 2 for o 2 retrieves (o 2 , 0.1). This changes only the global score interval
	of o 2 . candidates={(o 2 , [0.5, 1.5]), (o 3 , [0.9, 2.3])}.
	-A random access to S 3 for o 3 retrieves (o 3 , 0.8) and changes the global score interval of
	o 3 . candidates={(o 2 , [0.5, 1.5]), (o 3 , [1.7, 2.1])}.
	-

We consider that an object retrieved through a sorted access in a SR-source is not further accessed by a random access in the same source.

We consider that BestSortedSource does not return a source with no more objects.


Vincent Padois

Pascale Chiron

Jean-Yves Fourquet
email: fourquet@enit.fr

Adrien Carriay

J-Y Fourquet

Coordination and partial decoupling in tracking control for wheeled mobile manipulators

Keywords: mobile manipulation, kinematics, instantaneous kinematics, nonholonomy

Introduction

In this paper, we consider mobile manipulators built from a wheeled mobile platform and a serial chain robotic arm. These systems combine manipulation and mobility capabilities. So the majority of the tasks they are dedicated to require a certain level of coordination of the robotic arm and the platform. This is a specificity of mobile manipulation. In addition, in most tasks of manipulation, the user has to control the location (position and orientation) of the tool or the grip of his robot -named as the end-effector and denoted by EE from now on. This is also the case in mobile manipulation.

Recently some contributions concerning modelling and control of generic nonholonomic mobile manipulators ( [START_REF] Tchon | Kinematics of mobile manipulators: a control theoretic perspective[END_REF], [START_REF] Bayle | Manipulability of wheeled mobile manipulation: application to motion generation[END_REF][START_REF] Bayle | From manipulation to wheeled mobile manipulation: analogies and differences[END_REF]) have been proposed. Based on these proposals, it is now possible to consider modelling and control of mobile manipulators on a unified basis and a comparison can be made with classical manipulation. As for any compound system, a mobile manipulator can be seen as two subsystems cooperating or as a whole. In the first case, setpoints are defined for each subsystem from the tasks at hand whereas, in the second one, the setpoint is given directly to the whole system. Of course, redundancy plays an important role here and needs to be carefully defined.

We propose to compare both approaches at kinematic level on a tracking task for which the end-effector trajectory is imposed. This is illustrated on a planar example. In fact, we have developed:

• on one side, a generic formulation that is quite similar to the one used for holonomic arms

• on the other, a method based on decoupling the motion of the nonholonomic platform from that of the arm.

Manipulation and mobile robotics literature both provide modelling tools to solve this problem. On one hand, kinematics and instantaneous kinematics of robotic arms with a fixed base are now a very classical material along with the associated notions of redundancy, singularity and manipulability [START_REF] Sciavicco | Modelling and Control of Robot Manipulators[END_REF]. On the other hand, wheeled mobile platforms were properly described and modelled by [START_REF] Campion | Structural properties and classification of kinematic and dynamic models of wheeled mobile robots[END_REF]. Though less classical and less used in the robotics community, these notions are of great interest in the case of wheeled mobile manipulators.

In section 2 we first recall the main notions attached to task description. In section 3, a description of robotic arms and mobile platforms is given together with their respective kinematic models. Then, kinematics and instantaneous kinematics modelling of wheeled mobile manipulators is developed. Section 4 presents both approaches for tracking control of end-effector location. Simulation are given for a simple planar mobile manipulator.

Manipulation tasks

A task is defined by the user in the so-called operational space. A point in this space is a location. It is characterized by a set of operational coordinates that correspond to the value of the position and the orientation of a frame attached to the EE at a particular point of this EE. Note that the location of the EE can be defined in different ways, according to the task. For instance, for a planar problem, we will consider only the EE position and orientation in the plane. Both those values are measured with respect to a fixed reference frame. Let R = (O, x, y, z) be this reference frame with z vertical. Hereafter, the location of the EE is denoted by the m × 1 vector ξ. The tasks are mainly of two types : regulation or tracking. In a task of regulation, the goal is to reach a desired value of the EE location. In a task of tracking, one needs to realize a given velocity of this location, i. e. a given operational velocity, to follow a prescribed operational motion.

3 Kinematic modelling

¡ £¢ ¤ ¦¥ § © © § ¤ © ¤ ¢ ¥ § ! § ¥ ¤ ¢ " © # ¤ $ %
Figure 1: a planar mobile manipulator

Modelling of robotic arms

In classical manipulation, we consider a robotic arm built from n a mobile bodies, supposed perfectly rigid and articulated by n a revolute and/or prismatic joints. The most usual way to model it consists in using the Denavit-Hartenberg modified parameters proposed by [START_REF] Khalil | A new geometric notation for open and closed loop robots[END_REF]. These parameters define the location of all the bodies of the robotic arm, i. e. its whole geometry. This parameterization associates a frame, denoted here by The robotic arm configuration is known when the position of all its points in R 0 are known (see for instance [START_REF] Neimark | Dynamics of Nonholonomic Systems[END_REF]). It is defined by a vector q a of n a independent coordinates. These coordinates, called generalized coordinates of the robotic arm, characterize the values associated to the different joints: rotation angles for the revolute joints, translations for the prismatic ones and form the configuration q a = [q a1 q a2 . . . q an a ] T of the arm.

R i = (O i , x i , y i , z i ), with i = 0, 1, . . . ,
In this article, we choose to define the location of the EE relative to R 0 by a m a -dimensional vector of independent coordinates, denoted by ξ a = [ξ a1 ξ a2 . . . ξ am a ] T . This vector defines the position and the orientation of the EE in R 0 .

The kinematic model (KM) of the robotic arm sets the location of its EE as a function of its configuration:

f a : q a -→ ξ a = f a (q a ).
The instantaneous kinematic model (IKM) of the robotic arm sets the derivative of the EE location -or operational velocity -as a function of the derivative of the configuration -or generalized velocity:

J a (q a ) : qa -→ ξa = J a (q a ) qa ,
where J a (q a ) = ∂f a ∂q a (q a ) is the m a × n a Jacobian matrix of f a .

Wheeled mobile platforms

Let R = (O , x , y , z ) be a mobile frame linked to the platform (see Figure 1). The origin of R is usually chosen as a remarkable point of this platform (e.g. the midpoint of the rear axle). The location1 of the platform is given by a vector ξ p of 3 operational coordinates, which define its position and orientation in R. We write ξ p = [x y ϑ] T , where x and y are respectively the abscissa and the ordinate of O in R and ϑ the angle ( x, x ).

Let R(ϑ) be the 3-order rotation matrix expressing the orientation of R with respect to R. Rolling without slipping conditions give two kinds of instantaneous kinematics constraints. The first one defines allowable velocities for the platform location. It can be seen as the fact that there exists a δ m -dimensional vector η p of independent components (η p is the control of mobility of the platform) such that:

ξp = R(ϑ)Σ(β s )η p . ( 1
)
where β s is the δ s -dimensional vector of the steering angles of the wheels when the platform has such wheels and Σ(β s ) a 3 × δ m matrix, constant or not, depending on the existence of steering wheels. Equation ( 1) forms the instantaneous location kinematic model (ILKM) of the platform.

It sets the derivative of the platform location as a function of the control of mobility, for a given configuration.

When there are steering wheels, instantaneous kinematics are not completely described by the ILKM in the sense that this model does not fix the whole generalized velocity. We assume that we control the velocity of the δ s (δ s is the degree of steerability of the platform) steering wheels around their orientation axis. As a consequence, the δ s -dimensional vector ζ p is termed as the control of steerability of the platform:

βs = ζ p , (2)
With [START_REF] Campion | Structural properties and classification of kinematic and dynamic models of wheeled mobile robots[END_REF], let the (3 + δ s ) -dimensional vector

z p = [ξ T p β T s ]
T be the posture of the platform2 . If we define the control of manoeuvrability of the platform by the δ M -dimensional vector

u p = [η T p ζ T p ] T (δ M = δ m + δ s ), we get: żp = B p (ϑ, β s )u p ,
with:

B p (ϑ, β s ) = R(ϑ)Σ(β s ) 0 0 I δs ,
where I δs is the δ s -order identity matrix. This is the instantaneous posture kinematic model (IPKM). It can be shown that this model is irreducible (see [START_REF] Canudas De Wit | Theory of Robot Control[END_REF]). It constitutes the minimal model that allows to obtain the whole generalized velocity in the form:

qp = S p (ϑ, β s )u p , (3)
This equation relates the derivative of the platform configuration, for a given configuration, to its control of manoeuvrability. It is termed as the instantaneous kinematic configuration model (ICKM) of the platform.

Remark: for simplicity, we have assumed that the platform always has a number of actuators equal to its degree of manoeuvrability.

Wheeled mobile manipulators

The usual models of manipulation systems have been modified to take into account the nature of the platform. It results that the models of mobile manipulators are compromises between the models of platforms and those of robotic arms. Particularly, as mobile manipulators are manipulation systems, we write models to describe the location ξ of the EE, which is important from an operational point of view. The kinematic model (KM) of a mobile manipulator sets the location of its EE as a function of the robotic arm configuration q a and of the platform location ξ p :

ξ = f (q a , ξ p )
At the velocity level the instantaneous location kinematic model (ILKM) of a mobile manipulator sets the derivative of its location as a function of a set of ∆ m parameters of control, which form the mobile manipulator control vector of mobility η. These parameters are the control inputs of the system which have an influence on the EE velocity:

ξ = Jη. ( 4
)
The mobile manipulator degree of mobility ∆ m is the dimension of vector η.

The rest of the control parameters of a mobile manipulator consist of the δ s velocities βs (t) of the steering wheels -when they exist -of the platform about their orientation axis. The mobile manipulator control vector of manoeuvrability is given by the set of all the control parameters, i. e. by u = [η T ζ T p ] T . Finally the mobile manipulator degree of manoeuvrability ∆ M is the dimension of vector u.

To know the evolution of the mobile manipulator configuration we also define the mobile manipulator instantaneous configuration kinematic model (ICKM):

q = Su. (5)
It is fundamental to notice that, in general, the dimension m of operational space is less than the degree of mobility ∆ m of the mobile manipulator. In this case the problem, mobile manipulator and task, is redundant. From now on, we assume that it is the case.

Global or decomposed approach

From a kinematic point of view the problem of motion generation has been studied by various authors [START_REF] Seraji | An on-line approach to coordinated mobility and manipulation[END_REF][START_REF] Foulon | Control of a rovermounted manipulator[END_REF]. The difficulty consists in the necessary coordination of the two kinematically different subsystems: the platform and the arm. Whereas the tasks of a mobile manipulator are often described by the EE evolution -thus concerning manipulation aspects -it is compulsory to control the mobile platform adequately.

In fact, there are different factors acting for the definition of a planning and control strategy. First of all, we can think that the sole specification of the end-effector motion is not sufficient since the platform has to move without collision with the environment (and the arm). In the same way, since a kinematic scheme is incremental by nature, it does not take explicitly into account the proximity of the bounds.

Finally, different criteria may be considered. So, the task does not come down only to the end-effector location. Of course, these questions arise when there is more than one way to realize the imposed end-effector location.

Another point of view comes from the control problems. First of all, a kinematic scheme will be ill-conditioned near singularity of the linear map when the robot is not redundant w.r.t. the task. In the redundant case, convergence will be dependent on the chosen generalized inversion scheme. That is why different methods aim at defining additional tasks that must lead to robust invertible kinematic schemes [START_REF] Samson | Robot Control. The Task Function Approach[END_REF].

From the control viewpoint, nonholonomy must be studied carefully. It is now well-known that kinematic models of wheeled mobile platforms are quite difficult to control [START_REF] Canudas De Wit | Theory of Robot Control[END_REF].

In particular, point stabilisability is not ensured by continuous static feedback. Thus, this difficulty has to be taken into account when we are thinking in decomposing the task into a particular motion of the platform and an adapted motion of the arm. On the other side, when looking at the global mobile manipulator, the kinematic constraints of the platform may be compensated by an adequate generalized velocity of the arm to realize a prescribed end-effector task.

In that case, nonholonomy of the platform is somewhat hidden in the global instantaneous kinematics.

So, it is interesting to compare both viewpoints.

Two methods are possible: i) to get a solution for the robotic arm joint values, an adequate platform position and orientation, and then to compute a control law to stabilize the system around the corresponding configuration [START_REF] Yamamoto | Coordinating locomotion and manipulation of a mobile manipulator[END_REF]; ii) to compute directly the control inputs from the EE specified motion by an inverse of the adequate kinematic model [START_REF] Seraji | An on-line approach to coordinated mobility and manipulation[END_REF][START_REF] Foulon | Control of a rovermounted manipulator[END_REF].

We consider the operational motion tracking problem. In order to simplify the presentation, we suppose, from now on, that the mobile manipulators have no steering wheel. The manoeuvrability control of the mobile manipulator reduces to its mobility control, and so u = η.

A global approach

We synthesize the control inputs of the mobile manipulator to obtain the specified motion of the EE. The proposed scheme is as general as possible and consistent with on-line computation. Our control laws are based on the generic modelling proposed in [START_REF] Bayle | From manipulation to wheeled mobile manipulation: analogies and differences[END_REF] and recalled in the previous section.

Here, for a given operational motion ξ * (t), the problem is to find the mobility control η(t) such that ξ * (t) = J(t)η(t)

(see equation 4), in order to asymptotically stabilize the operational error e(t) = ξ * (t) -ξ(t). The matrix J(t) is m×∆ m . We suppose (this is the case in practice), that m ≤ ∆ m and that the rank of this matrix is m. Then the previous linear system is consistent and all the exact solutions are given by :

η = J+ (t) ξ * (t) + (I ∆m -J+ (t) J(t))g(t),
in which J+ (t) is the pseudo-inverse of J(t) and g(t) any ∆ m -dimensional vector. The solution obtained is the one that minimizes the Euclidean norm ||η -g||

In fact, in order to asymptotically stabilize the error e(t), one can choose:

η(t) = J+ (t)( ξ * (t) + W (ξ * (t) -ξ(t))) +(I ∆m -J+ (t) J(t))g(t), (6)
in which W is a m-order definite positive matrix.

Actually the previous control leads to the asymptotic stability of the transient error e(t), due to the equation:

ė(t) + W e(t) = 0, because J+ (t) is a right-inverse of J(t).
On one hand the mobile manipulator is redundant, because the dimension ∆ m of its control of mobility η is greater than the dimension m of its location ξ. On the other hand, we recall that q(t) = S(t)η(t) (see equation ( 5)). Then [START_REF] Khalil | A new geometric notation for open and closed loop robots[END_REF] writes:

q(t) = S(t) J+ (t)( ξ * (t) + W (ξ * (t) -ξ(t))) +S(t)(I ∆m -J+ (t) J(t))g(t).
In this equation the first term is due to the input and the second one is the internal motion. We can use the previous redundancy to propose a coordination strategy for the internal motion. For instance, it is interesting to avoid great variations of the components q i of q and constrain these coordinates around their mean values. This can be done by a gradient descent method in which the potential function has its minimum value for the previous means. In general, let P be a scalar function depending on the mobile manipulator configuration q(t). We can write: Ṗ(t) = ∇ T P(q(t)) q = ∇ T P(q(t))S(t)(I ∆m -J+ (t) J(t))g(t), for the internal motion (∇P(q(t)) is the gradient of the function P(q(t)). In order to decrease P(q(t)), that is ( Ṗ(t)) ≤ 0, we propose the choice:

g(t) = -k S(t)(I ∆m -J+ (t) J(t)) T ,
where k is a positive scalar. Indeed, with this choice:

( Ṗ(t)) = -k ∇ T P(q(t))S(t)(I ∆m -J+ (t) J(t)) S(t)(I ∆m -J+ (t) J(t)) T , and then ( Ṗ(t)) ≤ 0.

Finally, the mobility control is:

η(t) = J+ (t)( ξ * (t) + W (ξ * (t) -ξ(t)
)) -kS(t) I ∆m -J+ (t) J(t) S(t)(I ∆m -J+ (t) J(t))

T .

This approach can be applied with various choices for P.

The first figure (Fig. 2) shows an example with criteria based on maximum distance to obstacle and the second one (Fig. 3) illustrates how manipulability measure can be maximized (the ellipse shown is the ellipse of manipulability of the whole mobile manipulator) [START_REF] Bayle | Manipulability of wheeled mobile manipulation: application to motion generation[END_REF]. In both case, only the position of the end-effector in the plane is imposed.

A decomposition approach

In that part, we consider a way to decompose the task. First of all, we have to verify that the platform is always near enough to the end-effector. So, a trajectory is planned for the platform from the end-effector trajectory. Then, it is necessary to have a control scheme that ensures that the actual motion is close to the planned one. Specifically, we must characterize the distance between the planned platform location and the actual one. A way to do that is to plan a feasible trajectory for the platform i.e. a trajectory that respects the nonholonomic constraints. Different techniques exists but they do not solve the online control problem. We follow another direction through the use of practical stabilisability of the platform by transverse functions [START_REF] Morin | Practical stabilization of a class of nonlinear systems. application to chain systems and mobile robots[END_REF]. This technique allows to plan a trajectory, feasible or not, and to follow it actually with a location error that can be tuned quite easily. For simplicity, let us take the instantaneous kinematic model for a unicycle-like platform (i.e. with U = [η t p α] t the new 3-dimensional control vector with the external dynamic in α, A a full rank 3 × 3 matrix, and y a new variable such that when y goes to zero, ξ p is arbitrarily small. Then, by inverting the above system, arbitrary dynamics can be given to y and, as a result, ξ p can be practically stabilized i.e. can be steered into a arbitrary small ball around the target.

Then, the arm adapts its motion from the end-effector setpoint and the current value of the platform location through a simple linear controller.

Two results of simulation are presented for the same endeffector task that consists in following a line. In the first one, the induced platform trajectory is feasible since the platform can roll along the line parallel to the blackboard. In the second one, the induced trajectory of the platform is such that the position (x, y) of the platform must move along the same parallel line but with the orientation normal to this line. This trajectory is clearly non feasible since it needs a slipping of the platform. The transverse function method allows to follow this trajectory with a bounded error and then the arm can adapt itself to this error. Typically, the first simulation (Fig. 4) could be obtained easily with a global scheme whereas the second one (Fig. 5) shows how the dynamic feedback introduced by transverse functions method allows to produce efficient motions of the platform in the direction its instantaneous kinematics prevent.

Figure 2 :

 2 Figure 2: Obstacle avoidance

Figure 3 :

 3 Figure 3: Maximization of manipulability

Figure 4 :

 4 Figure 4: trajectory of the platform parallel to the EE trajectory

  n a , to the i-th body of the robotic arm. So, the frame R 0 is linked to the base. The center of the EE is denoted by O na+1 . Hence, both points O na and O na+1 are linked to the EE.

This quantity is not distinguished from the posture in[START_REF] Campion | Structural properties and classification of kinematic and dynamic models of wheeled mobile robots[END_REF]. Nonetheless, it seems important to us to isolate the part of the posture that is related to the EE location, on one side, and that will appear as the range of a linear map defined over the control of mobility (see hereafter).

Posture and location need to be distinguished only when the platform has steering wheels. When there is no steering wheels, posture and location are the same notion.