Agostino Martinelli

Nonlinear Unknown Input Observability: The Analytic Solution in the case of a Single Unknown Input

Keywords: Nonlinear observability, Unknown Input Observability, Observability Rank Condition, Observable Codistribution, Robotics Applications observabilité non linéaire, Observabilité avec entrées inconnues, Applications dans la robotique

This work presents the analytic solution of a fundamental open problem in the framework of nonlinear observability, which is the unknown input observability problem (UIO problem). The solution here provided holds in the case of a single unknown input. The first part of the work presents this analytic solution, namely the analytic criterion that allows us to obtain the observability of a nonlinear system in presence of a single unknown input and multiple known inputs. As for the observability rank condition, the proposed analytic criterion is based on the computation of the observable codistribution. Similarly to the case of only known inputs, the observable codistribution is obtained by recursively computing the Lie derivatives of the outputs along the vector fields that characterize the dynamics. However, in correspondence of the unknown input, the corresponding vector field must be suitably rescaled. Additionally, the Lie derivatives of the outputs must also be computed along a new set of vector fields that are obtained by recursively performing suitable Lie bracketing of the vector fields that define the dynamics. In practice, the entire observable codistribution is obtained by a very simple recursive algorithm. Finally, it is shown that the recursive algorithm converges in a finite number of steps and the criterion to establish that the convergence has been reached is provided. The proposed analytic extension of the observability rank condition is illustrated by checking the weak local observability of several nonlinear systems driven by multiple known inputs and a single unknown input. For these systems, extensive simulations are also provided. It is shown that, a simple estimator based on an Extended Kalman Filter, provides results that agree with what we could expect from the observability analysis. Finally, it is shown that the analytic criterion introduced in this work is not only a key analytical tool to automatically obtain the state observability but it can be also a fundamental tool to design an appropriate estimator.

Introduction

State observability is a necessary condition that a state must satisfy to be estimated. Checking the system observability is a fundamental step in state estimation. It has become praxis in many application fields to provide an observability analysis prior to solving an estimation problem (e.g., in robotics [START_REF] Bryson | Observability analysis and active control for airborne SLAM[END_REF][START_REF] Huang | Analysis and improvement of the consistency of extended Kalman filter based SLAM[END_REF][START_REF] Huang | Observability-based Rules for Designing Consistent EKF SLAM Estimators[END_REF][START_REF] Huang | A Quadratic-Complexity Observability-Constrained Unscented Kalman Filter for SLAM[END_REF][START_REF] Lee | On the Observability and Observability Analysis of SLAM[END_REF][START_REF] Perera | On the linear and nonlinear observability analysis of the SLAM problem[END_REF][START_REF] Trawny | Observability-based Consistent EKF Estimators for Multi-robot Cooperative Localization[END_REF][START_REF] Vidal-Calleja | On the Observability of Bearing-only SLAM[END_REF][START_REF] Wang | Observability analysis of SLAM using fisher information matrix[END_REF], in visual-inertial sensor fusion [START_REF] Hesch | Towards consistent visionaided inertial navigation[END_REF][START_REF] Hesch | Camera-IMU-based Localization: Observability Analysis and Consistency Improvement[END_REF][START_REF] Hesch | Consistency Analysis and Improvement of Vision-aided Inertial Navigation[END_REF][START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF][START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensorto-sensor self-calibration[END_REF][START_REF] Kottas | On the consistency of vision-aided inertial navigation[END_REF][START_REF] Li | Improving the accuracy of EKF-based visualinertial odometry[END_REF][START_REF] Martinelli | Vision and IMU data fusion: closed-form solutions for attitude, speed, absolute scale and bias determination[END_REF][START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF][START_REF] Mirzaei | A Kalman filter-based algorithm for IMU-camera calibration: Observability analysis and performance evaluation[END_REF][START_REF] Panahandeh | Observability Analysis of a Vision-Aided Inertial Navigation System using Planar Features on the Ground[END_REF], in sensor calibration [START_REF] Censi | Simultaneous calibration of odometry and sensor parameters for mobile robots[END_REF][START_REF] Chao | IMU-RGBD Camera 3D Pose Estimation and Extrinsic Calibration: Observability Analysis and Consistency Improvement[END_REF][START_REF] Li | Online Temporal Calibration for Camera-IMU Systems: Theory and Algorithms[END_REF][START_REF] Martinelli | Automatic Self-Calibration of a Vision System during Robot Motion[END_REF][START_REF] Mirzaei | 3D Lidar-Camera Intrinsic and Extrinsic Calibration: Observability Analysis and Analytical Least Squares-based Initialization[END_REF]). Investigating the observability properties is very simple in the linear case. Unfortunately, real systems are very rarely characterized by linearity.

The control theory community has developed the analytic tool necessary to check the state observability for nonlinear systems provided that all the system inputs are known. This is the observability rank condition introduced by Herman and Krener in 1977 [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF]. In accordance with this criterion, it is possible to derive all the observability properties of a nonlinear system by performing automatic computation. On the other hand, in many real scenarios, one or more disturbances can dramatically impact the system dynamics. A disturbance can be considered as an unknown input. Its presence can dramatically affect the observability properties of the state. This is for instance the case of a drone that operates in presence of wind. The wind is in general unknown, time-variant and acts on the system dynamics as an unknown input.

The problem of deriving an analytic tool able to determine the observability properties in presence of unknown inputs is known as the Unknown Input Observability (UIO) problem. This problem was introduced and firstly investigated by the automatic control community in the seventies [START_REF] Basile | On the observability of linear, time invariant systems with unknown inputs[END_REF][START_REF] Bhattacharyya | Observer design for linear systems with unknown inputs[END_REF][START_REF] Guidorzi | On Wonham stabilizability condition in the synthesis of observers for unknown-input systems[END_REF][START_REF] Wang | Observing the states of systems with unmeasurable disturbance[END_REF]. In particular, Basile and Marro provided the solution of this problem in the linear case [START_REF] Basile | On the observability of linear, time invariant systems with unknown inputs[END_REF]. In many application fields, most of the systems are characterized by nonlinear dynamics, even in very simple cases (e.g. in planar robotics). Additionally, the presence of disturbances cannot be ignored in many cases and can significantly affect the observability properties. The UIO problem in the nonlinear case has recently been investigated by the robotics community and partial solutions have recently been proposed [START_REF] Belo | 3 Known Landmarks are Enough for Solving Planar Bearing SLAM and Fully Reconstruct Unknown Inputs[END_REF][START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF][START_REF] Martinelli | Minimalistic sensor design in visual-inertial structure from motion[END_REF][START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF]. These solutions only provide sufficient conditions for the state observability. They are based on a suitable state extension.

This work provides the analytic solution of the UIO problem in the nonlinear case in the case of a single unknown input. This solution has been presented at the SIAM symposium on control and applications 2015 [START_REF] Martinelli | Nonlinear Unknown Input Observability: Analytical expression of the observable codistribution in the case of a single unknown input[END_REF]. In section 2 we define the class of systems for which we provide the solution. This class includes any nonlinear system linear in the inputs (both known and unknown).

In [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF][START_REF] Isidori | Nonlinear Control Systems[END_REF] the observability properties of a nonlinear system are obtained by computing the observable codistribution. The computation of this codistribution is the core of the observability rank condition introduced in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF]. In order to deal with the case of unknown inputs, we need to derive a new algorithm able to generate the observable codistribution. In section 3 we remind the reader the algorithm to compute the observable codistribution in the case without disturbances, together with some basic properties that characterize its convergence (section 3.1). Then, in section 3.2, we introduce the new algorithm that generates the entire observable codistribution in presence of a single unknown input, together with some basic properties that characterize its convergence. The solution of the UIO problem in the case of a single unknown input is summarized in section 4 and it is illustrated in section 5 by checking the observability of several robotics systems driven by multiple known inputs and a single unknown input, ranging from planar robotics up to aerial navigation systems. This section also contains extensive simulations and introduces a simple estimator. The results obtained by estimating the state with this estimator fully agree with the observability analysis carried out by using the proposed analytic criterion. In section 6 we provide all the analytical derivations necessary to prove the validity of the analytic results presented in section 3. In section 7 we provide our conclusion by remarking that, the analytic criterion here introduced, is not only a powerful and simple criterion to automatically detect the observable states for a general nonlinear system affected by a disturbance (i.e., the analytic solution of the UIO problem in the case of a single unknown input) but it can be also a key tool for designing an appropriate estimator.

Inria 2 System definition

We will refer to a nonlinear control system with m u known inputs (u [u 1 , • • • , u mu ] T ) and a single unknown input or disturbance (w). The state is the vector x ∈ M , with M an open set of R n . We assume that the dynamics are nonlinear with respect to the state and affine with respect to the inputs (both known and unknown). Finally, for the sake of simplicity, we will refer to the case of a single output y and we provide the extension to multiple outputs, which is trivial, separately. This will allow us to avoid the introduction of a further index. Our system is characterized by the following equations:

     ẋ = mu i=1 f i (x)u i + g(x)w y = h(x) (1)
where f i (x), i = 1, • • • , m u and g(x) are vector fields in M and the function h(x) is a scalar function defined on the open set M . Finally, we assume that the unknown input w is an analytic function of time. Throughout this document, in the case when m u = 1, we denote by f (x) the vector field f 1 (x).

Observable Codistribution

As for the observability rank condition, the analytic criterion to obtain the observability properties of the system in [START_REF] Basile | On the observability of linear, time invariant systems with unknown inputs[END_REF], is obtained by computing the observable codistribution 1 . In this section we provide the algorithm to compute this codistribution. For the clarity sake, we start by reminding the reader the standard algorithm that generates the observable codisribution in absence of unknown inputs (section 3.1). Then, in section 3.2, we provide the algorithm for the system in [START_REF] Basile | On the observability of linear, time invariant systems with unknown inputs[END_REF].

Note that this section directly provides the analytic results. All the analytic proofs will be provided later, in section 6.

Observable codistribution in the case without unknown inputs

We consider the system in (1) when all the inputs are known. We will denote with the symbol D the differential with respect to the state x. For instance, if x = [x 1 , x 2 ] T and h = x 1 + x 2 2 , we have 2 :

Dh = Dx 1 + 2x 2 Dx 2 .
For a given codistribution Ω and a given vector field θ = θ(x) (both defined on the open set M ), we denote by L θ Ω the codistribution whose covectors are the Lie derivatives along θ of the covectors in Ω. We remind the reader that the Lie derivative of a scalar function h(x) along the vector field f (x) is defined as follows:

L f h ∂h ∂x f
which is the product of the row vector ∂h ∂x with the column vector f . Hence, it is a scalar function. Additionally, by definition of Lie derivative of covectors, we have:

L f Dh = DL f h.
Finally, given two vector spaces V 1 and V 2 , we denote by V 1 + V 2 their sum, i.e., the span of all the generators of both V 1 and V 2 .

The observable codistribution is generated by the following recursive algorithm (see [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF] and [START_REF] Isidori | Nonlinear Control Systems[END_REF]):

Algorithm 1 Observable codistribution when w is known

1. Ω 0 = span{Dh}; 2. Ω m = Ω m-1 + mu i=1 L f i Ω m-1 + L g Ω m-1
In presence of multiple outputs, we only need to add to the codistribution Ω 0 , the span of the differentials of the remaining outputs. In [START_REF] Isidori | Nonlinear Control Systems[END_REF] it is proven that this algorithm converges. In particular, it is proven that it has converged when Ω m = Ω m-1 . From this, it is easy to realize that the convergence is achieved in at most n -1 steps 3 . 1 The reader non-familiar with the concept of distribution, as it is used in [START_REF] Isidori | Nonlinear Control Systems[END_REF], should not be afraid by the term distribution and the term codistribution. Very simply speaking, a distribution is a vector space defined on M (our set in R n where the system is defined). In particular, this vector space changes by moving on M . This vector space is in fact the span of a set of vector functions (vector fields) defined on M . A codistribution is the dual of a distribution. Very simply speaking (and this is enough to understand this manuscript) a distribution is generated by a set of column vectors. A codistribution is generated by a set of line vectors. All these vectors are vector functions (i.e., they depends on the point x ∈ M ) and they have the same dimension of x. 2 The span of the differentials of a set of scalar functions is a codistribution. The reader non familiar with the theory of distributions can simply consider the differential as the gradient operator. The gradient of a scalar function is a line vector. For instance, if x = [x 1 , x 2 ] T and h = x 1 + x 2 2 , we obtain for its gradient the line vector function [1, 2x 2 ]. Later, in section 5, we adopt this representation. According to this, a codistribuion will be the span of a set of line vectors and a covector (i.e., an element of a codistribution) will be a line vector.

3 This is a consequence of lemmas 1.9.1, 1.9.2 and 1.9.6 in [START_REF] Isidori | Nonlinear Control Systems[END_REF].

Inria

Observable codistribution in presence of a single unknown input

We now provide the new algorithm that generates the observable codistribution when w is an unknown input. We will denote by L 1 g = L 1 g (x) the first order Lie derivative of the function h(x) along the vector field g(x), i.e.,

L 1 g L g h (2)
The analytic computation of the observable codistribution is based on the assumption that L 1 g = 0 on a given neighbourhood of x 0 . In appendix A, we deal with the case when this condition is not satisfied. Specifically, we show that it is either possible to redefine the output, without altering the system observability properties, such that the Lie derivative of the new output along g does not vanish or the unknown input is spurious (i.e., it does not affect the observability properties). For these reasons, we can assume that L 1 g = 0. Before introducing the new algorithm that generates the entire observable codistribution, we introduce a new set of vector fields i φ m ∈ R n (i = 1, • • • , m u and for any integer m). They are obtained recursively by the following algorithm:

Algorithm 2 1. i φ 0 = f i ; 2. i φ m = [ i φm-1, g] L 1 g
where the parenthesis [•, •] denote the Lie bracket of vector fields, defined as follows:

[a, b] ∂b ∂x a(x) - ∂a ∂x b(x)
In other words, for each i = 1, • • • , m u , we have one new vector field at every step of the algorithm. Throughout this document, in the case when m u = 1, we denote by φ m the vector field 1 φ m .

We are now ready to provide the algorithm that generates the entire observable codistribution. It is the following: Algorithm 3 Observable codistribution when w is unknown

1. Ω 0 = span{Dh}; 2. Ω m = Ω m-1 + mu i=1 L f i Ω m-1 + L g L 1 g Ω m-1 + mu i=1 span Li φm-1 Dh
In presence of multiple outputs, we only need to add to the codistribution Ω 0 , the span of the differentials of the remaining outputs. Note that, in presence of multiple outputs, the function L 1 g is still a scalar function since it is still defined by using a single output. The result is independent of the chosen output (provided that L 1 g does not vanish 4 ). In section 6.2.2 we investigate the convergence properties of algorithm 3. We consider first the case of a single known input (i.e., m u = 1) and then the results are easily extended to the case of multiple known inputs (m u > 1) in section 6.2.3. We prove that algorithm 3 converges and we also provide the analytic criterion to check that the convergence has been attained. This proof and the convergence criterion cannot be the same that hold for algorithm 1, because of the last term that appears at the recursive step5 , i.e., the term mu i=1 span Li φm-1 Dh (the special case when, the contribution due to this last term is included in the other terms, is considered separately by lemma 6). In general, the criterion to establish that the convergence has been attained is not simply obtained by checking the condition Ω m+1 = Ω m . Deriving the new analytic criterion is not immediate. It requires to derive the analytic expression that describes the behaviour of the last term in the recursive step. This fundamental equation is provided in section 6 and it is the equation [START_REF] Panahandeh | Observability Analysis of a Vision-Aided Inertial Navigation System using Planar Features on the Ground[END_REF]. The analytic derivation of this equation allows us to detect the key quantity that governs the convergence of algorithm 3, in particular regarding the contribution due to the last term in the recursive step. This key quantity is the following scalar:

τ = L 2 g h (L 1 g ) 2 (3)
We prove (see lemma 10 in section 6) that, in general, it exists m such that Dτ ∈ Ω m (and therefore Dτ ∈ Ω m ∀m ≥ m ). Additionally, we prove that the convergence of the algorithm has been reached when Ω m+1 = Ω m , m ≥ m and m ≥ 2 (theorem 2). We also prove that the required number of steps is at most n + 2.

In section 6.2.1 it is also shown that the computed codistribution is the entire observable codistribution. Also in this case, the proof is given by first considering the case of a single known input (see theorem 1) and then, its validity is extended to the case of multiple inputs in section 6.2.3. Note that this proof is based on the assumption that the unknown input (w) is a differentiable function of time, up to a given order (the order depends on the specific case).

Algorithm 3 differs from the standard algorithm 1 because of the following reasons:

• In the recursive step, the vector field that corresponds to the unknown input (i.e., g) must be rescaled by dividing by L 1 g . • The recursive step also contains the sum of the contributions mu i=1 Li φm-1 Dh. In other words, we need to compute the Lie derivatives of the differential of the output along the vector fields obtained through the recursive algorithm 2.

• The convergence of algorithm 3 is achieved in at most n + 2 steps, instead of n -1 steps (in the special case dealt by lemma 6, this upper bound is n -1 for both cases).

• When Ω m = Ω m-1 algorithm 1 has converged. For algorithm 3, we also need to check that Dτ ∈ Ω m and m ≥ 2 (with the exception of the special case dealt by lemma 6).

The Analytic Criterion

In this section, we outline all the steps to investigate the weak local observability at a given point x 0 of a nonlinear system characterized by [START_REF] Basile | On the observability of linear, time invariant systems with unknown inputs[END_REF]. Basically, these steps are the steps necessary to compute the observable codistribution (i.e., the steps of algorithm 3) and to prove that the differential of a given state component belongs to this codistribution. Note that, in the trivial case analyzed by lemma 6, the criterion provided below simplifies, since we do not need to compute the quantity τ = 2 , and we do not need to check that its differential belongs to the codistribution computed at every step of algorithm 3. In practice, we skip the steps 4 and 5 in the procedure below.

L 2 g h (L 1 g h)
1. For the chosen x 0 , compute L 1 g (= L 1 g h). In the case when L 1 g = 0, choose another function in the space of functions F (defined as the space that contains h and its Lie derivative up to any order along the vector fields f 1 , • • • , f mu ) such that its Lie derivative along g does not vanish6 .

2. Compute the codistribution Ω 0 and Ω 1 (at x 0 ) by using algorithm 3.

Compute the vector fields

i φ m (i = 1, • • • , m u ) by using algorithm 2, starting from m = 0,
to check if the considered system is in the special case dealt by lemma 6 7 . In this trivial case, set m = 0, use the recursive step of algorithm 3 to build the codistribution Ω m for m ≥ 2, and skip to step 6.

4. Compute τ = L 2 g h (L 1 g ) 2
and Dτ . 7. If the differential of a given state component (x j , j = 1, • • • , n) belongs to Ω * (namely if Dx j ∈ Ω * ) on a given neighbourhood of x 0 , then x j is weakly locally observable at x 0 . If this holds for all the state components, the state x is weakly locally observable at x 0 . Finally, if the dimension of Ω * is smaller than n on a given neighbourhood of x 0 , then the state is not weakly locally observable at x 0 .

Applications

We apply the criterion described in section 4 in order to investigate the observability properties of several nonlinear systems characterized by the equations given in [START_REF] Basile | On the observability of linear, time invariant systems with unknown inputs[END_REF]. These examples will be discussed in sections 5.1, 5.2 and 5.3. The dynamics of the first two examples are the ones of the unicycle. In accordance with the unicycle dynamics, the motion is powered by two independent controls, which are the linear and the angular speed, respectively. In section 5.1 we consider the case when one of these two inputs is unknown and acts as an unknown input. In section 5.2 we consider the case when both these two inputs are known. However, the dynamics are also affected by an external unknown input. Finally, the last example regards a vehicle that moves in 3D (section 5.3). These examples are deliberately uncomplicated in order to allow us to compare the analytic results provided by the proposed criterion with what we can expect by following intuitive reasoning.

Note that the analytic criterion is very powerful and can be used to automatically obtain the observability properties of any system that satisfies (1), i.e., independently of the state dimension (intuitive reasoning becomes often prohibitive for systems characterized by high-dimensional states).

This section also contains extensive simulations and introduces a simple estimator. The results obtained by estimating the state with this estimator fully agree with the observability analysis carried out by using the proposed analytic criterion. These results also show that the analytic criterion is not only a criterion to check the state observability but also a fundamental tool to design an appropriate estimator for a given nonlinear system in presence of a disturbance (see section 7 for a discussion about this fundamental aspect).

Unicycle with one input unknown

The system

We consider a vehicle that moves on a 2D-environment. The configuration of the vehicle in a global reference frame, can be characterized through the vector [x v , y v , θ] T where x v and y v are the Cartesian vehicle coordinates, and θ is the vehicle orientation. We assume that the dynamics of this vector satisfy the unicycle differential equations:

   ẋv = v cos θ ẏv = v sin θ θ = ω (4)
where v and ω are the linear and the rotational vehicle speed, respectively, and they are the system inputs. We consider the following three cases of output (see also figure 1 for an illustration):

1. the distance (r) from the origin (e.g., a landmark is at the origin and its distance is measured by a range sensor);

2. the bearing angle (β) of the origin in the local frame (e.g., a landmark is at the origin and its bearing angle is measured by an on-board camera);

3. the bearing angle (φ) of the vehicle in the global frame (e.g., a camera is placed at the origin).

Inria We can analytically express the output in terms of the state. We remark that the expressions become very simple if we adopt polar coordinates: r x 2 v + y 2 v , φ = atan yv xv . We have, for the three cases, y = r, y = π -(θ -φ) and y = φ, respectively. For each of these three cases, we consider the following two cases: v is known, ω is unknown; v is unknown, ω is known. Hence, we have six cases. The dynamics of the unicycle in polar coordinates become:

    ṙ = v cos(θ -φ) φ = v r sin(θ -φ) θ = ω (5)

Intuitive procedure to obtain the observability properties

By using the observability rank condition in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF], we easily obtain that, when both the inputs are known, the dimension of the observable codistribution is 2 for the first two observations (y = r and y = θ -φ) and 3 for the last one (y = φ). In particular, for the first two observations all the initial states rotated around the vertical axis are indistinguishable. When one of the inputs misses, this unobservable degree of freedom obviously remains. On the other hand, when the linear speed is unknown (i.e., it acts as an unknown input (w = v)) and the observation is an angle (second and third observation, i.e., y = θ -φ and y = φ, respectively), we lose a further degree of freedom, which corresponds to the absolute scale. In table 1 we provide the dimension of the observable codistribuion obtained by following this intuitive reasoning for the six considered cases.

Case

Dimension of Ω

1 st : y = r, u = ω, w = v 2 2 nd : y = r, w = ω, u = v 2 3 d : y = θ -φ, u = ω, w = v 1 4 th : y = θ -φ, w = ω, u = v 2 5 th : y = φ, u = ω, w = v 2 6 th : y = φ, w = ω, u = v 3
Table 1: Dimension of the observable codistribution (Ω) obtained by following intuitive reasoning

Analytic results

We now derive the observability properties by applying the analytic criterion described in section 4. For all the cases we have m u = 1. Hence, we adopt the following notation: f f 1 (for the vector field in (1)) and φ m 1 φ m (for the vectors defined by algorithm 2). We consider the six cases defined in section 5.1, separately.

First Case: y = r, u = ω, w = v
We have:

f =   0 0 1   g =   cos(θ -φ) sin(θ-φ) r 0  
We apply the analytic criterion in section 4. We obtain:

Step 1

We have L 1 g = cos(θ -φ), which does not vanish, in general.

Step 2

We have:

Ω 0 = span{[1, 0, 0]}. Additionally, Ω 1 = Ω 0 .
Step 3

We have L φ0 L 1 g = L f L 1 g = -sin(θ -φ), which does not vanish, in general. This suffices to conclude that the considered system is not in the special case considered by lemma 6 and we need to continue with step 4.

Step 4

We have τ

L 2 g (L 1 g ) 2 = tan 2 (θ-φ) r and Dτ = tan(θ -φ) r - tan(θ -φ) r , - 2 cos 2 (θ -φ) , 2 cos 2 (θ -φ)
Step 5

We need to compute Ω 2 and, in order to do this, we need to compute φ 1 . We obtain:

φ 1 =   -tan(θ -φ) 1 r 0   and Inria Ω 2 = span [1, 0, 0], 0, 1 cos 2 (θ -φ) , - 1 cos 2 (θ -φ) It is immediate to check that Dτ ∈ Ω 2 , meaning that m = 2.
Step 6

By a direct computation, it is possible to check that Ω 3 = Ω 2 meaning that m * = 2 and

Ω * = Ω 2 Step 7
The dimension of the observable codistribution is 2. We conclude that the state is not weakly locally observable. This result agrees with the one in table 1 (second line).

Second Case: y = r, u = v, w = ω
We have:

f =   cos(θ -φ) sin(θ-φ) r 0   g =   0 0 1  
We apply the analytic criterion in section 4. We obtain:

Step 1

We easily obtain L g h = 0. We consider the function L f h ∈ F. We have: L f h = cos(θ -φ) and L g L f h = -sin(θ -φ), which does not vanish, in general. Hence, we can proceed with the steps in section 4 by setting:

h = cos(θ -φ)
We obtain:

L 1 g = -sin(θ -φ) Step 2
We have:

Ω 0 = span{[1, 0, 0], [0, sin(θ -φ), -sin(θ -φ)]}
as long as the function r is also a system output. Additionally, Ω 1 = Ω 0 .

Step 3

We have

L φ0 L 1 g = L f L 1 g = sin(θ-φ) cos(θ-φ) r
, which does not vanish, in general. This suffices to conclude that the considered system is not in the special case considered by lemma 6 and we need to continue with step 4.

Step 4

We have:

τ = - cos(θ -φ) sin 2 (θ -φ)
Step 5

By a direct computation we obtain Ω 2 = Ω 1 . Additionally, it is immediate to check that Dτ ∈ Ω 2 , meaning that m = 2.

Step 6 By a direct computation, it is possible to check that Ω 3 = Ω 2 meaning that m * = 2 and

Ω * = Ω 2 .
Step 7

The dimension of the observable codistribution is 2. We conclude that the state is not weakly locally observable. This result agrees with the one in table 1 (third line).

Third Case: y = θ -φ, u = ω, w = v We have:

f =   0 0 1   g =   cos(θ -φ) sin(θ-φ) r 0  
We apply the analytic criterion in section 4. We obtain:

Step 1

We have L 1 g = -sin(θ-φ) r , which does not vanish, in general.

Step 2

We have Ω 0 = span{[0, -1, 1]} and Ω 1 = Ω 0 .

Step 3

We have

L φ0 L 1 g = L f L 1 g = -cos(θ-φ) r
, which does not vanish, in general. This suffices to conclude that the considered system is not in the special case considered by lemma 6 and we need to continue with step 4.

Step 4

We have τ = 2 cot(θ -φ) and

Dτ = 2 sin 2 (θ -φ) [0, 1, -1]
Step 5

By a direct computation we obtain Ω 2 = Ω 1 . Additionally, it is immediate to check that Dτ ∈ Ω 2 , meaning that m = 2.

Step 6 By a direct computation, it is possible to check that Ω 3 = Ω 2 meaning that m * = 2 and

Ω * = Ω 2 .
Step 7

The dimension of the observable codistribution is 1. We conclude that the state is not weakly locally observable. This result agrees with the one in table 1 (fourth line). Note that, the new unobservable direction with respect to the case when both inputs are known, is precisely the absolute scale, since the vector Dr = [1, 0, 0] / ∈ Ω * .

