Control of agent swarms in random environments

The collective dynamic behavior of large groups of interacting autonomous agents (swarms) have inspired much research in both fundamental and engineering sciences. It is now widely acknowledged that the intrinsic nonlinearities due to mutual interactions can generate highly collective spatio-temporal patterns. Moreover, the resulting self-organized behavior cannot be simply guessed by solely investigating the elementary dynamic rules of single individuals. With a view to apply swarm collective behaviors to engineering, it is mandatory to thoroughly understand and master the mechanism of emergence to ultimately address the basic question: What individual dynamics and what type of interactions generate a given stable collective spatio-temporal behavior ? The present doctoral work is a contribution to the general common effort devoted to give an engineering operational answer to this simple and yet still highly challenging question. Swarms modeling is based on the dynamic properties of multi-agents systems (MAS). Methodological approaches for studying MAS are i) mathematics, ii) numerical simulation and iii) experimental validation on physical systems. While in this work we strive to construct and analytically solve new classes of mathematical MAS models, we also make a very special effort to develop new MAS modeling platforms for which one is simultaneously able to offer exact analytical results, corroborate these via simulation and finally implement the resulting control mechanism on swarms of actual robots. In full generality, MAS are formed by mutually interacting autonomous agents evolving in random environments. The presence of noise sources will indeed be unavoidable in any actual implementation. This drives us to consider coupled sets of stochastic nonlinear differential equations as being the natural mathematical modeling framework. We first focus on the simplest situations involving homogeneous swarms. Here, for large homogeneous swarms, the mean-field approach (borrowed from statistical physics) can be used to analytically characterize the resulting spatio-temporal patterns from the individual agent dynamics. In this context, we propose a new modeling platform (the so-called mixed-canonical dynamics) for which we are able to fully bridge the gap between pure mathematics and actual robotic implementation. In a second approach, we then consider heterogeneous swarms realized either when one agent behaves either as a leader or a shill (i.e as an infiltrated agent), or when two different sub-swarms compose the whole MAS. Analytical results are generally very hard to find for heterogeneous swarms, since the mean-field approach cannot be used. In this context, we use recent results in rank-based Brownian motions to approach some heterogeneous MAS models. In particular, we are able to analytically study i) a case of soft control of the swarm by a shill agent, and ii) the mutual interactions between two different societies (i.e., sub-groups) of homogeneous agents. Finally, the same mathematical framework enables us to consider a class of MAS where agents mutually interact via their environment (stigmergic interactions). Here, we can once again simultaneously present analytical results, numerical simulations and to ultimately implement the controller on a swarm of robotic boats.

Object-oriented approach for dynamic system modelling and simulation

Adel Besrour

Software engineering always cares to provide solutions for building applications as close as possible to what they should be, according to the requirements and the final users needs. Systems behavior simulation is a very common application to virtually reproduce and often predict the real-world behavior. Simulation is one of the most operational research tool in a large variety of engineering and scientific domains: Transport, telecommunication, medicine, chemical processes, physics, etc. The complexity of such application is relative to the increasing complexity of the systems. In this context, it is relevant to bring together different tools and formalisms such as markovian chain, Petri nets, etc., to improve the existent approaches and so to answer the simulations performances needs. The principle objective of this thesis is to bring together techniques from software engineering and safety engineering in order to improve the state of the art of modeling and simulation of dynamic systems in the industrial context. In addressing this objective, this work initially involves defining the essential limitations of the used formalisms, methods and tools regarding from one hand the software engineering modeling and simulation techniques and from the other hand the existent risk analysis methodologies. This work is conducted with respect to the problem of danger identification, considering the context of the complex systems behavior and their interaction with the human operator. In software engineering, it is well known that Petri/high-level nets have attractive characteristics to be used in systems simulation and behavior prediction such as the natural graphical representation, and their well-defined semantic. They are well-suited for the description of complex situations with concurrency (interleaving and true concurrency depending on the underlying semantics), conflict and confusion. However, the absence of structuring capabilities has been one of the main criticisms raised against Petri nets/high-level nets. Thus, there have been many attempts to introduce structuring principles in nets of this kind [BCM88] [Kie89] [JR91]. The attractive characteristics of Petri/high-level nets have prompted researchers to enrich these formalisms with object-oriented features. CO-OPN (Concurrent Object-Oriented Petri Net) approach, brings together the power of both Petri/high-level nets and object-orientation techniques, it has been devised so as to offer an adequate framework for the specification and design of large scale concurrent system [BG91]. CO-OPN, as a powerful modeling tool, has been used in a limited way to simulate systems. This work aims to provide a CO-OPN extension to allow a more realistic systems' simulation. Actually, its simulator semantic uses to be a suitable approach for modeling near closed systems and software components, because they need to loose coupling with external world. But, when we model more realistic problems like industrial processes, where human interaction is a relevant event, this approach is not sufficient to catch all system activity attributes. Moreover, the CO-OPN interpretation process does not allow interaction with the object internal states. This work provides a new solution to overcome CO-OPN simulation limitations and a set of prototypes to assist dynamic systems simulations. Furthermore, this work has been conducted in a Risk Analysis (RA) context, a domain where computer-based simulations research are of utmost interest. Actually, classical approaches used to address complex workplace hazard in a limited way, using checklists or sequence models. Moreover, the use of single oriented methods, such as AEA (man-oriented), FMEA (machine oriented) or HAZOP (process oriented), is not satisfactory to overcome the increasing sophistication of industrial processes. The automation of a part of the analysis process as well as the multiple-oriented approach allowed by dynamic modeling may indeed enhance significantly the analysis completeness and reduce the time analyzing time. This work, based on Object Oriented Petri net formalism (CO-OPN), propose an alternative multi-oriented approach where existent methods limitations have been criticized to develop a dynamic model, MORM (Man-machine Occupational Risk Modeling). A real industrial system (metal wire making process) has been specified to implement the different approach steps (system identification, model application, system simulation, system analysis).

