Matthieu Fruchard
email: matthieu.fruchard@univ-orleans.fr

Guillaume Allibert
email: allibert@i3s.unice.fr

Estelle Courtial
email: estelle.courtial@univ-orleans.fr

Choice of the control horizon in an NMPC strategy for the full-state control of nonholonomic systems

come

Choice of the control horizon in an NMPC strategy for the full-state control of nonholonomic systems

I. INTRODUCTION

The model predictive control has become the mature strategy that we know today thanks to many theoretical and practical developments during the last decades [START_REF] Camacho | Nonlinear model predictive control: An introductory review[END_REF]. Initially developed for slow systems, it is now currently used for fast nonlinear systems like mobile robots, PVTOL (planar vertical take off and landing) aircrafts,... In all the applications of an NMPC strategy, the choice of the prediction horizon and the control horizon still remains a difficulty. The prediction horizon, noted N p , is chosen in order to best satisfy a compromise between the stability of the closed-loop (long horizon) and the computational time required (short horizon). The control horizon, noted N c , is often chosen equal to N p . Although the role of the control horizon is relayed to the second plan, it can be decisive in some applications such as the control of mobile robots. The control of nonholonomic vehicles (unicycle, car, car-like vehicle with n trailers, etc.) has been largely studied. Albeit intrinsically controllable, a nonholonomic system has a linearized model which loses its controllability property at any fixed point. Furthermore Brockett [START_REF] Brockett | Asymptotic stability and feedback stabilization[END_REF] showed that no continuous timeinvariant feedback control could asymptotically stabilize this class of systems. Time-varying [START_REF] Samson | Velocity and torque feedback control of a nonholonomic cart[END_REF], [START_REF] Pomet | Explicit design of time-varying stabilizing control laws for a class of controllable systems without drift[END_REF], [START_REF] Closkey | Exponential stabilization of driftless nonlinear control systems using homogeneous feedback[END_REF], discontinuous [START_REF] De | Exponential stabilization of mobile robots with nonholonomic constraints[END_REF], hybrid [START_REF] Bennani | Robust stabilization of flat and chained systems[END_REF] feedbacks have been reported. NMPC implicitly provides a discontinuous feedback thereby bypassing Brockett's condition. If NMPC is often used to the rather simple problem of the trajectory tracking, only a limited number of studies addresses the difficult problem of the full-state (position and orientation) control [START_REF] Van Essen | Nonlinear model predictive control for constrained mobile robots[END_REF], [START_REF] Alamir | Constrained minimum-time-oriented feedback control for the stabilization of nonholonomic systems in chained form[END_REF], [START_REF] Grimm | Model predictive control: for want of a local control lyapunov function, all is not lost[END_REF]. The stability of the closed-loop system is ensured either under assumptions of detectability and boundedness of the cost function [START_REF] Grimm | Model predictive control: for want of a local control lyapunov function, all is not lost[END_REF] or by using time-varying weighted matrix [START_REF] Van Essen | Nonlinear model predictive control for constrained mobile robots[END_REF]. In all the aforementioned papers, the control horizon is chosen equal to N p , leading to a quite long computational time.

In this paper, the choice of the control horizon is addressed for the control of chained systems which can model many common nonholonomic systems. We establish a relation between the degree of nonholonomy and the minimum length of the control horizon in order to perform the full-state control of the chained system. A necessary condition on the control horizon of NMPC is then given and theoretically proved whatever the dimension of the chained system considered. From a practical point of view, an appropriate choice of control horizon makes it possible to reduce the computational load requirement. A real time implementation on fast robotic systems can consequently be considered.

The paper is organized as follows: section II briefly recalls the NMPC concept, nonholonomic vehicles and chained systems. The main result is stated in section III: how can we determine the minimal control horizon N c that will ensure the desired full-state to be reached? A necessary condition on N c is given for the state feedback control of chained systems. In section IV, the NMPC for chained system is described in detail. In section V, simulations on a car-like vehicle with one trailer modeled by a (2,5) chained system illustrate the decisive role of the control horizon. Conclusions are given in the last section.

II. BACKGROUND A. NMPC

The NMPC strategy is based on the receding horizon principle and is formulated as solving on-line a nonlinear optimization problem, see [START_REF] Camacho | Nonlinear model predictive control: An introductory review[END_REF] for a survey. From a practical point of view, the main advantage of NMPC is its ability to take into account constraints. Constraints on states, inputs or outputs can easily and explicitly be added to the optimization problem. The basic concepts of NMPC are the explicit use of a model to predict the process behavior over a finite prediction horizon N p and the minimization of a cost function J with respect to a sequence of N c controls. The cost function J, difference between the control task (the reference) and the predicted behavior is defined by:

J(x, u) = F(x(t + N p )) + t+N p t L(x(τ), u(τ), y re f (τ))dτ (1)
where x is the model state, u is the control input, L is a quadratic function and F(x(t + N p )) is a terminal constraint added to ensure the stability of the closed-loop system. The mathematical formulation of an NMPC problem is usually written as follows: min u J(x, u)

subject to ẋ = f (x, u). ( 2
)
The equation ẋ = f (x, u) represents the nonlinear dynamic model of the process to be controlled. The cost function J is minimized over the prediction horizon N p with respect to the sequence of controls u. Only the first element of the computed optimal sequence u is really applied to the process. At the next sampling time, the measurements are updated, the prediction horizon moves one step forward and the whole procedure is repeated.

B. Modeling of nonholonomic vehicles

This section recalls some properties of nonholonomic vehicles. For notions on Lie algebras and differential geometry, see [START_REF] Warner | Foundations of differential manifolds and Lie groups[END_REF], [START_REF] Nijmeijer | Nonlinear Dynamical Control Systems[END_REF]. Wheeled robots are characterized by non completely integrable velocity constraints resulting from the rolling without slipping assumption < a i (z), ż >= 0, i = 1, • • • , q, where z ∈ N is the configuration of the vehicle in a n differentiable manifold N, and the a i 's are assumed smooth and independent [START_REF] De | Nonlinear feedback control[END_REF]. Nonholonomic vehicles can hence be modeled by a kinematic driftless control system:

ż = m ∑ i=1 u i Z i (z), z(0) = z 0 (3)
where m = nq < n, z 0 is the initial configuration, the u i 's denote control variables and the Z i 's are smooth independent vector fields over N. The solution at time t of (3) is denoted:

z(t) = e t m ∑ i=1 u i Z i (z 0 ). (4)
Let Z (N) be the Lie algebra of all vector fields on N and g = L (Z 1 , • • • , Z m ) the Lie subalgebra of Z (N) generated by the vector fields Z 1 , • • • , Z m . We assume that system (3) satisfies the Lie algebra rank condition on N:

dim(span{Z(z) : X ∈ L (Z 1 , • • • , Z m )}) = n. ( 5
)
Under assumption (5), Chow's theorem implies that system (3) is controllable [START_REF] Nijmeijer | Nonlinear Dynamical Control Systems[END_REF].

