Spatial fields arise in a large variety of natural phenomena. We may think of ocean currents and temperature variations, wind patterns, or terrain elevations, as some of the traditionally studied examples. Spatial fields also arise in the form of collective motion patterns, such as in human crowds or traffic flow. The ability to model them is, therefore, of great interest in the fields of oceanography, topography, and urban planning, and an important challenge for robotic systems.
Scalable Gaussian processes (GPs) have emerged as a solution to this problem. The main idea behind monolithic, scalable GPs is to build sparse approximations of either the data or the GP itself, as a way to bound the computational complexity of the inference process. Alternatively, learning and inference can be performed in a distributed manner. In this scenario, a set of independent experts process a subset of the collected data, which is then used by a centralised computer to infer a global model.
It is therefore clear that multi-robot systems can successfully integrate GPs for scalable, decentralised regression. However, research on decentralised Gaussian process regression has been limited to settings where the learning agents have access to a positioning system. In swarm robotics, we do not make this assumption. To ensure the scalability of the swarm, robots rely only on local perception of the environment, and do not have access to global information, such as position data. This allows robot swarms to operate under GPS-denied conditions without compromising their performance.
To demonstrate the suitability of LU-GPR to estimate real-world spatial fields, we consider an evacuation scenario, where crowds are prone to exhibit collective motion patterns. In an indoor environment, a swarm of ground robots could sample pedestrian velocities to estimate the global crowd behaviour. These estimates could then be communicated to external security personnel, or used by the swarm itself to detect and prevent bottlenecks, oscillations, and other, potentially dangerous emergent phenomena.
Mathematical Background
This section introduces the mathematical concepts needed to understand the contribution. A complete presentation of these ideas is beyond the scope of this work.
Gaussian Belief Propagation
Gaussian belief propagation (GBP) is a method for performing marginal inference on a factor graph using message passing. Factor graphs are bipartite graphs whose nodes are either variables or factors. Variables represent quantities of interest that we want to estimate, but which are not directly observable. Factors connect variables and constrain their values based either on observations of the environment, or on specified priors.
In the standard GBP algorithm, the marginal posterior of each variable can be calculated through iterative message passing. At each iteration, the algorithm updates the belief at a variable node, given as a Gaussian distribution, using all its neighbouring factors. In tree-structured graphs, this will eventually converge to the exact marginals, but GBP gives empirically good results even in the presence of cycles.
Jones and Hauert recently implemented GBP in robot swarms. In their work, robots operate without global positioning and with limited-range communication only, and GBP allows them to converge to a common frame of reference. In their implementation, each robot keeps a bounded factor graph of variables representing its position with respect to the common frame, where positions are calculated from odometry measurements. As robots meet their neighbours, they create outward-facing factors that constrain their mutual factor graphs, allowing local position estimates to converge to a consistent representation.
Experimental Validation
LU-GPR is validated using two different scenarios. First, using a randomly generated synthetic function, the effects of the number of robots and the communication range on estimation quality are studied. Then, LU-GPR is used to model the behaviour of an evacuating crowd. For simplicity, the means of the GPs are assumed to be zero in both scenarios.
Synthetic Function Analysis
The robots converge to a solution, even for small swarm sizes. Larger swarm sizes lead to reduced estimation bias and variance, and convergence occurs at a faster rate. Interestingly, the communication range does not appear to have a significant impact on the final estimation; only on the convergence rate.
Discussion
LU-GPR is a solution to the spatial field estimation problem with robot swarms, where the robots do not have access to a positioning system. To focus on the novel aspects of LU-GPR, several aspects of the GPR framework were left unexplored, and some choices might have led to suboptimal solutions.
First, the update rules provide an adaptive and robust estimation framework, based on how their mathematical formulations compare to those presented in previous works. The results show that the robots can forget older samples, and that a simple weighting strategy results in a lower estimation bias of crowd behaviour. However, a systematic assessment of these properties in time-varying scenarios and in the presence of outliers remains an important subject for future work.
There is also the matter of the navigation strategy of the robots. Here, a simple, ballistic random walk was implemented. In order to take advantage of the full power of GPs, it is likely that an exploration strategy that uses the computed posterior variances through acquisition functions could lead to better optimised solutions. However, conceiving such a strategy is not trivial.
In the absence of full connectivity, robots in a swarm must decide individually how to act. Should they all use the full posterior estimate to decide where to move next, and assuming that all robots have a sufficiently accurate estimate, all robots could end up choosing the same strategy, resulting in poor exploration. Therefore, while a random walk might be a suboptimal exploration strategy, it could prove a more robust approach than naive implementations of acquisition functions.
The second type of input uncertainty comes from the position beliefs obtained through the GBP algorithm. In LU-GPR, the latest position estimates from the factor graph are used, and the corresponding uncertainties are ignored. As a result, one might argue that the posterior variances are overconfident.
A more accurate treatment of this source of uncertainty is, however, even less trivial than the one coming from odometry estimates. The reason is that this is a model-wide uncertainty, and mapping it to the individual input data points would destroy the correlation between the samples. One might think of using it to determine the weights of each individual model in the product of experts model. However, this would result in a conflicting effect with the uncertainties computed through the forgetting-based updates, and the resulting variances would be too conservative.
Finally, the choice of the product of experts model as an ensembling method could also be questioned. However, the product of experts is a suitable approach for decentralised systems, such as robot swarms. The main reason is that it does not assume any common priors for all the robots in the swarm. Therefore, each individual robot could, in principle, learn its own hyperparameters. For example, this approach can directly accommodate existing learning methods for distributed systems, like Bayesian model averaging.
In short, future work could focus on validating the adaptive and robust nature of the LU-GPR algorithm, enhancing its performance through exploration strategies that exploit the learned models, treating input noise more accurately, and introducing decentralised hyperparameter learning.
In addition, in order to make the solution easily portable to real robots, it would also be worth exploring messaging strategies with lower bandwidth requirements, as well as ensemble learning methods that scale sublinearly with the size of the swarm. Nevertheless, the solution is scalable and robust to both the limited communication ranges of a swarm and varying noise levels in the input data.
Frequently Asked Questions
What problem does LU-GPR address? LU-GPR estimates spatial fields with robot swarms whose robots do not have access to a positioning system.
Why are Gaussian processes useful for robot swarms? They support scalable, decentralised regression and allow multiple robots to contribute to a global spatial model.
How does communication range affect estimation? Communication range appears to affect convergence rate, but not the final estimation significantly.
What are the main areas for future work? Future work includes improved exploration, more accurate input-noise treatment, decentralised hyperparameter learning, lower-bandwidth messaging, and scalable ensemble methods.