Indoor Navigation Research with the Khepera III Mobile Robot: An Experimental Baseline with a Case-study on Ultra-wideband Positioning

Recent substantial progress in the domain of indoor positioning systems and a growing number of indoor location-based applications are creating the need for systematic, efficient, and precise experimental methods able to assess the localization and perhaps also navigation performance of a given device. With hundreds of Khepera III robots in academic use today, this platform has an important potential for single- and multi-robot localization and navigation research. In this work, we develop a necessary set of models for mobile robot navigation with the Khepera III platform, and quantify the robot’s localization performance based on extensive experimental studies. Finally, we validate our experimental approach to localization research by considering the evaluation of an ultra-wideband (UWB) positioning system. We successfully show how the robotic platform can provide precise performance analyses, ultimately proposing a powerful approach towards advancements in indoor positioning technology.

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

Synthesis, modeling, and experimental validation of distributed robotic search

James Pugh

The work of this thesis centers around the research subject of distributed robotic search. Within the field of distributed robotic systems, a task of particular interest is attempting to locate one or more targets in a possibly unknown environment. While numerous studies have proposed and analyzed methods to accomplish this, there is currently a lack of a strong foundation of tools and techniques that can be used to facilitate the development and evaluation of different approaches to distributed robotic search. In this work, we aim to provide such a foundation through tools, methods, models, and analysis of experimentation. An often overlooked aspect of the distributed robotic research process is the development and analysis of tools and modules to be used with robotic systems. These may include plug-ins for realistic robotic simulators, software/hardware systems to track multiple mobile robots in real-time, extension boards for robotic platforms, and the robots themselves. Along with other tools developed and used for this work, we focus particularly on the development, characterization, and validation of a fast, accurate on-board system for relative positioning and communication between robots, a capability which is critical for effective distributed robotic search. Designing individual robot controllers to generate a specific group behavior is a difficult and often counter-intuitive process. A possible alternative to hand-crafting distributed search controllers is automatic synthesis using machine-learning techniques. We explore the effectiveness of using a noise-resistant version of the Particle Swarm Optimization algorithm to optimize the weights of an embedded Artificial Neural Network, allowing the robot to learn obstacle avoidance behavior (a common benchmark for robotic learning techniques); we find that this technique appears to offer superior performance as compared to the canonical approach of using Genetic Algorithms for this type of learning. A method for faster learning using distributed evaluation in a robot team is tested and is found to offer comparable performance using only a fraction of the original learning time. This technique can be used for fast, effective learning and adaptation in a distributed robotic system performing search. The process of designing and analyzing algorithms for distributed robotic systems can be greatly facilitated if models are available to describe the dynamics of the algorithm at an abstract level. Inspired by previous examples in the distributed robotic field, we work to design a model of robotic search that captures the system at different levels of abstraction, ranging from accurately recreating the details of individual robots to describing the entire system as an indivisible whole. To capture the entire search process, we model both the exploration phase, where robots cover an environment in an effort to detect traces of targets, and the localization phase, where robots use target emission sensing to navigate towards the target. The utility of our models is demonstrated by using them to develop an effective technique for the declaration phase of search, where robots decide that a target has been accurately localized and announce its position. In distributed robotics research, it is important that techniques developed with abstracted simulations and models are ultimately validated using real robotic platforms in order to verify their correctness. In that spirit, we run systematic sound search experiments using teams of up to ten real robots. These experiments utilize the tools developed throughout the research process, demonstrate the utility of our learning technique for fast search adaptation, and serve to validate our models of distributed robotic localization. In addition, they allow us to analyze and better understand the subtle dynamics of the search process, providing information which should be useful for any future work on distributed robotic search.

EPFL2008

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