A Plume Tracking Algorithm Based on Crosswind Formations

We introduce a plume tracking algorithm based on robot formations. The algorithm is inherently designed for multi-robot systems, and requires at least two robots to collaborate. The robots try to keep themselves centered around the plume while moving upwind towards the source, and share their odor concentration and wind direction measurements with each other. In addition, robots know the relative poses of other team members. Systematic experiments with up to 5 real robots in a wind tunnel show that the robots achieve close-to-optimal performance in our scenario, and by far outperform previous approaches. The performance gain is attributed to the fact that robots continuously share information about the plume (odor concentration, wind direction) without spatially competing for acquiring it.

Bio-inspired and probabilistic algorithms for distributed odor source localization using mobile robots

Thomas Lochmatter

We compare six different algorithms for localizing odor sources with mobile robots. Three algorithms are bio-inspired and mimic the behavior of insects when exposed to airborne pheromones. Two algorithms are based on probability and information theory, and infer the source location by probabilistically merging concentration measurements at different positions in the environment. The last algorithm is a multi-robot algorithm based on a crosswind line formation. The algorithms are mainly compared with respect to their distance overhead – a metric directly related to the speed of an algorithm – and their success rate. The thesis also reports on the influence of various environmental and algorithmic parameters, and compares the algorithms' requirements regarding sensors, self-localization, maps, and other information. Systematic experiments under laminar flow conditions were carried out with real robots in an 18m long wind tunnel. The robots were thereby equipped with an ethanol sensor and a wind direction sensor, and could – if the algorithm required it – access their current position. Overall, more than 500 experimental runs with teams of up to 5 robots were carried out in this wind tunnel. Similar experiments were also carried out in simulation. Over 5000 runs were carried out in a realistically calibrated multi-robot simulator. Odor was thereby simulated as set of filaments that are transported by advection, an approach that generates the intermittence and stochasticity of real plumes. Additional, more than 10000 runs were carried out using body-less simulators under various plume models. Simulation runs were mostly used to quantify the influence of various parameters on the performance of the algorithms. Finally, the thesis also provides theoretical insights into the bio-inspired algorithms, and a general theoretical model for probabilistic odor source localization. For the latter, a number of potential real-world scenarios are discussed on the example of a simplified train station environment. None of the algorithms is strictly superior to all other algorithms. While the probabilistic algorithms offer more flexibility and a slightly better performance, the bio-inspired algorithms are much less CPU and memory intensive, and could therefore be deployed on extremely small and limited robotic platforms. Using multiple robots (with or without collaboration) for odor source localization was found to improve the performance under certain conditions only. The crosswind formation algorithm with 3 robots yielded excellent results, but the multi-robot experiments with the bio-inspired algorithms were hardly better than their single-robot counterparts. The thesis provides reasons for this, and discusses alternatives.

EPFL2010

Models and Algorithms for Ultra-Wideband Localization in Single- and Multi-Robot Systems

Amanda Stella Markowska Prorok