In order to classify nonholonomic systems, we recall the concept of nonholonomic degree defined in [START_REF] Gershkovich | Nonholonomic manifolds and nilpotent analysis[END_REF].

Definition 1 Let g 1 = span{Z 1 , • • • , Z m } and recursively g k = g k-1 + [g 1 , g k-1 ], k ≥ 2 where [g 1 , g k-1 ] = span{[X,Y ] : X ∈ g 1 ,Y ∈ g k-1 }.
Assuming the system is regular, we define the degree of nonholonomy as p = min{i ∈ N : g i = g}. The degree of nonholonomy is an image of the difficulty in controlling the system. Since the longer the Lie bracket is, the more difficult it is to move in its direction, the difficulty is the greatest when moving in the direction of the vector fields that belong to g\g p-1 . This degree is an intrinsic property of the system, i.e., it does not depend on the coordinate system the control is written in.

Concerning the kinematic modeling of a wide class of wheeled robots, such as a unicycle with n -3 trailers, [START_REF] Sørdalen | Conversion of the kinematics of a car with n trailers into a chained form[END_REF] gives a feedback change of coordinates (z, u 1 , u 2 ) → (x, v, w) converting system (3) in natural coordinates (i.e., defined on SE(2) × M with M denoting a (n -3)-dimensional manifold) into a (2, n) chained form, which is a particular case of system (3). Definition 2 A (2, n) chained system is a kinematic system in the form (3) with two control inputs and the following vector fields:

   ẋ = X 1 (x)v + X 2 w, x = (x 1 , • • • , x n ) ∈ R n X 1 = (1, 0, x 2 , • • • , x n-1 ) X 2 = (0, 1, 0, • • • , 0) (6)
The degree of nonholonomy of system ( 6) is p = n -1.

III. PROBLEM STATEMENT AND MAIN RESULT

Problem 1 Let N c denote the control horizon of a predictive control law and (v, w) ∈ R 2 , the control input of system [START_REF] De | Exponential stabilization of mobile robots with nonholonomic constraints[END_REF].

Consider a piecewise constant control family {v k , w k } k≤N c over N c sampling periods T e . With notations of section II-B, let:

s

: ν → x f = e Y Nc • • • • • e Y 2 • e Y 1 • x 0 ( 7
)
where

Y k (x) = T e (X 1 (x)v k + X 2 w k ) and ν = ( ṽ, w) is the con- trol sequence with ṽ = (v 1 , • • • , v N c ) and w = (w 1 , • • • , w N c ).
What is the minimal control horizon N c such that there exists a control sequence ν solving equation [START_REF] Bennani | Robust stabilization of flat and chained systems[END_REF] for any desired final configuration x f , i.e. such that s is surjective?

Solving Problem 1 is not always simple. Since the vector fields of system ( 6) are left-invariant on the Lie group R n , then equation ( 7) can be expressed as a product of exponentials, whose direct calculation is provided either using the Campbell-Hausdorff formula or using the group operation of the Lie group. For more generic systems in the form (3), producting the exponentials using the Campbell-Hausdorff formula will result in an infinite number of bracketings. If possible, it is thus preferable to feedback nilpotentize system (3) in order to avoid errors induced by the truncation of brackets longer than a given order [START_REF] Hermes | Nilpotent bases for distributions and control systems[END_REF]. Note however that feedback nilpotentization may induce singularities, thus limitating reachable points for a given control horizon.

Proposition 1 Solving Problem 1 for any (2, n) chained system (6) generically requires a control horizon N

c = p+1 = n.
The detailed proof is given in Appendix.

Remark 1

Solving Problem 1 for unicycle or car-like vehicles in natural coordinates, i.e., in the form (3) on respective manifolds N = SE [START_REF] Brockett | Asymptotic stability and feedback stabilization[END_REF] and

N = SE(2) × (-π 2 , π 2 )
with vector fields respectively given by:

Z 1 (z) = (cos θ , sin θ , 0), Z 2 = (0, 0, 1) (8a) Z 1 (z) = (cos θ , sin θ , tan φ L , 0), Z 2 = (0, 0, 0, 1) (8b)
generically requires a control horizon N c = p = n -1. Such trajectories consist of two semi arcs of circle and three arcs of clothoids, respectively. The price to pay using a chained system (6) instead of system in natural coordinates (3) with vector fields (8a) or (8b) is linked to the nilpotence degree p of the chained system, which increases the minimal control horizon length needed to solve Problem 1. Indeed, the minimal control horizon required to solve Problem 1 for the car is N c = p = 3 in natural coordinates, versus N c = p+1 = 4 in chained form. Let us discuss the case N c = p, where s is surjective for any motion along g p-1 \g p-2 , but is no longer surjective on g\g p-1 . This lack of solution is due to the nilpotentization, which is illustrated hereinafter by the significant car example, and therefore should not be regarded as an intrinsic property, but rather as a consequence of the choice of the coordinate system the nonholonomic system is written in.

Example 1 Any translation along g\g 2 , corresponding to a pure transversal motion (along

X 4 = [X 1 , [X 1 , X 2 ]] = (0, 0, 0, 1)
), is clearly feasible by a car modeled by system (3) with vector fields (8b) and N c = p = 3, but requires that the orientation reaches values forbidden by the nilpotentization feedback [START_REF] Murray | Steering nonholonomic systems in chained form[END_REF] (namely θ = ± π 2 ). Basically, along g\g 2 , the nilpotence degree p = 3 of the car in chained form [START_REF] De | Exponential stabilization of mobile robots with nonholonomic constraints[END_REF] results in a null translation. This motion is thus impossible to achieve for the car in chained form with N c = 3. The same problem was reported in [START_REF] Lafferriere | A general strategy for computing steering controls of systems without drift[END_REF] using the nilpotent approximation of the unicycle. Nevertheless, it should be noted that any motion along g 2 \g 1 (along X 3 = [X 1 , X 2 ] = (0, 0, -1, 0)), i.e., a pure rotation around the location of the rear wheels, can be achieved with N c = 3, whatever the coordinate system the car-like vehicle is written in.

Remark 2 Proposition 1 gives a sufficient and necessary condition on N c for the wide class of nonholonomic vehicles modeled by the (2, n) chained form, so as to ensure the existence of solutions to Problem 1 given arbitrary initial and final configurations. In the scope of optimization-based control, there are slight differences with the formulation of Problem 1. Firstly, the goal in NMPC is not explicitly to regulate to zero the error between the reference and the model output configuration obtained by applying N c control steps, but rather to minimize a weighted sum of errors over a prediction horizon N p ≥ N c . Secondly, the handling of constraints either on the control inputs and/or on the states may reduce the set of solutions. Restrictions imposed using an NMPC approach thus result in relaxing the sufficient and necessary condition for solving the theoretical Problem 1 into a necessary condition, in practice, for solving the NMPC optimization problem formulated in the next section.

