Robotic clusters: Multi-robot systems as computer clusters A topological map merging demonstration

In most multi-robot systems, an individual robot is not capable of solving computationally hard problems due to lack of high processing power. This paper introduces the novel concept of robotic clusters to empower these systems in their problem solving. A robotic cluster is a group of individual robots which are able to share their processing resources, therefore, the robots can solve difficult problems by using the processing units of other robots. The concept, requirements, characteristics and architecture of robotic clusters are explained and then the problem of “topological map merging” is considered as a case study to describe the details of the presented idea and to evaluate its functionality. Additionally, a new parallel algorithm for solving this problem is developed. The experimental results proved that the robotic clusters remarkably speedup computations in multi-robot systems. The proposed mechanism can be used in many other robotic applications and has the potential to increase the performance of multi-robot systems especially for solving problems that need high processing resources.

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

Communication in a Swarm of Miniature Robots: The e-Puck as an Educational Tool for Swarm Robotics

Christopher Cianci, Alcherio Martinoli, James Pugh, Xavier Raemy

Swarm intelligence, and swarm robotics in particular, are reaching a point where leveraging the potential of communication within an artificial systempromises to uncover newand varied directions for interesting research without compromising the key properties of swarmintelligent systems such as self-organization, scalability, and robustness. However, the physical constraints of using radios in a robotic swarm are hardly obvious, and the intuitive models often used for describing such systems do not always capture them with adequate accuracy. In order to demonstrate this effectively in the classroom, certain tools can be used, including simulation and real robots. Most instructors currently focus on simulation, as it requires significantly less investment of time, money, and maintenance—but to really understand the differences between simulation and reality, it is also necessary to work with the real platforms from time to time. To our knowledge, our coursemay be the only one in the world where individual students are consistently afforded the opportunity to work with a networked multi-robot system on a tabletop. The e-Puck,1 a low-cost small-scale mobile robotic platform designed for educational use, allows us bringing real robotic hardware into the classroom in numbers sufficient to demonstrate and teach swarm-robotic concepts.We present here a custom module for local radio communication as a stackable extension board for the e-Puck, enabling information exchange between robots and also with any other IEEE 802.15.4-compatible devices. Transmission power can be modified in software to yield effective communication ranges as small as fifteen centimeters. This intentionally small range allows us to demonstrate interesting collective behavior based on local information and control in a limited amount of physical space, where ordinary radios would typically result in a completely connected network. Here we show the use of this module facilitating a collective decision among a group of 10 robots.

2007

Design, Modeling and Optimization of Stochastic Reactive Distributed Robotic Systems

Grégory Mermoud

This dissertation describes a complete methodological framework for designing, modeling and optimizing a specific class of distributed systems whose dynamics result from the multiple, stochastic interactions of their constitutive components. These components can be robots endowed with very minimal capabilities, or even simpler entities such as insects, bacteria, particles, or molecules. We refer to such components as Smart Minimal Particles (SMPs). One of the main difficulties facing the modeling of SMPs is the potential complexity and richness of their dynamics. On the one hand, one needs detailed models that account for the physico-chemical properties of the lower-level components (e.g., shape, material, surface chemistry, charge, etc.), which, in turn, determine the nature and the magnitude of their interactions. On the other hand, one is also interested in models that can yield accurate numerical predictions of macroscopic quantities, and investigate formally their dependence on the system’s design and control parameters. These competing requirements motivate a combination of models at multiple levels of abstraction, as advocated by the Multi-Level Modeling Methodology (MLMM), which was introduced in prior works. The MLMM enables the fulfillment of both requirements in a very efficient way by incrementally building up models at increasing levels of abstraction in order to capture the relevant features of the system. This thesis extends and consolidates the MLMM along several axes. In a first step, we provide a theoretical consolidation of the MLMM. We propose a thorough classification of the different models of SMPs, and we discuss their underlying assumptions and simplifications. We shed light on the fundamental impact of embodiment and spatiality on models’ accuracy, and we define the conditions under which the macro-deterministic approximation is valid. These theoretical considerations are experimentally supported by five case studies of aggregation and Self-Assembly (SA) at different scales. The five case studies utilize three types of components: (i) miniature wheeled robots (Alice, 2 cm in size) endowed with limited computation, sensing, actuation, and communication capabilities, (ii) water-floating passive modules (Lily, 3 cm in size) endowed with four permanent magnets for mutual latching, and (iii) micro-fabricated cylinders (about 100 μm in diameter, studied in realistic simulation only) that can achieve SA in liquids. In a second step, we introduce the core contribution of this thesis, that is, a systematic and generic methodology for bridging the gap between real, physical systems and computationally efficient models at multiple abstraction levels. In particular, we describe the M3 computational framework, which enables the automated construction of models of SMPs. Our approach consists in observing (or simulating realistically) a system of interest, and building a hierarchical suite of models based on the observations (i.e., trajectories) collected during these experiments (or simulations). Internally, the framework first builds up a microscopic representation of the system based on these observations and on a list of interactions of interest specified by the user. This representation, called the Canonical Microscopic Model (CMM), is a formal and generic description of SMPs, and it serves as a blueprint for the construction of a macroscopic model, specified using the Chemical Reaction Network (CRN) formalism. The rates of the CRN are finally calibrated using a Maximum Likelihood Estimation (MLE) scheme. We validate the M3 framework on each of the three platforms discussed earlier, thereby illustrating its relevance both as a modeling and as an analysis tool. Finally, we discuss the role of multi-level modeling when designing and optimizing SMPs. In particular, we show that top-down model-based design of multi-robot systems is generally not amenable to efficient implementations when dealing with very resource-constrained robots. Instead, faithful and computationally efficient models built incrementally from the bottom up prove to be an essential tool for designing such systems. We further corroborate this claim by applying our automated modeling framework to the real-time control of the stochastic SA of Lily modules. Our scientific contribution is therefore three-fold. First, we provide a solid experimental and theoretical consolidation of the MLMM, which has been the subject of intense research efforts for the last decade. Second, we propose, for the first time, an approach to generate models at high abstraction level in a completely automated fashion, based solely on observations of the system of interest. Third, we provide deep insights into the modeling and the design of SMPs, with a specific emphasis on self-assembling systems ranging from the centimeter scale down to the micrometer scale.

EPFL2012