Coordinated Control of Robotic Swarms in Unknown Environments

This thesis gathers the work carried out by the author in the last three years of research and it concerns the study and implementation of algorithms to coordinate and control a swarm of mobile robots moving in unknown environments. In particular, the author's attention is focused on two different approaches in order to solve two different problems. The first algorithm considered in this work deals with the possibility of decomposing a main complex task in many simple subtasks by exploiting the decentralized implementation of the so called \emph{Null Space Behavioral} paradigm. This approach to the problem of merging different subtasks with assigned priority is slightly modified in order to handle critical situations that can be detected when robots are moving through an unknown environment. In fact, issues can occur when one or more robots got stuck in local minima: a smart strategy to avoid deadlock situations is provided by the author and the algorithm is validated by simulative analysis. The second problem deals with the use of concepts borrowed from \emph{graph theory} to control a group differential wheel robots by exploiting the Laplacian solution of the consensus problem. Constraints on the swarm communication topology have been introduced by the use of a range and bearing platform developed at the Distributed Intelligent Systems and Algorithms Laboratory (DISAL), EPFL (Lausanne, CH) where part of author's work has been carried out. The control algorithm is validated by demonstration and simulation analysis and, later, is performed by a team of four robots engaged in a formation mission. To conclude, the capabilities of the algorithm based on the local solution of the consensus problem for differential wheel robots are demonstrated with an application scenario, where nine robots are engaged in a hunting task.

Coordination and Control of Autonomous Mobile Robots Swarms by using Particle Swarm Optimization Algorithm and Consensus Theory

This thesis presents some different techniques designed to drive a swarm of robots in an a-priori unknown environment in order to move the group from a starting area to a final one avoiding obstacles. The presented techniques are based on two different theories used alone or in combination: Swarm Intelligence (SI) and Graph Theory. Both theories are based on the study of interactions between different entities (also called agents or units) in Multi- Agent Systems (MAS). The first one belongs to the Artificial Intelligence context and the second one to the Distributed Systems context. These theories, each one from its own point of view, exploit the emergent behaviour that comes from the interactive work of the entities, in order to achieve a common goal. The features of flexibility and adaptability of the swarm have been exploited with the aim to overcome and to minimize difficulties and problems that can affect one or more units of the group, having minimal impact to the whole group and to the common main target. Another aim of this work is to show the importance of the information shared between the units of the group, such as the communication topology, because it helps to maintain the environmental information, detected by each single agent, updated among the swarm. Swarm Intelligence has been applied to the presented technique, through the Particle Swarm Optimization algorithm (PSO), taking advantage of its features as a navigation system. The Graph Theory has been applied by exploiting Consensus and the application of the agreement protocol with the aim to maintain the units in a desired and controlled formation. This approach has been followed in order to conserve the power of PSO and to control part of its random behaviour with a distributed control algorithm like Consensus.

Evolutionary methods for self-organizing cooperation in peer-to-peer networks

The Peer-to-Peer network paradigm is drawing the attention of both final users and researchers for its features. P2P networks shift from the classic client-server approach to a high level of decentralization where there is no central control and all the nodes should be able not only to require services, but to provide them to other peers as well. While on one hand such high level of decentralization might lead to interesting properties like scalability and fault tolerance, on the other hand it implies many new problems to deal with. A key feature of many P2P systems is openness, meaning that everybody is potentially able to join a network with no need for subscription or payment systems. The combination of openness and lack of central control makes it feasible for a user to free-ride, that is to increase its own benefit by using services without allocating resources to satisfy other peers’ requests. One of the main goals when designing a P2P system is therefore to achieve cooperation between users. Given the nature of P2P systems based on simple local interactions of many peers having partial knowledge of the whole system, an interesting way to achieve desired properties on a system scale might consist in obtaining them as emergent properties of the many interactions occurring at local node level. Two methods are typically used to face the problem of cooperation in P2P networks: 1) engineering emergent properties when designing the protocol; 2) study the system as a game and apply Game Theory techniques, especially to find Nash Equilibria in the game and to reach them making the system stable against possible deviant behaviors. In this work we present an evolutionary framework to enforce cooperative behaviour in P2P networks that is alternative to both the methods mentioned above. Our approach is based on an evolutionary algorithm inspired by computational sociology and evolutionary game theory, consisting in having each peer periodically trying to copy another peer which is performing better. The proposed algorithms, called SLAC and SLACER, draw inspiration from tag systems originated in computational sociology, the main idea behind the algorithm consists in having low performance nodes copying high performance ones. The algorithm is run locally by every node and leads to an evolution of the network both from the topology and from the nodes’ strategy point of view. Initial tests with a simple Prisoners’ Dilemma application show how SLAC is able to bring the network to a state of high cooperation independently from the initial network conditions. Interesting results are obtained when studying the effect of cheating nodes on SLAC algorithm. In fact in some cases selfish nodes rationally exploiting the system for their own benefit can actually improve system performance from the cooperation formation point of view. The final step is to apply our results to more realistic scenarios. We put our efforts in studying and improving the BitTorrent protocol. BitTorrent was chosen not only for its popularity but because it has many points in common with SLAC and SLACER algorithms, ranging from the game theoretical inspiration (tit-for-tat-like mechanism) to the swarms topology. We discovered fairness, meant as ratio between uploaded and downloaded data, to be a weakness of the original BitTorrent protocol and we drew inspiration from the knowledge of cooperation formation and maintenance mechanism derived from the development and analysis of SLAC and SLACER, to improve fairness and tackle freeriding and cheating in BitTorrent. We produced an extension of BitTorrent called BitFair that has been evaluated through simulation and has shown the abilities of enforcing fairness and tackling free-riding and cheating nodes.