IV. NMPC DESIGN FOR FULL-STATE CONTROL OF CHAINED SYSTEMS

As for all predictive strategies, a reference trajectory, a model of the dynamic process, a cost function and a solving optimization method are necessary. In the sequel, the choice of these four points is discussed according to the control objective: the full-state control and stabilization of a chained system. First of all, to address robustness to modeling errors and disturbances, the well-known Internal Model Control (IMC) structure (see Fig. 1) has been chosen. The tracking of the reference trajectory y re f by the process output y p is equivalent to the tracking of the desired trajectory y d by the model output y m . The signal error e(k) = y p (k)y m (k) includes modeling errors and measurement noises. The error is assumed to be constant over the prediction horizon but is updated at each new measurement. The control task is to steer the process to the origin, consequently y re f is null. The model of prediction. The model has to predict the process behavior over the prediction horizon.

ẋ(t) = X 1 (x(t))v(t) + X 2 w(t) , x(0) = x 0 y m (k + j | k) = x((k + j)T e ). (9)
The variables x ∈ R n , (v, w) ∈ R 2 and y m ∈ R n are respectively the state, the input and the output of the model. The model output is sampled at each T e = 1s and y m(k+ j|k) is the predicted output at time k + j the current time k. The computed input is kept constant over a sampling period:

∀ j ∈ [1; N p ], v(t) = v(k + j -1 | k) for (k + j -1)T e < t < (k + j)T e , w(t) = w(k + j -1 | k) for (k + j -1)T e < t < (k + j)T e . (10)
The model output y m (k) is initialized with the updated measures of the process output y(k) providing an implicit feedback. The cost function. Due to the IMC structure and the sampled measurements of the process, the mathematical formulation of the cost function is written, in discrete-time, as: [START_REF] Warner | Foundations of differential manifolds and Lie groups[END_REF] where Q( j) is a symmetric positive definite matrix and y m (k + j | k) is given by ( 9). The role of the time-varying matrix Q( j) consists in weighting the tracking error at each iteration more and more over the prediction horizon. It reinforces the role of the terminal constraint. Giving a heavy weight at the end of N p , which corresponds to the final objective, makes the NMPC problem (2) tend to the theoretical Problem 1. The time variation of the weighted matrix Q( j) is given by:

J(x, u)= k+N p ∑ j=k+1 [y d -y m ](k+ j|k) T Q( j)[y d -y m ](k+ j|k) +F(x(k+N p ))
Q( j) = αQ( j -1), with α ≥ 1. ( 12
)
The solving optimization method. A sequential quadratic programming (SQP) is used (function fminunc from Matlab) to solve the optimization problem (2) with ( 9)-( 12). The cost function J is minimized with respect to the control sequence u = {u(k), u(k + 1), ..., u(k

+ N c ), ..., u(k + N p -1)}, composed of N c different controls. From u(k + N c + 1) to u(k + N p -1)
, the inputs are constant and equal to u(k + N c ).

The control horizon N c plays a crucial role: it provides a solution by proposing N c different controls at time k comparable to a manoeuvre. According to Proposition 1, the control horizon will be chosen equal to or greater than the degree of nonholonomy of the chained system: N c ≥ p + 1.

We have deliberately chosen a standard algorithm to show that the efficiency of the NMPC for full-state control is due to the control horizon and does not depend on the optimization algorithm.

V. SIMULATIONS

We consider a (2, 5) chained system, describing a car vehicle with one trailer, defined by the following vector fields:

X 1 (x) = (1, 0, x 2 , x 3 , x 4 ), X 2 = (0, 1, 0, 0, 0). ( 13
)
The degree of nonholonomy is given by p = n -1 = 4. All the simulations are performed on the chained system. The NMPC parameters are respectively set to N p = 10 and N c = 5 according to Proposition 1. The time variation of Q( j) is given by ( 12) with α = 5 and Q(1) = I. We first illustrate the role of N c as a necessary condition for the state feedback of chained systems without constraints. In the particular case where the initial state is (0, 0, 0, 0, 1) and the desired one is (0, 0, 0, 0, 0), the final position is not reached with N c < 5. With N c = 5, in accordance with Proposition 1, the control strategy is able to determine a control sequence such that the full-state converges to the desired state (see Fig. 2

(a) and 2(d)).

To better illustrate the effectiveness of the approach, a change of coordinates has been applied on the graphical illustration of the simulation results. Constraints handling is one of the advantages of NMPC design. In simulation 2, the control inputs and the state variables of the chained system are respectively constrained to ±2 and ±4. We can notice that the convergence is still obtained while the constraints are satisfied (see Fig. 2(b) and 2(e)). From a different initial state (0.2, -0.6, 0.25, -0.3, 0.5), the control strategy finds a control sequence satisfying the same constraints and the control task is always achieved (see Fig. 2(c) and 2(f)). To test the robustness of the approach, the initialization of the process is different from the model's one (25% on the state x 5 ), the controls really applied to the process have got an error of 5% on the computed value of v and w. With N c = 5 and N p = 6, the states of the chained system converge to the origin in spite of modeling errors (see Fig. 2(g) and 2(h)). The control inputs satisfy the constraints ±2 (see Fig. 2(i)).

Remark 3 For all the presented simulations performed on a PC intel Core 2 duo, 3.06 GHz under Matlab, the computational time required to solve the optimization problem was about 2 seconds. This computational time is composed of the Matlab function call, the differential equation resolution and the optimization solving. The over-all computational time can be greatly reduced by using a discrete-time model of the mobile robot (simulations have already been performed and required 50ms) and by using a more efficient minimization algorithm. It is worth mentioning that the computational load relative to the usual choice of N c = N p is divided by 3 by using the appropriate choice of N c = p + 1.

VI. CONCLUSION From a theoretical point of view, we have established a necessary condition on the length of the control horizon whatever the dimension of the chained system. This necessary condition provides a useful lower bound for the control horizon to ensure the full-state control of chained systems. From a practical point of view, the appropriate choice of the control horizon makes it possible to minimize the computational load. On the other hand, the choice of the prediction horizon still remains an open problem in an NMPC strategy. Since N c is often equal to N p , a useful information on the minimum length of the prediction horizon can also be given. However it is worth noting that the presence of constraints on states or inputs will inevitably impact the lengths of the horizons.