Location is a piece of information that empowers almost any type of application. In contrast to the outdoors, where global navigation satellite systems provide geo-spatial positioning, there are still millions of square meters of indoor space that are unaccounted for by location sensing technology. Moreover, predictions show that people’s activities are likely to shift more and more towards urban and indoor environments– the United Nations predict that by 2020, over 80% of the world’s population will live in cities. Meanwhile, indoor localization is a problem that is not simply solved: people, indoor furnishings, walls and building structures—in the eyes of a positioning sensor, these are all obstacles that create a very challenging environment. Many sensory modalities have difficulty in overcoming such harsh conditions when used alone. For this reason, and also because we aim for a portable, miniaturizable, cost-effective solution, with centimeter-level accuracy, we choose to solve the indoor localization problem with a hybrid approach that consists of two complementary components: ultra-wideband localization, and collaborative localization. In pursuit of the final, hybrid product, our research leads us to ask what benefits collaborative localization can provide to ultra-wideband localization—and vice versa. The road down this path includes diving into these orthogonal sub-domains of indoor localization to produce two independent localization solutions, before finally combining them to conclude our work. As for all systems that can be quantitatively examined, we recognize that the quality of our final product is defined by the rigor of our evaluation process. Thus, a core element of our work is the experimental setup, which we design in a modular fashion, and which we complexify incrementally according to the various stages of our studies. With the goal of implementing an evaluation system that is systematic, repeatable, and controllable, our approach is centered around the mobile robot. We harness this platform to emulate mobile targets, and track it in real-time with a highly reliable ground truth positioning system. Furthermore, we take advantage of the miniature size of our mobile platform, and include multiple entities to form a multi-robot system. This augmented setup then allows us to use the same experimental rigor to evaluate our collaborative localization strategies. Finally, we exploit the consistency of our experiments to perform cross-comparisons of the various results throughout the presented work. Ultra-wideband counts among the most interesting technologies for absolute indoor localization known to date. Owing to its fine delay resolution and its ability to penetrate through various materials, ultra-wideband provides a potentially high ranging accuracy, even in cluttered, non-line-of-sight environments. However, despite its desirable traits, the resolution of non-line-of-sight signals remains a hard problem. In other words, if a non-line-of-sight signal is not recognized as such, it leads to significant errors in the position estimate. Our work improves upon state-of-the-art by addressing the peculiarities of ultra-wideband signal propagation with models that capture the spatiality as well as the multimodal nature of the error statistics. Simultaneously, we take care to develop an underlying error model that is compact and that can be calibrated by means of efficient algorithms. In order to facilitate the usage of our multimodal error model, we use a localization algorithm that is based on particle filters. Our collaborative localization strategy distinguishes itself from prior work by emphasizing cost-efficiency, full decentralization, and scalability. The localization method is based on relative positioning and uses two quantities: relative range and relative bearing. We develop a relative robot detection model that integrates these measurements, and is embedded in our particle filter based localization framework. In addition to the robot detection model, we consider an algorithmic component, namely a reciprocal particle sampling routine, which is designed to facilitate the convergence of a robot’s position estimate. Finally, in order to reduce the complexity of our collaborative localization algorithm, and in order to reduce the amount of positioning data to be communicated between the robots, we develop a particle clustering method, which is used in conjunction with our robot detection model. The final stage of our research investigates the combined roles of collaborative localization and ultra-wideband localization. Numerous experiments are able to validate our overall localization strategy, and show that the performance can be significantly improved when using two complementary sensory modalities. Since the fusion of ultra-wideband positioning sensors with exteroceptive sensors has hardly been considered so far, our studies present pioneering work in this domain. Several insights indicate that collaboration—even if through noisy sensors—is a useful tool to reduce localization errors. In particular, we show that our collaboration strategy can provide the means to minimize the localization error, given that the collaborative design parameters are optimally tuned. Our final results show median localization errors below 10 cm in cluttered environments.

EPFL2013

Distributed Particle Swarm Optimization for limited-time adaptation with real robots

Ezequiel Leonardo Di Mario, Alcherio Martinoli

Evaluative techniques offer a tremendous potential for online controller design. However, when the optimization space is large and the performance metric is noisy, the overall adaptation process becomes extremely time consuming. Distributing the adaptation process reduces the required time and increases robustness to failure of individual agents. In this paper, we analyze the role of the four algorithmic parameters that determine the total evaluation time in a distributed implementation of a Particle Swarm Optimization (PSO) algorithm. For an obstacle avoidance case study using up to eight robots, we explore in simulation the lower boundaries of these parameters and propose a set of empirical guidelines for choosing their values. We then apply these guidelines to a real robot implementation and show that it is feasible to optimize 24 control parameters per robot within 2 h, a limited amount of time determined by the robots' battery life. We also show that a hybrid simulate-and-transfer approach coupled with a noise-resistant PSO algorithm can be used to further reduce experimental time as compared to a pure real-robot implementation.