Numerical simulations of magma chamber dynamics at Campi Flegrei, and associated seismicity, deformation and gravity changes

Understanding the complex relationships between quantities measured by volcanic monitoring network and shallow magma processes is a crucial headway for the comprehension of volcanic processes and a more realistic evaluation of the associated hazard. This question is very relevant at Campi Flegrei, a volcanic quiescent caldera immediately north-west of Napoli (Italy). The system activity shows a high fumarole release and periodic ground slow movement (bradyseism) with high seismicity. This activity, with the high people density and the presence of military and industrial buildings, makes Campi Flegrei one of the areas with higher volcanic hazard in the world. In such a context my thesis has been focused on magma dynamics due to the refilling of shallow magma chambers, and on the geophysical signals detectable by seismic, deformative and gravimetric monitoring networks that are associated with this phenomenologies. Indeed, the refilling of magma chambers is a process frequently occurring just before a volcanic eruption; therefore, the faculty of identifying this dynamics by means of recorded signal analysis is important to evaluate the short term volcanic hazard. The space-time evolution of dynamics due to injection of new magma in the magma chamber has been studied performing numerical simulations with, and implementing additional features in, the code GALES (Longo et al., 2006), recently developed and still on the upgrade at the Istituto Nazionale di Geofisica e Vulcanologia in Pisa (Italy). GALES is a finite element code based on a physico-mathematical two dimensional, transient model able to treat fluids as multiphase homogeneous mixtures, compressible to incompressible. The fundamental equations of mass, momentum and energy balance are discretised both in time and space using the Galerkin Least-Squares and discontinuity-capturing stabilisation technique. The physical properties of the mixture are computed as a function of local conditions of magma composition, pressure and temperature.The model features enable to study a broad range of phenomenologies characterizing pre and sin-eruptive magma dynamics in a wide domain from the volcanic crater to deep magma feeding zones. The study of displacement field associated with the simulated fluid dynamics has been carried out with a numerical code developed by the Geophysical group at the University College Dublin (O’Brien and Bean, 2004b), with whom we started a very profitable collaboration. In this code, the seismic wave propagation in heterogeneous media with free surface (e.g. the Earth’s surface) is simulated using a discrete elastic lattice where particle interactions are controlled by the Hooke’s law. This method allows to consider medium heterogeneities and complex topography. The initial and boundary conditions for the simulations have been defined within a coordinate project (INGV-DPC 2004-06 V3_2 “Research on active volcanoes, precursors, scenarios, hazard and risk - Campi Flegrei”), to which this thesis contributes, and many researchers experienced on Campi Flegrei in volcanological, seismic, petrological, geochemical fields, etc. collaborate. Numerical simulations of magma and rock dynamis have been coupled as described in the thesis. The first part of the thesis consists of a parametric study aimed at understanding the eect of the presence in magma of carbon dioxide in magma in the convection dynamics. Indeed, the presence of this volatile was relevant in many Campi Flegrei eruptions, including some eruptions commonly considered as reference for a future activity of this volcano. A set of simulations considering an elliptical magma chamber, compositionally uniform, refilled from below by a magma with volatile content equal or dierent from that of the resident magma has been performed. To do this, a multicomponent non-ideal magma saturation model (Papale et al., 2006) that considers the simultaneous presence of CO2 and H2O, has been implemented in GALES. Results show that the presence of CO2 in the incoming magma increases its buoyancy force promoting convection ad mixing. The simulated dynamics produce pressure transients with frequency and amplitude in the sensitivity range of modern geophysical monitoring networks such as the one installed at Campi Flegrei . In the second part, simulations more related with the Campi Flegrei volcanic system have been performed. The simulated system has been defined on the basis of conditions consistent with the bulk of knowledge of Campi Flegrei and in particular of the Agnano-Monte Spina eruption (4100 B.P.), commonly considered as reference for a future high intensity eruption in this area. The magmatic system has been modelled as a long dyke refilling a small shallow magma chamber; magmas with trachytic and phonolitic composition and variable volatile content of H2O and CO2 have been considered. The simulations have been carried out changing the condition of magma injection, the system configuration (magma chamber geometry, dyke size) and the resident and refilling magma composition and volatile content, in order to study the influence of these factors on the simulated dynamics. Simulation results allow to follow each step of the gas-rich magma ascent in the denser magma, highlighting the details of magma convection and mixing. In particular, the presence of more CO2 in the deep magma results in more ecient and faster dynamics. Through this simulations the variation of the gravimetric field has been determined. Afterward, the space-time distribution of stress resulting from numerical simulations have been used as boundary conditions for the simulations of the displacement field imposed by the magmatic dynamics on rocks. The properties of the simulated domain (rock density, P and S wave velocities) have been based on data from literature on active and passive tomographic experiments, obtained through a collaboration with A. Zollo at the Dept. of Physics of the Federici II Univeristy in Napoli. The elasto-dynamics simulations allow to determine the variations of the space-time distribution of deformation and the seismic signal associated with the studied magmatic dynamics. In particular, results show that these dynamics induce deformations similar to those measured at Campi Flegrei and seismic signals with energies concentrated on the typical frequency bands observed in volcanic areas. The present work shows that an approach based on the solution of equations describing the physics of processes within a magmatic fluid and the surrounding rock system is able to recognise and describe the relationships between geophysical signals detectable on the surface and deep magma dynamics. Therefore, the results suggest that the combined study of geophysical data and informations from numerical simulations can allow in a near future a more ecient evaluation of the short term volcanic hazard.