ACKNOWLEDGMENT The authors are very grateful to Pascal Morin for his helpful advices. APPENDIX PROOF OF PROPOSITION 1 Proof: The proof consists in four steps. The first step aims at reformulating the Problem 1 using the properties of the (2, n) chained systems. The second and third steps are devoted to the study of cases where s( ν) = e X (0), X ∈ g\g 1 and s( ν) = e X (0), X ∈ g\g N c -2 , that is motions in the direction of vector fields of increasing length, and thus of increasing difficulty. The last step concludes the proof. 1) First, we can make the Problem 1 more explicit for the (2, n) chained system. The nilpotent algebra generated by the vector fields of (6) underlies the following group operation on the Lie group N = R n : xy = exp (Ay 1 )x + y (A. [START_REF] Gershkovich | Nonholonomic manifolds and nilpotent analysis[END_REF] where A is the square matrix of dimension n which nonzero entries are only a i+1,i = 1, ∀i ≥ 2.

Since the vector fields of system ( 6) are left-invariant with respect to the group operation given by (A.14), [START_REF] Bennani | Robust stabilization of flat and chained systems[END_REF] can be expressed as a product:

s : ν → x f = x 0 e Y 1 (0)e Y 2 (0) • • • e Y Nc (0) (A.15)
with 0 denoting the identity element of N = R n . As the final configuration x f is any element of N, the initial condition can be set to x 0 = 0 without loss of generality. Thus (A.15) becomes s : ν

→ x f = x(1)x(2) • • • x(N c ),
where x( j) = e Y j (0) is the solution of equation ( 6) for the j th control input pair (v j , w j ) and initial condition 0. Let T e = 1s so as not to burden notations, then using direct integration of (6), we get:

x( j) = v j , w j , v j w j 2 , • • • , v n-2 j w j (n-1)! . (A.16)
Using the group operation (A.14) on R n , the solution to a succession of N c iterations is thus given by:

s( ν) = N c ∏ j=1 x( j) = N c -1 ∑ j=1 exp A N c ∑ i= j+1 v i x( j) + x(N c )
s( ν) =   1 • • • 1 0 • • • 0 0 • • • 0 1 • • • 1 0 n-2,N c B( ν)   ν, (A.17) with matrix B elements b i,N c = v i N c /(i + 1)! and b i, j = i ∑ r=0 N c ∑ q= j+1 v q i-r v r j (i -r)!(r + 1)! , ∀ j ≤ N c -1. (A.18)
2) If s( ν) = e X (0), X ∈ g\g 1 , i.e. the shift's two first components are null while the others are not, (A.17) gives:

(s 3 , . . . , s n )( ν) = B( ν) w, (A.19) with, ∀i ≤ n -2, ∀ j ≤ N c -1, coefficients of B given by: bi, j = (-1) i+1 ( N c -1 ∑ r=1 v r ) i - i ∑ q=0 i+1 q v i-q j ( j-1 ∑ r=1 v r ) q (i + 1)! . (A.20)
Using (A.20), we get N c -1 ∑ j=1 v j bi, j = 0, ∀i, and (A.19) gives:

(s 3 , . . . , s n )( ν) = D( ν) λ , (A.21)
where D denotes the N c -2 first columns of B, and λ = (λ 1 , . . . , λ N c -2 ) with λ j = w j -v j w N c -1 /v N c -1 .

3) We will now show that, with a control sequence of length N c , having s( ṽ) = e X (0) with

X ∈ g\g N c -2 implies that s N c (•) divides s N c +1 (•), • • • , s n (•).
Let s( ṽ) = e X (0) with X ∈ g\g N c -2 . We have s i (•) = 0, ∀i ≤ N c -1 and (A.21) can be decomposed as:

     0 1,N c -3 s N c . . . s n      ( ν) =      C E bN c ,1 R N c . . . . . . bn,1 R n      ( ν) λ , (A.22)
where the matrix D is partitioned in blocks C, R N c +q and E respectively denote (N c -3) column and raw vectors and a (N c -3) × (N c -3) matrix. Using the Schur complements for s N c +q (•), ∀q = 0, • • • , n -N c , we get:

s N c +q (•) = ( bN c +q,1 -R N c +q E -1 C)λ 1 . (A.23)
With the block matrix F N c +q defined by: v r P N c ,q , if i = N c -2 (A.26) with P N c ,q given by: P N c ,q = (-1) q (N c -1)! such that |I| = q, i.e. for every I j such that (A.28) In the same way, we obtain det E: (A.30) As P N c ,0 = 1, the equation (A.30) implies that s N c +q ( ṽ) = s N c ( ṽ)P N c ,q ( ṽ), ∀q = 1, • • • , (n -N c ). (A.31)

F N c +q = C E bN c +q,1 R N c +q , (
det E = (-1)
Consequently, s( ṽ) = e X (0) with X ∈ g\g N c -1 will involve that s( ṽ) = 0. Hence, s is not surjective for N c ≤ p = n-1.

4)

For N c = p + 1 = n, s( ṽ) = e X (0) with X ∈ g\g p-1 will have solutions provided that the numerator in (A.30) is not null, that is if v N c -1 = 0 and no sum of strictly less than N c -2 successive controls v i is null. As a result, s is surjective for N c = p + 1.

  Fig. 1. Control Structure

1 :

 1 Control inputs.

  Simulation 4: State evolution.

Fig. 2 .

 2 Fig. 2. Different simulations of the (2,5) chained systems

if i ≤ N c - 3 (- 1 ) 1 N

 311 A.24) the equation (A.23) leads to:s N c +q = det F N c +q (-1) N c -3 det E λ 1 . (A.25)The determinants in the latter equation are determined using a LU decomposition with a unit triangular matrix L.Let F N c +q = L N c +q U N c +q , then the diagonal matrix U n c +q coefficients are given using (A.20): Nc-1 (N c -1)! v Nc-

  is done for multiindex I = (I 1 , • • • , I N c -1 )

  c -r ) .(A.29) Using (A.28) and (A.29), (A.25) is simplified as:

1 (

 1 j ) P N c ,q λ


Estelle Courtial
email: estelle.courtial@univ-orleans.fr

Matthieu Fruchard
email: matthieu.fruchard@univ-orleans.fr

Guillaume Allibert
email: guillaume.allibert@unice.fr

Predictive Control of Chained Systems: a Necessary Condition on the Control Horizon

This paper deals with state feedback control of chained systems based on a Nonlinear Model Predictive Control (NMPC) strategy. Chained systems can model many common nonholonomic vehicles. We establish a relation between the degree of nonholonomy and the minimum length of the control horizon so as to make the NMPC feasible. A necessary condition on the control horizon of NMPC is given and theoretically proved whatever the dimension of the chained system considered. This relation is used to design a NMPC-based control strategy for chained systems. One of the advantages of NMPC is the capability of taking into account the constraints on state and on control variables. The theoretical results are illustrated through simulations on a (2,5) chained system, describing a car-like vehicle with one trailer. Difficult motion objectives that require a lateral displacement are considered.

I. INTRODUCTION