Fourth Case: y = θ -φ, u = v, w = ω We have:

f =   cos(θ -φ) sin(θ-φ) r 0   g =   0 0 1  
We apply the analytic criterion in section 4. We obtain:

Step 1

We have

L 1 g = 1 = 0. Step 2
By a direct computation we obtain:

Ω 0 = span{[0, -1, 1]} and Inria Ω 1 = span [0, -1, 1], - sin(θ -φ) r 2 , - cos(θ -φ) r , cos(θ -φ) r
Step 3 Since L 1 g = 1, it is immediate to realize that L φj L 1 g = 0, for any integer j ≥ 0. Hence, the considered system is in the special case considered by lemma 6 and we skip to step 6 by setting m = 0.

Step 6

By a direct computation, it is possible to check that Ω 2 = Ω 1 meaning that m * = 1 and

Ω * = Ω 1 .
Step 7

The dimension of the observable codistribution is 2. We conclude that the state is not weakly locally observable. This result agrees with the one in table 1 (fifth line).

Fifth Case: y = φ, u = ω, w = v We have:

f =   0 0 1   g =   cos(θ -φ) sin(θ-φ) r 0  
We apply the analytic criterion in section 4. We obtain:

Step 1

We have L 1 g = sin(θ-φ) r , which does not vanish, in general.

Step 2

We easily obtain Ω 0 = span{[0, 1, 0]} and Ω 1 = Ω 0 .

Step 3

We have

L φ0 L 1 g = L f L 1 g = cos(θ-φ) r
, which does not vanish, in general. This suffices to conclude that the considered system is not in the special case considered by lemma 6 and we need to continue with step 4.

Step 4

We have τ = -2 cot(θ -φ) and

Dτ = 2 sin 2 (θ -φ) [0, -1, 1]
Step 5

To compute Ω 2 we need to compute φ 1 . We obtain:

φ 1 =   -r cot(θ -φ) 0  
and

Ω 2 = span [0, 1, 0], 1 sin 2 (θ -φ) [0, 1, -1] It is immediate to check that Dτ ∈ Ω 2 , meaning that m = 2.
Step 6

By a direct computation we obtain Ω 3 = Ω 2 meaning that m * = 2 and Ω * = Ω 2 , whose dimension is 2.

Step 7

The dimension of the observable codistribution is 2. We conclude that the state is not weakly locally observable. This result agrees with the one in table 1 (sixth line). Note that, the new unobservable direction with respect to the case when both inputs are known, is precisely the absolute scale, since the vector Dr = [1, 0, 0] / ∈ Ω * .

Sixth Case: y = φ, u = v, w = ω We have:

f =   cos(θ -φ) sin(θ-φ) r 0   g =   0 0 1  
We apply the analytic criterion in section 4. We obtain:

Step 1

We easily obtain L g h = 0. We consider the function L f h ∈ F. We have:

L f h = sin(θ-φ) r and L g L f h = cos(θ-φ) r
, which does not vanish, in general. Hence, we can proceed with the steps in section 4 by setting:

h = sin(θ -φ) r L 1 g = cos(θ -φ) r
Step 2

We have:

Ω 0 = span [0, 1, 0], - sin(θ -φ) r 2 , - cos(θ -φ) r , cos(θ -φ) r
as long as the function φ is also a system output. We compute Ω 1 . By a direct computation, we obtain that its dimension is 3. Hence, we do not need to proceed with the remaining steps since we can directly conclude that the entire state is weakly locally observable. This result agrees with the one in table 1 (seventh line).

Unicycle in presence of an external unknown input

The system

We consider the same vehicle considered in section 5.1 and we adopt the same state [x v , y v , θ] T to characterize its position and orientation. We assume that the vehicle motion is also affected by an unknown input that produces an additional (and unknown) robot speed (denoted by w) along a fixed direction (denoted by γ). Hence, the dynamics are characterized by the following differential equations:

   ẋv = v cos θ + w cos γ ẏv = v sin θ + w sin γ θ = ω (6)
where v and ω are the linear and the rotational speed, respectively, in absence of the unknown input. We assume that these two speeds are known (we refer to them as to the known inputs), w is unknown (we refer to it as to the unknown input or disturbance) and γ is constant in time. See also figure 2 for an illustration.

Inria We consider the same three cases of output considered in section 5.1. Additionally, we deal with both the cases when γ is known and unknown (in section 5.2.2 and 5.2.3, respectively).

Observability properties when γ is known

The state is [x v , y v , θ] T and its dynamics are provided by the three equations in [START_REF] Guidorzi | On Wonham stabilizability condition in the synthesis of observers for unknown-input systems[END_REF], where γ is a known parameter. These equations are a special case of (1). From ( 6) and (1) we easily obtain:

m u = 2, u 1 = v, u 2 = ω, f 1 =   cos θ sin θ 0   , f 2 =   0 0 1   , g =   cos γ sin γ 0  
We consider the three outputs separately. For the simplicity sake, we actually consider the following three outputs:

y = r 2 = x 2 v + y 2 v instead of y = r, y = tan β = yv-xv tan θ xv+yv tan θ instead of y = β and y = tan φ = yv xv instead of y = φ.
Obviously, the result of the observability analysis does not change.

First Case: y = r 2 We apply the analytic criterion in section 4. We obtain:

Step 1

We have L 1 g = 2(x v cos γ + y v sin γ), which does not vanish, in general.

Step 2

We have

Ω 0 = span{[x v , y v , 0]} and Ω 1 = span{[x v , y v , 0], [cos θ, sin θ, y v cos θ -x v sin θ] }.
Step 3

RR n°9027

We have L1 φ0 L 1 g = L f 1 L 1 g = 2 cos(γ -θ), which does not vanish, in general. This suffices to conclude that the considered system is not in the special case considered by lemma 6 and we need to continue with step 4.

Step 4

We have τ =

Dτ = - 1 (x v cos γ + y v sin γ) 3 [cos γ, sin γ, 0]
Step 5

We need to compute Ω 2 and, in order to do this, we need to compute 1 φ 1 and 2 φ 1 through algorithm 2. We obtain:

1 φ 1 = 2 φ 1 =   0 0 0   . On the other hand, we obtain that L g L 1 g DL f 1 h / ∈ Ω 1 .
Hence, by using algorithm 3 we obtain that Ω 2 has dimension equal to 3. As a result, we do not need to proceed with the remaining steps, since we can directly conclude that the entire state is weakly locally observable.

Second Case: y = tan β We apply the analytic criterion in section 4. We obtain:

Step 1

We have

L 1 g = - yv cos γ-xv sin γ x 2 v cos 2 θ+2 sin θ cos θxvyv-y 2 v cos 2 θ+y 2 v
, which does not vanish, in general.

Step 2 By an explicit computation (by using algorithm 3) we obtain that the dimension of Ω 0 is 1 and the dimension of Ω 1 is 2.

Step 3

We have L2 φ0 L 1 g = L f 2 L 1 g = 0, in general. This suffices to conclude that the considered system is not in the special case considered by lemma 6 and we need to continue with step 4.

Step 4

We have τ = xv cos γ+yv sin γ+xv cos(γ-2θ)-yv sin(γ-2θ) yv cos γ-xv sin γ

Step 5

We need to compute Ω 2 . Also in this case, we obtain that

L g L 1 g DL f 1 h / ∈ Ω 1 .
Hence, by using algorithm 3 we obtain that Ω 2 has dimension equal to 3. As a result, we do not need to proceed with the remaining steps, since we can directly conclude that the entire state is weakly locally observable.

Third Case: y = tan φ We apply the analytic criterion in section 4. We obtain:

Step 1

We have

L 1 g = -yv cos γ-xv sin γ x 2 v
, which does not vanish, in general.

Step 2

We have

Ω 0 = span{[-y v , x v , 0]}.
In addition, by an explicit computation (by using algorithm 3) we obtain that the dimension of Ω 1 is 2.

Step 3

We have L2 φ0 L 1 g = L f 2 L 1 g = 0, in general. This suffices to conclude that the considered system is not in the special case considered by lemma 6 and we need to continue with step 4.

Step 4

We have τ = -

2x 4 v cos γ x 4 v sin γ-x 3 v yv cos γ
Step 5

Inria

We need to compute Ω 2 . Also in this case, we obtain that L g L 1 g

DL f 1 h / ∈ Ω 1 . Hence, by using algorithm 3 we obtain that Ω 2 has dimension equal to 3. As a result, we do not need to proceed with the remaining steps, since we can directly conclude that the entire state is weakly locally observable.

Observability properties when γ is unknown

The state is [x v , y v , θ, γ] T and its dynamics are provided by the following four equations:

     ẋv = v cos θ + w cos γ ẏv = v sin θ + w sin γ θ = ω γ = 0 (7)
From ( 7) and ( 1) we easily obtain:

m u = 2, u 1 = v, u 2 = ω, f 1 =     cos θ sin θ 0 0     , f 2 =     0 0 1 0     , g =     cos γ sin γ 0 0    
We consider the three outputs separately. As in section 5.2.2, we actually consider the following three outputs:

y = r 2 = x 2 v + y 2 v instead of y = r, y = tan β = yv-xv tan θ xv+yv tan θ instead of y = β and y = tan φ = yv xv instead of y = φ.
Obviously, the result of the observability analysis does not change.

First Case: y = r 2 We apply the analytic criterion in section 4. We obtain:

Step 1

We obviously obtain the same expression as in the case y = r 2 of section 5.2.2, i.e., L 1 g = 2(x v cos γ + y v sin γ), which does not vanish, in general.

Step 2

We have

Ω 0 = span{[x v , y v , 0, 0]} and Ω 1 = span{[x v , y v , 0, 0], [cos θ, sin θ, y v cos θ-x v sin θ, 0] }.
Step 3

We have

L1 φ0 L 1 g = L f 1 L 1 g = 2 cos(γ -θ)
, which does not vanish, in general. This suffices to conclude that the considered system is not in the special case considered by lemma 6 and we need to continue with step 4.

Step 4

We have τ = 1 2(xv cos γ+yv sin γ) 2 , as in the case y = r 2 of section 5.2.2. On the other hand, the differential of τ also includes the derivative with respect to γ, namely:

Dτ = -1 (x v cos γ + y v sin γ) 3 [cos γ, sin γ, 0, y v cos γ -x v sin γ]
Step 5

We need to compute Ω 2 and, in order to do this, we need to compute 1 φ 1 and 2 φ 1 through algorithm 2. We obtain:

1 φ 1 = 2 φ 1 =     0 0 0 0    
. By using algorithm 3 we compute Ω 2 and we obtain that its dimension is 3. Additionally, it is possible to verify that Dτ ∈ Ω 2 , meaning that m = 2.

Step 6 By a direct computation, it is possible to check that Ω 3 = Ω 2 meaning that m * = 2 and Ω * = Ω 2 .

Step 7

We conclude that the dimension of the observable codistribution is equal to 3(< 4) and the state is not weakly locally observable. In particular, since the differential of every state component does not belong to Ω 2 , we conclude that no state component is observable.

Second Case: y = tan β We apply the analytic criterion in section 4. We obtain:

Step 1

We obviously obtain the same expression as in the case y = tan β of section 5.2.2, i.e.,

L 1 g = - yv cos γ-xv sin γ x 2 v cos 2 θ+2 sin θ cos θxvyv-y 2 v cos 2 θ+y 2 v
, which does not vanish, in general.

Step 2

We compute Ω 0 and Ω 1 : their dimension are 1 and 2, respectively.

Step 3

We have L2 φ0 L 1 g = L f 2 L 1 g = 0, in general. This suffices to conclude that the considered system is not in the special case considered by lemma 6 and we need to continue with step 4.

Step 4

We have τ = xv cos γ+yv sin γ+xv cos(γ-2θ)-yv sin(γ-2θ)

yv cos γ-xv sin γ
, as in the case y = tan β of section 5.2.2. On the other hand, the differential of τ also includes the derivative with respect to γ.

Step 5

By using algorithm 3 we compute Ω 2 and we obtain that its dimension is 3. Additionally, it is possible to verify that Dτ ∈ Ω 2 , meaning that m = 2.

Step 6

By a direct computation, it is possible to check that Ω 3 = Ω 2 meaning that m * = 2 and Ω * = Ω 2 .

Step 7

We conclude that the dimension of the observable codistribution is equal to 3(< 4) and the state is not weakly locally observable. In particular, since the differential of every state component does not belong to Ω 2 , we conclude that no state component is observable.

Third Case: y = tan φ We apply the analytic criterion in section 4. We obtain:

Step 1

We obviously obtain the same expression as in the case y = tan φ of section 5.2.2, i.e.,

L 1 g = -yv cos γ-xv sin γ x 2 v
, which does not vanish, in general.

Step 2

We compute Ω 0 and Ω 1 : their dimension are 1 and 2, respectively.

Step 3

We have L2 φ0 L 1 g = L f 2 L 1 g = 0, in general. This suffices to conclude that the considered system is not in the special case considered by lemma 6 and we need to continue with step 4.

Step 4

We have τ = -

2x 4 v cos γ x 4 v sin γ-x 3
v yv cos γ , as in the case y = tan φ of section 5.2.2. On the other hand, the differential of τ also includes the derivative with respect to γ.

Step 5 By using algorithm 3 we compute Ω 2 and we obtain that its dimension is 4. As a result, we do not need to proceed with the remaining steps, since we can directly conclude that the entire state is weakly locally observable.

