Abstract
Monitoring widespread environmental fields is undoubtedly a practically important area of research with many complex and challenging tasks. It involves the building of models of the fields or natural phenomena to be monitored, the estimation of the spatiotemporal distribution of a variety of environmental parameters of interest, such as moisture or salinity in a crop field, or the spatial distribution of vital natural resources such as oil and gas, etc. Sampling, a key operation of the monitoring process, is a broad methodology for gathering statistical information about the phenomenon, or environmental variable, being monitored. To efficiently monitor widespread fields and estimate the spatiotemporal distribution of some particular environmental variable, calls for the use of a sampling strategy can fuse information from different scales of sensors. Such an attractive strategy is well catered for by both the capabilities and distributed nature of wireless sensor networks and the mobility of robots performing the sampling (sensing) tasks. This sampling strategy could even be rendered “adaptive” in that the decision of “where to sample next” evolves temporally with past measurements and is optimally computed. In this article, we examine various singlerobot and multirobot adaptive sampling schemes based on different extended Kalman filter filtering structures such as centralized and decentralized filters as well as our own novel decentralized and distributed filters. Our investigation shows that, whereas the first two filters suffer from a heavy computational or communication load, our proposed method, through its key feature of distributing the filtering task amongst the robots used, manages to reduce both loads and the total reconstruction time. It also enjoys the added attractive feature of scalability that allows the structure of the proposed monitoring scheme to grow with the complexity of the field under study. Our results are corroborated by our simulation work and offer ample encouragement for a further theoretical investigation of some properties of the proposed scheme and its implementation on a physical system. Both of these activities are currently underway.
Keywords:
Spatial field estimation; Adaptive sampling; Information fusion; Multiscale sensing; Robotic sensor network; Environmental monitoringIntroduction
Mobile robots are being increasingly used as sensorcarrying agents to perform sampling missions, such as searching for harmful biological and chemical agents, search and rescue in disaster areas, and environmental mapping and monitoring. One of the objectives of these sampling missions is ‘Field Estimation’. Field estimation is the construction of an estimate of how a certain parameter varies in space and time, i.e., an estimate of its spatiotemporal distribution, based on observed or sampled data. As the field of interest is spread over a wide area, using a dense and fixed sampling scheme for an efficient field mapping would simply be too costly and will involve a possibly prohibitive computational load. Instead, it is far more interesting to use a mobile sampling scheme that would collect samples at few judiciously selected locations, in a way that would enable it to gain enough information about the field to be able to infer, with significant accuracy, the value of the parameter of interest at the unsampled locations. A multitude of research groups have published results on sampling using mobile robots for chemical plume source localization [1,2], soil–moisture mapping for crop monitoring [3], ocean sampling [4,5], forestfire mapping [6], etc.
The sensor fusion schemes for sampling missions can broadly be classified into three categories based on (i) physical parametric models, (ii) featurebased inference techniques such as clustering algorithms, neural networks, etc., which are generally nonparametric in nature but can lead to black or grey box parametric representation of the process, and (iii) cognitivebased models, which use the inference processes of humans and animals and which are based on fuzzy logic rules, search techniques, informationtheoretic approaches, etc. Models acquired using these three broad classes of approaches can be either purely deterministic or purely stochastic. In many cases, deterministic models affected by some random noise can also be assumed.
In the area of physical deterministic parametric modeling representing the first category of sampling missions, Christopoulos and Roumeliotis [2] presented an approach for estimating the parameters of the diffusion equation that describes the propagation of an instantaneously released gas. Cannell and Stilwell [4] presented two approaches for adaptive sampling (AS) of underwater processes using AUVs. The first one assumes a parametric model, while the second one uses an informationtheoretic approach. A number of strategies for nonparametric AS can also be found in the literature. A solution for nonparametric ocean sampling is proposed in [7] based on a classification of the sampling area. The multirobot path planning problem is addressed in [8] using the mutual information collected using different paths. The study of [5] is also similar to that of [8] in the sense that both deal with generating optimal trajectories for multiple underwater vehicles for sampling purposes. Rulebased nonparametric approaches are also used widely in chemical plume tracing on land and in water, odor sensing [2], mine detection, etc.
Forest fires, chemical source leaks, and temperature variations in oceans are examples of complex natural phenomena for which the exact nonlinear model descriptions are unattainable due to the highlevel of complexity involved. Demetriou and Hussein [9] present a solution to the problem of estimating a spatial distribution when the process is described by a partial differential equation. In [10], a nonparametric model is considered, and a distributed scheme for field estimation is developed using a Kalman filterlike recursive scheme.
In geostatistics, spatial processes are generally modeled as random fields, and estimation is performed using Kriging Interpolation techniques [11,12]. Kriging is termed “simple” if the mean of the distribution is also known, and “universal” if the mean is treated as an unknown linear combination of known basis functions. In [13], a distributed algorithm is presented for spatial estimation using the Kriged Kalman filter. Graham and Cortes [14] proposed a Kriged Kalman filterbased approach for a spatiotemporal field where the discretetime evolution of the state is governed by the Kalman filter used. In [15], the authors represent the timevarying field with a random process with a covariance known up to a scaling parameter. They proposed gradient descent algorithm which can run in a distributed fashion on multiple robots. OlfatiSaber [16,17] developed a distributed Kalman filter approach along with consensus filters to estimate the state of a process and reach consensus of all nodes.
Due to the time and energycritical nature of some of these sampling scenarios, simply requiring the robots to perform a raster scan or randomly sample the field of interest would clearly be a suboptimal and highly inefficient sampling strategy. Moreover, many timevarying distributions of interest encompass a wide area, and must therefore be observed with sensors having variables characteristics such as multiple size scales, rates, and accuracies [18]. For example, a forest fire is monitored using satellite images which provide a large spatial fieldofview (FOV) but a lowresolution or fidelity. On the other hand, a plane flying at low altitude would provide a lowspatial FOV but highfidelity information.
In order to effectively fuse these different types of measurements, we proposed a Multiscale Multirate Adaptive Sampling approach with a parametric description of the field [6]. In this approach, sampling strategies continuously adapt in response to realtime measurements from sensors of different scales. This scheme relies on building parametric models of the field using spatial sensor measurements collected from a highaltitude, and which are thus less accurate, and then improving the models by using more accurate spot measurements. The extended Kalman filter (EKF) is used to derive a quantitative information measure that is needed for the selection of sampling locations that are mostly likely to yield optimal information. In this approach, the existing lowresolution information of the field is first used to acquire an initial parametric representation of the field whose parameters have a higher initial error covariance which gradually reduces as highresolution samples are taken and processed.
In our previous work [6], we presented a framework that extends our estimation of a simple parametric field to that of complex timevarying (e.g., forest fires [6]) by representing these with sums of overlapping Gaussians. The resulting algorithm was called EKF–NN–GAS, and is based on (a) a Radial Basis Function (RBF) neural network (NN) for the parameterization of the nonparametric field, (b) an EKF for parameter estimation, and (c) a heuristic search scheme called ‘Greedy Adaptive Sampling’ (GAS).
A further investigation of the AS algorithm using multiple robots is presented in this article. For widespread fields, it may be impractical and certainly inefficient for a singlerobot to map the entire field by navigating to different sampling locations, even when guided by an efficient sampling algorithm. However, when using multiple robots, the sampling area is first divided into smaller regions, and then each sampling instance in a particular region gains information about the parameters which have a dominant effect in that region. Therefore, in order to distribute computations, we need to be able to fuse the parameter estimates in order to construct the map of the field density distribution.
This problem is similar to reformulating the algorithm originally designed for a conventional singlesensor singleprocessor system to work on a more general multisensor, multiprocessor system. Distributed algorithms have been used before in many applications, and the degree of parallelism used in them varies from one algorithm to another, depending on the application at hand. An example of distributing processing includes target location estimation using several sensors for data collection, and then fusing together the collected measurements either at the central station or at each sensor in a multisensor fusion algorithm [1921].
Since complex fields are represented by hundreds of parameters [6], it is computationally cumbersome for a singlerobot to compute and store all parameter estimates and the uncertainty measures. It also quickly becomes unfeasible for individual robots to run a large AS algorithm, and share large covariance matrices wirelessly. Furthermore, with multirobot sampling, the resources can be allocated efficiently if some resources are either busy or not available.
If the filter computation can be distributed among multiple robots, the number of computations performed by all the robots, i.e., the overall computational efficiency would be greater than the processing carried out by a singlerobot having to carryout both the sampling and computational tasks. Moreover, we expect that the concomitant advantages such as the flexible degree of parallelism, speed of convergence, and reduction in complexity that will be thus gained would be significant. With a singlerobot, the total field estimation time includes the time necessary for navigation, sensing, and computation of the estimate (as there is no communication involved in this case). With multiple robots, the field estimation time includes the time taken for sensing, computation, communication, and final fusion to recover the field density distribution. We expect that the speed of convergence would increase by using multiple robots simply because of the sampling being done in parallel, and that the navigation time would be reduced significantly at the cost of modest increases in computation, communication, and fusion.
The rest of the article is organized as follows: in Section 2, we present the general formulation of the AS problem; Section 3 summarizes the existing centralized and decentralized filters, and their application to sensor network for field estimation; in Section 4, we present the novel federated distributed KF; Section 5 presents the simulation results for the proposed algorithm, and their discussion; finally Section 6 concludes the article.
Formulation of multirobot AS algorithm
As covered in our previous study, a singlerobotbased AS algorithm for a 2D spatially stationary field g(x,y)can be described as follows [6] (Figure 1).
(1) Lowresolution sampling: The field g(x,y) of size m × m is divided into uniform squaresized grids n × n such that n < m, and samples are collected at the centers of each of the n × n grids. Hence, m/n × m/n samples are collected as a lowresolution representation of the actual field.
(2) Parameterization: Parametric representation of the field g(x,y) is achieved by training a Bneuron RBF neural network with the acquired lowresolution data. This results in a representation of the field as a sum of B Gaussians (one per neuron), and an offset (or bias) parameter b, with each neuron having its own parameters such as its peak , variance , and center . Each of these parameters has an initial estimate value A_{0}, and an initial error covariance P_{0}. The number of neurons B is chosen depending on the complexity of the field and in such a way that the initial field estimation error is minimized to a value less than an acceptable threshold. Note at this stage that unlike the lowresolution samples which are uniformly distributed since they are acquired from uniformly distributed grids, the Gaussians (one Gaussian per RBF node) are distributed nonuniformly depending on the density of the field. We actually use more Gaussians in denser areas and fewer Gaussians in smoother areas of the field to be mapped. Further details on the relationship between the number of lowresolution samples and the number of neurons can be seen in [6].
Mathematically, a spatially stationary field is represented by the parameter vector A defined by
where A is the vector containing the true values of the parameters, which is not known due to (i) the resolution error between the actual field and the acquired lowresolution version, and (ii) RBF training error.
(3) Highresolution sampling: In order to improve the field estimate, spotmeasurements are made by a robotic vehicle which collects samples Z_{k} in a grid of size p × p(where p ≤ n) based on a heuristic GAS algorithm [6]. According to the GAS algorithm, the next sampling location is searched within the vicinity of the currently sampled location, based on a criterion of minimization of the norm of the parameters’ error covariance matrix.
Figure 1. Change in spatial resolutions for multiscale sampling.
The EKF governing and measurement equations are respectively given by
where Q is the process noise covariance, R is the measurement noise covariance and (x_{k}, y_{k}) are the robot sampling locations.
The multiagent (or multirobot) AS problem considered here can be described as follows:
Assumptions:
(i) A nonlinear spatiotemporal field variable is described via a parametric approximation Z = Z(A, X, t) depending on an unknown parameter vector A, position vector X, and time t.
(ii) N robotic vehicles (agents) sample the field with sensing uncertainty in order to obtain higher resolution estimates of the field.
(iii) The number of field parameters (L) and their initial guesses are based on a hypothesis originating from prior knowledge of the field consistent with a lowresolution image of the entire field.
As a complex spatial field is spread over a large area, its parameterization will require a large number of parameters. Therefore, it becomes unfeasible for a singlerobot to navigate to different locations, collect samples, and improve parameter estimates in a short period of time. In addition to time constraints, the sampling problem also experiences constraints in the amount of energy available to the robot, as well as suffers from a considerable computational burden. These constraints limited the performance of our singlerobot AS algorithm as described in [22]. Therefore, a key contribution of this article is to propose a better alternative that greatly alleviates the time and energy constraints imposed on the sampling process by the singlerobot approach of mapping a spatiotemporal stationary field.
It is assumed here that only a single parameter Z vector is measured by all of the mobile robots used. However, in the case where multiple parameter vectors are to be measured, and the measurement model of each measured parameter vector is known, then the general EKFbased framework of AS presented [6] can be used. In [23], we considered the scenario with two measurements only: the field measurement and the location of the robots.
It is important at this juncture to describe the following three main issues which underline the multirobot sampling problem tackled here.
(i) How can the sampling area be divided efficiently?
Section 2.1 discusses the above issue and suggests some efficient ways of tackling it.
(ii) How can the density distribution be estimated through efficient data fusion when robots are collecting measurements in parallel?
(iii) How can the computational and communication burden be distributed efficiently amongst the many robots used?
To address the last two issues, several possible algorithms are first presented in Sections 3&4, and then their respective simulation results presented and discussed in Section 5.
Partitioning of sampling area
A method is clearly needed to efficiently divide the sampling area into clusters, in order to run a parallel AS algorithm with multiple robots. Here, we propose an approach to efficiently divide the sampling area for parametric distributions using Fuzzy cmeans clustering (FCM) and Centroidal Voronoi Tessellation (CVT) diagrams.FCM has frequently been used in the past for the classification of numerical data. CVT diagrams [24] have also been used for forming nonuniform size grids to better explore highvariance areas for nonparametric distributions [7]. Here, we employ a scheme to efficiently divide the sampling areas for parametric distributions using both FCM and CVT. In this approach, FCM clusters samples based on the estimated centers of the approximating Gaussians used to map the field. Note here that we have assumed that the partitioning is performed once only at the beginning of the Fusion filter. For a timevarying field, further accuracy can be obtained by repartitioning the field (and hence repositioning the Gaussians) after some samples to account for the field evolution in time.
As discussed in the beginning of this section, lowresolution samples from g(x, y) are used to train the RBF neural network which gives an estimate of the field as a sum of B Gaussians (neurons). This clustering approach is illustrated in Figure 2, where a field represented by B = 100 Gaussians is partitioned into eight regions. The centers of these Gaussians shown in red circles are used for clustering.
Figure 2. Sampling area with Gaussian field centers partitioning performed in two steps using FCM and CVT.
As the clustering is fuzzy, it allows one piece of data to belong to several clusters via a membership grade u ranging between 0 and 1, and involves the iterative minimization of the cost function [25] given in Equation (3).
where is the number of Gaussian centers, N is the number of clusters which is equal to the number of robots in this case, u_{ij} is the degree of membership of center x_{i} in cluster j, c_{j} is the centroid of the cluster j and m is a real number greater than 1. Next, a CVT diagram based on Lloyd’s algorithm uses the centroid locations acquired by fuzzy clustering to classify all points in discrete space that are closest to the centroid, as a single group. Mathematically, given C clusters, each with a centroid denoted by c_{s}, then a point p on the field is said to be part of the cluster r if the following distance inequality is satisfied: .
As a result of this mapping scheme, more Gaussians will overlap in areas where there are large field variations. The use of FCM and the CVT diagram for area classification may result in regions which have more variations and which must be as small as required in order to sample them thoroughly, i.e., so as not to miss out on any vital information. The areas with less variation, though they may be large, would require fewer samples, since they are represented by only a few parameters.
Centralized, completely decentralized, and federated decentralized filters
In this section, we first examine completely centralized, completely decentralized, and federated decentralized filters, and their use in running the proposed multirobot AS algorithm. We then argue that a new and efficient filter is needed for this application which will be discussed in detail in the following section.
Using completely centralized filter
In a completely centralized sampling approach, each robot takes sensor measurement and transmits them to the central processor, which then calculates the required parameter estimates and error covariances . The central processor computes these estimates, shown below in (4), using the ‘KF equations for a single robot’, (while singlehandedly) taking on the task of fusing the multiple measurements it acquires from the N robots used.
Figure 3 illustrates the completely centralized approach, in which all robots transmit their sensor measurement to the central filter, which then calculates the field estimate using Equation (4) given below where the superscript ‘‘ in the vector A and matrix P indicates premeasurement, while the lack of it indicates postmeasurement:
Figure 3. Completely centralized filter for multirobot AS algorithm.
Here we assume a stationary field and hence time prediction is not needed, i.e., the a priori estimates will be and . In [6], we assumed a slow timevarying field, a single sampling robot was used, and we included the prediction too considering the time evolution of the field.
This type of scheme is simple, as there is little communication involved and no redundant computations. But, the disadvantage is that the sensing robots do not carry any information on the field to be estimated. Therefore, this algorithm cannot be adaptive for every sample because the latest estimates are required to generate new sampling locations, and these estimates are not calculated at every robot. Simulation results are shown in Section 5, where multiple sampling locations are chosen based on the current field estimate, and then all the measurement data collected are transmitted to the central filter for fusion, further processing and determination of the next sampling locations.
Using completely decentralized filter
For a completely decentralized filter implementation, each robot not only takes the sensor measurement, but also runs locally the AS algorithm. However, it only calculates partial estimates of the field parameters and error covariance. It also generates new sampling locations within the vicinity of its current position. After every few samples, the robots communicate and share with each other their partial field estimate information, in order to calculate the complete estimates. The parameter estimate vector and the error covariance are the two terms each robot needs to transmit to the other robots. Each robot assimilates the received information using a decentralized EKF scheme formulated in [19,26].
Figure 4 illustrates the completely decentralized filter structure in which each robot has its own filter to compute partial estimates, and a fusion filter for assimilating the estimates acquired from other nodes to generate the complete field estimate.
Figure 4. Completely decentralized filter for multirobot AS algorithm.
If a completely decentralized approach is considered, then an AS algorithm running on each robot carries the information about all the field parameters, and thus there is no need at all for a global fusion filter in this case. Hence, each robot j can calculate the partial or Local Estimate (LE), and after (k + 1)^{th} using Equation (5)
Note that G_{j,k,LE}, where j, k, LE stand for the sensor number, sample number, and LE, respectively, is the Jacobian of the Gaussian vector g_{j,k,LE}, and is used in the above linearized EKF measurement update equation to estimate .
To compute the r^{th} update, robot j calculates the total estimate after each robot has collected its own q samples as explained next. First it (robot j) acquires from the other robots their new partial estimates which were computed from q new samples and then assimilates these new partial estimates with both its previous total estimates and its own new partial estimates. The complete r^{th} updates, P_{j,r} and , are finally computed by robot j using Equation (6) [19]:
The advantage of this approach is that it does not involve any approximations, and there is no dependence on a central filter for computing the partial estimates. Also, the objective of sampling in parallel can be successfully achieved. The disadvantage of the algorithm is that it is demanding and inefficient in terms of communication and computational requirements when there are many parameters to estimate and heavy communication requirements to satisfy. This network has to be fully connected and there is excessive communication. This full parallelism (and complete distribution) of this type of algorithm can be taken advantage of in applications such as target tracking which involve the estimation of a few parameters (such as location, speed, etc., of the target) only. When a large number of parameters are to be estimated, dividing the entire field of interest into several sampling areas and provided a sufficient number of robots is allocated to each area, then there will be no doubt that, through communication, this will enable different robots to carry better information about different parameters, thus resulting in an improvement of the overall estimation of the field. If only a few robots are used to sample a particular area, then each robot will have a larger sampling area to cover and it will take more time to calculate the local parameter estimates up to a certain degree of accuracy, from which it will then calculate the global estimate of the field parameters. This may not be possible under time constraint. This is clearly illustrated in Table 1 where reduction in number of robots from 4 to 1 resulted in an almost four fold increase in the total sampling time.
Table 1. Comparison of simulation results for single robot, multirobot decentralized and federated decentralized filter
By the way of example, in adaptively sampling a field (shown in Figure 2) represented by B = 401 parameters. The field is divided into N = 8 partitions and the sampling operation is performed using 1 robot/partition. Running this decentralized algorithm would require each robot to calculate the partial estimate of 401 parameters, and to wirelessly transmit an error covariance matrix of size 401 × 401, and a parameter estimate vector of size 401 × 1 to every other robot. Clearly, such a scheme would be very inefficient and not scalable.
Using a federated decentralized filter
In this approach, each robot takes some sensor measurements, estimates partial error covariances and field parameters, and transmits this information to a global fusion filter for assimilation, in a similar fashion to the approach proposed in [20,21,27]. Each robot runs Equation (5), but the fusion is done only at the fusion filter using Equation (6). Then these estimates are transmitted by the global fusion center (or filter) to all of the robots. So, the only difference between federated and completely decentralized approach is that in the federated case, these estimates are centrally calculated by the common global fusion filter while in complete decentralization, these are locally estimated at each robot.
Figure 5 illustrates the federated decentralized filter in which each robot calculates partial field estimates, and transmits them to the global fusion filter, which then computes the complete field estimates. The advantage of this approach is that there is less communication compared to the completely decentralized case. Although in this case, none of the robots carries the complete information about all of the parameters all of the time, this approach will also be computationally more efficient than the completely decentralized implementation, simply because of the removal of the computational redundancy, due to fusion taking place at every robot, that was needed in the completely decentralized scheme. The disadvantage that this approach shares with the completely decentralized one is that partial estimates of all parameters are still being carried by all of the robots all of the time, although information about these estimates might not be complete. Therefore, by federating the decentralized KF filtering scheme, the computational aspect of the problem has been mitigated but not the communication one. A thorough examination of the above three filtering schemes has therefore led us to take a novel and fruitful approach that would reduce both computational and communication overheads simultaneously. This novel approach is underpinned by a shift in focus from the mere decentralization of the KF filter to its distribution as described in the following section.
Figure 5. Federated decentralized filter for multirobot AS algorithm.
Federated distributed Kalman filter
A decentralized and a distributed KF are two different formulations of the same KF algorithm [19]. In a decentralized algorithm, the filter is fullorder, which means that every local filter carries partial information about all parameters, and the information is shared in a star topology to reach consensus amongst all robots on the final parameter estimates. The objective of distributed algorithms is to efficiently decompose the fullorder filter into several reducedorder filters, in order to reduce the computational complexity and communication overhead, and hence improve the scalability. It can be said that decentralization is the first step toward efficient distribution. In case of no distribution, every collected sample is used to compute the estimates of all parameters in the field. But with distribution, this sample is used to compute the estimates of only those parameters which have significant impact on the region where this sample has been collected.
The objective of the work presented in this section is to modify the formulation of a federated decentralized scheme, in order to reduce both the communication overheads and the computational load involved. This formulation considers only the crosscovariance terms contributed by neighboring Gaussians only and ignores those contributed by distant Gaussians as a tradeoff between accuracy and computational complexity. The decision behind ignoring distant Gaussians is supported by the analysis provided in Section 5, where a threshold of 0.001% in the relative contribution of each Gaussian was used in deciding the number of Gaussians to keep. An accurate DKF is not possible in this AS problem because local measurement models are not available. Furthermore, the use of global measurement models at each node requires the estimate of all parameters, which will contradict the motivation behind the implementation of DKF. There are other schemes that handle the error covariance terms “very lightly” such as Kalman Consensus schemes, which take the average of the error covariances of the parameter estimates in order to implement the DKF with only communication between neighboring nodes being used [16,17].
Decentralized approaches are good enough for applications involving a small number of states such as tracking of objects, etc. But problems such as parametric sampling involve hundreds of parameters, and hence distributing the KF filter becomes all the more important for an efficient operation.
Approach to distributed computations and communications
Assume that we have a continuous field distribution within a certain perimeter, which means that there is discontinuity between the field and its surroundings. As shown in Figure 2, this field is represented by L parameters, where , and the field estimate is calculated at the central station based on the LEs received from N sampling robots. In the example shown in Figure 2, B = 100, N = 8, and L = 401. The circles shown are the center of B Gaussians. One of the highlighted partitions has S parameters, the estimates of which are expected to change by collecting samples from that partition. S includes all the parameters inside a partition, as well as the surrounding parameters which have a significant impact on that partition. The collection of a single sample leads to the change in M parameter estimates, whereas collecting multiple samples results in the change of C parameter estimates. Hence, from a settheoretic point of view, we can state that .For the decentralized case, M = C = S = L and all the crosscovariance terms contributed by all the Gaussians are considered. However, for the distributed case, we have and an increase in M, C, and S will lead to a better accuracy at the cost of a higher number of computations.
The idea behind this approach is to run a reducedorder KF rather than a fullorder one so as to reduce the computational load, as well as the communication overheads by transmitting only the smallest amount of information needed.
Given the following sizes of the variables involved: , this approach involve the following steps:
1. Transformation from to at the fusion filter.
The fusion filter evaluates the initial estimate of by first generating the binary transformation matrix U_{LS} (to transform L to S), and transmitting to robot 1. The matrix is kept in memory by the fusion filter for the final assimilation stage.
2. Transmit the estimates of S parameters to Robot #j
3. Collect the measurement and estimate pair,
where and are the binary matrices for transformation from M to C for the (k + 1)^{th} sample, and the transformation of C from k^{th} to (k + 1)^{th} sample, respectively.
5. Repeat steps3 and 4 until an update is requested from the fusion filter.
6. Transmit the pair to the fusion filter
7. The fusion filter then substitutes into which is unique to each robot.
8. The fusion filter finally runs the global update Equation (6) considering all the different pairs to be local updates from different robots.
For clarification, an example is shown below with L = 401, S = 10, C = 5, M = 3 (for two samples).
Let the sample taken at time (k + 1),(k + 2) and (k + 3), respectively, estimate the parameters (2,4,7), (3,4,6), and (1,2,4,9). Then,
For the first sample: parameters (2, 4, 7) changes. Therefore,
For the second sample: parameters (3, 4, 6) changes. Therefore,
For the third sample parameters (1, 2, 4, 9) changes. Therefore,
Computational and communication complexities
EKF has an O(L^{3}) computational complexity if each sample updates all of the L parameters of the twodimensional parametric field. However, as a firstorder approximation, it can be assumed that a single sample affects only neighboring parameters. With this assumption, the algorithm can run in a distributed fashion, and the computational complexity at the sampling nodes can then be reduced. Only the fusion filter’s complexity remains of order O(L^{3}), because it needs to combine information about all the L parameters. However, this central field parameter fusion process occurs less frequently and hence will have only a small effect on the overall computational burden.
Table 2 illustrates a comparison of computations and communication complexity for a centralized, completely decentralized, federated decentralized and distributed filter. Let N be the number of sampling robots, L is the number of field parameters, q is the number of sensor measurements per robot, and r is the number of times robots communicate to share their information with each other.
Table 2. Comparison of computational complexity and communication overhead for centralized, decentralized, federated decentralized, and federated distributed filter
For the centralized filter, the sensing robots do not perform any computation. Hence, the computational and communication complexity are O(qNL^{3}) and O(qN^{3}), respectively.
For a completely decentralized filter, the computational complexity involved in calculating the LE at each robot is O(qL^{3}), whereas that involved in calculating the global estimate at each robot is , after taking estimates from (N1) robots at a frequency r. Hence, the combined computational complexity becomes . At the same time, the communication complexity is .
In order to reduce the communication overhead and computational complexity, a federated filter calculates the global estimate on the fusion filter only, which reduces the computational complexity to , and the communication complexity to .
Finally, for the proposed distributed version of the federated decentralized filter, instead of calculating the estimates of L states at a single robot, we simply calculate the estimates of M (M < L) states at a single robot for each sample collected. This approach reduces the computational and communication complexity to and , respectively.
Simulation results
In our previous work, we have shown simulation and experimental results for a singlerobot AS procedure to validate our approach [6,22,23,28,29].We now consider the multirobot algorithm with centralized, decentralized, federated decentralized, and distributed filtering structures.
Here a complex field, of size , is generated as the truth field, and is to be reconstructed by AS using N = 4 robots. The field is divided into uniformlysized grids of size each, and samples are initially collected by considering a sample from the middle of each grid. These samples provide a lowresolution description of the field. These initial samples are used for training the RBF neural network and the training method used is of the ‘Selforganized selection of centers’ type ( [30]). We use the “new rb” function of MATLAB to train the neural network assuming B = 40 neurons and a spread parameter of σ = 30. This provides an initial estimate of the field with L4B + 1 = 161 parameters. Spot measurementbased AS is then performed by robots roaming in smaller grids, each of size , in order to improve the field estimate. All assumptions used and results obtained are shown in Table 1.
To estimate the field reconstruction accuracy, two convergence criteria are used. One is the 2norm of the error between the original and the estimated field, i.e., , henceforth referred to as the field error, which is achieved by calculating the errors for all points (x,y) in the field, and then calculating the 2norm of these pointwise error values. It is obvious that, for a fixed neural network structure, using more samples for the initial training would result in a smaller initial field estimation error. For example, as shown in Figure 6d, if lowresolution samples per uniform grid are used for RBF training, then the initial field error E_{2F} = 32, and the final field error after 302 samples is E_{2F} = 19.67. However, by increasing the number of lowresolution samples per a uniform grid from 100 to 900 (i.e., a nine fold increase), the initial value of the field error (E_{2F}) decreases from 32 to 20 (i.e., a decrease of 37.5%).
Figure 6. (ai: from left to right, then top to bottom): Simulation results for singlerobot adaptive sampling. Field estimate is calculated after every sample. Norm of error reduces to19.67 in 302 samples and it took 11.92 min.
However, it is important to note here that, while the example here, based on a lower number (100) samples per grid, has a high initial field error, it achieves the same accuracy as the example (covered in [6]), which uses a higher number (900) of samples per grid. The accuracy achieved by this example is due to the fact that it relies on AS while using only a smaller total number of samples of 100 (initial samples) + 302(adaptively acquired) = 402 samples than the one used in the example of [6].
The other criterion is the 2norm of the parameter error covariance matrix .
Figures 6 and 7, respectively, show the simulation results when using a singlerobot sampling and a multirobot one. It can be seen from Figure 6d that the field estimation error first increases to a peak value before it starts to decrease. This initial increase in error seems to be caused by an apparent divergence of the EKF filter which is prone to divergence because of its dependence on the firstorder linearization process that is performed to calculate the new estimate. More detailed analysis of this can be found in [29] where we carried out a thorough comparison between various nonlinear filters such as the EKF, Secondorder EK, Iterated EKF, and Unscented KF so as to study and highlight the limitations of the EKF filter. Another possible reason for this filter divergence could be the insufficient number of samples used. This can also be exacerbated by the fact that the further these few samples are apart, i.e., the larger the linearization step is, the worse the linearization error becomes. This increase in error could also be due to an insufficient coverage of the sampling area. This therefore reinforces our motivation to use multiple robots that ensure that different regions are adequately covered at the same time. The improvement brought about by the use of multiple robots can be seen in Figure 7d for the multirobot case where, the initial error increase, although not completely eliminated, has been greatly reduced compared to the single robot case (Figure 6d).
Figure 7. (ai: from left to right, then top to bottom): Simulation results for multirobot adaptive sampling with federated decentralized filter. Partial field estimates are calculated after every sample. Complete field estimates are calculated after every 80 samples. Norm of error becomes 19.33 in 320 samples, and it took 2.89 min.
As discussed in previous sections, if the centralized filter is used for multirobots, then AS is not possible. Figure 8 shows the simulation results when all the sampling locations for the four robots used are generated in advance based on the initial estimate. Hence, the sampling approach is nonadaptive in nature. Robots collect samples from these locations and transmit them to the central filter for fusion. It can be clearly seen from Figure 8e that if future sampling locations generated by the (nonadaptive) sampling algorithm are based on the initial estimate of error covariance only, then these locations would not provide much information about the global field distribution, as these locations are all closer to one another and hence would furnish only a localized knowledge of the field distribution. In fact, after collecting 300 samples, the error is still very high as shown in Figure 8d and Table 3. Moreover, it takes the nonnegligible time of 5.48 min to perform this mission. Figure 7 shows the results for a federated decentralized approach which is equally valid for a completely decentralized one. The only difference between these two approaches will be in the computation and communication load to be carried by the robots. For the completely decentralized approach, the total number of samples collected is q = 320. After every 20 samples collected, each robot sends its partial (local) estimate to the global filter for fusion. This way this update is performed r = 4 times.
Figure 8. (a–i: from left to right, then top to bottom): Simulation results for multirobot nonadaptive sampling. Field estimate is only calculated after all the measurements are taken. Norm of error is still 48 after 300 samples, and it took 5.48 min.
The use of four robots instead of one for sampling also reduces the time for field reconstruction from 11.92 to 2.98 min which amounts approximately to a fourfold reduction in time. The reason for this reduction can be explained intuitively since, by sampling using four robots, instead of one, not only does the number of samples collected by each robot gets reduced, but so does the navigation time as well because of the smaller sampling area allocated to each robot.
It is important to point out at this juncture that the process by which only the average number of the most influencing Gaussians is kept is based on their percent contribution relative to the total contribution of all the Gaussians. These influencing Gaussians are selected whenever their relative percent contributions exceed a very small threshold chosen to be equal to 0.001% in our simulation.
Table 3 illustrates the number of computations and communications involved in the above simulations. For the federated distributed filter, it is assumed that on the average, each collected sample influences the estimate of 10 neighboring Gaussians, and each communication update transmits the estimates of 15 Gaussians. Hence, the average number of parameters that can change after each sample is M = 41, since there are 10 Gaussians, 4 parameters per Gaussian and 1 free offset parameter (i.e., ).Furthermore in our simulation we are assuming that the number of all the parameters expected to change is equal to the number of all the parameters that actually change, i.e., . Using the formulae shown in Table 2 to calculate the number of computations and communication, the results we get for the federated decentralized case are, respectively, 1.14 and 1.5 times smaller than their counterparts in the completely decentralized case. Moreover, the number of computations and communication in the federated distributed case are, respectively, 35 and 7 times smaller than their counterparts in the federated decentralized case.
Scalability
The scalability of the proposed federated distributed algorithm is discussed here by comparing the numbers of computations and packets communicated (i.e., the computational and communication load) in two different scenarios, as explained below.
i. The number of sampling robots increases but the number of field parameters is kept unchanged. As the number of sampling robots increases, the computational and communication load increases almost linearly in the case of both the federated decentralized and distributed filters, whereas for the completely decentralized filter, this load increases quadratically. Figures 9 and 10, respectively, show that the computational and communication loads increase when the number of robots used increases from 4 to 20 for all 4 types of filter structures.
Figure 9. Number of computations versus number of sampling robots when the number of parameters representing the field remains unchanged.
Figure 10. Number of communications versus number of sampling robots when the number of parameters representing the field remains unchanged.
ii. The number of parameters representing the field increases but the number of robots remains unchanged. This scenario may represent different cases where either a highly complex field is used which requires a large number of parameters for its description but does not necessarily cover a wide area or a field that is modestly complex but ranges over a very wide area or possibly a field that combines both features. If the field is spread over a wide area, and the number of robot is kept unchanged, then it would require more time to reconstruct the field and the number of computations and communications would depends on the number of parameters used to represent the field.
Figures 11 and 12, respectively, show the computational and communicational loads when the increasing numbers of parameters used are 161, 241, 321, 401, and 481. These five scenarios reflect the cases where the field is represented with 40, 60, 80, 100, and 120 Gaussians, respectively. As shown in Table 2, the computational complexity is related cubically to the number of parameters. But, in the case of the distributed KF algorithm, the rate of increase is far smaller than the one for the other three filters as shown in Figure 11. This result is expected since, for the distributed KF filter, the complexity is proportional to M^{3}rather than to L^{3}, and M < L. The computational complexity can be further reduced by increasing the number of robots as the number of parameters increases as this will reduce the factor M.
Figure 11. Number of computations versus number of field parameters when number of sampling robots remains unchanged.
Figure 12. Number of communications versus number of field parameters when number of sampling robots remains unchanged.
The communication complexity is related quadratically to the number of parameters for the completely decentralized and federated decentralized filters. For the centralized filter, this complexity is not a function of the number of parameters, because it is the measurement Z, rather than the parameter estimate, that is transmitted. For the federated distributed filter, the communication complexity is related quadratically to the number of parameters. However, when the number of parameters increases, the rate of growth of the communication load is smaller is smaller than the corresponding rate for the completely decentralized and federated decentralized filters. The reason for this is that it is M and C, rather than the larger L, that are, respectively, used in the last two entries in the columns titled: “Combined” and “Communications” in Table 2.
Conclusion
In this article, we studied the problem of estimating the field distribution of some particular environmental variable (e.g., moisture, salinity, etc.) using both singlerobot and multirobot AS schemes and different filtering structures, such as the centralized and decentralized ones as well as our proposed federated distributed filtering structure. Our thorough simulation study, encompassing various AS schemes, clearly showed the superiority of using multirobotbased AS schemes over their singlerobotAS counterparts.
These attractive advantages enjoyed by the multirobot AS schemes are mainly due to their features of parallel sampling, a wider area coverage and a decentralization scheme offered by the multirobot approach. We proposed a novel scalable structure termed the decentralized distributed filter approach where the fullorder local KF filter used in the conventional decentralized approach has been distributed into several loworder KFs, thus leading to a further vital reduction in the field reconstruction time. Our simulation results corroborated very well our expectations of the higher performance of our novel decentralizationcumdistribution approach since the estimates of the communication and computational loads on the N robots used show that a dramatic inexcess ofNfold reduction in the sampling time can be achieved, leading to a similar reduction in the field reconstruction time. These very encouraging results provide us with ample encouragement to further investigate both the efficiency and convergence properties of our proposed distributed filter scheme. This analytical investigation as well as our ultimate goal of successfully testing our proposed approach on a physical multirobot system is both currently under way.
Competing interests
The authors declare that they have no competing interests.
Acknowledgment
This study was supported by the King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia, Projects # JF090014 and SB101017.
References