The interest in chained systems stems from the fact that the kinematic model of many common nonholonomic vehicles (unicycle, car, car-like vehicle with n trailers, etc.) can be converted into this form [START_REF] Sørdalen | Conversion of the kinematics of a car with n trailers into a chained form[END_REF]. The stabilization problem of nonholonomic vehicles has been largely investigated in the literature [START_REF] Morin | Trajectory tracking for non-holonomic vehicles : overview and case study[END_REF], [START_REF]Handbook of Robotics[END_REF]. Two control tasks can be distinguished: trajectory tracking and fixed point asymptotic stabilization. While the trajectory tracking is a rather simple problem (at least under the persistence of motion assumption), point-stabilization is far from straightforward when full-state stabilization (position and orientation) is considered. Albeit intrinsically controllable, a nonholonomic system has a linearized model which loses its controllability property at any fixed point. Therefore, linear control techniques cannot be used to stabilize this system at a given configuration. Moreover Brockett [START_REF] Brockett | Asymptotic stability and feedback stabilization[END_REF] showed that no continuous time-invariant feedback control could asymptotically stabilize this class of systems. Time-varying [START_REF] Samson | Velocity and torque feedback control of a nonholonomic cart[END_REF], [START_REF] Pomet | Explicit design of time-varying stabilizing control laws for a class of controllable systems without drift[END_REF], [START_REF] Closkey | Exponential stabilization of driftless nonlinear control systems using homogeneous feedback[END_REF], discontinuous [START_REF] De | Exponential stabilization of mobile robots with nonholonomic constraints[END_REF] and hybrid [START_REF] Bennani | Robust stabilization of flat and chained systems[END_REF] feedbacks have been proposed. Recently, practical full-state stabilization has been addressed via the use of transverse functions [START_REF] Morin | Control of nonholonomic mobile robots based on the transverse function approach[END_REF]. This control approach uses additional virtual control inputs through a dynamic extension, providing practical stabilization along any (even non admissible) trajectory or fixed point with a priori bounded error.

Model Predictive Control implicitly provides a discontinuous feedback thereby bypassing Brockett's condition. Indeed, the NMPC strategy is based on the receding horizon principle and is formulated as solving on-line a nonlinear optimization problem, see [START_REF] Camacho | Nonlinear model predictive control: An introductory review[END_REF] for a survey. The basic concepts of NMPC are the explicit use of a model to predict the process behavior over a finite prediction horizon N p and the minimization of a cost function with respect to a sequence of N c controls where N c is the control horizon. If NMPC is often applied to trajectory tracking of nonholonomic systems, only a limited number of studies deals with stabilization [START_REF] Van Essen | Nonlinear model predictive control for constrained mobile robots[END_REF], [START_REF] Alamir | Constrained minimum-time-oriented feedback control for the stabilization of nonholonomic systems in chained form[END_REF], [START_REF] Grimm | Model predictive control: for want of a local control lyapunov function, all is not lost[END_REF]. In [START_REF] Grimm | Model predictive control: for want of a local control lyapunov function, all is not lost[END_REF], the authors studied the stability of unconstrained discrete-time systems controlled using NMPC. Under assumptions of detectability and boundedness of the cost function, a prediction horizon length was determined to ensure stability. In [START_REF] Van Essen | Nonlinear model predictive control for constrained mobile robots[END_REF], the authors relaxed the restrictive terminal constraint by using a timevarying (exponential) weighted matrix to ensure stability. It was not sufficient to guarantee the full-state control from any initial configuration. In all the aforementioned papers, the control horizon was chosen equal to the prediction horizon. Nevertheless the control horizon plays a crucial role by providing a sequence of controls, similar to a manoeuvre, to drive the nonholonomic vehicle to its desired position. The question is to know how many controls are needed and therefore what is the minimal length of the control horizon N c sufficient to make the NMPC feasible? The objective of this paper is to point out and illustrate how the control horizon can be appropriately chosen in order to guarantee the feasibility of the predictive control for chained systems. We establish a relationship between the degree of nonholonomy and the minimum length of the control horizon. This necessary condition of NMPC feasibility is theoretically proved whatever the dimension of the chained system considered.

The paper is organized as follows: section II is devoted to a brief recap of NMPC design, nonholonomic vehicles and chained systems. In section III, the problem is stated: how can we determine the minimal control horizon N c that will ensure the NMPC feasibility ? A necessary condition on N c is given for the state feedback control of chained systems. In section IV, the NMPC design is detailed. In section V, simulations on a (2,5) chained system, describing a car vehicle with one trailer, highlight the decisive role of the control horizon. Constraints on state and control variables are also taken into account. Conclusions are finally given.

II. BACKGROUND

A. NMPC

The control objective is usually to steer the state to the origin or to an equilibrium state. A suitable change of coordinates transforms the second problem into the first which, therefore, we consider in the sequel. Consider the state x at the time k, the cost function is defined by:

J(x, u) = k+N p ∑ j=k L(x( j), u( j)) + F(x(k + N p )) (1)
where L is a quadratic function and x(k + N p )) is a terminal constraint added to ensure the stability of the closed-loop system. The classical NMPC formulation can be written as follows: min

u J(x, u). ( 2
)
The cost function J is minimized over the prediction horizon N p with respect to the control sequence. The control sequence u = u(k), u(k + 1), ..., u(k

+ N c ), ..., u(k + N p -1) is composed of N c different controls where N c is the control horizon. From u(k + N c + 1) to u(k + N p -1)
, the inputs are constant and equal to u(k + N c ). Only the first element of the computed optimal sequence of controls is really applied to the process. At the next sampling instant, the prediction horizon moves one step forward and the whole procedure is repeated with the updated measurements.

The main advantage of NMPC is its ability to handle constraints. Constraints on states, inputs or outputs can easily and explicitly be added to the optimization problem (2).

B. Modeling of nonholonomic vehicles

This section recalls some properties of nonholonomic vehicles. For notions on Lie algebras and differential geometry, see [START_REF] Warner | Foundations of differential manifolds and Lie groups[END_REF], [START_REF] Nijmeijer | Nonlinear Dynamical Control Systems[END_REF].

Wheeled robots are characterized by non completely integrable velocity constraints resulting from the rolling without slipping assumption < a i (z), ż >= 0, i = 1, • • • , q, where z ∈ N is the configuration of the vehicle in an n differentiable manifold N, and the a i 's are assumed smooth and independent [START_REF] De Wit | Nonlinear feedback control[END_REF]. Nonholonomic vehicles can hence be modeled by a kinematic driftless control system:

ż = m ∑ i=1 u i Z i (z), z(0) = z 0 ( 3
)
where m = nq < n, z 0 is the initial configuration, the u i 's denote control variables and the Z i 's are smooth independent vector fields over N. The solution at time t of (3) is denoted:

z(t) = e t m ∑ i=1 u i Z i (z 0 ). (4)
Let Z (N) be the Lie algebra of all vector fields on N and

g = L (Z 1 , • • • , Z m )
the Lie subalgebra of Z (N) generated by the vector fields Z 1 , • • • , Z m . We assume that system (3) satisfies the Lie algebra rank condition on N:

dim(span{Z(z) : X ∈ L (Z 1 , • • • , Z m )}) = n. ( 5
)
Under assumption ( 5), Chow's theorem implies that system (3) is controllable [START_REF] Nijmeijer | Nonlinear Dynamical Control Systems[END_REF].