Metamorfismo ercinico di bassa-pressione: evoluzione tettonico-metamorfica del complesso di mandatoriccio (massiccio della Sila - Calabria)

Low-pressure/high-temperature (LP/HT) metamorphic belts are characterised by rocks that experienced abnormal heat flow in shallow crustal levels (T > 600 °C; P < 4 kbar) resulting in anomalous geothermal gradients (60-150 °C/km). The abnormal amount of heat has been related to crustal underplating of mantle-derived basic magmas or to thermal perturbation linked to intrusion of large volumes of granitoids in the intermediate crust. In particular, in this latter context, magmatic or aqueous fluids are able to transport relevant amounts of heat by advection, thus favouring regional LP/HT metamorphism. However, the thermal perturbation consequent to heat released by cooling magmas is responsible also for contact metamorphic effects. A first problem is that time and space relationships between regional LP/HT metamorphism and contact metamorphism are usually unclear. A second problem is related to the high temperature conditions reached at different crustal levels. These, in some cases, can completely erase the previous metamorphic history. Notwithstanding this problem is very marked in lower crustal levels, petrologic and geochronologic studies usually concentrate in these attractive portions of the crust. However, only in the intermediate/upper-crustal levels of a LP/HT metamorphic belt the tectono-metamorphic events preceding the temperature peak, usually not preserved in the lower crustal portions, can be readily unravelled. The Hercynian Orogen of Western Europe is a well-documented example of a continental collision zone with widespread LP/HT metamorphism, intense crustal anatexis and granite magmatism. Owing to the exposure of a nearly continuous cross-section of the Hercynian continental crust, the Sila massif (northern Calabria) represents a favourable area to understand large-scale relationships between granitoids and LP/HT metamorphic rocks, and to discriminate regional LP/HT metamorphic events from contact metamorphic effects. Granulite-facies rocks of the lower crust and greenschist- to amphibolite-facies rocks of the intermediate-upper crust are separated by granitoids emplaced into the intermediate level during the late stages of the Hercynian orogeny. Up to now, advanced petrologic studies have been focused mostly in understanding P-T evolution of deeper crustal levels and magmatic bodies, whereas the metamorphic history of the shallower crustal levels is poorly constrained. The Hercynian upper crust exposed in Sila has been subdivided in two different metamorphic complexes by previous authors: the low- to very low-grade Bocchigliero complex and the greenschist- to amphibolite-facies Mandatoriccio complex. The latter contains favourable mineral assemblages in order to unravel the tectono-metamorphic evolution of the Hercynian upper crust. The Mandatoriccio complex consists mainly of metapelites, meta-arenites, acid metavolcanites and metabasites with rare intercalations of marbles and orthogneisses. Siliciclastic metasediments show a static porphyroblastic growth mainly of biotite, garnet, andalusite, staurolite and muscovite, whereas cordierite and fibrolite are less common. U-Pb ages and internal features of zircons suggest that the protoliths of the Mandatoriccio complex formed in a sedimentary basin filled by Cambrian to Silurian magmatic products as well as by siliciclastic sediments derived from older igneous and metamorphic rocks. In some localities, metamorphic rocks are injected by numerous aplite/pegmatite veins. Small granite bodies are also present and are always associated to spotted schists with large porphyroblasts. They occur along a NW-SE trending transcurrent cataclastic fault zone, which represents the tectonic contact between the Bocchigliero and the Mandatoriccio complexes. This cataclastic fault zone shows evidence of activity at least from middle-Miocene to Recent, indicating that brittle deformation post-dated the Hercynian orogeny. P-T pseudosections show that micaschists and paragneisses of the Mandatoriccio complex followed a clockwise P-T path characterised by four main prograde phases: thickening, peak-pressure condition, decompression and peak-temperature condition. During the thickening phase, garnet blastesis started up with spessartine-rich syntectonic core developed within micaschists and paragneisses. Coevally (340 ± 9.6 Ma), mafic sills and dykes injected the upper crustal volcaniclastic sedimentary sequence of the Mandatoriccio complex. After reaching the peak-pressure condition (≈4 kbar), the upper crust experienced a period of deformation quiescence marked by the static overgrowths of S2 by Almandine-rich-garnet rims and by porphyroblasts of biotite and staurolite. Probably, this metamorphic phase is related to isotherms relaxation after the thickening episode recorder by the Rb/Sr isotopic system (326 ± 6 Ma isochron age). The post-collisional period was mainly characterised by decompression with increasing temperature. This stage is documented by the andalusite+biotite coronas overgrown on staurolite porphyroblasts and represents a critical point of the metamorphic history, since metamorphic rocks begin to record a significant thermal perturbation. Peak-temperature conditions (≈620 °C) were reached at the end of this stage. They are well constrained by some reaction textures and mineral assemblages observed almost exclusively within paragneisses. The later appearance of fibrolitic sillimanite documents a small excursion of the P-T path across the And-Sil boundary due to the heating. Stephanian U-Pb ages of monazite crystals from the paragneiss, can be related to this heating phase. Similar monazite U-Pb ages from the micaschist combined with the lack of fibrolitic sillimanite suggest that, during the same thermal perturbation, micaschists recorded temperatures slightly lower than those reached by paragneisses. The metamorphic history ended with the crystallisation of cordierite mainly at the expense of andalusite. Consequently, the Ms+Bt+St+And+Sill+Crd mineral assemblage observed in the paragneisses is the result of a polyphasic evolution and is characterised by the metastable persistence of the staurolite in the stability fields of the cordierite. Geologic, geochronologic and petrographic data suggest that the thermal peak recorded by the intermediate/upper crust could be strictly connected with the emplacement of large amounts of granitoid magmas in the middle crust. Probably, the lithospheric extension in the relatively heated crust favoured ascent and emplacement of granitoids and further exhumation of metamorphic rocks. After a comparison among the tectono-metamorphic evolutions of the different Hercynian crustal levels exposed in Sila, it is concluded that the intermediate/upper crustal level offers the possibility to reconstruct a more detailed tectono-metamorphic history. The P-T paths proposed for the lower crustal levels probably underestimate the amount of the decompression. Apart from these considerations, the comparative analysis indicates that P-T paths at various crustal levels in the Sila cross section are well compatible with a unique geologic scenario, characterized by post-collisional extensional tectonics and magmas ascent.

