Design, Modeling and Optimization of Stochastic Reactive Distributed Robotic Systems

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.

Real-Time Automated Modeling and Control of Self-Assembling Systems

Alcherio Martinoli, Massimo Mastrangeli, Grégory Mermoud, Utkarsh Upadhyay

We present the M3 framework, a formal and generic computational framework for modeling and controlling distributed stochastic systems of purely reactive robots in an automated and real-time fashion. Based on the trajectories of the robots, the framework builds up an internal microscopic representation of the system, which then serves as a blueprint of models at higher abstraction levels. These models are then calibrated using a Maximum Likelihood Estimation (MLE) approach. We illustrate the structure and performance of the framework by performing the online optimization of a simple bang-bang controller for the stochastic self-assembly of water- floating passive robots. The experimental results demonstrate that the generated models can successfully optimize the assem- bly of desired structures.

Ieee2012

Error handling in multimodal voice-enabled interfaces of tour-guide robots using graphical models

Plamen Prodanov

Mobile service robots are going to play an increasing role in the society of humans. Voice-enabled interaction with service robots becomes very important, if such robots are to be deployed in real-world environments and accepted by the vast majority of potential human users. The research presented in this thesis addresses the problem of speech recognition integration in an interactive voice-enabled interface of a service robot, in particular a tour-guide robot. The task of a tour-guide robot is to engage visitors to mass exhibitions (users) in dialogue providing the services it is designed for (e.g. exhibit presentations) within a limited time. In managing tour-guide dialogues, extracting the user goal (intention) for requesting a particular service at each dialogue state is the key issue. In mass exhibition conditions speech recognition errors are inevitable because of noisy speech and uncooperative users of robots with no prior experience in robotics. They can jeopardize the user goal identification. Wrongly identified user goals can lead to communication failures. Therefore, to reduce the risk of such failures, methods for detecting and compensating for communication failures in human-robot dialogue are needed. During the short-term interaction with visitors, the interpretation of the user goal at each dialogue state can be improved by combining speech recognition in the speech modality with information from other available robot modalities. The methods presented in this thesis exploit probabilistic models for fusing information from speech and auxiliary modalities of the robot for user goal identification and communication failure detection. To compensate for the detected communication failures we investigate multimodal methods for recovery from communication failures. To model the process of modality fusion, taking into account the uncertainties in the information extracted from each input modality during human-robot interaction, we use the probabilistic framework of Bayesian networks. Bayesian networks are graphical models that represent a joint probability function over a set of random variables. They are used to model the dependencies among variables associated with the user goals, modality related events (e.g. the event of user presence that is inferred from the laser scanner modality of the robot), and observed modality features providing evidence in favor of these modality events. Bayesian networks are used to calculate posterior probabilities over the possible user goals at each dialogue state. These probabilities serve as a base in deciding if the user goal is valid, i.e. if it can be mapped into a tour-guide service (e.g. exhibit presentation) or is undefined – signaling a possible communication failure. The Bayesian network can be also used to elicit probabilities over the modality events revealing information about the possible cause for a communication failure. Introducing new user goal aspects (e.g. new modality events and related features) that provide auxiliary information for detecting communication failures makes the design process cumbersome, calling for a systematic approach in the Bayesian network modelling. Generally, introducing new variables for user goal identification in the Bayesian networks can lead to complex and computationally expensive models. In order to make the design process more systematic and modular, we adapt principles from the theory of grounding in human communication. When people communicate, they resolve understanding problems in a collaborative joint effort of providing evidence of common shared knowledge (grounding). We use Bayesian network topologies, tailored to limited computational resources, to model a state-based grounding model fusing information from three different input modalities (laser, video and speech) to infer possible grounding states. These grounding states are associated with modality events showing if the user is present in range for communication, if the user is attending to the interaction, whether the speech modality is reliable, and if the user goal is valid. The state-based grounding model is used to compute probabilities that intermediary grounding states have been reached. This serves as a base for detecting if the the user has reached the final grounding state, or wether a repair dialogue sequence is needed. In the case of a repair dialogue sequence, the tour-guide robot can exploit the multiple available modalities along with speech. For example, if the user has failed to reach the grounding state related to her/his presence in range for communication, the robot can use its move modality to search and attract the attention of the visitors. In the case when speech recognition is detected to be unreliable, the robot can offer the alternative use of the buttons modality in the repair sequence. Given the probability of each grounding state, and the dialogue sequence that can be executed in the next dialogue state, a tour-guide robot has different preferences on the possible dialogue continuation. If the possible dialogue sequences at each dialogue state are defined as actions, the introduced principle of maximum expected utility (MEU) provides an explicit way of action selection, based on the action utility, given the evidence about the user goal at each dialogue state. Decision networks, constructed as graphical models based on Bayesian networks are proposed to perform MEU-based decisions, incorporating the utility of the actions to be chosen at each dialogue state by the tour-guide robot. These action utilities are defined taking into account the tour-guide task requirements. The proposed graphical models for user goal identification and dialogue error handling in human-robot dialogue are evaluated in experiments with multimodal data. These data were collected during the operation of the tour-guide robot RoboX at the Autonomous System Lab of EPFL and at the Swiss National Exhibition in 2002 (Expo.02). The evaluation experiments use component and system level metrics for technical (objective) and user-based (subjective) evaluation. On the component level, the technical evaluation is done by calculating accuracies, as objective measures of the performance of the grounding model, and the resulting performance of the user goal identification in dialogue. The benefit of the proposed error handling framework is demonstrated comparing the accuracy of a baseline interactive system, employing only speech recognition for user goal identification, and a system equipped with multimodal grounding models for error handling.

EPFL2006

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.