In order to classify nonholonomic systems, we recall the concept of nonholonomic degree defined in [START_REF] Gershkovich | Nonholonomic manifolds and nilpotent analysis[END_REF].

Definition 1 Let g 1 = span{Z 1 , • • • , Z m } and recursively g k = g k-1 + [g 1 , g k-1 ], k ≥ 2 where [g 1 , g k-1 ] = span{[X,Y ] : X ∈ g 1 ,Y ∈ g k-1 }.
Assuming the system is regular, we define the degree of nonholonomy as p = min{i ∈ N : g i = g}.

The degree of nonholonomy is an image of the difficulty in controlling the system. Since the longer the Lie bracket is, the more difficult it is to move in its direction, the difficulty is the greatest when moving in the direction of the vector fields that belong to g\g p-1 . This degree is an intrinsic property of the system, i.e. it does not depend on the coordinate system the control is written in.

Concerning the kinematic modeling of a wide class of wheeled robots, such as a unicycle with n -3 trailers, [START_REF] Sørdalen | Conversion of the kinematics of a car with n trailers into a chained form[END_REF] gives a feedback change of coordinates (z,

u 1 , u 2 ) → (x, v, w) converting system (3) in natural coordinates (i.e. defined on SE(2) × M with M denoting a (n -3)-dimensional manifold) into a (2, n) chained form, which is a particular case of system (3).
Definition 2 A (2, n) chained system is a kinematic system in the form (3) with two control inputs and the following vector fields:

   ẋ = X 1 (x)v + X 2 w, x = (x 1 , • • • , x n ) ∈ R n X 1 = (1, 0, x 2 , • • • , x n-1 ) X 2 = (0, 1, 0, • • • , 0) (6)
The degree of nonholonomy of system ( 6) is p = n -1.

Example 1 Let us illustrate the modeling of a nonholonomic vehicle in a chained form. The car-like vehicle is commonly expressed in natural coordinates, i.e. it is modeled by system

(3) with configuration z = (x c , y c , θ , φ ) ∈ SE(2) × (-π 2 , π 2
), and vector fields given by:

Z 1 (z) = (cos θ , sin θ , tan φ l , 0), Z 2 = (0, 0, 0, 1). ( 7
)
(x c , y c , θ ) denotes the location of the rear wheels and orientation, and φ , l are respectively the front steering angle with respect to the car's body and the wheelbase. The kinematics of the car are given by system (3) with control vector fields [START_REF] Closkey | Exponential stabilization of driftless nonlinear control systems using homogeneous feedback[END_REF] where u 1 , u 2 are the linear and steering velocities of the vehicle. The car-like vehicle can be written in chained form [START_REF] Pomet | Explicit design of time-varying stabilizing control laws for a class of controllable systems without drift[END_REF] as:

x =     x c tan φ l cos 3 θ tan θ y c     , v w = u 1 cos θ u 2 l cos 3 θ cos 2 φ + 3 tan 2 φ l 2 sin θ u 1 cos 4 θ . (8)
We thus obtain the system (6) on the (2, 4) chained form, nilpotent of order 3, defined on the Lie group N = R 4 , with vector fields:

X 1 (x) = (1, 0, x 2 , x 3 ) X 2 = (0, 1, 0, 0). ( 9
)
Note that the feedback (8) induces a singularity, since it is clear that defining the control input w as well as tan θ in the state x requires that θ ∈ (-π 2 , π 2 ).

III. PROBLEM STATEMENT AND MAIN RESULT

A. Problem Statement

Problem 1 Let N c denote the control horizon of a predictive control law and (v, w) ∈ R2 , the control input of system [START_REF] Pomet | Explicit design of time-varying stabilizing control laws for a class of controllable systems without drift[END_REF]. Consider a piecewise constant control family {v k , w k } k≤N c over N c sampling periods T e . With notations of section II-B, let:

s : ν → x f = e Y Nc • • • • • e Y 2 • e Y 1 • x 0 ( 10
)
where Y k (x) = T e (X 1 (x)v k + X 2 w k ) and ν = ( ṽ, w) is the con- trol sequence with ṽ = (v 1 , • • • , v N c ) and w = (w 1 , • • • , w N c ).
What is the minimal control horizon N c such that there exists a control sequence ν solving equation [START_REF] Morin | Control of nonholonomic mobile robots based on the transverse function approach[END_REF] for any desired final configuration x f , i.e. such that s is surjective?

Solving Problem 1 is not always simple. Since the vector fields of system ( 6) are left-invariant1 on a Lie group, then equation ( 10) can be expressed as a product of exponentials, whose direct calculation is provided either using the Campbell-Hausdorff formula or using the group operation 2 of the Lie group. For more generic systems in the form (3), producting the exponentials using the Campbell-Hausdorff formula will result in an infinite number of bracketings. If possible, it is thus preferable to feedback nilpotentize system (3) in order to avoid errors induced by the truncation of brackets longer than a given order [START_REF] Hermes | Nilpotent bases for distributions and control systems[END_REF]. Note however that feedback nilpotentization may induce singularities, thus limitating reachable points for a given control horizon. Firstly, the goal in NMPC is not explicitly to regulate to zero the error between the reference and the model output configuration obtained by applying N c control steps, but rather to minimize a weighted sum of errors over a prediction horizon N p ≥ N c . Secondly, the handling of constraints either on the control inputs and/or on the states may reduce the set of solutions. Restrictions imposed using a NMPC approach thus result in relaxing the sufficient and necessary condition for solving the theoretical Problem 1 into a necessary condition, in practice, for solving the NMPC optimization problem formulated in the next section.

B. Solution to Problem 1 for chained systems

Let us discuss the case N c = p = n-1, where s is surjective for any motion along g p-1 \g p-2 , but is no longer surjective on g\g p-1 . This lack of solution is due to the nilpotentization, which is illustrated hereinafter by the significant example of the car in natural coordinates, and therefore should not be regarded as an intrinsic property of the system, but rather as a consequence of the choice of the coordinate system the nonholonomic system is written in.

Remark 3 Any translation along g\g 2 , corresponding to a pure transversal motion (along

X 4 = [X 1 , [X 1 , X 2 ]] = (0, 0, 0, 1)
), is clearly feasible by a car-like vehicle modeled by system (3) with vector fields [START_REF] Closkey | Exponential stabilization of driftless nonlinear control systems using homogeneous feedback[END_REF] and N c = p = 3, but it requires that the orientation reach values forbidden by the nilpotentization (8) (namely θ = ± π 2 ). That is why this motion is impossible to achieve for the car modeled in the chained form [START_REF] Pomet | Explicit design of time-varying stabilizing control laws for a class of controllable systems without drift[END_REF] with N c = 3. The same problem was reported in [START_REF] Lafferriere | A general strategy for computing steering controls of systems without drift[END_REF] using the nilpotent approximation of the unicycle. Nevertheless, it should be noted that any motion along g 2 \g 1 (along X 3 = [X 1 , X 2 ] = (0, 0, -1, 0)), i.e. a pure rotation around the location of the rear wheels, can be achieved with N c = 3, whatever the coordinate system the car-like vehicle is written in.