W Jatmiko, K Sekiyama, T Fukuda, A mobile robots PSObased for odor source localization in dynamic advection–diffusion environment. IEEE/RSJ International Conference on Intelligent Robots and Systems, 4527–4532 (2006)

VN Christopoulos, S Roumeliotis, Adaptive sensing for instantaneous gas release parameter estimation. IEEE International Conference on Robotics and Automation, 4450–4456 (2005)

DA Robinson, CS Campbell, JW Hopmans, BK Hornbuckle, SB Jones, RO Knight, F Ogden, J Selker, O Wendroth, Soil moisture measurement for ecological and hydrological watershedscale observatories: a review. Vadose Zone J. 7, 358–389 (2008). Publisher Full Text

CJ Cannell, DJ Stilwell, A comparison of two approaches for adaptive sampling of environmental processes using autonomous underwater vehicles. Proceedings of MTS/IEEE OCEANS, 1514–1521 (2005)

NE Leonard, D Paley, F Lekien, R Sepulchre, DM Fratantoni, R Davis, Collective motion, sensor networks and ocean sampling. Proc. IEEE 95(1), 48–74 (2007)

MF Mysorewala, DO Popa, Multiscale adaptive sampling with mobile agents for mapping of forest fires. J. Intell. Robot. Syst. 54(4), 535–565 (2009). Publisher Full Text