Table 2 summarizes the results of the observability analysis carried out in this section. We conclude this section by remarking that these results agree with our expectation. By using the observability rank condition in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF], we easily obtain that, in absence of the unknown input, the dimension of the observable codistribution is 2 for the first two observations (y = r and y = β) and 3 for the last one (y = φ). In particular, for the first two observations, all the initial states rotated around the vertical axis are indistinguishable. In other words, in these two cases, the system exhibits a continuous symmetry [START_REF] Martinelli | State Estimation Based on the Concept of Continuous Symmetry and Observability Analysis: the Case of Calibration[END_REF]. In presence of the unknown input, when γ is known, the aforementioned system invariance is broken and the entire state becomes observable. When γ is unknown, the symmetry still remains (and obviously also concerns the new state component γ). Note also a very important aspect. The presence of an unknown input improves the observability properties of a system (this regards the case when γ is known). In particular, if w = 0 (absence of unknown input), the state becomes unobservable despite the knowledge of the unknown input (we know that it is zero), while, when w = 0, the state is observable even if w is unknown. Note that having an unknown input equal to zero is an event that occurs with zero probability and our theory accounts this fact since it is based on definition 1. To this regard, note also that the validity of theorem 1, which allows us to introduce the algorithms 2 and 3, holds when the unknown input is different from 0.

Simulations

The scope of this section is to show that, by using a very simple estimator based on an Extended Kalman Filter, we obtain results which agree with our observability analysis.

Simulated trajectories and robot sensors

The trajectories are simulated as follows. The equations in (6) are discretized with a time step of 5 * 10 -4 s and they last for 10 s. The linear speed, i.e. v, is constant and equal to 0.1 m s -1 . The angular speed, i.e. ω, is generated randomly. Specifically, its value is settled at each step and follows a Gaussian distribution with mean value 2π 10 rad s -1 and variance 6π 10 2 rad 2 s -2 .

A typical example of trajectory, obtained with this setting, is displayed in fig. 3, left side. The disturbance is generated as follows. The parameter γ is set equal to 0.7 π. The unknown input w is generated randomly. Specifically, its value is settled at each step and follows a Gaussian distribution with mean value 0.05 m s -1 and variance (0.005) 2 m 2 s -2 . A typical example of trajectory is displayed in fig. 3, right side. The robot is equipped with proprioceptive sensors able to measure at each time step the linear and the angular speed. These measurements are affected by errors. Specifically, each measurement is generated at every time step of 5 * 10 -4 s by adding to the true value a random error that follows a Gaussian distribution. The mean value of this error is zero and the standard deviation is 0.01 times the true value for both the linear and the angular speed.

Regarding the exteroceptive measurements, they are generated at a lower frequency. Specifically, the measurements are generated each 2.5 * 10 -2 s. Also these measurements are affected by errors. Specifically, the measurement is generated by adding to the true value a random error that follows a Gaussian distribution. The mean value of this error is zero and the standard deviation is 0.01 m for the range measurements and 1 deg for the two angular measurements (bearing of the origin in the robot frame and bearing of the robot in the global frame).

Estimation results

We adopt an Extended Kalman Filter that estimates an extended state that includes the unknown input together with its first order time derivative. In other words, in the case when γ is known, the estimated state is: [x v , y v , θ, w, w (1) ]. Its dynamics are obtained from [START_REF] Guidorzi | On Wonham stabilizability condition in the synthesis of observers for unknown-input systems[END_REF] and are:

         ẋv = v cos θ + w cos γ ẏv = v sin θ + w sin γ θ = ω ẇ = w (1) ẇ(1) = w (2) (8)
When γ is unknown, the estimated state also includes γ and the dynamics are given by ( 8) and the additional equation γ = 0.

In order to implement the prediction phase of our Extended Kalman Filter we have to provide the value of w (2) , which is unknown. We set this quantity to zero. Note that the simulated trajectory does not satisfy this hypothesis since the disturbance is randomly generated. However, the estimator is able to provide good performance as it is shown in figures 4-6.

Figure 4 displays the estimated trajectory in the case when the output is provided by the range sensor (h = r). Dots blue are the ground truth, red circles the estimated trajectory by Inria only using the knowledge of the proprioceptive measurements (i.e., the measurements of v and ω), black stars the trajectory estimated by our estimator. Left side is the case when γ is known and right side when it is unknown. In accordance with our observability analysis, the estimator follows the true trajectory only in the case when γ is known. Figure 5 displays the estimated trajectory in the case when the output is provided by the on-board bearing sensor (h = β). Also in this case, the estimator follows the true trajectory only in the case when γ is known, in accordance with our observability analysis. Finally, figure 6 displays the estimated trajectory in the case when the output is provided by the bearing sensor at the origin (h = φ). In this case, the estimator follows the true trajectory both in the case when γ is known and when it is unknown. Also this result agrees with our observability analysis. We conclude this section by remarking that the results of our simulations fully agree with the observability analysis provided in sections 5.2.2 and 5.2.3. Note that we showed the result of a Figure 6: The same as in figure 4 in the case when the output is h = φ. single trial. However, we found always similar results by running many trials.

Vehicle moving in 3D in presence of a disturbance

The system

We consider a vehicle that moves in a 3D-environment. We assume that the dynamics of the vehicle are affected by the presence of a disturbance (e.g., this could be an aerial vehicle in presence of wind). We assume that the direction of the disturbance is constant in time and a priori known. Conversely, the disturbance magnitude is unknown and time dependent. The vehicle is equipped with speed sensors (e.g., airspeed sensors in the case of an aerial vehicle), gyroscopes and a bearing sensor (e.g., monocular camera). We assume that all the sensors share the same frame (in other words, they are extrinsically calibrated). Without loss of generality, we define the vehicle local frame as this common frame. The airspeed sensors measure the vehicle speed with respect to the air in the local frame. The gyroscopes provide the angular speed in the local frame. Finally, the bearing sensor provides the bearing angles of the features in the environment expressed in its own local frame. We consider the extreme case of a single point feature and, without loss of generality, we set the origin of the global frame at this point feature (see figure 7 for an illustration). Additionally, we assume that the z-axis of the global frame is aligned with the direction of the disturbance. Our system can be characterized by the following state:

X [x, y, z, q t , q x , q y , q z ] T [START_REF] Hesch | Towards consistent visionaided inertial navigation[END_REF] where r = [x, y, z] is the position of the vehicle in the global frame and q = q t + q x i + q y j + q z k is the unit quaternion that describes the transformation change between the global and the local frame. The dynamics are affected by the presence of the disturbance. The disturbance is characterized by the following vector (in the global frame):

w = w   0 0 1   ( 10
)
where w is its unknown magnitude. In the sequel, for each vector defined in the 3D space, the pedix q will be adopted to denote the corresponding imaginary quaternion. For instance, regarding the vehicle position, we have: r q = 0 + x i + y j + z k. Additionally, we denote by V and Ω the following physical quantities:

Inria

• V = [V x , V y , V z ]
is the vehicle speed with respect to the air expressed in the local frame (hence, w k + qV q q * is the vehicle speed with respect to the ground expressed in the global frame).

• Ω [Ω x Ω y Ω z ] is the angular speed (and

Ω q = 0 + Ω x i + Ω y j + Ω z k).
The dynamics of the state are:

  ṙq = w k + qV q q * q = 1 2 qΩ q (11)
The monocular camera provides the position of the feature in the local frame (F q = -q * r q q) up to a scale. Hence, it provides the ratios of the components of F :

h cam (X) [h u , h v ] T = (q * r q q)
x (q * r q q) z , (q * r q q) y (q * r q q) z T [START_REF] Huang | Analysis and improvement of the consistency of extended Kalman filter based SLAM[END_REF] where the pedices x, y and z indicate respectively the i, j and k component of the corresponding quaternion. We have also to consider the constraint q * q = 1. This provides the further observation:

h const (X) q * q ( 13
)
Our system is characterized by the state in [START_REF] Hesch | Towards consistent visionaided inertial navigation[END_REF], the dynamics in [START_REF] Hesch | Consistency Analysis and Improvement of Vision-aided Inertial Navigation[END_REF] and the three outputs h u , h v and h const in ( 12) and (13).

Observability in absence of disturbance

Our system is characterized by the state in [START_REF] Hesch | Towards consistent visionaided inertial navigation[END_REF], the dynamics in [START_REF] Hesch | Consistency Analysis and Improvement of Vision-aided Inertial Navigation[END_REF] with w = 0 and the three outputs h u , h v and h const in ( 12) and [START_REF] Huang | Observability-based Rules for Designing Consistent EKF SLAM Estimators[END_REF].

By comparing [START_REF] Hesch | Consistency Analysis and Improvement of Vision-aided Inertial Navigation[END_REF] with (1) we obtain that our system is characterized by six known inputs (m u = 6) that are: u 1 = Ω x , u 2 = Ω y , u 3 = Ω z , u 4 = V x , u 5 = V y and u 6 = V z . Additionally, we obtain:

f 1 = 1 2           0 0 0 -q x q t q z -q y           , f 2 = 1 2           0 0 0 -q y -q z q t q x           , f 3 = 1 2           0 0 0 -q z q y -q x q t           , f 4 =           q 2 t + q 2
x -q 2 y -q 2 z 2q t q z + 2q x q y 2q x q z -2q t q y 0 0 0 0

          , f 5 =           2q x q y -2q t q z q 2 t -q 2 x + q 2 y -q 2 z 2q t q x + 2q y q z 0 0 0 0           , Inria f 6 =           2q t q y + 2q x q z 2q y q z -2q t q x q 2 t -q 2 x -q 2 y + q 2 z 0 0 0 0          
Finally, in absence of disturbance we have:

g = [0, 0, 0, 0, 0, 0, 0]

T In this case we can apply the observability rank condition, i.e., algorithm 1, to obtain the observable codistribution. We compute the codistribution Ω 0 by computing the differentials of the three functions h u , h v and h const . We obtain that this codistribution has dimension equal to 3. We use algorithm 1 to compute Ω 1 . We obtain that its dimension is 4. In particular, the additional covector is obtained by the differential of the following Lie derivative:

L f 4 h u
In other words:

Ω 1 = span Dh u , Dh v , Dh const , DL f 4 h u ,
All the remaining first order Lie derivatives have differential that is in the above codistribution. Additionally, by an explicit computation, it is easy to realize that Ω 2 = Ω 1 . This means that algorithm 1 has converged and the observable codistribution is Ω 1 . By an explicit computation, it is possible to check that the differentials of the components of the vector F belong to Ω 1 . This means that all the observable modes are the components of F , i.e., the position of the feature in the local frame (obviously, the fourth observable mode is the norm of the quaternion). In particular, no component of the vehicle orientation is observable.

Observability in presence of the disturbance

We now consider the case when the dynamics are affected by the presence of the disturbance. By comparing [START_REF] Hesch | Consistency Analysis and Improvement of Vision-aided Inertial Navigation[END_REF] with (1) we obtain that the vector fields that characterize the dynamics are the same that characterize the dynamics in absence of disturbance with the exception of the last one, which becomes:

g = [0, 0, 1, 0, 0, 0, 0] T
To derive the observability properties we apply the proposed analytic tool, by following the seven steps provided in section 4.

First Step

We start by computing the Lie derivatives of the outputs h u , h v and h const along the vector field g. We find that the result differs from zero for the first two outputs. Hence, we use the first output (h u ) to define L 1 g (we could choose also the second output h v ). In particular, we obtain:

L 1 g L g h u = -y(2q t q z -2q x q y ) -x(q 2 t -q 2 x + q 2 y -q 2 z ) [z(q 2 t -q 2
x -q 2 y + q 2 z ) + 2x(q t q y + q x q z ) + 2y(q y q z -q t q x )] 2

Second Step

We compute the codistribution Ω 0 by computing the differentials of the three functions h u , h v and h const . This coincides with the case without disturbance, and we obtain that this codistribution has dimension equal to 3.

We use algorithm 3 to compute Ω 1 . We obtain that its dimension is 5. In particular, the additional two independent covectors are obtained by the differentials of the following two Lie derivatives:

L f 4 h u , L g L 1 g h v
In other words:

Ω 1 = span Dh u , Dh v , Dh const , DL f 4 h u , DL g L 1 g h v
All the remaining first order Lie derivatives have differential that is in the above codistribution.

Third Step

We compute 1 φ 1 , 2 φ 1 , 3 φ 1 , 4 φ 1 , 5 φ 1 and 6 φ 1 by using algorithm 2. We obtain that all these vectors vanish. As a result, all the subsequent steps of algorithm 2 provide null vectors. Therefore, the assumptions of lemma 6 are trivially met. We set m = 0 and we skip to the sixth step.

Sixth Step

We use algorithm 3 to compute Ω 2 and we obtain:

Ω 2 = Ω 1 + span DL f 4 L g L 1 g h v
Hence, its dimension is 6. Finally, by using again algorithm 3 it is possible to compute Ω 3 and to check that Ω 3 = Ω 2 . This means that the algorithm has converged and the observable codistribution is Ω * = Ω 2 .

Seventh Step

By computing the distribution orthogonal to the codistribution Ω * we can find the continuous symmetry that characterizes the unobservable space [START_REF] Martinelli | State Estimation Based on the Concept of Continuous Symmetry and Observability Analysis: the Case of Calibration[END_REF]. By an explicit computation we obtain the following vector:

-y, x, 0, - q z 2 , - q y 2 , q x 2 , q t 2 T
This symmetry corresponds to an invariance with respect to a rotation around the z-axis of the global frame. This means that we have a single unobservable mode that is the yaw in the global frame. We conclude by remarking that the presence of the disturbance, even if its magnitude is unknown and is not constant, makes observable the roll and the pitch angles. This result is similar to the result that we obtain in the case of visual and inertial sensor fusion in presence of gravity. The presence of gravity makes observable the roll and the pitch angles, even if its magnitude is unknown [START_REF] Martinelli | Vision and IMU data fusion: closed-form solutions for attitude, speed, absolute scale and bias determination[END_REF][START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF]. What it is non intuitive in the case now investigated, is that, not only the magnitude of the disturbance is unknown, but it is also time dependent.

Inria

Simulations

As in section 5.2.4, the scope of this section is to show that, by using a simple estimator based on an Extended Kalman Filter, we obtain results that agree with our observability analysis.

