Adaptive on-line planning
of environmental sampling
mission with a team of
cooperating autonomous
Adaptive on-line planning
of AUV Teams
environmental mission
This contribution introduces two algorithms for adaptive on-line planning of oceanographic missions to be performed in cooperation by a team of AUVs. The mission goal is defined in terms of accu-racy in the reconstruction of the environmental field to be sampled. Adaptive cooperative behaviour is achieved by each vehicle in terms of locally evaluating the smoothness of the sampled field, and select-ing the next samplselect-ing point in order to achieve the desired accuracy; smoothness evaluation and accuracy estimation have been proposed either in terms of analytical formulation related to field estimation with RBFs (Radial Basis Functions), or in terms of empirically de-rived fuzzy-like rules. Simulative results show that the vehicles team does behave as expected, increasing the spatial sampling rate as an
increase in the environmental variability is detected. The number of samples required by both algorithms is sensibly inferior to those needed by sampling the area at equally spaced locations, as in the case of off-line, non-adaptive planners.
4.1
Introduction
Monitoring of sea and fresh water environments, for oceanographic, geophysical and/or biological processes, has always been a costly, time-consuming operation. In particular, area surveys require the availability of ships to carry on transects over the region of inter-est, collecting data in transit or sampling at fixed intervals along the tracks. When in presence of a limited basin, as coastal areas or lakes and lagoons, fixed environmental stations as instrumented buoys are sometime used. Both methods present conceptual as well as operational disadvantages: in particular, survey ships can reach the complete spatial coverage of the area within some time, while fixed stations can reach complete time coverage within a given spa-tial interval. Complete time and spaspa-tial coverage (“synoptic sur-vey”) of a marine area with traditional methods is far beyond the budget constraints and the practical possibilities of most agencies and private companies. Moreover, there are situations where, even with unlimited budget, some assets just cannot be deployed: such is the case, for instance, of shallow Marine Protected Areas, where even small oceanographic vessels are not allowed to operate. With the fast development of autonomous oceanographic instrumentation, and re-lated communication systems, in [23] has been fostered since the
early ‘90s the vision of an highly integrated system of autonomous units (Autonomous Ocean Sampling Network - AOSN) to replace in a cost-effective way the traditional survey methods, with the fun-damental added bonus of providing synoptic data and to be easily repeatable over time. The key idea of AOSN is to integrate a suite of fixed sensors with a fleet of Autonomous Underwater Vehicles (AUVs), each one carrying some appropriate payload, and collecting data over appropriate survey tracks not reached by the fixed stations. The critical component of the AOSN concept was the AUV, through which synoptic observations can be obtained at potentially very reduced cost. At the time of the AOSN proposal, the avail-able operational AUVs were designed for deep water geophysical surveys, accordingly to the needs of the oil and off-shore industries. However, the technological evolution of the last decade has made small, relatively low-cost AUVs a reality: the available systems, some of them commercial, some of them still research prototypes, range from those employed in acoustic surveillance and surveys for military applications [24] and [25], to those best suited for environ-mental measurements [26], [27], [28], to those that can be configured for dual purposes (acoustics/environmental measurements, and also deep/shallow water – [29]). It has also been demonstrated how, ex-ploiting the peculiarities of the mission objective in the design, very substantial savings in cost can be achieved [30], [18] and [19]. So it can be safely claimed that the mobile autonomous low-cost in-strumentation foreseen in the AOSN vision is now a technological reality.
The research problem that has still to reach mature solution is that of coordination and cooperation of the AUV fleet in reaching
the mission objective (i.e., in conducting a synoptic survey with the required time and space resolution) while minimizing the overall mis-sion cost. It is clear that the easiest possibility is that of pre-planning the tracks and sampling positions of each of the available AUVs be-fore the mission, and then let each vehicle perform its mission inde-pendently from the others. It is also clear that this approach may not lead to the most effective way to employ the available resources; moreover, being it essentially an open loop strategy, it may even lead to mission failure in case of malfunctioning and/or unpredicted perturbations. For this reason, recent research efforts have been concentrated over cooperative strategies and adaptive behaviour of AUVs fleet. A pre-requisite of this research line is the definition of an appropriate metric to measure mission success. In [31] a general metric for oceanographic surveys has been defined taking into ac-count the spatial and temporal variability of the oceanographic field (through its spectral components), mission time and required survey resolution. In a companion paper, [32] have discussed possibilities of classifying the spectral characteristics of the processes under obser-vation from the AUV samples as they become available, as first step toward an adaptive sampling strategy. On the basis of these works, [33] reports the results of a multi-platform synoptic ocean survey conducted in the Monterey Bay over a period of more than a month. In the field experiment reported, however, the vehicle tracks were pre-planned and some prior knowledge on the ocean dynamics, in the form of spatial and temporal correlations, was assumed. The ef-ficacy and accuracy of the experiment was then evaluated a posteriori with the metric proposed in [31]. In addition to the works reported, in [34] and references therein have been proposed several approaches
to sampling metrics, exploitable in a multi-platform survey, in terms of optimal experimental design. A general framework for mission adaptation, including concurrent localization and mapping as well as adaptive oceanographic sampling, has been proposed in [35], in terms of state estimation through a discrete-time Extended Kalman Filter (EKF); additional optimization goals can be added to the gen-eral framework. A non-negligible aspect of the approach proposed is that due to the need of synchronization among the vehicles and of acoustic underwater communications. These requirements not only pose performance limits, but also require specific instrumentation (as acoustic modems) on board the vehicles.
Research efforts in coordination of underwater vehicles has mainly concentrated on formation control, for missions requiring the reach-ing of a specific geographical location by at least one vehicle (e.g., save and rescue or mine counter measurement operations), or for the synchronized reaching of a set of positions [36], [37]. The approaches here are partially inspired from aerospace control, where formation flight has a long research tradition. An interesting approach within this line of research has been proposed and investigated in [38], as referred to ocean gliders with the task of identifying the gradient of environmental oceanographic quantities.
AUV cooperation research has been developing over two main research lines:
• use of multiple vehicles, each one of them suited for a spe-cific operation (i.e., the vehicles are carrying different payloads and/or may be different one from the other), and merging of the results obtained from each vehicle in an appropriate data
fusion system. A specific example of this approach is reported by [39].
• use of multiple vehicles with similar characteristics adapting their mission autonomously or through a centralized informa-tion relay stainforma-tion, accordingly to the data samples as they be-come available; along this line, examples have been discussed as for acoustic scattering and propagation measurements [40], and environmental mapping and self-localization [41]. The cited work, [35], is also part of this line of research, though its methodological approach is more general.
It is interesting that, in the underwater robotics and oceanic en-gineering literature, little concern is given to the specific algorithms that will be used to merge the sampled data in order to estimate the environmental map of the quantity of interest over the whole area. In particular, any specific estimation algorithm has an error that depends in general on the spatial/temporal smoothness of the oceanic field to be estimated, and on the density (in space and time) of the sampled data. The available measurement of the field itself may be incrementally used to estimate, at least locally, the smooth-ness characteristics of the oceanic field and to adaptively redefine the sampling strategy of the AUV fleet. Smoothness of the oceanic field is the counterpart in space of the frequency approach suggested in [31], and it can be directly connected to the analytical expression of the estimation error. A preliminary work on this line, in which however the smoothness properties of the field were empirically eval-uated from available historical data, has been reported in [42].
This chapther tackles the problem of on-line adaptive mission planning for a team of AUVs cooperating in an environmental map-ping mission. Mission adaptation has the purpose of maintaining a desired accuracy on the reconstruction of the environmental map through estimation of the local smoothness properties of the map itself as new measurements become available. While guarantee-ing accuracy of the environmental map, the adaptation algorithm has an additional degree of freedom that can be used for the op-timization/minimization of other mission-related performance mea-sures (e.g., total mission time, energy consumption, total sampling stations number, etc.). The chapter is mainly concerned with the methodology and algorithms for adaptive, on-line planning; the ex-amples reported include a specific additional mission optimization in terms of locally increasing the spatial distance among the AUVs, but this approach can be replaced by any other different figure of merit without prejudice to the general scheme.
Two on-line adaptive mission planning algorithms are reported: the first one is based on the analytical expression of the error avail-able for a wide class of estimation/interpolation algorithms appli-cable to irregularly spaced data points. This innovative method is rigorously based, but it requires assumptions that, though often re-spected by oceanographic dynamic processes, may in some cases be difficult to ensure. The second approach, an extension of the one proposed in [42], is a fuzzy-like heuristics based on the prior knowl-edge of historical data, and it can be employed when the first one is at doubt in order to obtain a first information on the sampled field. As it will be shown, in applications both methods generate a behaviour of the AUV team in which the areas with greater
environ-mental variability have a denser sampling. The analytical approach, at the price of a greater number of sampling stations needed, has a better approximation error control then the empirical approach.
The environmental mission scenario to which the above algo-rithms are best suited is that of missions requiring sampling of a given quantity (e.g., temperature) at a specific geographical loca-tion; moreover, stationarity with respect to time of the measured quantity is assumed. This means that the overall mission time must be smaller than the time constant of the oceanic process observed.
The AUV team share at each time the available information gath-ered as the mission proceeds; after taking a data sample at a given location, each AUV, on the basis of the shared knowledge, selects au-tonomously its own next sampling point running the proposed plan-ning algorithm. Through this procedure, the AUV team exhibits a collective behaviour satisfying the mission requirement, while each vehicle will autonomously plan, in an incremental way, its survey path on the basis of the available shared knowledge.
The requirement on the AUVs team for implementation of both algorithms is the capability of communication, either point-to-point or through an information relay station, in order to share the past information. Communications can be asynchronous and can tolerate important delays, so that they can be achieved also from sea surface with appropriate radio/satellite links.
Both environmental and AUV system assumptions reported in the previous paragraph are respected in coastal oceanographic sur-veys, where radio links with shore stations are easily achieved, and where the limited extension of the survey area makes it feasible to complete the sampling preserving the stationarity assumption. The
very low cost vehicle ”F´olaga” [19], [18], and also 3, is perfectly suited for the operation, and it will be employed in the field for algorithm verification.
The chapter is organized as follows. In the next section the sampling problem is formally stated, and the general cooperative approach described. In section 4.3 the analytical approach is pre-sented, with discussion of the relevant assumptions as for on-line smoothness estimation; a thinning algorithm is also introduced to reduce ill-conditioning in the map estimation. In section 4.4 the heuristic, fuzzy-like approach is reported. In section 4.5, issues re-lated to the optimality of the method in presence of communication and localization uncertainties is discussed, with specific reference to the implementation of the algorithms on a team of F´olaga – class
AUVs.
In section 4.6 simulative results are presented in an ad-hoc case, purposely built to emphasize the behaviour of the algorithm in a sce-nario characterized by very high spatial variability, and in a realistic oceanographic case generated with the Harvard Ocean Prediction System (HOPS) model initialized with field data. The performance of the two methods is compared in terms of error in estimating the environmental map and number of required sampling points; com-parison is also made with the number of sampling points required by off-line non-adaptive planning over a regular grid. Finally, con-clusions are given.
4.2
Problem statement and general
co-operative approach
Let us suppose we have the availability of n AUVs, each equipped with a sensor able to point-wise sample an environmental quantity
θ at the geographical coordinates x = (x, y). It is assumed that the
quantity is stationary, i.e., the sampling mission time-scale is smaller than the environmental variation time scale. Let A be the geograph-ical domain of interest, i.e., x ∈ A. The behaviour of each vehicle
j in the team is event-driven, where each event is the conclusion of
a sampling operation at a given geographical location; after every event, each vehicle has to autonomously select the location of its next sampling station on the basis of the available information, and proceed to perform the measurement. Let xj,kj be the kj-th
mea-surement point of the vehicle j; let M(j)=
n h=1 kh i=1
{xh,i} be the set of
points sampled by the whole team and known to the j-th vehicle after its last measurement, then I(j) = M(j); θ = θ (x) x∈ M(j) (the sampling points and the related measurement) is the information set available to the vehicle j after the event corresponding to the kj-th
measurement. Let S be an estimation algorithm that computes an estimate ˆθj of the quantity θ over the whole region A on the basis of
the current available information I(j), i.e. ˆθj(x) = S
I(j) . On the basis of the estimation algorithm S and the available information set, one can define the estimation error:
εj(x) = θ (x) − ˆθj(x) (4.1)
out-put of dynamic systems with distributed parameters, they have a local smoothness behaviour that can be predicted a-priori or esti-mated through the measurements themselves. This allows in gen-eral to estimate the upper bound of the estimation error: ˆεj(x) = ˆ
εj
S, (I(j), j = 1...n) such that εj(x)≤ ˆεj(x)≤ maxAε(x),∀ (x) ∈ A, where maxAε(x) is the largest possible error determined a priori
on the basis of the physically consistent range of the measured vari-able. Alternatively, one can use a derived quantity, the “confidence level”, defined as:
Cj(x) = 1−
ˆ
εj(x)
maxAε (x)
(4.2)
The goal of the mission is to survey the region so that eventu-ally a desired confidence level is reached over the whole area (or the estimation error is everywhere below a given threshold). The gen-eral cooperative strategy to attain the mission goal proposed in this work is to let each vehicle j select incrementally its next sampling point after completing its kj-th measurement accordingly to the
fol-lowing algorithm. On the basis of the information set I(j), the j-th vehicle selects its next measurement point (xk+1, yk+1)(j) among the
points of a circle of radius ρ(j)k+1, centred at the last sampling point (xk, yk)(j). The radius ρ(j)k+1 is chosen so that the error of the
estima-tion map is below (or the confidence above) the required threshold at every point inside the circle, assuming that the local smoothness of the environmental field at the point (xk+1, yk+1)(j) is the same of
that estimated at the point (xk, yk)(j). The selection of the specific point (xk+1, yk+1)(j)on the circumference of centre (xk, yk)(j)and
oceanic field; hence it can be used as the additional degree of free-dom for optimizing some mission figure of merit. In the simulations reported at the end of the chapter, the point (xk+1, yk+1)(j) has been
selected in order to maximize its distance from the (known) position of both the other AUVs and the past sampling stations, in order to spread the vehicles over the experimental area; however, though simulation results with this choice have been thoroughly satisfying, it is by no means intended as “the best” possible approach. In fact, this additional degree of freedom can be exploited, depending on the specific mission requirements, to optimize other mission param-eters, as described for instance in the next chapter where the vehicles are required to maintain the communication link at every sampling operation.
The above cooperative approach is well suited to the operation of an AUV, since the incremental sampling points are chosen in a convenient neighborhood of the current vehicle position. Within this setting, critical aspects to be discussed are: the choice of the estima-tion algorithm S; the incremental estimaestima-tion of the error/confidence level; the choice of the radius ρ(j)k+1 at each new step. The follow-ing sections will concentrate specifically on these aspects. How-ever, one other general point still needs discussion: the sampling of the oceanographic quantity of interest (e.g., temperature) is usu-ally taken at the geographical location (x,y) for the whole depth of
the water column; this means that one gets a vector of values at
each sampling point, as a function of water depth. The number of data points in depth at each geographical location may vary in dependence of the resolution sought (for instance, one temperature reading every meter in depth) and, of course, of the bathymetry. It
is customary in oceanography to use Empirical Orthogonal Func-tions (EOFs) in order to reduce the dimensionality of the depth dependence of the measurements. The vertical temperature profile is projected on the functional space spanned by a set of m orthog-onal basis functions (EOFs): θ(x, y, z) =
m
i=1
ci(x, y)ϕi(z), where the
EOFs ϕi(z), i = 1, ..., m are empirically defined on the basis of the
cross-correlation matrix of historical data. In this way, the problem of estimation of the environmental field in three dimensions, is re-duced to the problem of estimation of m independent fields ci(x, y), i = 1, ..., m in two dimensions. In shallow water and coastal areas
(but also, in many cases, in deep water), the number m of EOFs is very limited (typically, m = 3, 4); moreover, the relative weight of the EOFs in representing the environmental field is known in ad-vance, and it is usually strongly biased toward the first component (e.g.: ϕ1 accounts for the 90% of the oceanographic field energy,
ϕ2 for the 6%, etc.); this means that there does exist an indepen-dent, a priori known, measure of relative importance among the m 2-dimensional maps. In the following of the chapter the discussion will be based, for the sake of simplicity, on the reconstruction of a single 2-dimensional map. All the algorithms and formulas can be generalized to the case of m independent maps, weighted according to their relative importance. In the following, the map to be esti-mated will still be referred as the map θ(x, y) of an environmental quantity, although it has to be understood that what is actually esti-mated is the map of the coefficients of the EOFs of the environmental quantity of interest.
4.3
Analytical approach: exploiting
ap-proximation properties of Radial
Ba-sis Functions
The development of the planning approach described in the previ-ous section critically depends on the method employed to estimate the approximation error (or the confidence level). In this section, in order to derive an analytical formulation of the estimation error, we focus on approximation algorithms belonging to the class of Radial Basis Functions (RBFs). There are several good reasons for this choice: RBFs are ideally suited for interpolation and approximation of maps sampled on irregular grids (i.e., with samples not necessar-ily evenly spaced), as it is the case discussed here. Moreover, RBFs have a long successful history of applications in the environmental field and in geostatistics [43], [44] and have seen a renewed inter-est in the ‘90s when their relation with artificial neural network has been enlightened [45]. Finally, the RBFs class is still fairly gen-eral, including multiquadric functions, thin-plate splines, B-splines, Gaussian functions, etc. The basic results on RBFs employed in the following of the section can be found in [46] and [47]; the thinning algorithm described to avoid numerical ill-conditioning is a variation of the original algorithm proposed in [48].
Let us select a family of RBFs Φ : Rd → R, where d = 2 in our
case; then the approximation algorithm S becomes:
SI(j)(x) = n h=1 kh i=1 αh,iΦ (x− xh,i) (4.3)
In equation (4.3) it is assumed that one basis function is centred at each sampled point: strictly speaking, this means that we are performing an interpolation of the measured data, and not an ap-proximation. This assumption will be relaxed in the following, since it may lead to numerical difficulties, and approximation formulas will be used. Let θ : Rd → R be the function approximated by S. It is assumed that θ(x) is smooth enough to belong to the native
space associated with the radial basis function Φ used to perform
the interpolation, NΦ = θ∈ L2Rd ˆ θ ˆ Φ ∈ L2Rd ! (4.4)
The native space NΦ has the structure of a Hilbert space with Φ(x, y) as reproducing kernel, and (semi-)norm
θ 2Φ = (2π)−d d ˆθ(ω) 2 ˆ Φ (ω) dω (4.5)
where ˆθ (ω) denotes the Fourier transform of θ and ˆΦ (ω) stands for the generalized Fourier transform of the radial basis function. Note that the assumption of θ belonging to a specific Hilbert space is an assumption on the regularity of the environmental map with respect to (x, y) coordinates. Note also that, depending on the spe-cific choice amongst the RBF family, Φ can be positive definite, or conditionally positive definite. If Φ is conditionally positive definite (of order m) the interpolation equation (4.3) must be complemented with a suitable basis for the space Πdm of d-variate polynomials of to-tal degree m 0. In both cases the interpolation and approximation
formulas reported in the following do not change.
Within this setting, the approximation error in a ball of radius ρ centred in a point x is given by:
ε(x) =|θ (x) − S (x)| ≤ θ ΦFΦ(h1/2
ρ) (4.6)
where the explicit dependence of and S from the information set I has been omitted for the sake of simplicity. The quantity hρ
is the so-called fill distance, in the RBFs jargon, and it depends on the density of the sampling points around x inside a ball of radius ρ centered at x itself:
hρ(x) = sup
w∈B(x,ρ) y∈Mmin(j) w−y 2 (4.7)
while FΦ(·) (an upper bound of the so called power function in approximation theory) is a known function that depends solely on the specific RBF chosen (gaussian, multiquadric, etc.); some typical forms, given by [46], are reported in Table 1. Assuming that uniform interior cone condition holding on the domain of interest A, [49], Equation (4.6) can be extended to the whole domain A by replacing the local fill distance with the global fill distance i.e. the fill distance over the domain A:
hA,M(j) = sup
w∈A y∈Mmin(j) w−y 2 (4.8)
Note that a compact, convex survey area A is sufficient to guar-antee the interior cone condition and the validity of equations 4.8 over the whole area. The error bound defined by Equation (4.6) cannot directly be applied due to the presence of the unknown term
θ Φ; however, assuming θ belonging to the native space of the ra-dial basis function used to perform the approximation (i.e. θ can be recovered through interpolation using Φ(x) as a basis function) then the following bound can be used to evaluate the local approximation error in an adaptive prediction-correction schema.
ε(x) =|θ (x) − S (x)| ≤ S (x) ΦFΦ1/2(hρ(x)) (4.9)
The error bound is incrementally computed on the basis of the available data using the current approximation of the environmental map in the place of the map itself. Crucial to this development is the assumption of Equations (4.4): in practical terms, Equations (4.4) implies that the environmental map θ can be reconstructed by the radial basis function Φ selected for the interpolation process. This regularity condition is indeed strong and, in general, it could be difficult to guarantee a priori, however it must be noted that the native space of Gaussisans contains the so-called band-limited
functions and, being the oceanographic processes we are interested
in band-limited processes, a reconstruction by a suitable gaussian radial basis function is possible. As usually made in oceanography, a suitable choice of the basis function Φ (and its shape parameters), can be made on the basis of previous historical data (see for instance [50] as far as the selection of the background covariance is concerned in the definition of the sampling metric).
Equation (4.9) provides a local error bound on the basis of a local subset Ir(j)of the available information set I(j). The local subset Ir(j)
Ir(j)= "
(x, θ (x)) x ∈ M(i)#Bxj,kj, r $ (4.10) where Bxj,kj, r is a ball of radius r centered at the last sampling point of the j-th vehicle. The radius r is an user defined parameter which specifies the wideness of the area used to evaluate the local error.
Assuming Equation(4.4) to hold, the j-th vehicle can incremen-tally determine its exploring radius ρ(j)k+1 at each new step in the planning (on the basis of the information subset Ir(j)) as the local fill
distance to be inserted in Equation (4.9) to locally satisfy the error requirements of the mission.
A global interpolation method, based on the whole information set I(j) is used to incrementally evaluate the improvement in the approximation of θ through S over the region A. The approximation improvement is defined as the increment of S Φ at each step of the algorithm (which causes the reduction of fill distance hA,M(j)):
∆ (kj) = S (kj) Φ− S (kj − 1) Φ (4.11)
where kj indicates the current step of the algorithm for the vehicle
number j. The limit of the sequence S (k) Φ is θ Φ when hA,M(j)
tends to zero. Let us consider the energy splitting theorem [51]:
θ 2Φ = θ − S 2Φ+ S 2Φ (4.12) on the basis of the assumption (4.4) θ Φ is bounded and from Equation (4.6), when the fill distance hA,M(j) tends to zero, the
lim
h
A,M(j)→0
F hA,M(j) = 0⇒ |θ − S| → 0 (4.13)
and so, from (4.12)
θ − S 2Φ → 0 ⇒ S 2Φ → θ 2Φ (4.14) An important computational step not yet discussed is that re-lated to the computation of the coefficients αh,j in the basis function
expansion of Equation (4.3). In principle, they are computed by inverting the data matrix DΦ,I(j) = (Φ (xi− xj))x∈M(j); from a
theo-retical point of view, if θ belongs to the Hilbert space with reproduc-ing kernel Φ, and Φisapositivedef initef unction, the data matrix is positive definite (hence invertible) for every choice of data points xi, xj ∈ Rd. However, from a practical perspective, ill-conditioning
of the data matrix may occur. In order to avoid it, a subset of the measured point is used to produce the approximated environmen-tal map at every step; the subset is determined through a thinning algorithm now described.
Let X = {xi, i = 1, ..., n} be the set of data points under
con-sideration (possibly a subset or all the data points available in the current sampling points set M(j) - note that we have again dropped the dependence of X from k and j for the sake of simplicity). Let us define:
qX = min
xi,xj∈Xi=j xi− xj
(4.15) as the separation distance in X, i.e., the minimum distance among any two points in X. It can be shown that qX is directly related to
the minimum singular value of the data matrix DX through known
functions Gφ(q) of the chosen RBF family (see [46], and Table 1).
Moreover, being X ⊂ A a bounded set, the maximum singular value of the data matrix DX can be bounded with a value depending only
on A. Hence, increasing the separation distance leads to a decrease of the condition number of the data matrix, reducing numerical ill-conditioning problems. So, one way to overcome ill-ill-conditioning is to eliminate some samples xj from the set of RBF centres. This is achieved with the following thinning algorithm:
• Initialization: the minimum separation distance qX is fixed,
and X0 = M(j) is assigned.
• Thinning process: the separation distance over Xiis computed,
and the segment with length qX determined; let −−→xhxk be this
segment; if qXi ≤ qX, the extremal of the segment −−→xhxk with
minimum distance with respect to all the other points in the set Xi is removed from Xi. Let xk be the point removed; the
new set Xi+1 = Xi\ {xk} is determined. The thinning process
stops when qXi > qX.
The above algorithm has been inspired by the one proposed by [48], but the time-consuming “exchange” procedure suggested in [48] has been removed, however the method presents good performance at lower computational cost.
Once the thinning algorithm has been completed after m + 1 steps (note that, being X a finite set of n elements the algorithm will always end in a finite number of steps), the resulting set Xm
RBFs centres for the approximation of the environmental field. The approximation of the environmental field θ is thus obtained as:
ˆ θk,h(x) = SI(h) k (x) = n−m xj∈Xm αjΦ (x− xj) (4.16)
with the coefficients αj determined solving in the least-square
sense the linear algebraic equation:
D ⎛ ⎜ ⎝ α1 .. . αn−m ⎞ ⎟ ⎠ = ⎛ ⎜ ⎝ θ(x1) .. . θ(xn) ⎞ ⎟ ⎠ (4.17)
and the n× (n − m) data matrix D defined as:
Dij = (Φ (xi− xj)) ,
xi ∈ X, i = 1, ..., n,
xj ∈ Xm, j = 1, ..., n− m
(4.18)
The error equation (4.9) is slightly modified by the use of the approximation expressions (4.16) – (4.18); in particular, it becomes [48] and [49]:
ε(x)≤ θ (x) Φ·√m· FΦ1/2(hA,X) (4.19)
where the explicit dependence from the information set has been again omitted and we have to replace θ (x) by S (x) in order to obtain an adaptive and iterative estimation of the unknown quantity
θ. The quantity hA,X is the fill distance computed over the thinned set X.
The steps in the adaptive planning algorithm are now summa-rized. The algorithm is the same for every vehicle, and it is here described for the generic j-th vehicle.
1. Measurement at point x(j)k : θ(x(j)k ) (including projection on the EOFs set);
2. Update of the information set I(j) with the new measurement and information made available from the other vehicles; 3. Update of the approximated map:
(a) Computation of the separation distance (equation (4.15)); (b) Thinning algorithm;
(c) Computation of the updated map (equation (4.16)); (d) Computation of the global fill distance over the thinned
set;
4. Choice of next measurement point
(a) If the improvement on the approximation of θ through S is below a pre-set threshold, and Equation (4.9) is locally satisfied over the whole region, the exploration ends and the algorithm is exited; The previous conditions indicate that the unknown function θ has been correctly estimated, with the required resolution, over the whole mission area; in particular, in equation (4.11), ∆ (kj) < ¯δS, where ¯δS
is a user defined parameter, and equation (4.19) is satis-fied over all the sub areas obtained through a Delaunay triangulation over all the measurement points.
(b) If one of the conditions above is not satisfied, (i.e. the global error is above the threshold and there are unex-plored regions in the area), determine a radius ρ from the current measurement point x(j)k as the largest local fill distance (equation (4.7)) for which the local error (equa-tion (4.19) with the local fill distance) is below the pre-set threshold;
(c) Among the points on the frontier of the ball B(x(j)k , ρ)
choose the one such the a given auxiliary cost function is minimized; this point is set as x(j)k+1;
5. Move to point x(j)k+1 and repeat from step 1.
The communication aspects related to step 2 are discussed in the last section of the chapter with respect to the “Folaga” – class vehicles. As for the auxiliary cost function of step 4.3, a possible choice is reported in the next subsection.
4.3.1
Auxiliary cost function
An auxiliary cost function, based on the minimization of a scalar potential, is used to select a new sampling point among the points belonging to the frontier of the ball B(x(j)k , ρ). Each past sampling
point and each (known) position of the other AUVs in the team are considered as a positive electrical charge, moreover a negative charge is placed at the point xf d, where the global fill distance is reached.
Within this setting, it is possible to define the scalar potential field as a function of the position x:
ϕ (x) = q n i=1 1 d (x, xi) − Q d (x, xf d) (4.20)
where q is the positive charge related to each past sampling point
xi, while Q is the negative charge related to the point xf dand d (x, xi)
is the distance between x and xi.
The next sampling point is selected as a solution of the following constrained optimization problem:
min ϕ (x) x∈ ∂B ρ(j)k+1, x(j)k (4.21)
The cost function proposed allows us to improve the convergence rate of the algorithm and, at the same time, to maximize the dis-tance of the next sampling points from both the old sampling points and the other AUVs in the team, in order to spread the vehicles over the experimental area. Within the simulations presented in the following, as anticipated in the previous section, we have minimized equation (4.20), in order to spread the vehicles over the experimental area. Different choices are, of course, compatible with the proposed algorithm as reported in 5, where, in order to tackle additional con-straints, suitable cost functions are considered.
4.4
Empirical approach: fuzzy-like
plan-ning algorithm
The approach presented in the previous section is based on a ana-lytical background; however, in presence of approximation schemes
that, unlike the RBF families, do not allow for an analytical eval-uation of the approximation error, it cannot be directly applied. A relevant case is that represented by neural networks in the form of multi-layer perceptrons, for whom only asymptotic expressions of the approximation error are known. A possible alternative approach, suited to this situation, is proposed in this section. The general idea is similar to that of the algorithm of 4.3: after a measurement at location x(j)k , on the basis of the available information set I(j), the
j-th vehicle select its next sampling point x(j)k+1 among those on the circumference centred in x(j)k and of radius ρ. The main difference is now in the determination of ρ, since no analytical formulation of the approximation error is available.
The idea of the approach is to link, through analysis of historical data, a spatially distributed confidence level Ck(x), x∈ A (see
equa-tion (4.2) for the formal definiequa-tion of confidence level) to every mea-surement location xk. In particular, assuming the measurement error to be negligible with respect to the approximation error, the confi-dence level at the measurement point itself is taken as Ck(xk) = 1,
with the confidence decreasing as the spatial distance x − xk 2 in-creases. Loosely speaking, this approach reflects the fact that, due to the spatial smoothness properties of the environmental field, a mea-surement at a given location can be taken as a representative of a neighborhood of the location itself. In the oceanographic literature, it is customary to refer to the spatial correlation of oceanic field. The confidence level function Ck(x) can be determined on the
ba-sis of the expected spatial correlation as estimated from background historical data or whatever kind of background information may be available. In particular, this leads to the determination of the rate of
decay of Ckaway from xk (confidence level drops close to zero below
a given correlation threshold), as well as the directional properties of this decay. At the end of this section a specific example related to temperature measurements will be presented.
Let M = n h=1 kh i=1
{xh,i}, as defined in 4.2 be the set of available
measurement points, and Ξ ={Ci(x), i = 1, ...,|M| , x ∈ A} the set of associated confidence functions. A global confidence function over the whole region A is determined in terms of a combination of the confidence functions in Ξ with a rule Γ that can also be empirically determined:
CX(x) = Γ(C1(x),· · · , C|M|(x)), x∈ A (4.22)
The mission goal is now specified in terms of reaching a global confidence function such that the confidence is above a given thresh-old δ over the whole region A. Since the confidence level, once fixed the approximation algorithm, depends only on the spatial location of the measurement points and on the local smoothness properties of the environmental map, the radius ρ to determine the next sam-pling point can now be determined as the maximum distance from xk such that C(x) ≥ δ∀x ∈ B(xk, ρ), assuming that the
environ-mental map in the set B(xk, ρ) has the same smoothness properties
as those measured on the point xk.
An example is now given of application of the above procedure to temperature measurements. The example (whose simulative results are reported in the next section, and compared with those of the algorithm in 4.3) has been worked out using a data set consisting in temperature vs. depth profiles θ(x, z) collected, for entirely
differ-ent purposes, in a shallow, closed area of the Baltic Sea, within the framework of the SITAR research project [52]. The overall data set is reported in figure 4.1. The approximation algorithm to be
em-4 5 6 7 8 9 10 11 12 13 14 0 10 20 30 40 50 60 70 Temperature (°C) Depth (m) Temperature profiles 2003−09−27 a 2003−09−27 b 2003−09−27 c 2003−09−28 a 2003−09−28 b 2003−09−28 c 2003−09−29 a 2003−09−29 b 2003−09−29 c 2003−09−30 a 2003−09−30 b 2003−09−30 c 2003−10−01 a 2003−10−01 b
Figure 4.1: Set of temperature profiles used to empirically determine the confidence function law.
ployed is that of a multi-layer perceptron. For each element in the data set, the cross-correlation with the other samples taken (approx-imately) at the same time in neighborough locations is computed. Having verified isotropic behaviour of the temperature field in the experimental area, a Gaussian structure for the local confidence Ck
has been assumed, with rate of decay away from xkcontrolled by the variance σk. Moreover, by correlating the local gradient vs. depth
at each sample with the estimated local variance σk, it has been
derived an empirical rule relating the local smoothness in x of the temperature field to the gradient vs. depth of the temperature
pro-file. In particular, the variance has been taken large (small rate of decay) in correspondence of small values of the temperature gradi-ent vs. depth; while it has been taken small (large rate of decay) in correspondence of the large values of the temperature gradient vs. depth. In formulas: Ck= √2πσ1 k exp −x−xk2 σ2k σk =−κ ∇zθ(xk, z) + σ0, κ,σ0 > 0 (4.23)
The parameters κ, σ0 are fine-tuned with the historical data set. In figure 4.2 an example is reported showing the different decays of the confidence over the whole region in dependence of different temperature vs. depth profiles.
The local confidence functions have been combined in a global confidence function with the following, fuzzy-like, rule:
CX(x) = min k Ck; 1 (4.24)
An example of the combination of three Gaussian-shaped con-fidence functions according to Equation (4.24) is reported in figure 4.3.
The major drawback of the empirical approach lies in the fact that it does require a substantial amount of prior knowledge on the specific experimental area in terms of historical data. Moreover, it may be difficult to transpose the parameters and rules determined for a given area (or even a given season) to a different area. In section 4.6 both the analytical and the empirical approach are compared through simulative results.
11.5 12 12.5 13 13.5 14 −70 −60 −50 −40 −30 −20 −10 0 Temperature (°C) Depth (m)
Fourth historical data
(a) 4 6 8 10 12 14 16 −70 −60 −50 −40 −30 −20 −10 0 Temperature (°C) Depth (m)
Fourth historical data
(b)
(c) (d)
Figure 4.2: On the top: representative temperature profiles, with null gradient vs. depth (left) and with high gradient vs. depth (right). On the bottom: associated Gaussian confidence levels, with hot colours coding high levels of confidence, and cold colours coding low levels of confidence. The confidence functions are centred on the measurement point, with small decay rate away from the measure-ment (left) and high decay rate away from the measuremeasure-ment (right).
(a)
(b)
Figure 4.3: On the top: local, Gaussian-shaped, confidence functions associated to three different measurement points; On the bottom: combined global confidence accordingly to the fuzzy rule of 4.24.
4.5
Mission implementation: optimality
considerations and the effect of
com-munication and localization
uncer-tainties
The adaptive planning procedure introduced in the previous sections, either in the analytical or in the fuzzy-like version, it is in general only locally optimal, since it is based on local information and the reconstructed environmental field is an unknown function. Moreover, local optimality is ensured only in the case in which the information set I(j) is the same at any event for all the vehicles in the team. In such case each vehicle runs autonomously the decisional procedure on the basis of complete shared knowledge with the whole vehicle team; however, in order to assume that all the vehicles effectively share at any time the same information set, communication with negligible delay has to be assumed among the team. If this requirement is not met (as it may well be the case, see the following discussion for a specific case), the adaptive planning is run by each vehicle on the basis of its own information set, producing, even locally, a sub-optimal choice. In general, this may affect not so much the accuracy of the estimated field (i.e., the choice of the radius ρ(j)k+1, which is in any case based on the local properties of the sampled field evaluated in the neighbourhood of the vehicle j), but may have more critical consequences on the choice of the sampling point (xk+1, yk+1)(j), since
this point is selected on the basis of the additional available degree of freedom, which in turn may depend on global parameters.
As outlined in the above paragraphs, a critical operational aspect is that of communication among the vehicle team. In particular, in order to achieve complete shared knowledge, underwater acoustic communication must be considered, and it must be always feasi-ble among the vehicles. If suboptimal solutions are allowed, delayed communications, either with acoustical links or with radio links from the surface, can be tolerated. Different systems will of course have different solution. As an example of delayed communication, we are currently implementing both planning algorithms on “Folaga”-class vehicles [18], [19] and part 2. The restriction of vehicle operation to specific areas and survey methodologies has allowed to obtain a simple yet effective design at very low costs. In particular, the navi-gation of a Folaga vehicle is carried out at the sea surface, with GPS signal availability; when on the desired sampling location, the vehicle dives in depth, glider-like style, measuring the desired quantity along a vertical profile. Once back at the surface, the vehicle carries on toward the next sampling location, after communicating at a remote station (typically a PC ashore or on a surface platform) the measured data through a GPRS communication link. During navigation, the current vehicle position is always transmitted to the remote station through the same link, together with some other system parame-ters (battery consumption, etc.) in order to allow the monitoring of the mission. From the remote station it is possible to interrupt the vehicle operation in autonomous mode and send directly high level (new mission points) or low-level (engine commands) to the vehicle, making it a wireless remotely operated vehicle.
The mode of operation of the Folaga makes it immediately suit-able for the implementation of the planning algorithms proposed,
(a)
(b)
Figure 4.4: F´olaga vehicle: on the top in navigation, communicating with a shore station; on the bottom in the laboratory.
since the implementation has no impact on, and it does not inter-fere with, the guidance navigation and control system of the vehicle. In particular, the central station can act as relay information centre, collecting information from all the vehicles and broadcasting updates of the information set I(j) to each vehicle. In such cases each vehicle runs the decision procedure autonomously on the basis of complete shared knowledge with the whole vehicle team; however, the vehicles do not necessarily share the same information set all the times, since they are in contact with the broadcasting station only at the sur-face. So it may happen (one simulative example will be shown in the next section) that one vehicle takes a decision on the next sampling point without considering the sampling currently being performed by another vehicle that has not resurfaced yet.
Another issue to be addressed is that of uncertainties in the local-ization of the robot team. Throughout the previous sections, it has been assumed that the sampling points, as well as the current vehi-cles positions, are exactly known. Uncertainties in these quantities leads to additional uncertainties in the estimated map, and, in turn, this may lead to erroneous results from the adaptation algorithm. When dealing with this problem, one has to take into account that oceanic dynamics, even in coastal waters, exhibits spatial scales of the order of thousands of meters; this implies that localization er-rors of the order of hundredths of meters can be tolerated without prejudice to the accuracy of the reconstructed oceanic field. Usually AUVs have much better positioning accuracy, so that localization errors do not affect the performance of the proposed algorithm. For instance, in the case of the Folaga system described above, GPS po-sitioning gives errors of the order of few meters. Issues can be raised
on the effect of underwater currents during the dive of the system, when GPS positioning is not available to the vehicle. The vertical diving speed of the Folaga is approximately 0.2 m/s, so that, with a sea current of 1 m/s (2 knots), a 40m depth dive will produce at the worst (i.e., without considering any compensation from the vehicle, or any additional correction through current velocity estimation al-gorithms) a localization uncertainty of approximately 200m, still in the range acceptable for oceanic measurements. Of course, one may find extreme cases (faster currents, very high ocean dynamics) that lead to unacceptable errors: tidal currents in the North Atlantic Sea may well represent such a situation, and in fact in such conditions vehicles much more performing than the Folaga are needed. It has to be considered that standard oceanographic equipment (gliders, or CTD casts from surface platforms) do not employ any kind of correction or even monitoring of the sampling instrument position in the diving phase. The simulative example presented in the next section with the use of an oceanographic prediction model and field data exhibits spatial scale variability compatible with considerably larger localization errors than those discussed here.
4.6
Simulative results
The two algorithms described in 4.3 and 4.4 are now applied to two different simulative cases; in both cases it is required to produce the 3-D map of the water temperature field. The critical aspect investi-gated through the simulations, with the possibility of comparing the “true” temperature field with the estimated one, is whether the error
control schemes envisaged by the algorithms are indeed respected, and if the sampling is indeed increased in the regions of higher vari-ability of the oceanic field; in the following of the section the “true” temperature field is called the reference field.
The first case has been generated ad hoc, considering a tempera-ture field with a very high temperatempera-ture variability; the second case, more realistic from an oceanographic point of view, has been gener-ated using HOPS - the Harvard Ocean Prediction System (Robin-son, 1999), over a region of the Mediterranean Sea, and initialized with field data kindly provided by IMEDEA, Inst. of Mediterranean Studies, Esporlas, Spain.
In both examples, and for both algorithms, a team of three ve-hicle is considered. Simulations have been carried out in Matlab, importing within the Matlab environment the oceanographic field. The vehicles are modelled as kinematic points, with mode of opera-tion similar to that of the Folaga vehicles: each vehicle dive at each measurement points and new information is communicated to the other vehicles only when a vehicle re-surface. Only the vehicles at the surface receive the updated information, while those on dive, if any, will receive it only when back to the surface. Vehicles surface speed has been taken as 1.5 m/s (3 knots) which is the Folaga max-imum cruise speed. Disturbances (sea currents, etc.) have not been considered in the simulation. As previously stated, the additional degree of freedom in the algorithm has been exploited so that, once fixed the sampling distance from the current point, the next sam-pling point (xk+1, yk+1)(j)is chosen in order to maximize its distance
from the (known) position of the other AUVs, and spread the ve-hicles over the experimental area. The approximation algorithms
1010.110.210.310.410.510.610.7 42.6 42.7 42.8 42.9 43 43.1 43.2 43.3 (a) (b)
Figure 4.5: Geographical area (North of Elba Island, Tuscany Archipelago, Tyrrhenian Sea) under study and HOPS generated temperature distribution at 14m depth over a grid of 20x20 km. No smoothing has been performed over HOPS data.
employed with the fuzzy-like adaptation is that of a neural network of multilayer perceptron with one hidden layer composed by 8 neu-ral units. The information set is used as training set of the network, and training is repeated as the information set increases. The empir-ical parameters (κ, σ0 in equation (4.23)) have been determined by taking 15 random samples of the reference field and by correlation analysis over these samples. The approximation algorithm employed in the analytical approach uses multiquadrics RBFs (Table 1, second row). In both algorithms (analytical and empirical) the accuracy re-quirement is that of an approximation error less than 1°C in the ad
hoc case, and less than 0.1 °C in the HOPS-generated case.
In the ad hoc case, the reference field has been generated over an area of width 3.5 x 3.5 km, and constant water depth of 70 m. The reference field is characterized by a warmer water mass layer of ellipsoidal shape at the centre of the exploration area and at 14 m depth, extending 10 m above and below in depth. The temperature of the warmer layer decreases away from the area centre.
In 4.6, the reconstructed field, the approximation error and the adaptively generated sampled paths in the case of the RBF analytical approach are reported. Sampling stations are denser in the higher variability central area, as expected, and the accuracy is within the prescribed level of 1°C over the whole area. A total number of 71 sampling stations have been generated; an equally spaced regular grid to map this area with the same approximation algorithm would require an overall number of 121 sampling locations (11 x 11 grid, with 0.5 km spacing between the grid nodes).
In 4.7, the reconstructed field, the approximation error and the adaptively generated sampled paths in the case of the fuzzy-like
al-(a) (b) 0 1 2 3 4 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 o o o Mission Area x [Km] y [Km] S1 S2 S3 E1 E2 E3 (c)
Figure 4.6: Reconstructed field, approximation error and AUVs path and sampling points generated with the analytical algorithm, ad hoc case. The three vehicles start at positions S1, S2, S3. The accuracy is within the prescribed level of 1° C. Sampling stations are denser in the higher variability central area.
(a) (b) 0 1 2 3 4 5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 o o o Mission Area x [Km] y [Km] S1 S2 S3 E1 E2 E3 (c)
Figure 4.7: Reconstructed field, approximation error and AUVs path and sampling points generated with the empirical algorithm, ad hoc case. The three vehicles start at positions S1, S2, S3. The accuracy is within the prescribed level of 1°C. Sampling stations are denser in the higher variability central area.
gorithm with neural network approximation schemes are reported. Also in this case the sampling stations are denser in the higher vari-ability central area, as expected, and the accuracy is within the prescribed level of 1 °C over the whole area, although with higher mean error. A total number of 87 sampling stations have been gen-erated. The comparison between the results reported in fugures 4.6 and 4.7 seems to indicate a greater difficulty in practice to tune the fuzzy-like algorithm
In the second simulative example, the HOPS oceanographic model has been used to generate a grid of sea water temperatures over a 20x20 km shallow area of the Tyrrhenian Sea north of Elba Island. Bathymetry in the area does not exceed 40m water depth. The model has been initialized with field data taken over a larger area with traditional methods (i.e., CTD casts from ship), made avail-able from the Institute of Mediterranean Studies (IMEDEA) from a field cruise in winter conditions. Figure 4.5 reports the geographical area and the HOPS generated data at a depth again of 14 m. It has to be noted that these data show much less variability than the previous case; moreover, HOPS update in this case the temperature field every 4 hours, but each update leads to negligible variations, so that the stationarity assumption with respect to time is respected throughout the whole mission. An accuracy threshold of 0.1°C was set as the target for both adaptive algorithms in the exploration of the area.
In figure 4.8 the reconstructed field, the approximation error and the adaptively generated sampled paths in the case of the RBF an-alytical approach are reported. Sampling stations are denser in the higher variability upper left corner of the study area, as expected,
while the accuracy is less than expected in the lower right corner of the area, possibly due to boundary effects in the approximation (similar effects are also present in figure 4.6, though in that case they were not violating the desired accuracy level). A total number of 43 sampling stations have been generated; an equally spaced regular grid to map this area with the same approximation algorithm would require an overall number of 121 sampling locations (11 x 11 grid, with 2 km spacing between the grid nodes).
In figure 4.7 the reconstructed field, the approximation error and the adaptively generated sampled paths in the case of the fuzzy-like algorithm with neural network approximation schemes are reported. Also in this case the sampling stations are denser in the higher vari-ability upper left area, as expected; however, as in the previous example, the approximation error is higher than in the RBF algo-rithm case, and not everywhere within the prescribed limit. A total number of 58 sampling stations have been generated.
4.7
Conclusions
The chapter has described two algorithms for adaptive on-line plan-ning of oceanographic missions to be performed in cooperation by a team of AUVs. The mission goal has been defined in terms of accu-racy in the reconstruction of the environmental field to be sampled. Adaptive cooperative behaviour is achieved by each vehicle in terms of locally evaluating the smoothness of the sampled field, and select-ing the next samplselect-ing point in order to achieve the desired accuracy; smoothness evaluation and accuracy estimation have been proposed
(a) (b) 0 4 8 12 16 20 0 4 8 12 16 20 o o o Mission Area x [Km] y [Km] S1 S2 S3 E1 E3 E2 (c)
Figure 4.8: Reconstructed field, approximation error and AUVs path and sampling points generated with the analytical algorithm, HOPS case. The three vehicles start at positions S1, S2, S3. The accuracy is within the prescribed level of 1° C. Sampling stations are denser in the higher variability central area.
(a) (b) 0 4 8 12 16 20 0 4 8 12 16 20 o oo Mission Area x [Km] y [Km] S1 S2 S3 E2 E3 E1 (c)
Figure 4.9: Reconstructed field, approximation error and AUVs path and sampling points generated with the empirical algorithm, HOPS case. The three vehicles start at positions S1, S2, S3. The accuracy is within the prescribed level of 1°C. Sampling stations are denser in the higher variability central area.
either in terms of analytical formulation related to field estimation with RBFs, or in terms of fuzzy-like rules empirically derived from correlation analysis. The proposed algorithms have an additional degree of freedom that can be employed to optimize some additional mission parameter. In the implementation presented, this additional degree of freedom has been employed to locally spread the vehicle team over the investigation area.
Simulative results have been presented for both algorithms in two test cases, one generated ad hoc to test the main feature of the ap-proach, and the other one with an oceanographic model generated from field data. The results reported, in addition to show that the vehicles team does behave as expected, covering the investigation area and increasing the spatial sampling rate as an increase in the environmental variability is detected, reveal that the analytical algo-rithm reliably confirms the theoretical predictions as for error con-trol. The empirical approach has exhibited a less reliable behaviour in the oceanographic test case, most likely due to the difficulties of the authors in properly tuning in a systematic way the algorithm parameters. It has to be remarked that a possible improvement in the fuzzy-like approach is that of refining the rules as new data be-come available during the experiment, leading to an adaptive fuzzy process. The number of samples required by both algorithms has been largely inferior to those needed by a regular, equally spaced, grid, as those generated by off-line, non-adaptive planners.
4.8
Acknowledgment
I would want to thank Dr. A. Alvarez and Dr. R. Onken, as well as the whole staff at IMEDEA Institute, in the set-up of the HOPS model and in making available the field data for HOPS initialization. This work has been partially supported by MIUR, Italian Ministry of University and Research, Research Projects of National Interest initiative, project PICTURE, and by the Italian Ministry of Foreign Affairs, on the bilateral Spain-Italy collaboration efforts.
Autonomous Mobile Sensor
Networks
5.1
Introduction
Mobile networked systems are experiencing an extraordinary growth in civilian and military applications. Robustness, versatility and bet-ter performances are the advantages offered by multi-agents systems. Nowadays the availability of embedded computational resources in autonomous vehicles and the progresses in communication systems make it feasible the set-up of small and low-cost mobile platforms, with increased capabilities, which can be usefully employed in a num-ber of applications. In particular, sensor-driven tasks such as survey, exploration, and environmental monitoring gain benefit from using multi-agents systems. There are many examples in the literature of applications of robot cooperation, from exploration of unknown en-vironments [53], [54] to military missions, where teams of unmanned
vehicles (land, aerial, underwater) are asked to perform operations such as border patrol [55], mine counter measurements [56] or target identification and visit [57]. The literature on mobile multi-robot cooperation is rather wide and rapidly evolving; a relatively recent summary of research contributions can be found in [58]. Some spe-cific aspects of formation control have been introduced in [59] and formation stability has been further addressed, among others, by [60].
It is not at all trivial, however, to transpose cooperation tech-niques well suited for mobile terrestrial and aerial vehicles to Au-tonomous Underwater Vehicles (AUVs), due to the communication and localization constraints posed by the marine environment (i.e., lack of GPS localization and band and range-limited acoustic com-munications) [61]. An attempt to translate formation control in the marine context has been reported in [36]. In [62] the null-space-based behavioural approach has been applied to the control of a fleet of surface vehicles (for which, however, communication and lo-calization are not as problematic as in underwater applications), while in [63], [64] formation control techniques have been applied to coordinated path-following of marine vehicles, considering commu-nication delays and failures. Interesting oceanographic applications are investigated in [50], as referred to ocean gliders with the task of identifying the gradient of environmental oceanographic quantities; in [65] the combined deployment of a fleet of gliders and profiling floats is investigated in order to optimize the trajectories of the glid-ers with respect to a sampling metric based on the spatial correlation of the sampled environmental parameters.
development of methodologies and strategies for cooperative sam-pling of oceanographic environmental quantities, as water temper-ature and salinity. The ultimate goal is to provide a multi-vehicle system for rapid environmental assessment in coastal waters. In particular, in [66], [67] an on-line distributed adaptive algorithm has been proposed, in which mission adaptation aims to maintain a desired accuracy on the reconstruction of the environmental field, through estimation of the local smoothness properties of the field itself as new measurements become available. While preserving the accuracy of the estimated map, the team was spread over the inves-tigation area in order to optimize area coverage with the minimum number of sampling stations or, alternatively, minimizing the mis-sion time. The approach presented assumed that the vehicles were always able to share a common information set through a suitable communication system.
Specific applications require different types of communication technologies: wireless local area networks can be easily established among surface vehicles through radio links, while acoustic modems are generally used for communication between underwater vehicles. Underwater acoustic communication suffers from transmission delay, multi-path fading and limited range and bandwidth.
This chapter tackles the problem of a behaviour-based adaptive mission planning for a team of autonomous underwater vehicles co-operating in an environmental monitoring mission (e.g., measure-ment of the temperature field) subject to communication constraints. In particular a distributed optimization algorithm for incremental ocean sampling, to be applied by a team of AUVs over a given oceanic region is proposed. Essentially, each vehicle applies the
algorithm on the basis of a common information set consisting in the set of previous measurements, and then decides on its own next sampling station. After each new sampling, the information set is updated and the algorithm run again locally on each vehicle. The algorithm is based on three different goals:
1. adaptive sampling : the density in space of the sampling points is estimated as the measurements progress on the basis of the estimated smoothness of the sampled oceanic field (e.g. sea-water temperature), with the aim of increasing the sampling density where the field is rapidly varying in space, and de-creasing the sampling density where the field is slowly varying. Technically, this is achieved by using Radial Basis Functions as described in 4.3;
2. area coverage: in order to minimize the mission time, the ve-hicles are spread over the measurements area. This is achieved by casting the planning of the next sampling points as an op-timization problem in which the proximity to already sampled points is penalized.
3. communication constraint: in order to share the same infor-mation set, the team must be able to exchange inforinfor-mation; underwater this can be achieved with acoustic communication modem, that, however, do suffer of bandwidth and range lim-itations due to the harshness of the transmission medium. To maintain communication, an upper limit on vehicle range must be respected. This is achieved imposing a network structure to the team, and having the range constraint applied to any two