V Hombal, AC Sanderson, R Blidberg, A nonparametric iterative algorithm for adaptive sampling and robotic vehicle path planning. IEEE/RSJ International Conference on Intelligent Robots and Systems, 217–222 (2006)

A Singh, A Krause, C Guestrin, W Kaiser, Efficient informative sensing using multiple robots. J. Artif. Intell. Res. (JAIR) 34, 707–755 (2009)

MA Demetriou, II Hussein, Estimation of spatially distributed processes using mobile spatially distributed sensor network. SIAM J. Control. Optim. 48, 266–291 (2009). Publisher Full Text

S Martinez, Distributed interpolation schemes for field estimation by mobile sensor networks. IEEE Trans. Control. Syst. Technol. 18(2), 491–500 (2010)

NAC Cressie, Statistics for Spatial Data, d (Wiley, New York, 1993)

ML Stein, in Interpolation of Spatial Data, ed. by . Some Theory for Kriging. Springer Series in Statistics (Springer, New York, 1999)

J Cortes, Distributed Kriged Kalman filter for spatial estimation. IEEE Trans. Automat. Control 54(12), 2816–2827 (2009)

R Graham, J Cortes, Spatial statistics and distributed estimation by robotic sensor networks. American Control Conference (ACC), 2422–2427 (2010)