Simulated trajectories and robot sensors

The trajectories are simulated as follows. The equations in [START_REF] Hesch | Consistency Analysis and Improvement of Vision-aided Inertial Navigation[END_REF] are discretized with a time step of 0.01 s. Each trial lasts 200 s. The initial vehicle speed is set to zero. The initial position is set equal to [0.5 0.5 0.5]m. The vehicle motion is randomly generated. The angular speed, i.e. Ω, is Gaussian. Specifically, its value at each step follows a zero mean Gaussian distribution with covariance matrix equal to (1 deg) 2 I 3 , where I 3 is the identity 3×3 matrix. At each time step, the vehicle speed is incremented by adding a random vector with zero mean Gaussian distribution. In particular, the covariance matrix of this distribution is set equal to σ 2 I 3 , with σ = 10 -4 m. Finally, we simulate the disturbance as a vector along the z-axis, whose magnitude is generated as a random Gaussian variable, with mean value 0.2 ms -1 and variance 0.05 2 m 2 s -2 .

Typical trajectories, obtained with this setting, are displayed in figures 8 and 9. The vehicle is equipped with proprioceptive sensors able to measure at each time step the speed with respect to the air and the angular speed. These measurements are affected by errors. Specifically, each measurement is generated at every time step of 0.01 s by adding to the true value a random error that follows a Gaussian distribution. The mean value of this error is zero and the standard deviation is 0.01 ms -1 for the airspeed and 1 deg s -1 for the gyroscope. Regarding the exteroceptive measurements, they are generated at a lower frequency. Specifically, the measurements are generated each 0.1 s. Also these measurements are affected by errors. Specifically, each measurement is generated by adding to the true value a random error that follows a zero mean Gaussian distribution, with variance 1 deg 2 . We simulate two point features, one at the origin and the other one at the position [2 0 0]m (note that the result of the observability analysis is independent of the number of point features).

Estimation results

We adopt an EKF that estimates an extended state that includes the state in ( 9) and the unknown input (w) together with its first order time derivative (w (1) dw dt ). In other words, the estimated state is: x, y, z, q t , q x , q y , q z , w, w (1) T . Its dynamics are given in [START_REF] Hesch | Consistency Analysis and Improvement of Vision-aided Inertial Navigation[END_REF] with the two further equations: ẇ = w (1) ẇ(1) = w (2) (14

)
In order to implement the prediction phase of our EKF we have to provide the value of w (2) ( d 2 w dt 2 ), which is unknown. We set this quantity to zero. Note that the simulated trajectory does not satisfy this hypothesis since the disturbance is randomly generated. However, the estimator is able to provide good performance as it is shown in figures 10-14.

Figure 8 displays the estimated trajectory in absence of the disturbance. The red line is the trajectory obtained by only using the proprioceptive measurements, while the black line is the trajectory obtained by the proposed EKF. The true trajectory is in blue. Both the estimated trajectories diverge. However, the divergence is slower for the trajectory estimated by the EKF. This divergence is consistent with our observability analysis. The vehicle position is not observable (both with and without disturbance). Figure 9 displays the same of figure 8 for a trial in presence of the disturbance. Note that, in this case, the z-axis has now a different scale (much larger). This is to show the trajectory obtained by only using the proprioceptive measurements, whose divergence is much faster due to the presence of the disturbance along the z-axis.

In the remaining figures, we show the performance of the proposed EKF in estimating the distances of the two features and the roll, the pitch and the yaw angles. In accordance with our observability analysis, the distances of the features are observable both with and without the disturbance. In contrast, the roll and the pitch angles are observable only in presence of Inria the disturbance. Finally, the yaw angle is always unobservable. All these results are clearly confirmed by our simulation results. Figures 10 and11 show the error on the two distances, in absence and in presence of the disturbance, respectively. We note that, the error does not increase with time in both cases.

Figures 12, 13 and 14 show the error on the roll, pitch and yaw angles, respectively. The left side is in absence of the disturbance while the right side is in presence of the disturbance. In absence of the disturbance, the error increases with time for all the three angles. In presence of the disturbance, it does not increase for the roll and the pitch angle. We conclude this section by remarking that the results of our simulations fully agree with the observability analysis provided in section 5.3.3. Also note that we showed the result of a single trial. However, we found always similar results by running many trials.

Analytic Derivations

In this section, we prove the validity of the analytic results presented in section 3. We start by introducing several important concepts starting by providing the definition of state indistinguishability in presence of unknown inputs (section 6.1). These concepts hold for any number of unknown inputs and when the dynamics are affine in the inputs (and not simply linear). Then, section 6.2 is devoted to prove the results that hold in the case of a single unknown input and therefore to prove the validity of the results provided in sections 3 and 4.

State Indistinguishability, State augmentation and Observable Codistribution

As mentioned in the introduction of this section, the concepts introduced in this section, hold for any number of unknown inputs (m w ) and when the dynamics are affine in the inputs. Specifically, we will refer to the following dynamics:

ẋ = g 0 (x) + mu i=1 f i (x)u i + mw j=1 g j (x)w j ( 15
)
where g 0 (x),

f i (x), i = 1, • • • , m u , and g j (x), j = 1, • • • , m w , are vector fields in M ⊂ R n .
In [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF][START_REF] Isidori | Nonlinear Control Systems[END_REF] the observability properties of a nonlinear system driven by only known inputs are derived starting from the definition of indistinguishable states. According to this definition, it is proven the following fundamental property: Proposition 1 The Lie derivatives of any output computed along any direction allowed by the system dynamics take the same values at the states which are indistinguishable.

Starting from this fundamental property it is possible to prove that algorithm 1 generates the observable codistribution [START_REF] Isidori | Nonlinear Control Systems[END_REF]. In presence of unknown inputs, we first need to introduce a new definition of indistinguishability. To be conservative, the new definition must consider two states indistinguishable if there exists at least one pair of unknown inputs, such that, the outputs obtained starting from the first state under the effect of the first unknown input on a given time interval (I), coincide with the outputs obtained starting from the second state under the effect of the second unknown input on the same time interval, and this holds for any choice of the known inputs. On the other hand, if this condition is achieved only for a unique pair of unknown inputs, the probability that this event occurs is zero. For this reason, we require that this condition is met for infinite pairs of unknown inputs. The concept of measure in spaces with infinite dimensions is not trivial. In particular, there is no analogue of Lebesgue measure on an infinite-dimensional Banach space. One possibility, which is frequently adopted, is to use the concept of prevalent and shy sets [START_REF] Hunt | Prevalence: a translation-invariant "almost every" on infinite-dimensional spaces[END_REF]. Let us denote by W the functional space of all the possible unknown input functions. The probability that a given unknown input belongs to a shy subset of W, is 0. The probability that a given unknown input belongs to a prevalent subset of W, is 1. Finally, the probability that a given unknown input belongs to a non-shy subset of W, is strictly larger than 0.

We introduce the following definition:

Definition 1 (Indistinguishable states) Two states x a and x b are indistinguishable if, for every u(t) (the known input vector function), there exists a non-shy subset W a in the functional space of all the possible unknown input functions, such that, for any unknown input function w a ∈ Inria W a it exists an unknown input function w b such that h(x(t; x a ; u; w a )) = h(x(t; x b ; u; w b )) ∀t ∈ I.

The property stated by proposition 1 does not hold in presence of unknown inputs. Our first objective is to extend the original state in order to obtain a similar property for the resulting extended system. This new property will be the one stated by proposition 4.

To obtain such a result, we proceed as follows. We extend the original state by including the unknown inputs together with their time derivatives. Specifically, we denote by k x the extended state that includes the unknown inputs and their time derivatives up to the (k -1)-order:

k x [x T , w T , w (1) T , • • • , w (k-1) T ] T ( 16
)
where w (k)

d k w dt k and k x ∈ M (k) , with M (k)
an open set of R n+kmw . From [START_REF] Hunt | Prevalence: a translation-invariant "almost every" on infinite-dimensional spaces[END_REF] it is immediate to obtain the dynamics for the extended state:

k ẋ = G + mu i=1 F i u i + mw j=1 W j w (k) j (17)
where:

G         g 0 + mw j=1 g j w j w (1) w (2) • • • w (k-1) 0 mw         (18)
F i f i 0 kmw , W j   0 n+(k-1)mw+j-1 1 0 mw-j   ( 19
)
and we denoted by 0 m the m-dimensional zero column vector. We remark that the resulting system has still m u known inputs and m w unknown inputs. However, while the m u known inputs coincide with the original ones, the m w unknown inputs are now the k-order time derivatives of the original unknown inputs. The state evolution depends on the known inputs via the vector fields F i , (i = 1, • • • , m u ) and it depends on the unknown inputs via the unit vectors W j , (j = 1, • • • , m w ). Finally, we remark that only the vector field G depends on the new state elements.

In the sequel, we will denote the extended system by Σ (k) . Additionally, we use the notation:

ξ [w T , w (1) T , • • • , w (k-1) T ] T .
In this notation we have k x = [x T , ξ T ] T . We also denote by Σ (0) the original system, i.e., the one characterized by the state x and the equations in [START_REF] Hunt | Prevalence: a translation-invariant "almost every" on infinite-dimensional spaces[END_REF].

We start by providing a simple result for Σ (k) :

Lemma 1 In Σ (k)
, the Lie derivatives of the output up to the m th order (m ≤ k) are independent of w

(f ) j , j = 1, • • • , m w , ∀f ≥ m.
Proof: We proceed by induction on m for any k. When m = 0 we only have one zero-order Lie derivative (i.e., h(x)), which only depends on x, namely it is independent of w (f ) , ∀f ≥ 0. Let us assume that the previous assert is true for m and let us prove that it holds for m + 1. If it is true for m, any Lie derivative up to the m th order is independent of w (f ) , for any f ≥ m. In other words, the analytical expression of any Lie derivative up to the m-order is represented by a function g(x, w, w (1)

, • • • , w (m-1) ). Hence, dg = [ ∂g ∂x , ∂g ∂w , ∂g ∂w (1) , • • • , ∂g ∂w (m-1) , 0 (k-m)mw ].
It is immediate to realize that the product of this differential by any vector field in [START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF] depends at most on w (m) , i.e., it is independent of w (f ) , ∀f ≥ m + 1

A simple consequence of this lemma is the following property:

Proposition 2 Let us consider the system Σ (k) . The Lie derivatives of the output up to the k th order along at least one vector among W j (j = 1, • • • , m w ) are identically zero.

Proof: From the previous lemma it follows that all the Lie derivatives, up to the (k-1)-order are independent of w (k-1) , which are the last m w components of the extended state in [START_REF] Isidori | Nonlinear Control Systems[END_REF]. Then, the proof follows from the fact that any vector among

W j (j = 1, • • • , m w ) has the first n + (k -1)m w components equal to zero
We have the following property:

Proposition 3 The Lie derivatives of the output up to the k th order along any vector field G, F 1 , • • • , F mu for the system Σ (k) coincide with the same Lie derivatives for the system Σ (k+1)

Proof: We proceed by induction on m for any k. When m = 0 we only have one zero-order Lie derivative (i.e., h(x)), which is obviously the same for the two systems, Σ (k) and Σ (k+1) . Let us assume that the previous assert is true for m and let us prove that it holds for m+1 ≤ k. If it is true for m, any Lie derivative up to the m th order is the same for the two systems. Additionally, from lemma 1, we know that these Lie derivatives are independent of w (f ) , ∀f ≥ m. The proof follows from the fact that the first n + mm w components of the vector fields G, F 1 , • • • , F mu for Σ (k) , coincide with the first n + mm w components of the same vector fields for Σ (k+1) , when m < k For Σ (k) we have a fundamental property that is the extension of the one stated by proposition 1:

Proposition 4 If x a and x b are indistinguishable, there exist ξ a and ξ b such that, in Σ (k) , the Lie derivatives of the output up to the k th -order, along all the vector fields that characterize the dynamics of Σ (k) , take the same values at [x a , ξ a ] and [x b , ξ b ].

Proof: We consider a piecewise-constant input ũ as follows

(i = 1, • • • , m u ): ũi (t) = (20)          u 1 i t ∈ [0, t 1 ) u 2 i t ∈ [t 1 , t 1 + t 2 ) • • • u g i t ∈ [t 1 + t 2 + • • • + t g-1 , t 1 + t 2 + • • • + t g-1 + t g )
Since x a and x b are indistinguishable, there exist two unknown input functions w a (t) and w b (t) such that the output coincide on x a and x b . In particular, we can write:

h(x(t; [x a , ξ a ]; ũ; w (k) a )) = h(x(t; [x b , ξ b ]; ũ; w (k) b )) (21) ∀t ∈ [0, t 1 + t 2 + • • • + t g-1 + t g ) ⊂ I.
On the other hand, by taking the two quantities in (21) at t = t 1 + t 2 + • • • + t g-1 + t g , we can consider them as functions of the g arguments t 1 , t 2 , • • • , t g . Hence, by differentiating with respect to all these variables, we also have:

∂ g h(x(t 1 + • • • + t g ; [x a , ξ a ]; ũ; w (k) a )) ∂t 1 ∂t 2 • • • ∂t g = ( 22
) Inria = ∂ g h(x(t 1 + • • • + t g ; [x b , ξ b ]; ũ; w (k) b )) ∂t 1 ∂t 2 • • • ∂t g
By computing the previous derivatives at t 1 = t 2 = • • • = t g = 0 and by using proposition 2 we obtain, if g ≤ k:

L g θ1θ2•••θg h x = x a ξ = ξ a = L g θ1θ2•••θg h x = x b ξ = ξ b ( 23
)
where

θ h = G + mu i=1 F i u h i , h = 1, • • • , g.
The equality in [START_REF] Martinelli | Automatic Self-Calibration of a Vision System during Robot Motion[END_REF] must hold for all possible choices of u h 1 , • • • , u h mu . By appropriately selecting these u h 1 , • • • , u h mu , we finally obtain:

L g v1v2•••vg h x = x a ξ = ξ a = L g v1v2•••vg h x = x b ξ = ξ b ( 24
)
where

v 1 v 2 • • • v g are vector fields belonging to the set {G, F 1 , • • • , F mu }
The main difference between propositions 1 and 4 is that, in the latter, we cannot consider any order Lie derivative, since the order cannot exceed k. This will have important consequences, as we will see. Before discussing this point, we remark that in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF] it was also defined the concept of V -indistinguishable states, with V a subset of the definition set that includes the two considered states. From this definition and the previous proof we can alleviate the assumptions in the previous proposition. Specifically, we have the following:

Remark 1 The statement of proposition 4 also holds if x a and x b are V -indistinguishable. Now let us discuss how we can use the result stated by the proposition 4 to investigate the observability properties. Thanks to the results stated by propositions 3 and 4 we can easily build a codistribution that is observable. In the sequel, we will denote by d the differential with respect to the entire extended state. We will call original state the vector x and, we remind the reader that we denote by D the differential with respect to the original state. The observable codistribution for Σ (k) is the span of the differentials of all the Lie derivatives of the output along G, F 1 , • • • , F mu up to the k-order. Hence, for any m ≤ k, it is obtained recursively by the following algorithm:

Algorithm 4 Observable codistribution for the extended state (m ≤ k)

1. Ω0 = span{dh}; 2. Ωm = Ωm-1 + L G Ωm-1 + mu i=1 L F i Ωm-1
It is possible to obtain all the observability properties of the original state starting from the codistributions generated by the previous algorithm. In order to show this, we introduce the concept of Observable Mode. This concept can be also useful in the case without unknown inputs. Given x 0 , we denote by I x0 the set of all the states x such that x and x 0 are indistinguishable. According to the theory of observability, a system is observable in x 0 if I x0 = x 0 . We introduce here the following new definition:

RR n°9027 Definition 2 (Observable Mode) A scalar function is observable in x 0 if it is constant on I x0 . Additionally, it is weakly observable in x 0 if it exists an open neighbourhood B x0 such that it is constant on B x0 ∩ I x0 .
The basic idea behind definition 2 is the following. Let us suppose that the true initial state is x 0 . According to the definition of indistinguishable set (which is based on definition 1), the system only contains the information to establish whether the initial state belongs to the indistinguishable set I x0 or not. Hence, if a scalar function takes the same value on this set, we conclude that the system has enough information to know the value of this scalar function at the initial time. We also remark that definition 2 generalizes the definition of observability. Specifically, a system is observable in x 0 when all the components of the state x are observable modes in x 0 . When the scalar function is only weakly observable at x 0 , we conclude that the system has enough information to know the value of this scalar function at the initial time, provided that we a priori know that the initial state is sufficiently close to x 0 .

The following two propositions generalize theorem 3.1 and 3.11 in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF].

Proposition 5 Given a scalar function θ(x), if it exists an integer k such that for the extended system Σ (k) , dθ ∈ Ωk in a given x 0 and for a given extension ξ 0 , then θ is weakly observable in x 0 .

Proof: θ(x) can be expressed in terms of the Lie derivatives of the output along the fields that characterize the dynamics of Σ (k) , up to the k-order. We can write θ

(x) = G(φ 1 (x, ξ), • • • , φ L (x, ξ)), ∀x ∈ B x0 where φ 1 (x, ξ), • • • , φ L (x, ξ) are L Lie
derivatives among the ones of above and G is a given function.

Let us consider a given x indistinguishable from x 0 and that belongs to B x0 . In other words, x ∈ B x0 ∩I x0 . From proposition 4 there are two extensions ξ a and ξ b , such that, the Lie derivatives φ 1 (x, ξ), • • • , φ L (x, ξ) take the same values on the two extended states [x, ξ a ] and [x 0 , ξ b ]. Therefore, ∀x ∈ B x0 ∩I x0 we have: ∈ Ωk . This means that ∀k and ξ it exists a distribution with dimension larger than zero that is orthogonal to the codistribution Ωk in C r x0 . This means that it exists at least one vector field s, of the same dimension of the original state, such that, ∀k and ξ, it exists at least one vector field s k of dimension km w , such that the vector field [s T , s T k ] T is orthogonal to the codistribution Ωk in C r x0 . From this, we obtain that it exists > 0 such that the states x 0 and x 0 + s are indistinguishable. Indeed, it is possible to express the m-time derivative of the output at the initial time, for a generic integer m, in terms of the Lie derivatives of the output along the fields of Σ (k) , up to the m-order, and the known inputs and their time derivatives (see [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF], sect 2.5.1). Since this holds for any k, the m-order time derivative of the output at the initial time coincides in x 0 and x 0 + s. Since this holds for any order m, from the Taylor theorem the output coincides on a given time interval and consequently x 0 and x 0 + s are indistinguishable. But this means that also θ(x 0 ) = θ(x 0 + s). Hence, dθ • s = 0 a.e. on an open neighbourhood B x0 and dθ ∈ Ωk a.e. on an open neighbourhood B x0 Propositions 5 and 6 state that all the observability properties of the original state are contained in the codistributions generated by algorithm 4. From this, we can easily obtain a sufficient Inria condition for the observability of the original state. Indeed, if on a given x 0 , the differential of a given component of x (the original state) belongs to Ωm for a given integer m ≤ k, we can conclude that this state component is weakly locally observable (in x 0 ). If this holds for all the state components, we can conclude that the entire original state is weakly locally observable. More in general, we can conclude that, a given scalar function of the original state, is weakly observable in a given point x 0 if its differential (computed in x 0 ) belongs to Ωm (computed in x 0 ) for a given integer m ≤ k. On the other hand, we remark the following two fundamental differences between algorithms 1 and 4:

θ(x) = G(φ 1 (x, ξ a ), • • • , φ L (x, ξ a )) = G(φ 1 (x 0 , ξ b ), • • • , φ L (x 0 , ξ b )) = θ(x 0 )
1. In the latter, since the state augmentation can be continued indefinitely, we do not have convergence;

2. The latter provides a codistribution that describes simultaneously the observability properties of the original state and its extension.

The goal of the next section is to address these fundamental issues in the case of a single unknown input. In particular, we show that it is possible to directly compute the entire observable codistribution of the original system, namely, without the need of extending the state.

Proof of the validity of the analytic criterion

This section is devoted to the case of a single unknown input (i.e., m w = 1) and dynamics linear in the inputs (the vector g 0 is the null vector). In other words, we are considering the system characterized by [START_REF] Basile | On the observability of linear, time invariant systems with unknown inputs[END_REF]. When m w = 1, the extended state that includes the time derivatives of w up to the (k -1)-order is:

k x [x T , w, w (1) , • • • , w (k-1) ] T (25)
where w (j) d j w dt j . The dimension of the extended state is in this case n + k. For the clarity sake, let us consider the case of a single known input (i.e., we consider the system in (1) with m u = 1). We provide all the analytic results in this simpler case and then we extend them to the case of m u > 1. From (1) it is immediate to obtain the dynamics for the extended state:

k ẋ = G( k x) + F (x)u + W w (k) (26)
where:

F         f (x) 0 0 • • • 0 0         G         g(x)w w (1) w (2) • • • w (k-1) 0         W         0 0 0 • • • 0 1         (27)
and we set f (x) f 1 (x).

Algorithm 4 becomes:

Algorithm 5 Observable codistribution for the extended state in the case m u = 1 (m ≤ k)

1. Ω0 = span{dh}; 2. Ωm = Ωm-1 + L G Ωm-1 + L F Ωm-1
where G is now the simpler vector field given in [START_REF] Martinelli | Nonlinear Unknown Input Observability: Analytical expression of the observable codistribution in the case of a single unknown input[END_REF] and d denotes the differential respect to the state in [START_REF] Martinelli | Vision and IMU data fusion: closed-form solutions for attitude, speed, absolute scale and bias determination[END_REF]. We will address the two fundamental issues mentioned at the end of the previous section. This is obtained by two separates steps. In the first step (sect. 6.2.1) we perform a separation on the observable codistribution defined by algorithm 5. This codistribution can be split into two codistributions: the former is the codistribution generated by algorithm 3, once embedded in the extended space, and the latter is the codistribution L m defined in section 6.2.1 (see theorem 1). We prove (Lemma 2) that the second codistribution (L m ) can be ignored when deriving the observability properties of the original state. In the second step (sect. 6.2.2) we prove that algorithm 3 converges in at most n + 2 steps and we provide the convergence criterion. Finally, in section 6.2.3 we extend the results of the previous two theorems to the case of multiple known inputs (m u > 1).

Separation

For each integer m, we generate the codistribution Ω m by using algorithm 3 (note that here we are considering m u = 1). By construction, the generators of Ω m are the differentials of scalar functions that only depend on the original state (x) and not on its extension. In the sequel, we need to embed this codistribution in R n+k . We will denote by [Ω m , 0 k ] the codistribution made by covectors whose first n components are covectors in Ω m and the last components are all zero. Additionally, we will denote by L m the codistribution that is the span of the Lie derivatives of dh up to the order m along the vector

G, i.e., L m span{L 1 G dh, L 2 G dh, • • • , L m G dh}.
We finally introduce the following codistribution:

Definition 3 ( Ω codistribution) This codistribution is defined as follows: Ωm [Ω m , 0 k ]+L m
The codistribution Ωm consists of two parts. Specifically, we can select a basis that consists of exact differentials that are the differentials of functions that only depend on the original state (x) and not on its extension (these are the generators of [Ω m , 0 k ]) and the differentials

L 1 G dh, L 2 G dh, • • • , L m G dh.
The second set of generators, i.e., the differentials

L 1 G dh, L 2 G dh, • • • , L m G dh
, are m and, with respect to the first set, they are differentials of functions that also depend on the state extension ξ = [w, w (1) , • • • , w (m-1) ] T . We have the following result:

Lemma 2 Let us denote with x j the j th component of the state (j = 1, • • • , n). We have: Dx j ∈ Ω m if and only if dx j ∈ Ωm Proof: The fact that Dx j ∈ Ω m implies that dx j ∈ Ωm is obvious since [Ω m , 0 k ] ⊆ Ωm by definition. Let us prove that also the contrary holds, i.e., that if dx j ∈ Ωm then Dx j ∈ Ω m . Since dx j ∈ Ωm we have

dx j = N1 i=1 c 1 i ω 1 i + N2 i=1 c 2 i ω 2 i , where ω 1 1 , ω 1 2 , • • • , ω 1 N1 are N 1 generators of [Ω m , 0 k ], ω 2 1 , ω 2 2 , • • • , ω 2 N2 are N 2 generators of L m and c 1 1 , • • • , c 1 N1 , c 2 1 , • • • , c 2
N2 are suitable coefficients. We want to prove that N 2 = 0.

We proceed by contradiction. Let us suppose that N 2 ≥ 1. We remark that the first set of generators have the last k entries equal to zero, as for dx j . The second set of generators consists of the Lie derivatives of dh along G up to the m order. Let us select the one that is the highest order Lie derivative and let us denote by j this highest order. We have 1 ≤ N 2 ≤ j ≤ m. By a direct computation, it is immediate to realize that this is the only generator that depends on w (j -1) . Specifically, the dependence is linear by the product L 1 g w (j -1) (we remind the reader that L 1 g = 0). But this means that dx j has the (n + j ) th entry equal to L 1 g = 0 and this is not possible since dx j = [Dx j , 0 k ] Inria A fundamental consequence of this lemma is that, if we are able to prove that Ωm = Ωm , the weak local observability of the original state x, can be investigated by only considering the codistribution Ω m . In the rest of this section we prove this fundamental theorem, stating that Ωm = Ωm .

For a given m ≤ k we define the vector Φ m ∈ R n+k by the following algorithm:

1. Φ 0 = F ; 2. Φ m = [Φ m-1 , G]
where now the Lie brackets [•, •] are computed with respect to the extended state, i.e.:

[F, G] ∂G ∂ k x F ( k x) - ∂F ∂ k x G( k x)
By a direct computation it is easy to realize that Φ m has the last k components identically null.

In the sequel, we will denote by Φm the vector in R n that contains the first n components of Φ m .

In other words, Φ m [ ΦT m , 0 T k ] T . Additionally, we set φm

φ m 0 k (φ m is defined by algorithm 2).
We have the following result:

Lemma 3 L G Ωm + L Φm dh = L G Ωm + L F L m G dh Proof: We have L F L m G dh = L G L F L m-1 G dh + L Φ1 L m-1 G dh. The first term L G L F L m-1 G dh ∈ L G Ωm . Hence, we need to prove that L G Ωm + L Φm dh = L G Ωm + L Φ1 L m-1 G dh.
We repeat the previous procedure m times. Specifically, we use the equality

L Φj L m-j G dh = L G L Φj L m-j-1 G dh + L Φj+1 L m-j-1 G dh, for j = 1, • • • , m, and we remove the first term since L G L Φj L m-j-1 G dh ∈ L G Ωm Lemma 4 Φm = m j=1 c n j (L G h, L 2 G h, • • • , L m G h)φ j , i.e.
, the vector Φm is a linear combination of the vectors φ j (j = 1, • • • , m), where the coefficients (c n j ) depend on the state only through the functions that generate the codistribution L m Proof: We proceed by induction. By a direct computation it is immediate to obtain:

Φ1 = φ 1 L G h. Inductive step: Let us assume that Φm-1 = m-1 j=1 c j (L G h, L 2 G h, • • • , L m-1 G h)φ j .
We have:

Φ m = [Φ m-1 , G] = m-1 j=1 c j φ j 0 k , G = m-1 j=1 c j φ j 0 k , G - m-1 j=1 L G c j φ j 0 k
We directly compute the Lie bracket in the sum (note that φ j is independent of the unknown input w and its time derivatives):

