{'fraction_non_alphanumeric': 0.04234035128533209, 'fraction_numerical': 0.01531542010778954, 'mean_word_length': 4.477171373964748, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Sensor-based Long Baseline Position and Velocity Navigation Filter for Underwater Vehicles

This paper presents a novel Long Baseline (LBL) position and velocity navigation filter for underwater vehicles based directly on the sensor measurements. The solution departs from previous approaches as the range measurements are explicitly embedded in the filter design, therefore avoiding inversion algorithms. Moreover, the nonlinear system dynamics are considered to their full extent and no linearizations are carried out whatsoever. The filter error dynamics are globally asymptotically stable (GAS) and it is shown, under simulation environment, that the filter achieves similar performance to the Extended Kalman Filter (EKF) and outperforms linear position and velocity filters based on algebraic estimates of the position obtained from the range measurements.


INTRODUCTION
Accurate navigation systems are essential for the successful operation of autonomous vehicles. Although there exist alternatives such as terrain-based navigation, most navigation systems contain an Inertial Navigation System (INS) that provides the state of the vehicle by integrating, in open-loop, the information provided by inertial sensors, e.g., accelerometers and rate gyros. Although INS provides very good short term results, its performance necessarily degrades over time, not only due to the integration of sensor noise but also due to sensor bias errors. In order to overcome these drawbacks, aiding devices are considered to correct INS errors. This paper addresses the problem of vehicle navigation using ranges to a set of landmarks disposed in a Long Baseline (LBL) configuration.
Among the myriad of aiding devices, the Global Positioning System (GPS) is a very popular choice, see, e.g., Sukkarieh et al. (1999) Yun et al. (1999), and Vik, B. and Fossen, T. (2001). For underwater vehicles, GPS is not a solution due to the strong attenuation that the electromagnetic field suffers in water. Therefore, other solutions have been sought in the past, including acoustic positioning systems like LBL and Short Baseline (SBL), see Jouffroy and Opderbecke (2004), Kinsey and Whitcomb (2003), Larsen (2001), Larsen (2000), Vaganay et al. (1998), and references therein. In Youngberg (1992) the author proposes a GPS-like system consisting of buoys equipped with DGPS receptors. A related solution, denominated as GPS Intelligent Buoy (GIB) system, is now commercially available, see Thomas (1998). Further work on the GIB underwater positioning system can be found in Alcocer et al. (2007). Position and linear velocity globally asymptotically stable (GAS) filters based on a Ultra-Short Baseline (USBL) positioning system were presented by the authors in Batista et al. (2008). For interesting discussions and more detailed surveys on underwater vehicle navigation and sensing devices see Kinsey et al. (2006) and Leonard et al. (1998). This paper presents a position and linear velocity navigation filter based on range measurements disposed in a LBL configuration. Traditional solutions resort either to the Extended Kalman Filter (EKF) or to solutions based on position algebraic estimates obtained from the range measurements. The solution presented in the paper departs from previous approaches as the range measurements are explicitly embedded in the filter design, therefore avoiding inversion algorithms. Moreover, the nonlinear system dynamics are considered to their full extent and no linearizations are carried out whatsoever, which allows to show that the filter error dynamics are globally asymptotically stable. Central to the proposed filtering framework is the derivation of a linear time-varying (LTV) system that captures the dynamics of the nonlinear system. The LTV model is achieved through appropriate state augmentation, which is shown to mimic the nonlinear system. Applications of the proposed solution are many and, under simulation environment, it is shown that the filter achieves similar performance to the Extended Kalman Filter (EKF) and outperforms linear position and velocity filters based on position algebraic estimates obtained directly from the range measurements.
The paper is organized as follows. The problem statement and nominal system dynamics are introduced in Section 2, while the filter design is detailed in Section 3. Simulation results are presented in Section 4 and Section 5 summarizes the main conclusions of the paper.

Notation
Throughout the paper the symbol 0 n×m denotes an n × m matrix of zeros, I n an identity matrix with dimension n × n, and diag(A 1 , . . . , A n ) a block diagonal matrix. When the dimensions are omitted the matrices are assumed of appropriate dimensions. If x and y are two vectors of identical dimensions, x × y and x · y represent the cross and inner products, respectively.

PROBLEM STATEMENT
Consider an underwater vehicle moving in a scenario where there is a set of fixed landmarks installed in a Long Baseline configuration and suppose that the vehicle measures the range to each of the landmarks, as depicted in Fig. 1. Further assume that the vehicle is equipped with an Inertial Measurement Unit (IMU), consisting of two triads of orthogonally mounted accelerometers and rate gyros, and an Attitude and Heading Reference System (AHRS). The problem considered in the paper is the design of a sensor-based globally asymptotically stable filter to estimate the position and linear velocity of the vehicle.

System Dynamics
In order to detail the problem framework, let {I} denote an inertial reference coordinate frame and {B} a coordinate frame attached to the vehicle, commonly denominated as the body-fixed coordinate frame. The linear motion of the vehicle is described bẏ where p ∈ R 3 denotes the inertial position of the vehicle, v ∈ R 3 is the velocity of the vehicle relative to {I} and expressed in body-fixed coordinates, and R is the rotation matrix from {B} to {I}, which satisfiesṘ(t) = R(t)S (ω(t)), where ω ∈ R 3 is the angular velocity of {B}, expressed in body-fixed coordinates, and S (ω) is the skewsymmetric matrix such that S (ω) x is the cross product ω × x.
The AHRS provides the attitude rotation matrix R and the angular velocity ω, while the IMU, assumed mounted at the center of mass of the vehicle, measures the linear acceleration a, which satisfies where g ∈ R 3 denotes the acceleration of gravity, expressed in body-fixed coordinates. Ideal accelerometers would not measure the gravitational term but in practice this term must be considered due to the inherent physics of the accelerometers, see Kelly (1994) for further details. Since the magnitude of g is usually well known, it would be possible to cancel this term in (2) as the attitude of the vehicle is measured. However, even small errors on R would lead to large errors in the acceleration compensation. Therefore, the acceleration of gravity is considered here as unknown state, in addition to p and v. The term S (ω(t)) v(t) corresponds to the Coriolis acceleration and cannot be neglected, particularly for vehicles that execute aggressive maneuvers. Finally, let s i ∈ R 3 , i = 1, . . . , n L , denote the inertial positions of the landmarks. Then, the range measurements are given by The derivative of the velocity can be written, from (2), aṡ v(t) = a(t) − S (ω(t)) v(t) + g(t).
(4) The derivative of g, assuming that the acceleration of gravity is constant in inertial coordinates, is given bẏ g(t) = −S (ω(t)) g(t).
(5) Combining (1) and (3)-(5) yields the nonlinear system The problem considered in the paper is the design of a filter for (6) assuming noisy measurements.
In the accelerometer measurements (2) it was not considered accelerometer bias. Its inclusion in the system dynamics is trivial but the observability analysis would result even more tedious. Nevertheless, the observability of linear motion quantities considering accelerometer bias was previously studied by the authors in Batista et al. (2009a) and it is rather straightforward to conclude about the necessary (and sufficient) conditions for observability of the system considering also accelerometer bias. For the sake of simplicity and clarity of presentation, which focuses on the novel Long Baseline solution, the accelerometer is assumed to be calibrated in this paper and the overall system analysis and design will be considered elsewhere.

Long Baseline Configuration
Long Baseline acoustic configurations have been widely used in the past in the design of navigation systems. In the remainder of the paper the following assumption is considered: Assumption 1. There exists at least 4 noncoplanar landmarks.
When there exist at least 4 noncoplanar landmarks, it is always possible to determine the position of the vehicle from the range measurements. When there are fewer measurements that may not always be possible. For example, for a static vehicle and 3 landmarks, there exist two possible solutions. Although it is assumed that there are at least 4 noncoplanar landmarks, the proposed solution is general and a more detailed discussion on different LBL configurations will be presented in the sequel.

FILTER DESIGN
This section presents the main results of the paper. Firstly, a state transformation is applied, in Section 3.1, to reduce the complexity of the system dynamics. Afterwards, state augmentation is proposed, in Section 3.2, in order to derive sensor-based deterministic system dynamics, and in Section 3.3 the observability of the resulting system is analyzed. The design of a Kalman filter is detailed in Section 3.4 and finally, in Section 3.5, some practical considerations are presented.

State Transformation
Let T(t) := diag (I, R(t), R(t)) and consider the state transformation which is a Lyapunov state transformation previously used by the authors, see Batista et al. (2009b). The new system dynamics are given by where u(t) := R(t)a(t). Notice that, as (7) is a Lyapunov state transformation, all observability properties are preserved Brockett (1970). The advantage of considering the state transformation (7) is that the new system is time invariant, although it is still nonlinear.

State Augmentation
To derive a linear system that mimics the dynamics of the nonlinear system (8), define n L + 4 additional scalar state variables as and denote by . . x nL+7 T ∈ R n , n = 13 + n L , the augmented state. It is easy to verify that the augmented dynamics can be written aṡ where and In order to complete the augmented system dynamics, notice first that the states x 4 , . . . , x 3+nL are measured. In addition to that, it is straightforward to show that where the right side of (10) is known and the left side depends on the system state. Discarding the original nonlinear system output, it is possible to write an augmented system output as . .
where C nL 2 is the number of 2-combinations of n L elements, i.e., C nL 2 = (nL−1)nL 2 . In compact form, the augmented system dynamics are given by where is the matrix that encodes all the possible combinations of differences of pairs of ranges.
The dynamic system (11) can be regarded as a linear timevarying system, even though the system matrices A(t) and C(t) depend explicitly on the system input and output, as evidenced by (9) and (12). However, these are known signals and therefore pose no problem, other than the fact that the observability of the system may depend on the system input, which does not happen for linear systems whose system matrices do not depend on the system input. Also, notice that there is nothing in (11) imposing These restrictions could be easily implemented but this form is preferred since it allows to consider the system as linear. However, care must be taken when extrapolating conclusions from the observability of (11) to the observability of (8) or (6). Finally, the following assumption is required so that (9) is well defined, which is not restrictive from the practical point of view since it would make no sense to have the vehicle at the same position of a landmark, where an acoustic transponder is installed. Assumption 2. The motion of the vehicle is such that

Observability Analysis
In the previous section a LTV system was derived that aims to capture the behavior of the original nonlinear system. The analysis of the observability of this LTV system is carried out in this section and its behavior compared with that of the nonlinear system.
In order to proceed with the analysis of the observability of the LTV system (11), it is convenient to compute the observability Gramian associated with the pair (A(t), C(t)) and, in order to do so, the transition matrix associated with the system matrix A(t). Let Long, but straightforward, computations show that the transition matrix associated with A(t) is given by and φ CA (t, t 0 ) and φ CC (t, t 0 ) are omitted for the sake of simplicity, as they are not required in the sequel. The observability Gramian associated with the pair (A(t), C(t)) is simply given by The following theorem establishes the observability of the LTV system (11). Theorem 1. The linear time-varying system (11) is observable on [t 0 , t f ], t 0 < t f .
Proof. The proof follows by contradiction. Suppose that the LTV system (11) is not observable on I : Taking the time derivative of (14) yields for all t ∈ I. Substituting t = t 0 in (15) gives which implies immediately that d 4 = 0.
(17) Substituting (17) in (16) gives It is straightforward to show that, under Assumption 1, the only solution of (18) is for all t ∈ I. Expanding (20), and considering (17) and (19), allows to write for all i = 1, . . . , n L , t ∈ I or, equivalently, Substituting t = t 0 in (21) gives  Again, it is straightforward to show that, under Assumption 1, the only solution of (22) is Now, considering (23) in (21) and taking its time derivative gives for all i = 1, . . . , n L and t ∈ I. With t = t 0 in (24), Again, under Assumption 1, the only solution of (25) is Finally, substituting (26) in (24) gives for all t ∈ I. Since t − t 0 and (t − t 0 ) 2 are linearly independent functions, the only solution of (27) is d 7 = d 8 = 0. But that contradicts the hypothesis that there exists a nonnull vector d such that (14) is true. Therefore, the LTV system (11) is observable.
The fact that (11) is observable does not mean that the nonlinear system (8) is observable nor that an observer for (11) is also an observer for (8), as there is nothing in the system dynamics (11) imposing the algebraic restrictions (13). However, this turns out to be true, as shown in the following theorem. Theorem 2. The nonlinear system (8) is observable in the sense that, given the output T is uniquely defined. Moreover, a state observer for the LTV system (11) with globally asymptotically stable error dynamics is also a state observer for the nonlinear system (8), with globally asymptotically stable error dynamics.
Proof. It has been shown, in Theorem 1, that the LTV system (11) is observable. Therefore, given the output {y(t), t ∈ [t 0 , t f ]} and the input {u(t), t ∈ [t 0 , t f ]}, the initial state of (11) is uniquely defined. Let T z 1 , z 2 , z 3 ∈ R 3 , z 4 , . . . , z nL+7 (t 0 ) ∈ R, be the initial state of (11) and T be the initial state of the nonlinear system (8). It is easy to show that the evolution, for the nonlinear system, of x 1 (t), is given by while the output of the nonlinear system satisfies Therefore, from (28) and (29), it is trivially shown that for all i, j ∈ {1, . . . , n L } and t ∈ I. Now, notice that, for the LTV system, multiplying the set of augmented outputs y nL+1 , . . . , y nL+C n L 2 by the corresponding sums of pair of ranges yields , while its evolution can be shown to satisfy for all i, j ∈ {1, . . . , n L } and t ∈ I. The states of the augmented LTV system x 4 (t), . . . , x nL+7 (t) are actually measured and correspond to the range measurements. Therefore, it must be z 3+i (t 0 ) = x 1 (t 0 ) − s i (32) for all i ∈ {1, . . . , n L }. Then, from the comparison of (30) and (31), and considering (32), it follows that Under Assumption 1 the only solution of (33) is x 1 (t 0 ) = z 1 (t 0 ) . From (29) it is possible to write for all i, j ∈ {1, . . . , n L } and t ∈ I. On the other hand, the evolution of the square of range for the LTV system (11) can be written as for all i ∈ {1, . . . , n L }. Therefore, it is possible to write for all i, j ∈ {1, . . . , n L } and t ∈ I. Taking the time derivative of both (34) and (35) and comparing for t = t 0 gives Again, under Assumption 1 the only solution of (36) is x 2 (t 0 ) = z 2 (t 0 ) . Finally, taking the second time derivative of both (34) and (35) and comparing for t = t 0 gives Again, under Assumption 1 the only solution of (37) is x 3 (t 0 ) = z 3 (t 0 ). This concludes the proof, as the initial state of the LTV system (11), which is uniquely defined, matches the initial state of the nonlinear system (8). Remark 1. The concept of observability for nonlinear systems is not as strong as that presented in the statement of Theorem 2, see Hermann and Krener (1977). That is the reasoning behind explicitly describing in what sense the system is observable. Remark 2. In the proof of Theorem 2 it was not shown that all the algebraic relations (13) are satisfied. It was only shown that the initial state of the LTV system (11) coincides with the initial state of the nonlinear system (8). However, it is trivial to show that those relations are indeed preserved. Remark 3. Before concluding this section, it is important to remark that, although the observability results were derived with respect to the nonlinear system (8), they also apply to the original nonlinear system (6) as they are related through a Lyapunov transformation. Also, the design of an observer for the original nonlinear system follows simply by reversing the state transformation (7), as it will be detailed in the following section.

Kalman Filter
Although all the results derived so far were presented in a deterministic setting, in practice there exists measurement noise and often system disturbances. Therefore, a filtering solution is proposed in this section instead of an observer. On the other hand, Theorem 2 provides a constructive result in the sense that a dynamic system with globally asymptotically stable error dynamics for the LTV system (8) provides globally asymptotically stable error dynamics for the estimation of the state of the nonlinear system. Therefore, the design of a Kalman filter follows for the LTV system (11), albeit other solutions could be devised, e.g., an H ∞ filter. It is important to stress, however, that this filter is not optimal. Indeed, looking into the system matrices, it is easy to see that, in the presence of noise in the range or acceleration measurements, there exists multiplicative noise. Nevertheless, the Kalman filter is GAS, as it is straightforward to show that the system under consideration is not only observable but also uniformly completely observable.
In order to recover the augmented system dynamics in the original coordinate space, consider the augmented state transformation , 1, . . . , 1 . Then, the nominal augmented system dynamics in the original coordinate space are given by where Including system disturbances and sensor noise to tune the Kalman filter gives the final system dynamics where it is assumed that n x and n y are uncorrelated zeromean Gaussian noise, with E n x (t)n T x (τ ) = Q x δ (t − τ ) and E n y (t) n T y (τ ) = Q y δ (t − τ ) .

Practical Considerations
It was assumed in the paper that there were at least 4 noncoplanar landmarks, in order to fit the configuration of a Long Baseline acoustic setup. Nevertheless, the proposed solution is general and can be applied to any number of landmarks, including the case of single range measurements. This last setup was already studied by the authors, see Batista et al. (2009c) and Batista et al. (2010). The remaining cases of 2 and 3 landmarks differ only in the observability analysis. When there is a single range measurement, it was shown in Batista et al. (2010) that the corresponding LTV system would be observable if and only if the set of functions is linearly independent on [t 0 , t f ]. The cases of 2 and 3 landmarks require less demanding conditions so that the corresponding LTV systems are observable. These conditions will be presented elsewhere. Nevertheless, the design follows the same steps.

SIMULATION RESULTS
In order to evaluate the performance achieved with the proposed navigation solution, simulations were carried out using a kinematic model for an underwater vehicle. The fact that the full nonlinear dynamics of the vehicle are not considered is not a drawback as the proposed filter relies solely on the vehicle kinematics, which are exact. Therefore, the proposed solution applies to any underwater vehicle, independently of the particular dynamics.
The trajectory described by the vehicle is shown in Fig. 2. Sensor noise was considered for all sensors. In particular, the range, acceleration, and angular velocity measurements are assumed to be corrupted by additive uncorrelated zero-mean white Gaussian noise, with standard deviations of 1 m, 2×10 −3 m/s 2 , and 0.05°/s, respectively. The attitude, parameterized by roll, pitch, and yaw Euler angles, was also assumed to be corrupted by zero-mean additive white Gaussian noise, with standard deviation of 0.03°for the roll and pitch and 0.3°for the yaw. To tune the Kalman filter, the state disturbance intensity matrix was chosen as Q x = 10 −5 I and the output noise intensity matrix as Q y = diag (1, 1, 1, 1, 2, 2, 2, 2, 2, 2). The initial conditions were set to zero for the position and velocity. The acceleration of gravity was initialized closed to the true value, with [0 0 10] T m/s 2 as the attitude is measured and the magnitude of the acceleration of gravity is usually known. Notice that it would be possible to initialize the position with a close estimate obtained from the inversion of the first set of LBL range measurements. The states corresponding to the range measurements were initialized with the first set of measurements while the remaining states were set to zero, apart from x 11 , which corresponds to the square of the magnitude of the acceleration of gravity, which was initialized with 100.
The initial evolution of the position, velocity, and acceleration of gravity errors is depicted in Fig. 3, whereas the initial evolution of the range errors is shown in Fig. 4. The initial convergence of the remaining state errors is shown in Fig. 5. As it can be seen from the various plots, the convergence rate of the filter is quite fast. x y z Fig. 3. Initial convergence of the position, velocity, and acceleration of gravity error In order to better illustrate the performance achieved with the proposed solution, the steady-state errors of the position, velocity, and acceleration of gravity are shown in Fig. 6. Notice that the errors are confined to very tight intervals, in spite of the realistic measurement noise. The proposed filter was compared against two different solutions: the first is the well-known Extended Kalman Filter; the second consists in applying the linear Kalman filter proposed in Batista et al. (2009b) using a position algebraic estimate obtained from the range measurements to feed the filter. Unfortunately, it is not possible to show the results here due to the lack of space, but in short, the performance of the proposed solution is similar to the EKF and outperforms the one based on the algebraic inversion of the problem. These results will be shown in an extended version of the paper.

CONCLUSIONS
This paper presented a novel Long Baseline (LBL) position and velocity navigation filter for underwater vehicles based directly on the sensor measurements. Traditional solutions resort either to the Extended Kalman Filter (EKF) or to solutions based on position algebraic estimates obtained from the range measurements. The solution presented in the paper departs from previous approaches as the range measurements are explicitly embedded in the filter design, therefore avoiding inversion algorithms. Moreover, the nonlinear system dynamics are considered to their full extent and no linearizations are carried out whatsoever, which allows to show that the filter error dynamics are globally asymptotically stable. State augmentation is at the core of the proposed framework. Indeed, the proposed filter has 13 + n L states, which compares to a minimum of 9 states for traditional solutions. It is the opinion of the authors that the achieved performance coupled with the guarantee of global asymptotic stability justify the additional computational complexity, at least for those missions where extreme constraints on power do not exist.
Under simulation environment it was shown that the filter achieves similar performance to the Extended Kalman Filter (EKF) and outperforms linear position and velocity filters based on position algebraic estimates obtained directly from the range measurements. The advantage over the EKF is however clear due to the GAS property of the proposed solution, which is not guaranteed for the EKF.
Finally, although sensor bias, in particular, accelerometer bias, is a very important problem, in this paper it is assumed, for the sake of clarity of presentation and simplicity of design, that the accelerometer has been previously calibrated. Nevertheless, it is easy to include the accelerometer bias in the system design, which leads to observability conditions so that it is possible to estimate both the gravity and the bias, according to previous work by the authors.
The overall system design and observability analysis will be presented elsewhere.