R Graham, J Cortes, Cooperative adaptive sampling of random fields with partially known covariance. Int. J. Robust Nonlinear Control 22(5), 504–534 (2012). Publisher Full Text

R OlfatiSaber, Distributed Kalman filter with embedded consensus filters. 44th IEEE Conference on Decision and Control, 2005 and 2005 European Control Conference. CDCECC '05, 8179–8184 (2005)

R OlfatiSaber, Distributed Kalman filtering for sensor networks, in 46th IEEE Conference on Decision and. Control 2007(12–14), 5492–5498 (2007)

A Singh, D Budzik, W Chen, M Batalin, M Stealey, H Borgstrom, W Kaiser, Multiscale sensing: a new paradigm for actuated sensing of high frequency dynamic phenomena. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2006, 328–335 (2006)

AG Mutambara, Decentralized Estimation and Control for Multisensor Systems, Chapters 2–3 (CRC Press, Boca Raton, 1998), pp. pp. 19–79. doi:

HR Hashmipour, S Roy, AJ Laub, Decentralized structures for parallel Kalman filtering. IEEE Trans. Automat. Control 33(1), 88–93 (1988). Publisher Full Text

Y Gao, EY Krakiwsky, MA Abousalem, JF Mclellan, Comparison and analysis of centralized, decentralized, and federated filters. Navigation 40(1), 69–86 (1993)