EPFL2005

Computational fluid dynamics for naval engineering problems

Nicola Parolini

The subject of this thesis is the numerical simulation of viscous free-surface flows in naval engineering applications. State-of-the-art numerical methods based on the solution of the Navier-Stokes equations are used to predict the flow around different classes of boats. We investigate the role of the Computational Fluid Dynamics in the design of racing boats, such as America's Cup yachts and Olympic class rowing hull. The mathematical models describing the different aspects of the physical problem, as well as the numerical methods adopted for their solution, are introduced and critically discussed. The different phases of the overall numerical simulation procedure, from grid generation through the solution of the flow equations to the post-processing of the results, are described. We present the numerical simulations that have been performed to investigate the role of different design parameters in the conception of America's Cup yachts and we describe how the results obtained from the simulations are integrated into the overall design process. The free-surface flow around an Olympic rowing boat is also considered. We propose a simplified approach to take into account the effect of the boat dynamics in the prediction of the hydrodynamic forces acting on the boat. Based on the results of the simulations, we propose a new design concept and we investigate its potential benefits on the boat performances. One of the aspects that is found to be not completely satisfactory, within the standard numerical methods adopted, is the modelling of complex free-surface flows. The second part of this thesis is devoted to a more theoretical and methodological investigation of this aspect. In particular, we present and analyse a new numerical method based on the level set approach for the solution of two-fluid flows. The numerical scheme based on a finite element discretization is introduced and different critical aspects of its implementation are discussed. In particular, we present and analyse a new technique for the stabilization of the advection equation associated to the level set problem. Moreover, we propose a new reinitialization procedure for the level set function which plays a crucial role in the accuracy of the algorithm. The convergence properties of this procedure are analysed and comparisons with more standard approaches are presented. Finally, the proposed method has been used to solve a variety of test cases concerning time dependent two-fluid viscous flows. The results of the simulation are presented and discussed.

EPFL2004

Statistical Analysis of Chao’s Immune System Simulation

Eric Winnington

Modeling the immune system (IS) means putting together a set of assumptions about its components (cells and organs) and their interactions. Simulations of a model show joint behavior of the components, which for complex realistic models is often impossible to find analytically. Simulations allow us to experiment on how initial concentrations and properties of the immune cells and viruses impact the IS behavior, and gain better quantitative and qualitative insight into how the IS works and why different behavior patterns occur. A simulation, once it has been created, must be reviewed both statistically and analytically as well as validated from the biological point of view. We analyzed Chao’s immune system simulation [1][2] from a statistical and analytical point. We explicited both the Markov chain which was simulated and the underlying process on which Chao’s stage-structured approach was built. Furthermore, we established a test protocol for timestep validation which Chao’s simulator passed. We evaluated Chao’s simulator’s dependence on the random number generator, which was shown to be negligible. Finally, we evaluated the simulator output and our major result is the discovery of a secondary response to a primary infection, an occurrence is not shown in Chao’s dissertation. A tertiary response to the infection is never possible due to the size of the secondary response caused by memory cells.