Analysis of eruptive and seismic sequences to improve the short-and long-term eruption forecasting

Forecasting the time, location, nature, and scale of volcanic eruptions is one of the most urgent aspects of modern applied volcanology. The reliability of probabilistic forecasting procedures is strongly related to the reliability of the input information provided, implying objective criteria for interpreting the historical and monitoring data. For this reason both, detailed analysis of past data and more basic research into the processes of volcanism, are fundamental tasks of a continuous information-gain process; in this way the precursor events of eruptions can be better interpreted in terms of their physical meanings with correlated uncertainties. This should lead to better predictions of the nature of eruptive events. In this work we have studied different problems associated with the long- and short-term eruption forecasting assessment. First, we discuss different approaches for the analysis of the eruptive history of a volcano, most of them generally applied for long-term eruption forecasting purposes; furthermore, we present a model based on the characteristics of a Brownian passage-time process to describe recurrent eruptive activity, and apply it for long-term, time-dependent, eruption forecasting (Chapter 1). Conversely, in an effort to define further monitoring parameters as input data for short-term eruption forecasting in probabilistic models (as for example, the Bayesian Event Tree for eruption forecasting -BET_EF-), we analyze some characteristics of typical seismic activity recorded in active volcanoes; in particular, we use some methodologies that may be applied to analyze long-period (LP) events (Chapter 2) and volcano-tectonic (VT) seismic swarms (Chapter 3); our analysis in general are oriented toward the tracking of phenomena that can provide information about magmatic processes. Finally, we discuss some possible ways to integrate the results presented in Chapters 1 (for long-term EF), 2 and 3 (for short-term EF) in the BET_EF model (Chapter 4).