MF Mysorewala, L Cheded, MS Baig, DO Popa, A distributed multirobot adaptive sampling scheme for complex field estimation. 11th International Conference on Control Automation Robotics & Vision (ICARCV) 2010, 7–10, 2466–2471 (2010)

DO Popa, MF Mysorewala, FL Lewis, EKFbased adaptive sampling with mobile robotic sensor nodes. International Conference on Intelligent Robots and Systems, 2006 IEEE/RSJ, 2451–2456 (2006)

Q Du, V Faber, M Gunzburger, Centroidal voronoi tessellations: applications and algorithms. SIAM Rev. 41, 637–676 (1999). Publisher Full Text

JC Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms( Kluwer Academic Publishers (Norwell, MA, 1981)

BS Rao, HF DurrantWhyte, Fully decentralized algorithm for multisensor Kalman filtering. IEE Proc. Control Theory Appl. 138, 413–420 (1991). Publisher Full Text

NA Carlson, Federated square root filter for decentralized parallel processes. IEEE Trans. Aerospace Electron. Syst. 26(3), 517–525 (1990). Publisher Full Text

DO Popa, AC Sanderson, RJ Komerska, SS Mupparapu, DR Blidberg, SG Chappel, Adaptive sampling algorithms for multiple autonomous underwater vehicles. Autonomous Underwater Vehicles, 108–118 (2004)

MF Mysorewala, L Cheded, A Qureshi, Comparison of nonlinear filters for the estimation of parametrized spatial field by robotic sampling. 6th IEEE conference on Industrial Electronics and Applications, 2005–2010 (2011)

S Haykin, Neural Networks: A Comprehensive Foundation, d (Prentice Hall PTR, 1998)