φ j 0 k , G = [φ j , g]w 0 k = φ j+1 L 1 G h 0 k
Regarding the second term, we remark that

L G c j = m-1 i=1 ∂cj ∂(L i G h) L i+1 G h. By setting cj = c j-1 L 1
G h for j = 2, • • • , m and c1 = 0, and by setting cj = -

m-1 i=1 ∂cj ∂(L i G h) L i+1 G h for j = RR n°9027
1, • • • , m -1 and cm = 0, we obtain Φm = m j=1 (c j + cj )φ j , which proves our assert since

c n j ( cj + cj ) is a function of L G h, L 2 G h, • • • , L m G h
It also holds the following result:

Lemma 5 If w = 0, φm = m j=1 b n j (L G h, L 2 G h, • • • , L m G h)Φ j , i.e.
, the vector φm is a linear combination of the vectors Φ j (j = 1, • • • , m), where the coefficients (b n j ) depend on the state only through the functions that generate the codistribution L m Proof: We proceed by induction. By a direct computation it is immediate to obtain:

φ1 = Φ 1 1 L G h (note that L G h = L 1 g w = 0). Inductive step: Let us assume that φm-1 = m-1 j=1 b j (L G h, L 2 G h, • • • , L m-1 G h)Φ j . We need to prove that φm = m j=1 b n j (L G h, L 2 G h, • • • , L m G h)Φ j .
We start by applying on both members of the equality φm-1 =

m-1 j=1 b j (L G h, L 2 G h, • • • , L m-1 G
h)Φ j the Lie bracket with respect to G. We obtain for the first member:

[ φm-1 , G] = φm L 1 G h.
For the second member we have:

m-1 j=1 [b j Φ j , G] = m-1 j=1 b j [Φ j , G] - m-1 j=1 L G b j Φ j = = m-1 j=1 b j Φ j+1 - m-1 j=1 m-1 i=1 ∂b j ∂(L i G h) L i+1 G hΦ j Since L G h = L 1 g w = 0, by setting bj = bj-1 L 1
G h for j = 2, • • • , m and b1 = 0, and by setting bj = -

m-1 i=1 ∂bj ∂(L i G h) L i+1 G h L 1 G h for j = 1, • • • , m
1. span{L Φ0 dh, L Φ1 dh, • • • , L Φm dh, L 1 G dh, • • • L m G dh}; 2. span{L φ0 dh, L φ1 dh, • • • , L φm dh, L 1 G dh, • • • L m G dh};
We are now ready to prove the following fundamental result:

Theorem 1 (Separation) If w = 0, Ωm = Ωm [Ω m , 0 k ] + L m
Proof: We proceed by induction. By definition, Ω0 = Ω0 since they are both the span of dh. Inductive step: Let us assume that Ωm-1 = Ωm-1 . We have:

Ωm = Ωm-1 + L F Ωm-1 + L G Ωm-1 = Ωm-1 + L F Ωm-1 + L G Ωm-1 = Ωm-1 + [L f Ω m-1 , 0 k ] + L F L m-1 + L G Ωm-1 . On the other hand, L F L m-1 = L F L 1 G dh + • • • + L F L m-2 G dh + L F L m-1 G dh.
The first m -2 terms are in Ωm-1 . Hence we have:

Ωm = Ωm-1 + [L f Ω m-1 , 0 k ] + L F L m-1 G dh + L G Ωm-1
. By using lemma 3 we obtain:

Ωm = Ωm-1 + [L f Ω m-1 , 0 k ] + L Φm-1 dh + L G Ωm-1
. By using again the induction assumption we obtain:

Ωm = [Ω m-1 , 0 k ] + L m-1 + [L f Ω m-1 , 0 k ] + L Φm-1 dh + L G [Ω m-1 , 0 k ]+L G L m-1 = [Ω m-1 , 0 k ]+L m +[L f Ω m-1 , 0 k ]+L Φm-1 dh+[L g L 1 g Ω m-1 , 0 k ], where we used L m + L G [Ω m-1 , 0 k ] = L m + [L g L 1 g Ω m-1 , 0 k ],
which holds because L G h = L 1 g w = 0. By using proposition 7, we obtain:

Ωm = [Ω m-1 , 0 k ]+L m +[L f Ω m-1 , 0 k ]+L φm-1 dh+[L g L 1 g Ω m-1 , 0 k ] = Ωm
Inria Theorem 1 is fundamental. It allows us to obtain all the observability properties of the original state by restricting the computation to the codistribution defined by algorithm 3, namely a codistribution whose covectors have the same dimension of the original space. In other words, the dimension of these covectors is independent of the state augmentation.

Convergence

Algorithm 3 is recursive and Ω m ⊆ Ω m+1 . This means that, if for a given m the differentials of the components of the original state belong to Ω m , we can conclude that the original state is weakly locally observable. On the other hand, if this is not true, we cannot exclude that it is true for a larger m. The goal of this section is precisely to address this issue. We will show that the algorithm converges in a finite number of steps and we will also provide the criterion to establish that the algorithm has converged (theorem 2). This theorem will be proved at the end of this section since we need to introduce several important new quantities and properties. When investigating the convergence properties of algorithm 3, we remark that, the main difference between algorithm 1 and 3, is the presence of the last term in the recursive step of the latter. Without this term, the convergence criterion would simply consist of the inspection of the equality Ω m+1 = Ω m , as for algorithm 1. Indeed, the convergence criterion of algorithm 1 is a consequence of the fact that, all the terms that appear at the recursive step of algorithm 1, are the Lie derivative of the codistribution at the previous step, along fixed vector fields (i.e., vector fields that remain the same at each step of the algorithm). This is not the case for the last term at the recursive step of algorithm 3.

The following result provides the convergence criterion in a very special case that basically occurs when the contribution due to the last term in the recursive step of algorithm 3 is included in the other terms. In this case, we obviously obtain that the convergence criterion consists of the inspection of the equality Ω m+1 = Ω m , as for algorithm 1. For any integer j ≥ 0 we define:

χ j L φj L 1 g L 1 g (28)
We have the following result:

Lemma 6 Let us denote by Λ j the distribution generated by φ 0 , φ 1 , • • • , φ j and by m(≤ n -1) the smallest integer for which Λ m+1 = Λ m (n is the dimension of the state x). In the very special case when χ j = 0, ∀j = 0, • • • , m, algorithm 3 converges at the integer j such that Ω j+1 = Ω j and this occurs in at most n -1 steps8 .

Proof: First of all, we remind the reader that the existence of an integer m(≤ n-1) such that Λ m+1 = Λ m is proved in [START_REF] Isidori | Nonlinear Control Systems[END_REF]. In particular, the first chapter in [START_REF] Isidori | Nonlinear Control Systems[END_REF] analyzes the convergence of Λ j with respect to j. It is proved that the distribution converges to Λ * and that the convergence is achieved at the smallest integer for which we have Λ m+1 = Λ m . Additionally, we have Λ m+1 = Λ m = Λ * and m cannot exceed n -1.

In the very special case when χ j = 0, ∀j = 0, • • • , m, thanks to the aforementioned convergence of the distribution Λ j , we easily obtain that L φj-1 L g h = 0 ∀j ≥ 1. Now, let us consider special case is now characterized by

L i φ j L 1 g L 1 g = 0, ∀j = 0, • • • , m and ∀i = 1, • • • , mu.

RR n°9027

the following equation:

L φj h = 1 L 1 g L φj-1 L g h -L g L φj-1 h (29) Since L φj-1 L g h = 0 ∀j ≥ 1, we have L φj h = -L g L 1 g
L φj-1 h, for any j ≥ 1. Therefore, we conclude that, the last term in the recursive step of algorithm 3, is included in the second last term and, in this special case, algorithm 3 has converged when Ω m+1 = Ω m . This occurs in at most n -1 steps, as for algorithm 1.

Let us consider now the general case. To proceed we need to introduce several important new quantities and properties. For a given positive integer j we define the vector ψ j ∈ R n by the following algorithm:

1. ψ 0 = f ; 2. ψ j = [ψ j-1 , g L 1 g ]
It is possible to find the expression that relates these vectors to the vectors φ j , previously defined. Specifically we have:

Lemma 7 It holds the following equation:

ψ j = φ j + j-1 i=0 (-) j-i L j-i-1 g L 1 g L φi L 1 g L 1 g g L 1 g (30)
Proof: We proceed by induction. By definition ψ 0 = φ 0 = f and equation ( 30) holds for j = 0. Inductive step: Let us assume that it holds for a given j -1 ≥ 0 and let prove its validity for j. We have:

ψ j = ψ j-1 , g L 1 g = φ j-1 , g L 1 g + j-2 i=0 (-) j-i-1 L j-i-2 g L 1 g L φi L 1 g L 1 g g L 1 g , g L 1 g
On the other hand:

φ j-1 , g L 1 g = φ j - L φj-1 L 1 g L 1 g g L 1 g and j-2 i=0 (-) j-i-1 L j-i-2 g L 1 g L φi L 1 g L 1 g g L 1 g , g L 1 g = -L g L 1 g j-2 i=0 (-) j-i-1 L j-i-2 g L 1 g L φi L 1 g L 1 g g L 1 g = j-2 i=0 (-) j-i L j-i-1 g L 1 g L φi L 1 g L 1 g g L 1
g Inria Hence:

ψ j = φ j - L φj-1 L 1 g L 1 g g L 1 g + j-2 i=0 (-) j-i L j-i-1 g L 1 g L φi L 1 g L 1 g g L 1
g , which coincides with [START_REF] Mirzaei | A Kalman filter-based algorithm for IMU-camera calibration: Observability analysis and performance evaluation[END_REF] We have the following result:

Lemma 8 For i = 0, 1, • • • , m -2, we have: D L φi L 1 g L 1 g ∈ Ω m (31)
Proof: By construction, DL φi h ∈ Ω m , for any i = 1, • • • , m -1. On the other hand, we have:

L φi h = 1 L 1 g [L φi-1 L g h -L g L φi-1 h] = L φi-1 L 1 g L 1 g -L g L 1 g L φi-1 h
We compute the differential of both members of this equation. Since

DL g L 1 g L φi-1 h ∈ Ω m , for any i = 1, • • • , m -1, also D L φ i-1 L 1 g L 1 g
∈ Ω m From lemma 7 with j = 1, • • • , m -1 and lemma 8 it is immediate to obtain the following result:

Proposition 8 If Ω m is invariant with respect to L f and L g L 1 g
then it is also invariant with

respect to L φj , j = 1, • • • , m -1.
In order to obtain the convergence criterion for algorithm 3 we need to find the analytic expression that relates three consecutive Lie derivatives, L φj h, L φj-1 h and L φj-2 h. This will allow us to detect the key quantity that governs the convergence of algorithm 3, in particular regarding the contribution due to the last term in the recursive step. This quantity is a scalar and it is the one provided in (3). For the sake of clarity, we provide equation (3) below:

τ L 2 g (L 1 g ) 2
where L 2 g L 2 g h. The behaviour of the last term in the recursive step of algorithm 3 is given by the following lemma: Lemma 9 We have the following key equality:

L φj h = L φj-2 τ + τ L φj-2 L 1 g L 1 g -L g L 1 g L φj-2 L 1 g L 1 g + L φj-1 h (32) j ≥ 2.
Proof: We will prove this equality by an explicit computation. We have:

L φj h = 1 L 1 g L φj-1 L g h -L g L φj-1 h RR n°9027
The second term on the right hand side simplifies with the last term in [START_REF] Panahandeh | Observability Analysis of a Vision-Aided Inertial Navigation System using Planar Features on the Ground[END_REF]. Hence we have to prove:

1 L 1 g L φj-1 L 1 g = L φj-2 τ + τ L φj-2 L 1 g L 1 g -L g L 1 g L φj-2 L 1 g L 1 g (33)
We have:

1 L 1 g L φj-1 L 1 g = 1 (L 1 g ) 2 L φj-2 L 2 g -L g L φj-2 L 1 g (34)
We remark that:

1 (L 1 g ) 2 L φj-2 L 2 g = L φj-2 τ + 2τ L φj-2 L 1 g L 1 g and 1 (L 1 g ) 2 L g L φj-2 L 1 g = τ L φj-2 L 1 g L 1 g + L g L 1 g L φj-2 L 1 g L 1 g
By substituting these two last equalities in [START_REF] Trawny | Observability-based Consistent EKF Estimators for Multi-robot Cooperative Localization[END_REF] we immediately obtain [START_REF] Perera | On the linear and nonlinear observability analysis of the SLAM problem[END_REF] Lemma 10 In general, it exists an integer m ≤ n + 2 (being n the dimension of x) such that Dτ ∈ Ω m .

Proof: Let us introduce the following notation, for a given integer j:

• Z j L φj+2 h; • B j L φj τ ; • χ j L φ j L 1 g L 1 g .
By construction, DZ j ∈ Ω j+3 . On the other hand, from equation (32), we immediately obtain:

DZ j = DB j + χ j Dτ + τ Dχ j -L g L 1 g Dχ j + DL φj+1 h (35)
By using lemma 8 we obtain the following results:

• τ Dχ j ∈ Ω j+2 ; • L g L 1 g Dχ j ∈ Ω j+3 .
Additionally, L g L 1 g

DL φj+1 h ∈ Ω j+3 . Hence, from [START_REF] Vidal-Calleja | On the Observability of Bearing-only SLAM[END_REF], we obtain that the following covector:

Z j DB j + χ j Dτ (36)
belongs to Ω j+3 . Let us denote by j * the smallest integer such that:

DB j * = j * -1 j=0 c j DB j + c -1 Dh (37)

Inria

Note that j * is a finite integer and in particular j * ≤ n -1. Indeed, if this would not be the case, the dimension of the codistribution generated by Dh, DB 0 , DB 1 , • • • , DB n-1 would be n + 1, i.e., larger than n. From ( 37) and ( 36) we obtain:

Z j * = j * -1 j=0 c j DB j + c -1 Dh + χ j * Dτ (38)
From equation [START_REF] Wang | Observing the states of systems with unmeasurable disturbance[END_REF], for j = 0, • • • , j * -1, we obtain: DB j = Z j -χ j Dτ . By substituting in (38) we obtain:

Z j * - j * -1 j=0 c j Z j -c -1 Dh =   - j * -1 j=0 c j χ j + χ j *   Dτ (39)
We remark that the left hand side consists of the sum of covectors that belong to Ω j * +3 . Since in general χ j * = j * -1 j=0 c j χ j , we have Dτ ∈ Ω j * +3 . By setting m j * + 3, we have m ≤ n + 2 and Dτ ∈ Ω m The previous lemma ensures that, in general, it exists a finite m ≤ n + 2 such that Dτ ∈ Ω m . Note that the previous proof holds if the quantity χ j * -j * -1 j=0 c j χ j does not vanish. This holds in general, with the exception of the trivial case considered in lemma 6, in which case χ j = 0, ∀j.

The following theorem allows us to obtain the criterion to stop algorithm 3:

Theorem 2 If Dτ ∈ Ω m and Ω m is invariant under L f and L g L 1 g
, then Ω m+p = Ω m ∀p ≥ 0

Proof: We proceed by induction. Obviously, the equality holds for p = 0. Inductive step: let us assume that Ω m+p = Ω m and let us prove that Ω m+p+1 = Ω m . We have to prove that DL φm+p h ∈ Ω m . Indeed, from the inductive assumption, we know that

Ω m+p (= Ω m ) is invariant under L f and L g L 1 g
. Additionally, because of this invariance, by using proposition 8, we obtain that Ω m is also invariant under L φj , for j = 1, 2 , also the Lie

derivatives along g L 1 g of DL φm+p-1 h and D L φ m+p-2 L 1 g L 1 g
belong to Ω m . Now, we use equation ( 32) for j = m + p. By computing the differential of this equation it is immediate to obtain that DL φm+p h ∈ Ω m We conclude this section by providing an upper bound for the number of steps that are in general necessary to achieve the convergence. The dimension of Ω j * +2 is at least the dimension of the span of the covectors:

Dh, Z 0 , Z 1 , • • • , Z j * -1 .
From the definition of j * , we know that the vectors Dh, DB 0 , DB 1 , • • • , DB j * -1 are independent meaning that the dimension of their span is j * + 1. Hence, from [START_REF] Wang | Observing the states of systems with unmeasurable disturbance[END_REF], it easily follows that the dimension of the span of the vectors Dh, Z 0 , Z 1 , • • • , Z j * -1 , Dτ is at least j * + 1. Since Ω j * +3 contains this span, its dimension is at least j * + 1. Therefore, the condition Ω m+1 = Ω m , for m ≥ j * + 3 is achieved for m ≤ n + 2.

Extension to the case of multiple known inputs

It is immediate to repeat all the steps carried out in the previous two subsections and extend the validity of theorem 1 to the case of multiple known inputs (m u > 1). Additionally, also theorem 2 can be easily extended to cope with the case of multiple known inputs. In this case, requiring that Ω m+1 = Ω m means that Ω m must be invariant with respect to L g L 1 g and all L f i simultaneously.

Inria 7 Conclusion

The goal of this work was to present the analytic solution of a fundamental open problem in control theory. The problem is known in the literature as the Unknown Input Observability (UIO) problem. It consists in deriving the analytic criterion that allows us to check the system observability in presence of unknown inputs (throughout this work we also used the term disturbance to mean an unknown input). The solution here provided holds in the case of a single unknown input. In other words, it is provided the analytic criterion that allows us to obtain the observability of a nonlinear system in presence of a single unknown input and multiple known inputs (see section 2 for a definition of the considered systems).

As for the observability rank condition, the proposed analytic criterion is based on the computation of the observable codistribution. Similarly to the case of only known inputs, the observable codistribution is obtained by recursively computing the Lie derivatives of the outputs along the vector fields that characterize the dynamics. However, in correspondence of the unknown input, the corresponding vector field must be suitably rescaled. Additionally, the Lie derivatives of the outputs must also be computed along a new set of vector fields that are obtained by recursively performing suitable Lie bracketing of the vector fields that define the dynamics. In practice, the entire observable codistribution is obtained by a very simple recursive algorithm. This algorithm was provided in section 3. Finally, it was shown that the recursive algorithm converges in a finite number of steps and the criterion to establish that the convergence has been reached was provided.

The analytic criterion here introduced is the extension of the observability rank condition to the case when the dynamics are driven by an unknown input (and multiple known inputs). The analytic criterion was quickly outlined in section 4 to make easy its automatic implementation. Its validity was proven in section 6. Finally, it was illustrated in section 5 by checking the weak local observability of several nonlinear systems driven by multiple known inputs and a single unknown input.

We are currently extending the proposed analytic criterion to deal with the general case of multiple unknown inputs and when the dynamics are affine (and not simply linear) in the inputs (both known and unknown). In few words, to deal with the general case described by equation [START_REF] Hunt | Prevalence: a translation-invariant "almost every" on infinite-dimensional spaces[END_REF].

We conclude this work with the following remark, which has a fundamental practical importance for designing an estimator in presence of a single unknown input. We remark that, the state estimated by the two estimators adopted in section 5 (sections 5.2.4 and 5.3.4), includes the disturbance together with its first order time derivative. We found a much worse performance by using an estimator that only estimates the original state or by including in the state only the disturbance (without its time derivative).

We conjecture that this is a consequence of the fact that the observable codistibution is Ω 2 , i.e., for the considered system, algorithm 3 converges at its second step. Indeed, we proved that, for a system for which algorithm 3 converges to Ω m (i.e., converges in m steps) the observable modes 9 satisfy a fundamental property. These functions are constant on the indistinguishable sets only in the extended state space that includes the disturbance and its time derivatives up to the m -1 order (see proposition 4 together with theorem 1 and lemma 2). Note that, in the space of the original state (or in a less extended space, namely, that does not include all the first m -1 time derivatives), the observable modes are not constant on the indistinguishable sets. Proving this conjecture will require further theoretical investigations. The validity of this conjecture would make the analytic tool not only a tool to check the state observability but also a fundamental tool to design an appropriate estimator for a given nonlinear system in presence of a disturbance.

Inria

A The case when L 1 g = 0

We consider the case of multiple outputs. In other words, our system is defined by the following equations:

     ẋ = mu i=1 f i (x)u i + g(x)w y k = h k (x), k = 1, • • • , p (40)
We introduce the following notation:

• F is the space of functions that contains all the outputs h 1 , • • • , h p and their Lie derivatives along the vector fields f 1 , • • • , f mu , up to any order;

• DF is the codistribution generated by the differentials, with respect to the state x, of the functions in F;

• L G F is the space of functions that consists of the Lie derivatives along G of the functions in F (we remind the reader that G is the vector defined in ( 27));

It is immediate to prove the following properties:

• From F we can select a set of functions such that their differentials generate DF.

• It exists an integer m such that, by running m recursive steps of algorithm 4, we obtain a codistribution Ωm that contains [DF, 0 m ] (i.e., the codistribution DF once embedded in R n+m ) 10 .

• In general, the functions belonging to L G F, are functions of x and w.

Because of the second property, we are allowed to choose any function in F as a system output (note that the functions in F only depend on the state x and not on the unknown input w).

Hence, if for a given system the condition L g h k = 0, ∀k = 1, • • • p, we can redefine the output by choosing any function in F.

To conclude, let us consider the case when no function in L G F depends on w. This means that L G F only contains the zero function (the Lie derivative along G of any function in F vanishes). As a result, any order Lie derivative of any outputs, computed along F 1 , • • • , F mu (which are the vector fields defined in ( 27)) and at least once along G, vanishes. This means that, in algorithm 4, we can ignore the contribution due to the Lie derivative along G. But this trivially means that the observable codistribution is precisely DF and the unknown input is spurious.

5 . 6 .

 56 Use the recursive step of algorithm 3 to build the codistribution Ω m for m ≥ 2, and, for each m, check if Dτ ∈ Ω m . Denote by m the smallest m such that Dτ ∈ Ω m . For each m ≥ m , check if Ω m+1 = Ω m and denote by Ω * = Ω m * , where m * is the smallest integer such that m * ≥ m and Ω m * +1 = Ω m * (note that m * ≤ n + 2).

Figure 1 :

 1 Figure 1: The vehicle state in cartesian and polar coordinates ([x v , y v , θ] T and [r, φ, θ] T , respectively) together with the three considered outputs (r, β and φ).

Figure 2 :

 2 Figure 2: The vehicle state together with the three considered outputs.

1 2 (

 2 xv cos γ+yv sin γ) 2 and

Figure 3 :

 3 Figure 3: Typical simulated trajectories. Left side without disturbance, right side with disturbance.

Figure 4 :

 4 Figure 4: Estimated trajectory in the case when the output is h = r. Dots blue are the ground truth, red circles the estimated trajectory by only using the knowledge of the proprioceptive measurements, black stars the trajectory estimated by our estimator. On the left side is the case when γ is known and on the right side when it is unknown.

Figure 5 :

 5 Figure 5: The same as in figure 4 in the case when the output is h = β.

Figure 7 :

 7 Figure 7: Local and global frame for the considered problem.The z-axis of the latter is aligned with the direction of the disturbance (assumed to be known and constant in time). The speed V is the vehicle speed with respect to the air, which differs from the ground speed because of the disturbance (w).

Figure 8 :

 8 Figure 8: A typical simulated trajectory in absence of disturbance. In blue the true trajectory, in red the trajectory estimated by only integrating the gyroscope and the airspeed measurements and in black the trajectory estimated by the proposed EKF.

Figure 9 :

 9 Figure 9: A typical simulated trajectory in presence of disturbance along the z-axis. In blue the true trajectory, in red the trajectory estimated by only integrating the gyroscope and the airspeed measurements and in black the trajectory estimated by the proposed EKF.

Figure 10 :

 10 Figure 10: Estimation error on the distance of the two observed point features in absence of the disturbance.

Figure 11 :

 11 Figure 11: As in fig. 10 but in presence of the disturbance.

Figure 12 :

 12 Figure 12: Estimation error on the vehicle roll angle. Left side in absence of the disturbance, right side in presence of the disturbance.

Inria

Figure 13 :

 13 Figure 13: As in fig. 12 but for the pitch angle.

Figure 14 :

 14 Figure 14: As in fig. 12 but for the yaw angle.

and θ is weakly observable in x 0 Proposition 6

 06 If the scalar function θ(x) is weakly observable in x 0 , then ∃k and ξ 0 such that dθ ∈ Ωk a.e. on an open neighbourhood B x0 . Proof: We proceed by contradiction. ∀k and ξ and for any open ball centered on x 0 with radius r (B r x0 ), it exists a set C r x0 ⊆ B r x0 with measure strictly larger than zero for which dθ /

- 1 Proposition 7

 17 and bm = 0, we obtain φm = m j=1 ( bj + bj )Φ j , which proves our assert since bn j ( bj + bj ) is a function of L G h, L 2 G h, • • • , L m G hAn important consequence of the previous two lemmas is the following result: If w = 0, the following two codistributions coincide:

1 3 . 2 7 4 1

 13271 Observable codistribution in the case without unknown inputs . . . . . . . . . . . 6 Observable codistribution in presence of a single unknown input . . . . . . . . . Unicycle with one input unknown . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.1.

Table 2 :

 2 Weak local observability of the state in all the considered scenarios

	Inria

  1 The system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.1.2 Intuitive procedure to obtain the observability properties . . . . . . . . . 11 5.1.3 Analytic results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.2 Unicycle in presence of an external unknown input . . . . . . . . . . . . . . . . . 16 5.2.1 The system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.2.2 Observability properties when γ is known . . . . . . . . . . . . . . . . . . 17 5.2.3 Observability properties when γ is unknown . . . . . . . . . . . . . . . . . 19 5.2.4 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.3 Vehicle moving in 3D in presence of a disturbance . . . . . . . . . . . . . . . . . 24 5.3.1 The system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.3.2 Observability in absence of disturbance . . . . . . . . . . . . . . . . . . . 26 5.3.3 Observability in presence of the disturbance . . . . . . . . . . . . . . . . . 27 5.3.4 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 State Indistinguishability, State augmentation and Observable Codistribution . . 34 6.2 Proof of the validity of the analytic criterion . . . . . . . . . . . . . . . . . . . . . 39 6.2.1 Separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.2.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6.2.3 Extension to the case of multiple known inputs . . . . . . . . . . . . . . . 47

	6 Analytic Derivations	34
	6.1 7 Conclusion	49
	A The case when L 1 g = 0	51

RR n°9027

RESEARCH CENTRE GRENOBLE -RHÔNE-ALPES

Inovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

RR n°9027

The case when L 1 g = 0 for all the outputs is dealt in appendix A.RR n°9027

The convergence criterion of algorithm 1 is a consequence of the fact that, all the terms that appear at the recursive step of algorithm 1, are the Lie derivative of the codistribution at the previous step, along fixed vector fields (i.e., vector fields that remain the same at each step of the algorithm). This is not the case for the last term at the recursive step of algorithm 3.Inria

If the Lie derivative of any function in F vanishes, it means that the unknown input can be ignored to obtain the observability properties, as it is shown in appendix A.

Note that this check requires at most n -1 (simple) operations.RR n°9027

Note that, in the case of multiple known inputs (i.e., mu > 1), the previous result does not change. In particular, Λ j becomes the distribution generated by1 φ 0 , 1 φ 1 , • • • , 1 φ j , • • • , mu φ 0 , mu φ 1 , • • • , muφ j and the very

See definition 2 for the definition of observable mode.RR n°9027

Note that, from proposition 5, the functions in F are weakly observable.RR n°9027