IV. NMPC DESIGN FOR STATE FEEDBACK CONTROL OF CHAINED SYSTEMS

The NMPC framework is now described in detail. ) is chosen to take into account modeling errors and disturbances [START_REF] Morari | Robust control[END_REF]. The tracking of the reference trajectory y re f by the process output y p is equivalent to the tracking of the desired trajectory y d by the model output y m . At time t = kT e where the sampling period is T e = 1s, the desired trajectory is defined by

y d (k) = y re f (k) -ε(k).
The signal error ε(k) = y p (k)y m (k) includes modeling errors and measurement noises. The error is assumed to be constant over the prediction horizon but is updated at each new measurement. 2) The model has to predict the process behavior over the prediction horizon.

ẋ(t) = X 1 (x(t))v(t) + X 2 w(t) , x(0) = x 0 y m (k + j | k) = x((k + j)T e ). (11)
The variables x ∈ R n , (v, w) ∈ R 2 and y m ∈ R n are respectively the state, the input and the output of the model. The output is sampled at each T e and the computed input is kept constant over a sampling period:

∀ j ∈ [1; N p ], v(t) = v(k + j -1 | k) for (k + j -1)T e < t < (k + j)T e , w(t) = w(k + j -1 | k) for (k + j -1)T e < t < (k + j)T e . ( 12
)
The model output y m (k), needed for the prediction, is initialized with the updated measure of the process output y(k) that guarantees an implicit feedback of the IMC structure.

3) The quadratic function L (1) is defined as:

L = [y d(k+ j|k) -y m(k+ j|k) ] T Q ( j) [y d(k+ j|k) -y m(k+ j|k) ] (13)
where Q ( j) is a symmetric definite positive matrix. 4) The prediction horizon N p should satisfy a compromise between closed-loop stability (long horizon) and numerical feasibility in terms of computational time required (short horizon). If N p tends to infinity, the control problem becomes an optimal control known to ensure closedloop stability [START_REF] Camacho | Nonlinear model predictive control: An introductory review[END_REF]. 5) The control horizon N c plays a crucial role by proposing N c different controls at time k comparable to a manoeuvre. According to Proposition 1, the control horizon will be chosen equal to or greater than the degree of nonholonomy of the chained system: N c ≥ p + 1. 6) The time-varying matrix Q( j) weights the tracking error at each iteration more and more over the prediction horizon. It reinforces the role of the terminal constraint. Giving a heavy weight at the end of N p , which corresponds to the final objective, makes the NMPC problem (2) tend to the theoretical Problem 1. The time variation of the weighted matrix Q( j) is given by:

Q( j) = αQ( j -1), with α ≥ 1. ( 14
)
7) The resolution method: a sequential quadratic programming (SQP) is used (function fminunc from Matlab optimization toolbox) to solve the optimization problem ( 2) with ( 11)-( 14). We have deliberately chosen a standard algorithm to show that the efficiency of the NMPC for full-state control is due to the control horizon and does not depend on the optimization algorithm.

V. SIMULATIONS

We first illustrate the role of N c as a necessary condition for the state feedback of chained systems without constraints. We consider a (2, 5) chained system, described by the following vector fields:

X 1 (x) = (1, 0, x 2 , x 3 , x 4 ), X 2 = (0, 1, 0, 0, 0). (15)
The degree of nonholonomy is given by p = n -1 = 4. The prediction horizon and the control horizon were respectively set to N p = 10 and N c = 5. The time variation of Q( j) is given by ( 14) with α = 5 and Q(1) = I. We study the particular case where the initial state is (0, 0, 0, 0, 1) and the desired one is (0, 0, 0, 0, 0), corresponding to the difficult motion that requires a lateral displacement. With N c < 5, the final position is not reached. With N c = 5, in accordance with Proposition 1, the control strategy is able to determine a control sequence such that the fullstate converges to the desired state (see Fig. 2(a) and 2(e)). Constraints handling is one of the advantages of NMPC design. In simulation 2, the control inputs of the (2,5) chained system are constrained to ±2. We can notice that the convergence is still obtained while the control constraints are satisfied (see Fig. 2(b) and 2(f)). The time of convergence is a bit longer and the amplitude of the state evolution is also greater. In Fig. 2(c) and 2(g), the state variables are also constrained to ±4. The control objective is always achieved. From a different initial state (0.2, -0.6, 0.25, -0.3, 0.5), the control strategy finds a control sequence satisfying the same constraints and the task (see Fig. 2(d) and 2(h)).

Remark 4 For all the presented simulations performed on a PC intel Core 2 duo, 3.06 GHz under Matlab, the computational time required to solve the optimization problem was about 2 seconds. This computational time is composed of the Matlab function call, the differential equations and the optimization solving. The over-all computational time can be greatly reduced by using a discrete-time model of the mobile robot (simulations have already been performed and required 50ms) and by using a more efficient minimization algorithm. It is worth mentioning that the computational load relative to the usual choice of N c = N p is divided by 3 approximately by using the appropriate choice of N c = p + 1.

VI. CONCLUSION

An NMPC strategy has been applied to the state feedback control of chained systems. From a theoretical point of view, we have established a necessary condition on the length of the control horizon to ensure the NMPC feasibility. To achieve this, we have combined tools from differential geometry with NMPC approach. The link to the degree of nonholonomy provides a useful lower bound for the control horizon. Based on differential geometry, the proof of the necessary condition is given whatever the dimension of the chained system. From a practical point of view, the appropriate choice of the control horizon makes it possible to optimize the computational time. The theoretical results were illustrated on a car-like vehicle with one trailer, modeled by a chained system.

APPENDIX PROOF OF PROPOSITION 1

Proof: The proof consists in four steps. The first step aims at reformulating the Problem 1 using the properties of the (2, n) chained systems. The second and third steps are devoted to the study of cases where s( ν) = e X (0), X ∈ g\g 1 and s( ν) = e X (0), X ∈ g\g N c -2 , that is motions in the direction of vector fields of increasing length, and thus of increasing difficulty. The last step concludes the proof. 1) First, we can make the Problem 1 more explicit for the (2, n) chained system. The nilpotent algebra generated by the vector fields of (6) underlies the following group operation on the Lie group N = R n :

xy = exp (Ay 1 )x + y (A.16)
where A is the square matrix of dimension n which nonzero entries are only a i+1,i = 1, ∀i ≥ 2.

Since the vector fields of system ( 6) are left-invariant with respect to the group operation given by (A. [START_REF] Nijmeijer | Nonlinear Dynamical Control Systems[END_REF]), [START_REF] Morin | Control of nonholonomic mobile robots based on the transverse function approach[END_REF] can be expressed as a product:

