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., traj