Petrology and geochemistry of Lipari Island (Aeolian archipelago): constraints on magma genesis and evolution

A full set of geochemical and Sr, Nd and Pb isotope data both on bulk-rock and mineral samples is provided for volcanic rocks representative of the whole stratigraphic succession of Lipari Island in the Aeolian archipelago. These data, together with petrographic observations and melt/fluid inclusion investigations from the literature, give outlines on the petrogenesis and evolution of magmas through the magmatic and eruptive history of Lipari. This is the result of nine successive Eruptive Epochs developing between 271 ka and historical times, as derived from recentmost volcanological and stratigraphic studies, combined with available radiometric ages and correlation of tephra layers and marine terrace deposits. These Eruptive Epochs are characterized by distinctive vents partly overlapping in space and time, mostly under control of the main regional tectonic trends (NNW-SSE, N-S and minor E-W). A large variety of lava flows, scoriaceous deposits, lava domes, coulees and pyroclastics are emplaced, ranging in composition through time from calcalkaline (CA) and high-K (HKCA) basaltic andesites to rhyolites. CA and HKCA basaltic andesitic to dacitic magmas were erupted between 271 and 81 ka (Eruptive Epochs 1-6) from volcanic edifices located along the western coast of the island (and subordinately the eastern Monterosa) and the M.Chirica and M.S.Angelo stratocones. These mafic to intermediate magmas mainly evolved through AFC and RAFC processes, involving fractionation of mafic phases, assimilation of wall rocks and mixing with newly injected mafic magmas. Following a 40 ka-long period of volcanic quiescence, the rhyolitic magmas were lately erupted from eruptive vents located in the southern and north-eastern sectors of Lipari between 40 ka and historical times (Eruptive Epochs 7-9). They are suggested to derive from the previous mafic to intermediate melts through AFC processes. During the early phases of rhyolitic magmatism (Eruptive Epochs 7-8), enclaves-rich rocks and banded pumices, ranging in composition from HKCA dacites to low-SiO2 rhyolites were erupted, representing the products of magma mixing between fresh mafic magmas and the fractionated rhyolitic melts. The interaction of mantle-derived magmas with the crust represents an essential process during the whole magmatic hystory of Lipari, and is responsible for the wide range of observed geochemical and isotopic variations. The crustal contribution was particularly important during the intermediate phases of activity of Lipari when the cordierite-bearing lavas were erupted from the M. S.Angelo volcano (Eruptive Epoch 5, 105 ka). These lavas are interpreted as the result of mixing and subsequent hybridization of mantle-derived magmas, akin to the ones characterizing the older phases of activity of Lipari (Eruptive Epochs 1-4), and crustal anatectic melts derived from dehydration-melting reactions of metapelites in the lower crust. A comparison between the adjacent islands of Lipari and Vulcano outlines that their mafic to intermediate magmas seem to be genetically connected and derive from a similar mantle source affected by different degrees of partial melting (and variable extent of crustal assimilation) producing either the CA magmas of Lipari (higher degrees) or the HKCA to SHO magmas of Vulcano (lower degrees). On a regional scale, the most primitive rocks (SiO2<56%, MgO>3.5%) of Lipari, Vulcano, Salina and Filicudi are suggested to derive from a similar MORB-like source, variably metasomatized by aqueous fluids coming from the slab and subordinately by the additions of sediments.