s : ν → x f = x 0 e Y 1 (0)e Y 2 (0) • • • e Y Nc (0) (A.17)
with 0 denoting the identity element of N = R n . As the final configuration x f is any element of N, the initial condition can be set to x 0 = 0 without loss of generality. Thus (A.17) becomes s : ν

→ x f = x(1)x(2) • • • x(N c ),
where x( j) = e Y j (0) is the solution of equation ( 6) for the j th control input pair (v j , w j ) and initial condition 0. Let T e = 1s so as not to burden notations, then using direct integration of ( 6), we get:

x( j) = v j , w j , v j w j 2 , • • • , v n-2 j w j (n-1)! . (A.18)
Using the group operation (A.16) on R n , the solution to a succession of N c iterations is thus given by:

s( ν) = N c ∏ j=1 x( j) = N c -1 ∑ j=1 exp A N c ∑ i= j+1 v i x( j) + x(N c )
Using (A.18) in the previous equation leads to: with, ∀i ≤ n -2, ∀ j ≤ N c -1, coefficients of B given by: bi

s( ν) =   1 • • • 1 0 • • • 0 0 • • • 0 1 • • • 1 0 n-2,N c B( ν)   ν, (A.19) with matrix B elements b i,N c = v i N c /(i + 1)! and b i, j = i ∑ r=0 N c ∑ q= j+1 v q i-r v r j (i -r)!(r + 1)! , ∀ j ≤ N c -1. (A.20) 2) If s( ν) = e X (
, j = (-1) i+1 ( N c -1 ∑ r=1 v r ) i - i ∑ q=0 i+1 q v i-q j ( j-1 ∑ r=1 v r ) q (i + 1)! . (A.22) Using (A.22), we get N c -1 ∑ j=1
v j bi, j = 0, ∀i, and (A.21) gives:

(s 3 , . . . , s n )( ν) = D( ν) λ , (A.23)
where D denotes the N c -2 first columns of B, and

λ = (λ 1 , . . . , λ N c -2 ) with λ j = w j -v j w N c -1 /v N c -1 .
3) We will now show that, with a control sequence of length N c , having s( ṽ) = e X (0) with

X ∈ g\g N c -2 implies that s N c (•) divides s N c +1 (•), • • • , s n (•).
Let s( ṽ) = e X (0) with X ∈ g\g N c -2 . We have s i (•) = 0, ∀i ≤ N c -1 and (A.23) can be decomposed as:

     0 1,N c -3 s N c . . . s n      ( ν) =      C E bN c ,1 R N c . . . . . . bn,1 R n      ( ν) λ , (A.24)
where the matrix D is partitioned in blocks C, R N c +q and E respectively denote (N c -3) column and raw vectors and a (N c -3) × (N c -3) matrix. Using the Schur complements for s N c +q (•), ∀q = 0, • • • , n -N c , we get:

s N c +q (•) = ( bN c +q,1 -R N c +q E -1 C)λ 1 . (A.25)
With the block matrix F N c +q defined by: The determinants in the latter equation are determined using a LU decomposition with a unit triangular matrix L.

F N c +q = C E bN c +q,1 R N c +q , (
Let F N c +q = L N c +q U N c +q , then the diagonal matrix U n c +q coefficients are given using (A.22):

U i,i =        (-1) i+1 (i+1)! N c -1 ∑ j=i+1 v j i-1 ∏ j=1 i ∑ r= j v r , if i ≤ N c -3 (-1) Nc-1 (N c -1)! v Nc-1 N c -3 ∏ j=1 N c -2 ∑ r= j v r P N c ,q , if i = N c -2
(A.28) with P N c ,q given by: P N c ,q = (-1) q (N c -1)! such that |I| = q, i.e. for every I j such that (A.32) As P N c ,0 = 1, the equation (A.32) implies that s N c +q ( ṽ) = s N c ( ṽ)P N c ,q ( ṽ), ∀q = 1, • • • , (n -N c ). (A.33)

Consequently, s( ṽ) = e X (0) with X ∈ g\g N c -1 will involve that s( ṽ) = 0. Hence, s is not surjective for N c ≤ p = n-1. 4) For N c = p + 1 = n, s( ṽ) = e X (0) with X ∈ g\g p-1 will have solutions provided that the numerator in (A.32) is not null, that is if v N c -1 = 0 and no sum of strictly less than N c -2 successive controls v i is null. As a result, s is surjective for N c = p + 1.

Proposition 1 Remark 1 Remark 2

 112 Solving Problem 1 for any (2, n) chained system[START_REF] Pomet | Explicit design of time-varying stabilizing control laws for a class of controllable systems without drift[END_REF] generically requires a control horizon N c = p+1 = n.The detailed proof is given in Appendix. Proposition 1 gives a sufficient and necessary condition on N c for the wide class of nonholonomic vehicles modeled by the (2, n) chained form, so as to ensure the existence of solutions to Problem 1 given arbitrary initial and final configurations. In the scope of optimization-based control, there are slight differences with the formulation of Problem 1.

  Fig. 1. Control Structure 1) The Internal Model Control (IMC) structure (see Fig.1) is chosen to take into account modeling errors and disturbances[START_REF] Morari | Robust control[END_REF]. The tracking of the reference trajectory y re f by the process output y p is equivalent to the tracking of the desired trajectory y d by the model output y m . At time t = kT e where the sampling period is T e = 1s, the desired trajectory is defined byy d (k) = y re f (k) -ε(k).The signal error ε(k) = y p (k)y m (k) includes modeling errors and measurement noises. The error is assumed to be constant over the prediction horizon but is updated at each new measurement.

1

 1

x 2 x 3 x 4 x 5 (x 2 x 3 x 4 x 5 (1 x 2 x 3 x 4 x 5 (1 x 2 x 3 x 4 x 5 ( 4 :

 55554 Control inputs.

Fig. 2 .

 2 Fig. 2. States and control variables of the chained system. Simulation 1: without constraints. Simulation 2: with control constraints. Simulations 3 and 4: with state and control constraints.

  A.26) the equation (A.25) leads to:s N c +q = det F N c +q (-1) N c -3 det E λ 1 .(A.27)

  is done for multiindex I = (I 1 , • • • , I N c -1 )

N c - 1 ∑(

 1 j=1I j = q.Combining (A.28) and (A.29), we finally obtain: det F N c +q = Nc,q .(A.30) In the same way, we obtain det E: det E =(-1)

( 1 N

 1 A.31) Using (A.30) and (A.31), (A.27) is simplified as:s N c +q (•) = (-1) Nc-1 v Nc-j ) P N c ,q λ 1 (N c -1)! N c -3 c -r ).

A system is left-invariant if its vector fields are left-invariant, i.e. if dL σ (τ) • X(τ) = X(L σ (τ)) with L denoting the left-translation operator: L σ (τ) = σ τ.

Note that, in general, the group operation may be difficult to determine explicitly.

ACKNOWLEDGMENT

The authors are very grateful to Pascal Morin for his helpful advices.