Search

This paper demonstrates a swarm robotics construction system where the intelligence that coordinates construction has been moved from the robots to an advanced building material. This building material, that we call Stigmergic Blocks, is capable of computation and local communication. Using comprehensive simulation models based on real hardware, we investigate approaches to improving the efficiency and flexibility of a swarm robotics construction system., SCOPUS: cp.k, info:eu-repo/semantics/published

As the number of processing cores is increasing dramatically, the communication among them is of high importance. Network-on-Chip (NoC) has direct access to all resources and information within a System-on-Chip (SoC) by rendering it appealing to attackers. In this paper a novel Hardware Trojan (HT) assisted Denial of Service (DoS) attack, called Greyhole attack is introduced. The HT-Greyhole attack targets the routers within NoC by causing performance decrease and packet loss increase. However, during an HT-Greyhole attack certain packets, which are arriving towards the router, are dropped which makes it hard to detect. In this paper, we design a detection and defense method, against HT-Greyhole attack, which is based on Software Defined Network-on-Chip (SDNoC) architecture. The results demonstrate that by using the proposed defense method the packet loss decreases by 76% under Transpose traffic, 77% under BitReverse and 50% under Uniform traffic., SCOPUS: cp.k, info:eu-repo/semantics/published

With the increasing amount of information needed for diagnosis and therapeutic decision-making, and new trends such as “personalized medicine”, pathologists are expressing an increasing demand for automated tools that perform their most recurrent tasks in their daily practice, as well as an increase in the complexity of the analyses requested in their research activities. With current advances in histopathology, oncology, and biology, the current questions require the analysis of protein expression - evidenced using immunohistochemical (IHC) staining - within specific histological structures or tissue components, or the analysis of the co-expression of several proteins in a large number of tissue samples. In this Ph.D. thesis, we developed innovative solutions to make these analyses available for pathologists. To achieve this objective, we have used recent “machine learning” and, in particular, “deep learning” methodologies. We addressed different problems such as image normalization, to solve the important problem of inter-batch variability of IHC staining, and the automatic segmentation of histological structures, to compartmentalize protein expression quantification. Finally, we adapted image registration techniques to Tissue MicroArray (TMA) slide images to enable large-scale analyses of IHC staining colocalization. While imagenormalization will improve study reproducibility, the tools developed for automated segmentation will drastically reduce time and expert resources required for some studies as well as errors and imprecision due to the human factor. Finally, the work on image registration can provide answers to complex questions that require studying the potential interaction between several proteins on numerous histological samples., Avec la quantité croissante d’informations nécessaires au diagnostic et à la prise de décision thérapeutique, et le développement de la “médecine personnalisée”, les pathologistes ont un besoin croissant d’outils automatisés pour exécuter leurs tâches les plus récurrentes. Ces outils se doivent également de réaliser des tâches de plus en plus complexes. En effet, avec les progrès récents en histopathologie, oncologie et biologie, les questions actuelles demandent, par exemple, l’analyse de l’expression de protéines révélées par marquages immunohistochimiques (IHC) au sein de structures ou compartiments histologiques spécifiques, ou encore l’analyse de la co-expression de plusieurs protéines dans un grand nombre d’échantillons. Dans cette thèse de doctorat, nous avons développé des solutions innovantes pour mettre ce type d’analyse à la disposition des pathologistes. Pour atteindre cet objectif, nous avons notamment fait appel à des méthodologies récentes de “machine learning” et, particulièrement, de “deep learning”. Nous avons ainsi abordé différentes questions telles que la normalisation d’images, pour résoudre l’important problème de la variabilité des marquages IHC, et la segmentation automatique de structures histologiques, pour permettre une quantification compartimentée de l’expression de protéines. Enfin, nous avons adapté des techniques dites de “recalage” aux images de lames de Tissue MicroArrays (TMA) pour permettre des analyses de colocalisation de marquages IHC à grande échelle. Alors que la normalisation des images améliore la reproductibilité des évaluations de marquages IHC, les outils développés pour la segmentation automatisée permettent de réduire significativement le temps et les ressources expertes nécessaires, ainsi que les erreurs et imprécisions dues au facteur humain. Enfin, les travaux sur le recalages d’images permettent d’apporter des éléments de réponse à des questions complexes qui nécessitent d’étudier l’interaction potentielle entre plusieurs protéines sur de nombreux échantillons histologiques., Doctorat en Sciences de l'ingénieur et technologie, info:eu-repo/semantics/nonPublished

Research in swarm robotics focuses mostly on how robots interact and cooperate to perform tasks, rather than on the details of task execution. As a consequence, researchers often consider abstract tasks in their experimental work. For example, foraging is often studied without physically handling objects: the retrieval of an object from a source to a destination is abstracted into a trip between the two locations---no object is physically transported. Despite being commonly used, so far task abstraction has only been implemented in an ad hoc fashion.In this dissertation, I propose a collection of tools for flexible and reproducible task abstraction. At the core of this collection is a physical device that serves as an abstraction of a single-robot task to be performed by an e-puck robot. I call this device the TAM, an acronym for "task abstraction module". A complex multi-robot task can be abstracted using a group of TAMs by first modeling the task as the set of its constituent single-robot subtasks and then representing each subtask with a TAM. I propose a novel approach to modeling complex tasks and a framework for controlling a group of TAMs such that the behavior of the group implements the model of the complex task.The combination of the TAM, the modeling approach, and the control framework forms a collection of tools for conducting research in swarm robotics. These tools enable research on cooperative behaviors and complex tasks with simple, cost-effective robots such as the e-puck - research that would be difficult and costly to conduct using specialized robots or ad hoc solutions to task abstraction. I present proof-of-concept experiments and several studies that use the TAM for task abstraction in order to illustrate the variety of tasks that can be studied with the proposed tools., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

For a little over twenty years, researchers have worked on integrating multi-criteria aggregation procedures (MCAP) to GIS. Several notable contributions have brought this field to what it is today. After studying the course of MCDA-GIS integration through several works, we question the future of such an attempt. Indeed most works that aim for an integration do not survive long after their direct purpose has been fulfilled. We end up understanding through a critical review of the existing systems that technical integration means nothing if it is not visible to the user on an operational level.We therefore propose several contributions to improve the usability of MCDA methods in a geographic context. One of our works consists in adapting the PROMETHEE-GAIA methodology to be used on maps for spatially referenced problems. To do so, we define symbols/glyphs that display select parts of the results obtained through the PROMETHEE and GAIA methods. This allows for the comparison of alternatives' profiles and characteristics based on their geographic location which wasn't possible before. This adaptation helps us combine multicriteria and geographic aspects in an entirely new way.We also propose some extensions of the GAIA method to improve the quality of the results and reduce the risk of wrong interpretations to be made due to losses of data., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

The implementation is based on available open source software packages - Deal.II, Trilinos, PARALUTION and AGMG. These packages provide toolboxes with state-of-the-art implementations of iterative solution methods and preconditioners for multicore computer platforms and GPU. We present performance results in terms of numerical and the computational efficiency, number of iterations and execution time, and compare the timing results against a sparse direct solver from a commercial finite element package, that is often used by applied scientists in their simulations., SCOPUS: cp.k, info:eu-repo/semantics/published

In this dissertation, we propose and study methods for information transfer within a swarm of mobile robots that coordinately move, or flock, in a common direction. We define information transfer as the process whereby robots share directional information in order to coordinate their heading direction. We identify two paradigms of information transfer: explicit information transfer and implicit information transfer. In explicit information transfer, directional information is transferred via communication. Explicit information transfer requires mobile robots equipped with a a communication device. We propose novel communication strategies for explicit information transfer, and we perform flocking experiments in different situations: with one or two desired directions of motion that can be static or change over time. We perform experiments in simulation and with real robots. Furthermore, we show that the same explicit information transfer strategies can also be applied to another collective behavior: collective transport with obstacle avoidance. In implicit information transfer, directional information is transferred without communication. We show that a simple motion control method is sufficient to guarantee cohesive and aligned motion without resorting to communication or elaboratesensing. We analyze the motion control method for its capability to achieve flocking with and without a desired direction of motion, both in simulation and using real robots. Furthermore, to better understand its underlying mechanism, we study thismethod using tools of statistical physics, showing that the process can be explained in terms of non-linear elasticity and energy-cascading dynamics., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

Continuous optimization problems are optimization problems where all variableshave a domain that typically is a subset of the real numbers; mixed discrete-continuousoptimization problems have additionally other types of variables, sothat some variables are continuous and others are on an ordinal or categoricalscale. Continuous and mixed discrete-continuous problems have a wide rangeof applications in disciplines such as computer science, mechanical or electricalengineering, economics and bioinformatics. These problems are also often hard tosolve due to their inherent difficulties such as a large number of variables, manylocal optima or other factors making problems hard. Therefore, in this thesis ourfocus is on the design, engineering and configuration of high-performing heuristicoptimization algorithms.We tackle continuous and mixed discrete-continuous optimization problemswith two classes of population-based heuristic algorithms, ant colony optimization(ACO) algorithms and evolution strategies. In a nutshell, the main contributionsof this thesis are that (i) we advance the design and engineering of ACO algorithms to algorithms that are competitive or superior to recent state-of-the-artalgorithms for continuous and mixed discrete-continuous optimization problems,(ii) we improve upon a specific state-of-the-art evolution strategy, the covariancematrix adaptation evolution strategy (CMA-ES), and (iii) we extend CMA-ES totackle mixed discrete-continuous optimization problems.More in detail, we propose a unified ant colony optimization (ACO) frameworkfor continuous optimization (UACOR). This framework synthesizes algorithmiccomponents of two ACO algorithms that have been proposed in the literatureand an incremental ACO algorithm with local search for continuous optimization,which we have proposed during my doctoral research. The design of UACORallows the usage of automatic algorithm configuration techniques to automaticallyderive new, high-performing ACO algorithms for continuous optimization. We alsopropose iCMAES-ILS, a hybrid algorithm that loosely couples IPOP-CMA-ES, aCMA-ES variant that uses a restart schema coupled with an increasing populationsize, and a new iterated local search (ILS) algorithm for continuous optimization.The hybrid algorithm consists of an initial competition phase, in which IPOP-CMA-ES and the ILS algorithm compete for further deployment during a secondphase. A cooperative aspect of the hybrid algorithm is implemented in the formof some limited information exchange from IPOP-CMA-ES to the ILS algorithmduring the initial phase. Experimental studies on recent benchmark functionssuites show that UACOR and iCMAES-ILS are competitive or superior to otherstate-of-the-art algorithms.To tackle mixed discrete-continuous optimization problems, we extend ACOMV and propose CESMV, an ant colony optimization algorithm and a covariance matrix adaptation evolution strategy, respectively. In ACOMV and CESMV ,the decision variables of an optimization problem can be declared as continuous, ordinal, or categorical, which allows the algorithm to treat them adequately. ACOMV andCESMV include three solution generation mechanisms: a continuous optimizationmechanism, a continuous relaxation mechanism for ordinal variables, and a categorical optimization mechanism for categorical variables. Together, these mechanisms allow ACOMV and CESMV to tackle mixed variable optimization problems.We also propose a set of artificial, mixed-variable benchmark functions, which cansimulate discrete variables as ordered or categorical. We use them to automatically tune ACOMV and CESMV's parameters and benchmark their performance.Finally we test ACOMV and CESMV on various real-world continuous and mixed-variable engineering optimization problems. Comparisons with results from theliterature demonstrate the effectiveness and robustness of ACOMV and CESMVon mixed-variable optimization problems.Apart from these main contributions, during my doctoral research I have accomplished a number of additional contributions, which concern (i) a note on thebound constraints handling for the CEC'05 benchmark set, (ii) computational results for an automatically tuned IPOP-CMA-ES on the CEC'05 benchmark set and(iii) a study of artificial bee colonies for continuous optimization. These additionalcontributions are to be found in the appendix to this thesis., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

In this thesis, we propose an approach to achieve autonomous task partitioning in swarms of robots. Task partitioning is the process by which tasks are decomposed into sub-tasks and it is often an advantageous way of organizing work in groups of individuals. Therefore, it is interesting to study its application to swarm robotics, in which groups of robots are deployed to collectively carry out a mission. The capability of partitioning tasks autonomously can enhance the flexibility of swarm robotics systems because the robots can adapt the way they decompose and perform their work depending on specific environmental conditions and goals. So far, few studies have been presented on the topic of task partitioning in the context of swarm robotics. Additionally, in all the existing studies, there is no separation between the task partitioning methods and the behavior of the robots and often task partitioning relies on characteristics of the environments in which the robots operate.This limits the applicability of these methods to the specific contexts for which they have been built. The work presented in this thesis represents the first steps towards a general framework for autonomous task partitioning in swarms of robots. We study task partitioning in foraging, since foraging abstracts practical real-world problems. The approach we propose in this thesis is therefore studied in experiments in which the goal is to achieve autonomous task partitioning in foraging. However, in the proposed approach, the task partitioning process relies upon general, task-independent concepts and we are therefore confident that it is applicable in other contexts. We identify two main capabilities that the robots should have: i) being capable of selecting whether to employ task partitioning and ii) defining the sub-tasks of a given task. We propose and study algorithms that endow a swarm of robots with these capabilities., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

Dans cette thèse nous nous sommes intéressés principalement, dans le cadre de l’e-learning, à mettre en oeuvre une méthodologie qui a pour mission d’assurer une interopérabilité entre la plate-forme de l’Université de Lubumbashi et les plates-formes des universités partenaires belges afin de permettre un transfert des contenus d’apprentissage. Notre démarche n’a pas voulu s’arrêter à l’échange des contenus, nous sommes allés jusqu’à proposer des moyens de permettre un suivi dynamique des étudiants via les outils de communication./ In this thesis we were mainly interested, within the framework of the e-learning, to implement(operate) a methodology which has for mission to assure(insure) an interoperability between the platform of the University of Lubumbashi and the platforms of the Belgian partner universities to allow a transfer of the contents of learning(apprenticeship). Our approach(initiative) did not want to stop(arrest) in the exchange of the contents, we went as far as suggesting means allowing a dynamic follow-up of the students via communications tools., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

Le but principal de cette thèse de doctorat est de concevoir un système de chirurgie assistée par la connaissance. Cette connaissance est extraite de l'information issue des données et du contexte capturés en salle d'opération. Ce contexte est défini à l'aide d'un modèle de processus opératoire (surgical workflow - SWf). L'assistance porte sur la capture des modèles, l'automatisation de tâches ou encore la gestion des erreurs et des imprévus.The main goal of this PhD thesis is to design a computer assisted surgery system based on surgical workflow (SWf) modeling, and intra-operative data and metadata acquired during the operation. For the SWf modeling, workflow-mining techniques will be developed based on dynamic learning and incremental inference. An ontology will be used to describe the various steps of the surgery and their attributes., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

Cette thèse décrit le développement et la mise en œuvre d'un système d'acquisition 3D ayant pour but la localisation temps réel en 3D et l'identification d'électrodes et des antennes utilisées lors d'un examen MEG/EEG. La seconde partie concerne la mise en correspondance de ces données avec les informations de la résonance magnétique., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

The present work proposes visibly pushdown transducers (VPTs) for defining transformations of documents with a nesting structure. We show that this subclass of pushdown transducers enjoy good properties. Notably, we show that functionality is decidable in PTime and k-valuedness in co-NPTime. While this class is not closed under composition and its type checking problem against visibly pushdown automata is undecidable, we identify a subclass, the well-nested VPTs, closed under composition and with a decidable type checking problem. Furthermore, we show that the class of VPTs is closed under look-ahead, and that the deterministic VPTs with look-ahead characterize the functional VPTs transductions. Finally, we investigate the resources necessary to perform transformations defined by VPTs. We devise a memory efficient algorithm. Then we show that it is decidable whether a VPT transduction can be performed with a memory that depends on the level of nesting of the input document but not on its length., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

A swarm intelligence system is a type of multiagent system with the following distinctive characteristics: (i) it is composed of a large number of agents, (ii) the agents that comprise the system are simple with respect to the complexity of the task the system is required to perform, (iii) its control relies on principles of decentralization and self-organization, and (iv) its constituent agents interact locally with one another and with their environment. Interactions among agents, either direct or indirect through the environment in which they act, are fundamental for swarm intelligence to exist; however, there is a class of interactions, referred to as "interference", that actually blocks or hinders the agents' goal-seeking behavior. For example, competition for space may reduce the mobility of robots in a swarm robotics system, or misleading information may spread through the system in a particle swarm optimization algorithm. One of the most visible effects of interference in a swarm intelligence system is the reduction of its efficiency. In other words, interference increases the time required by the system to reach a desired state. Thus, interference is a fundamental problem which negatively affects the viability of the swarm intelligence approach for solving important, practical problems.We propose a framework called "incremental social learning" (ISL) as a solution to the aforementioned problem. It consists of two elements: (i) a growing population of agents, and (ii) a social learning mechanism. Initially, a system under the control of ISL consists of a small population of agents. These agents interact with one another and with their environment for some time before new agents are added to the system according to a predefined schedule. When a new agent is about to be added, it learns socially from a subset of the agents that have been part of the system for some time, and that, as a consequence, may have gathered useful information. The implementation of the social learning mechanism is application-dependent, but the goal is to transfer knowledge from a set of experienced agents that are already in the environment to the newly added agent. The process continues until one of the following criteria is met: (i) the maximum number of agents is reached, (ii) the assigned task is finished, or (iii) the system performs as desired. Starting with a small number of agents reduces interference because it reduces the number of interactions within the system, and thus, fast progress toward the desired state may be achieved. By learning socially, newly added agents acquire knowledge about their environment without incurring the costs of acquiring that knowledge individually. As a result, ISL can make a swarm intelligence system reach a desired state more rapidly. We have successfully applied ISL to two very different swarm intelligence systems. We applied ISL to particle swarm optimization algorithms. The results of this study demonstrate that ISL substantially improves the performance of these kinds of algorithms. In fact, two of the resulting algorithms are competitive with state-of-the-art algorithms in the field. The second system to which we applied ISL exploits a collective decision-making mechanism based on an opinion formation model. This mechanism is also one of the original contributions presented in this dissertation. A swarm robotics system under the control of the proposed mechanism allows robots to choose from a set of two actions the action that is fastest to execute. In this case, when only a small proportion of the swarm is able to concurrently execute the alternative actions, ISL substantially improves the system's performance., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

We investigate the use of self-assembly in a robotic system as a means of responding to dierent environmental contingencies. Self-assembly is the mechanism through which agents in a multi-robot system autonomously form connections with one another to create larger composite robotic entities. Initially, we consider a simple response mechanism that uses stochastic self-assembly without any explicit control over the resulting morphology | the robots self-assemble into a larger, randomly shaped composite entity if the task they encounter is beyond the physical capabilities of a single robot. We present distributed behavioural control that enables a group of robots to make this collective decision about when and if to self-assemble in the context of a hill crossing task. In a series of real-world experiments, we analyse the eect of dierent distributed timing and decision strategies on system performance. Outside of a task execution context, we present fully decentralised behavioural control capable of creating periodically repeating global morphologies. We then show how arbitrary morphologies can be generated by abstracting our behavioural control into a morphology control language and adding symbolic communication between connected agents. Finally, we integrate our earlier distributed response mechanism into the morphology control language. We run simulated and real-world experiments to demonstrate a self-assembling robotic system that can respond to varying environmental contingencies by forming dierent appropriate morphologies., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/published

Stochastic combinatorial optimization problems are combinatorial optimization problems where part of the problem data are probabilistic. The focus of this thesis is on stochastic routing problems, a class of stochastic combinatorial optimization problems that arise in distribution management. Stochastic routing problems involve finding the best solution to distribute goods across a logistic network. In the problems we tackle, we consider a setting in which the cost of a solution is described by a random variable; the goal is to find the solution that minimizes the expected cost. Solving such stochastic routing problems is a challenging task because of two main factors. First, the number of possible solutions grows exponentially with the instance size. Second, computing the expected cost of a solution is computationally very expensive. To tackle stochastic routing problems, stochastic local search algorithms such as iterative improvement algorithms and metaheuristics are quite promising because they offer effective strategies to tackle the combinatorial nature of these problems. However, a crucial factor that determines the success of these algorithms in stochastic settings is the trade-off between the computation time needed to search for high quality solutions in a large search space and the computation time spent in computing the expected cost of solutions obtained during the search. To compute the expected cost of solutions in stochastic routing problems, two classes of approaches have been proposed in the literature: analytical computation and empirical estimation. The former exactly computes the expected cost using closed-form expressions; the latter estimates the expected cost through Monte Carlo simulation.Many previously proposed metaheuristics for stochastic routing problems use the analytical computation approach. However, in a large number of practical stochastic routing problems, due to the presence of complex constraints, the use of the analytical computation approach is difficult, time consuming or even impossible. Even for the prototypical stochastic routing problems that we consider in this thesis, the adoption of the analytical computation approach is computationally expensive. Notwithstanding the fact that the empirical estimation approach can address the issues posed by the analytical computation approach, its adoption in metaheuristics to tackle stochastic routing problems has never been thoroughly investigated. In this thesis, we study two classical stochastic routing problems: the probabilistic traveling salesman problem (PTSP) and the vehicle routing problem with stochastic demands and customers (VRPSDC). The goal of the thesis is to design, implement, and analyze effective metaheuristics that use the empirical estimation approach to tackle these two problems. The main results of this thesis are: 1) The empirical estimation approach is a viable alternative to the widely-adopted analytical computation approach for the PTSP and the VRPSDC; 2) A principled adoption of the empirical estimation approach in metaheuristics results in high performing algorithms for tackling the PTSP and the VRPSDC. The estimation-based metaheuristics developed in this thesis for these two problems define the new state-of-the-art., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

Radiofrequency ablation (RFA) is a minimally invasive treatment for either hepatocellular carcinoma or metastasis liver carcinoma. In order to resect large lesions, the surgeon has to perform multiple time-consuming destruction cycles and reposition the RFA needle for each of them. The critical step in handling a successful ablation and preventing local recurrence is the correct positioning of the needle. For small tumors, the surgeon places the middle of the active needle tip in the center of the tumor under intra-operative ultrasound guidance. When one application is not enough to cover the entire tumor, the surgeon needs to repeat the treatment after repositioning of the needle, but US guidance is obstructed by the opacity stemming from the first RFA application. In this case the surgeon can only rely on anatomical knowledge and the repositioning of the RFA needle becomes a subjective task limiting the treatment accuracy. We have developed a computer assisted surgery guidance application for this repositioning procedure. Our software application handles the complete process from preoperative image analysis to tool tracking in the operating room. Our framework is mostly used for this RFA procedure, but is also suitable for any other medical or surgery application., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

De nos jours, il est peu de processus ou de tâches qui ne requièrent pas l'optimisation d'une quantité :diminuer le temps de livraison, diminuer l'espace utilisé, réduire les efforts de développement, C'est donc sans surprise que la recherche en optimisation soit l'un des domaines les plus actifs des sciences des technologies de l'information. En optimisation combinatoire, les métaheuristiques sont à compter parmi le fleuron des techniques algorithmiques. Mais ce succès est encore au prix d'une quantité significative de temps de conception et développement. Ne serait-il pas possible d'aller encore plus loin ?D'automatiser la préparation des métaheuristiques ?En particulier dans des conditions telles le manque de temps, l'ignorance de techniques spécialisées ou encore la mauvaise compréhension du problème traité ?C'est ce à quoi nous répondons dans la présente thèse au moyen d'une approche de méta-modélisation de la recherche :l'heuristique de la Gestalt.Considérant la représentation du problème comme un levier que l'on peut activer sous le processus de recherche mené par une métaheuristique, la thèse suggère la construction d'une abstraction de cette représentation capable d'assister la métaheuristique à trouver de bonnes solutions en contraignant sa recherche. Cette approche, inspirée de la psychologie de la Gestalt, nous l'appelons l'heuristique de la Gestalt. Son fonctionnement repose principalement sur l'agrégation des variables de la représentation. Cette agrégation donne lieu à une abstraction structurelle, mais également fonctionnelle en ce sens que les opérateurs de la métaheuristique doivent désormais respecter l'intégrité des agrégats définis.Après avoir établi le contexte de la dissertation, nous discutons de la transposition de la psychologie de la Gestalt dans le cadre de l'optimisation combinatoire et des métaheuristiques. S'ensuit la formalisation de l'heuristique de la Gestalt et la description de sa réalisation. Finalement, une série d'études expérimentales sont menées pour éprouver le concept avancé et valider l'implémentation basée sur les algorithmes évolutionnistes que nous proposons. En conclusion, nous affirmons que l'implémentation de l'heuristique de la Gestalt basée, entre autres, sur un algorithme génétique de groupement est capable d'assister positivement des algorithmes génétiques lorsque les instances de problèmes traitées possèdent une structure riche et complexe, que leur taille est importante, que l'on est tôt dans le processus d'optimisation et que l'algorithme génétique n'est pas paramétré spécifiquement., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

Notre thèse est consacrée à l’étude des méthodes de rangements multicritères dans le cadre de la problématique de tri. Dans un problème de tri une personne, appelée décideur, désire assigner un objet, appelé action, à des catégories prédéfinies. Des problèmes de tri surgissent régulièrement dans la vie de tous les jours. Par exemple, un médecin ausculte son patient et sur base des symptômes observés, il assigne son patient à une catégorie de pathologies. Ainsi, le médecin peut prescrire un traitement approprié. Par ailleurs, on catégorise les cyclones tropicaux en fonction de leur vitesse, pression superficielle et de la hauteur de marée. En fonction de la catégorie du cyclone, des dégâts éventuels peuvent être prédits et des mesures de protection adéquates devront être prises. Dans un problème de tri, un décideur regroupe ainsi les actions qu’il considère similaires, à des fins descriptives, organisationnelles ou préventives. Nous supposerons en outre que le décideur exprime une relation de préférence entre les classes préalablement définies. D’autre part, les méthodes de rangement permettent de ranger les actions de la meilleure à la moins bonne. Nul étudiant ne peut nier l’existence des " rankings " d’universités. Une société ordonne les candidats à l’issue d’un entretien d’embauche. Une société désire par ailleurs établir des partenariats avec les fournisseurs les plus performants. Nous sommes tous confrontés à cette tâche délicate de ranger les actions de la meilleure à la moins bonne. Les méthodes d’aide à la décision proposent des techniques permettant à un décideur d’obtenir un rangement d’actions. L’objectif de cette thèse est d’étudier la possibilité de résoudre des problèmes de tri à l’aide de méthodes de rangement. L’approche adoptée est de ranger une action particulière par rapport à des normes ou profils définissant les catégories. L’assignation de l’action sera dès lors basée sur sa position dans ce rangement particulier. Quelles sont les hypothèses nécessaires pour un tel modèle ?Ces méthodes présentent-elles un biais ou ont-elles d’autres avantages par rapport aux méthodes de tri existantes? Est-il préférable de modéliser les catégories à l’aide de critères même si celles-ci ne présentent pas de relation de préférence ?Dans cette thèse nous donnerons des premiers éléments de réponse en développant de nouvelles méthodes de tri basées sur des méthodes de rangement existantes., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

In this thesis, we use evolutionary robotics techniques to automatically design and synthesisebehaviour for groups of simulated and real robots. Our contribution will be onthe design of non-trivial individual and collective behaviour; decisions about solitary orsocial behaviour will be temporal and they will be interdependent with communicativeacts. In particular, we study time-based decision-making in a social context: how theexperiences of robots unfold in time and how these experiences influence their interactionwith the rest of the group. We propose three experiments based on non-trivial real-worldcooperative scenarios. First, we study social cooperative categorisation; signalling andcommunication evolve in a task where the cooperation among robots is not a priori required.The communication and categorisation skills of the robots are co-evolved fromscratch, and the emerging time-dependent individual and social behaviour are successfullytested on real robots. Second, we show on real hardware evidence of the success of evolvedneuro-controllers when controlling two autonomous robots that have to grip each other(autonomously self-assemble). Our experiment constitutes the first fully evolved approachon such a task that requires sophisticated and fine sensory-motor coordination, and ithighlights the minimal conditions to achieve assembly in autonomous robots by reducingthe assumptions a priori made by the experimenter to a functional minimum. Third, wepresent the first work in the literature to deal with the design of homogeneous controlmechanisms for morphologically heterogeneous robots, that is, robots that do not sharethe same hardware characteristics. We show how artificial evolution designs individualbehaviours and communication protocols that allow the cooperation between robots ofdifferent types, by using dynamical neural networks that specialise on-line, depending onthe nature of the morphology of each robot. The experiments briefly described abovecontribute to the advancement of the state of the art in evolving neuro-controllers forcollective robotics both from an application-oriented, engineering point of view, as well asfrom a more theoretical point of view., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

In this thesis we provide a model for a bufferless optical burst switching (OBS) and an optical packet switching (OPS) network. The thesis is divided in three parts. In the first part we introduce the basic functionality and structure of OBS and OPS networks. We identify the blocking probability as the main performance parameter of interest. In the second part we study the statistical properties of the traffic that will likely run through these networks. We use for this purpose a set of traffic traces obtained from the Universidad Politécnica de Catalunya. Our conclusion is that traffic entering the optical domain in future OBS/OPS networks will be long-range dependent (LRD). In the third part we present the model for bufferless OBS/OPS networks. This model takes into account the results from the second part of the thesis concerning the LRD nature of traffic. It also takes into account specific issues concerning the functionality of a typical bufferless packet-switching network. The resulting model presents scalability problems, so we propose an approximative method to compute the blocking probability from it. We empirically evaluate the accuracy of this method, as well as its scalability., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

In this thesis, we investigate the problem of path formation and prey retrieval in a swarm of robots. We present two swarm intelligence control mechanisms used for distributed robot path formation. In the first, the robots form linear chains. We study three variants of robot chains, which vary in the degree of motion allowedto the chain structure. The second mechanism is called vectorfield. In this case,the robots form a pattern that globally indicates the direction towards a goal orhome location. Both algorithms were designed following the swarm robotics controlprinciples: simplicity of control, locality of sensing and communication, homogeneityand distributedness.We test each controller on a task that consists in forming a path between twoobjects—the prey and the nest—and to retrieve the prey to the nest. The difficultyof the task is given by four constraints. First, the prey requires concurrent, physicalhandling by multiple robots to be moved. Second, each robot’s perceptual rangeis small when compared to the distance between the nest and the prey; moreover,perception is unreliable. Third, no robot has any explicit knowledge about theenvironment beyond its perceptual range. Fourth, communication among robots isunreliable and limited to a small set of simple signals that are locally broadcast.In simulation experiments we test our controllers under a wide range of conditions,changing the distance between nest and prey, varying the number of robotsused, and introducing different obstacle configurations in the environment. Furthermore,we tested the controllers for robustness by adding noise to the different sensors,and for fault tolerance by completely removing a sensor or actuator. We validate thechain controller in experiments with up to twelve physical robots. We believe thatthese experiments are among the most sophisticated examples of self-organisationin robotics to date., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

In this dissertation, we study two new approaches to fault detection for autonomous robots. The first approach involves the synthesis of software components that give a robot the capacity to detect faults which occur in itself. Our hypothesis is that hardware faults change the flow of sensory data and the actions performed by the control program. By detecting these changes, the presence of faults can be inferred. In order to test our hypothesis, we collect data in three different tasks performed by real robots. During a number of training runs, we record sensory data from the robots both while they are operating normally and after a fault has been injected. We use back-propagation neural networks to synthesize fault detection components based on the data collected in the training runs. We evaluate the performance of the trained fault detectors in terms of the number of false positives and the time it takes to detect a fault.The results show that good fault detectors can be obtained. We extend the set of possible faults and go on to show that a single fault detector can be trained to detect several faults in both a robot's sensors and actuators. We show that fault detectors can be synthesized that are robust to variations in the task. Finally, we show how a fault detector can be trained to allow one robot to detect faults that occur in another robot.The second approach involves the use of firefly-inspired synchronization to allow the presence of faulty robots to be determined by other non-faulty robots in a swarm robotic system. We take inspiration from the synchronized flashing behavior observed in some species of fireflies. Each robot flashes by lighting up its on-board red LEDs and neighboring robots are driven to flash in synchrony. The robots always interpret the absence of flashing by a particular robot as an indication that the robot has a fault. A faulty robot can stop flashing periodically for one of two reasons. The fault itself can render the robot unable to flash periodically.Alternatively, the faulty robot might be able to detect the fault itself using endogenous fault detection and decide to stop flashing.Thus, catastrophic faults in a robot can be directly detected by its peers, while the presence of less serious faults can be detected by the faulty robot itself, and actively communicated to neighboring robots. We explore the performance of the proposed algorithm both on a real world swarm robotic system and in simulation. We show that failed robots are detected correctly and in a timely manner, and we show that a system composed of robots with simulated self-repair capabilities can survive relatively high failure rates.We conclude that i) fault injection and learning can give robots the capacity to detect faults that occur in themselves, and that ii) firefly-inspired synchronization can enable robots in a swarm robotic system to detect and communicate faults., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

In this thesis we have studied different aspects of the novel field of quantum information with continuous variables. The higher efficiency and bandwidth of homodyne detection combined with the easiness of generation and manipulation of Gaussian states makes continuous-variable quantum information a promising and flourishing field of research. This dissertation is divided in two parts. The first part explores two applications of the “photon subtraction” operation; Firstly, a technique to generate highly non-Gaussian single-mode states of light; Secondly, an experimental setup capable of realizing a loophole-free Bell test. The second part of this dissertation develops a detailed analysis of an important family of continuous-variable quantum key distribution protocols, namely those based on Gaussian modulation of Gaussian states./Dans cette thèse on a étudié différents aspects de l'information quantique à variables continues. Les meilleures efficacité et bande passante de la détection homodyne combinées à la simplicité de génération et de manipulation d'états gaussiens rend l'information quantique à variables continues un domaine de recherche très prometteur, qui est actuellement en plein essor. La dissertation est divisée en deux parties. La première explore deux applications de l'opération “soustraction de photon”; en premier lieu on présente une nouvelle technique capable de générer des états mono-modaux de la lumière hautement non-gaussiens; deuxiemement on présente un schéma expérimental capable de réaliser un test de Bell sans faille logique. La deuxième partie de cette dissertation développe une étude détaillée d'une famille très importante de protocoles de distribution quantique de clé à variables continues, ceux basés sur la modulation gaussienne d'états gaussiens., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

L'introduction du temps dans les bases de données classiques et spatiales apparaît de plus en plus, aujourd'hui, comme une nécessité pour une gestion optimale de l'historicité. En effet, les applications de bases de données spatio-temporelles sont présentes dans un grand nombre d'applications. Le besoin, par exemple, est de sauvegarder l'historique des géométries des parcelles dans le système d'information d'un plan cadastral, la prévention d'incendie dans le système de gestion forestière, le système de navigation des véhicules, etc. Cet historique des phénomènes permet de mieux comprendre ce qui s'est produit dans le passé, de manière à éventuellement anticiper certaines évolutions futures.Etant donné ces nouveaux besoins, cette thèse se focalise sur la modélisation et l'implantation des aspects temporels dans bases de données. En effet, la conception d'une application de base de données se fait par un enchaînement de trois phases (conceptuelle, logique et physique). Au niveau conceptuel, plusieurs modèles conceptuels ont été proposés intégrant les caractéristiques temporelles et spatiales.Malheureusement, au niveau logique, les modèles de données des SGBD actuels n'offrent pas les concepts nécessaires pour implanter le modèle conceptuel spatio-temporel. Nous proposons donc de nouvelles règles de traductions d'un schéma conceptuel, basé sur le modèle MADS (Modélisation des Applications à des données spatio-temporelles), en un schéma logique MADSLog pour les modèles cibles à savoir :relationnel et relationnel-objet. Chaque règle transforme un concept structurel, temporel et spatial du modèle MADS en un ou plusieurs concepts supportés par la cible. Par exemple, la propriété spatiale définissant la géométrie d'un type d'objet est traduite par la création d'un nouvel attribut de type spatial dans ce type d'objet. Un outil CASE(Computer-Aided Software Engineering) appelé Schema Translateur est développé dans cette thèse implémentant toutes les règles de traductions.La traduction de schémas conceptuels en schémas logiques peut impliquer une perte sémantique en raison de la différence de la puissance d'expression entre le modèle conceptuel et le modèle de données des SGBD existants. D'où la nécessité de générer un ensemble de contraintes d'intégrité afin de préserver la sémantique définie dans le schéma conceptuel. Ces contraintes sont exprimées à ce niveau par des formules logiques.Avec l'apparition de GML (Geographic Markup Language ) qui est conçu pour la modélisation, le transport et le stockage d'informations géographiques. Nous transformons également le schéma conceptuel MADS en GML. De nouveaux schémas GML temporel et spatial sont définis qui peuvent être employés par n'importe application de base de données spatio-temporelle.Au niveau physique, nous proposons une méthode d'adaptation du schéma logique en schéma physique pour le modèle relationnel-objet.Elle permet de définir les tables, les types abstraits, les types d'objets, les domaines, etc. Notre proposition permet aussi la génération des contraintes d'intégrité au niveau physique. En effet, chaque contrainte d'intégrité (structurelle, temporelle ou spatiale) qui est définie en calcul logique est exprimée soit directement par des contraintes déclaratives ou soit par des déclencheurs du SGBD choisi. Les déclencheurs spatiaux sont fondés sur les fonctionnalités prédéfinies dans Oracle, alors que les déclencheurs temporels sont basés sur les opérateurs et méthodes appliquées sur les types temporels.Enfin, la traduction de requêtes est une deuxième clef de cette recherche. Le but de la traduction de requêtes, exprimées en algèbre, étant de reconstituer l'information au sens MADS à partir de la base de données stockées dans le SGDB cible. Elle permet de traduire les expressions algébriques MADS, qui sont définies sur le schéma conceptuel et non sur le schéma physique, en requêtes opérationnelles qui peuvent être exécutées sur une base de données spatiale et temporelle sous un SGBD ou un SIG., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

Doctorat en Sciences, info:eu-repo/semantics/nonPublished

The all-over trend for an universal access and ubiquitous access to the Internet is driving a revolution in our societies. In order to support this era of nomadic applications, new flexible network architectures have emerged. They are referred to as “wireless ad-hoc networks.” Since human-operated devices will more likely be used indoor, it leads to many issues related to the strength of the fading in this environment. Recently, it has been suggested that a possible interaction might exist between various parameters of the ad-hoc networks and, more precisely, between the propagation model and the routing protocol. To address this question, we present in this dissertation a cross-layer perspective of the analysis of these indoor ad-hoc networks. Our reasoning is made of four stages. First, the cross-layer interactions are analyzed by the means of multivariate statistical techniques. Since a cross-layering between the physical layer and the routing protocol has been proven to be significant, we further investigate the possible development a physical layer-constrained routing algorithm. Second, fundamental equations governing the wireless telecommunications systems are developed in order to provide insightful informations on how a reliable routing strategy should be implemented in a strongly-faded environment. After that, and in order to allow a better spatial reuse, the routing protocol we propose is further enhanced by the adjonction of a power control algorithm. This last feature is extensively analyzed and a closed-form expression of the link probability of outage in presence of non-homogeneous transmission powers is given. Numerous simulations corroborate the applicability and the performance of the derived protocol. Also, we evaluate the gain, in terms of radio channel ressources, that has been achieved by the means of the power control algorithm. Third, an architecture for the interconnection with a cellular network is investigated. A closed-form expression of the relaying stability of a node is given. This equation expresses the minimal requirement that a relaying node from the ad-hoc network must fullfil in order to bridge properly the connections to the base-station. Finally, a real-life implementation is provided as a validation of the applicability of this novel ad-hoc routing protocol. It is concluded that, both from the performance and the spatial re-use point-of-views, it can be taken advantage from the cross-layering between the physical and the routing layers to positively enhance the networking architectures deployed in an indoor environment., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

In this thesis, we examine algorithms for the division of labour in a group of robot. The algorithms make no use of direct communication. Instead, they are based only on the interactions among the robots and between the group and the environment.Division of labour is the mechanism that decides how many robots shall be used to perform a task. The efficiency of the group of robots depends in fact on the number of robots involved in a task. If too few robots are used to achieve a task, they might not be successful or might perform poorly. If too many robots are used, it might be a waste of resources. The number of robots to use might be decided a priori by the system designer. More interestingly, the group of robots might autonomously select how many and which robots to use. In this thesis, we study algorithms of the latter type.The robotic literature offers already some solutions, but most of them use a form of direct communication between agents. Direct, or explicit, communication between the robots is usually considered a necessary condition for co-ordination. Recent studies have questioned this assumption. The claim is based on observations of animal colonies, e.g. ants and termites. They can effectively co-operate without directly communicating, but using indirect forms of communication like stigmergy. Because they do not rely on communication, such colonies show robust behaviours at group level, a condition that one wishes also for groups of robots. Algorithms for robot co-ordination without direct communication have been proposed in the last few years. They are interesting not only because they are a stimulating intellectual challenge, but also because they address a situation that might likely occur when using robots for real-world out-door applications. Unfortunately, they are still poorly studied.This thesis helps the understanding and the development of such algorithms. We start from a specific case to learn its characteristics. Then we improve our understandings through comparisons with other solutions, and finally we port everything into another domain.We first study an algorithm for division of labour that was inspired by ants' foraging. We test the algorithm in an application similar to ants' foraging: prey retrieval. We prove that the model used for ants' foraging can be effective also in real conditions. Our analysis allows us to understand the underlying mechanisms of the division of labour and to define some way of measuring it.Using this knowledge, we continue by comparing the ant-inspired algorithm with similar solutions that can be found in the literature and by assessing their differences. In performing these comparisons, we take care of using a formal methodology that allows us to spare resources. Namely, we use concepts of experiment design to reduce the number of experiments with real robots, without losing significance in the results.Finally, we apply and port what we previously learnt into another application: Sensor/Actor Networks (SANETs). We develop an architecture for division of labour that is based on the same mechanisms as the ants' foraging model. Although the individuals in the SANET can communicate, the communication channel might be overloaded. Therefore, the agents of a SANET shall be able to co-ordinate without accessing the communication channel., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

Decision support systems are interactive, computer-based information systems that provide data and analysis tools in order to better assist managers on different levels of organization in the process of decision making. Data warehouses (DWs) have been developed and deployed as an integral part of decision support systems. A data warehouse is a database that allows to store high volume of historical data required for analytical purposes. This data is extracted from operational databases, transformed into a coherent whole, and loaded into a DW during the extraction-transformation-loading (ETL) process. DW data can be dynamically manipulated using on-line analytical processing (OLAP) systems. DW and OLAP systems rely on a multidimensional model that includes measures, dimensions, and hierarchies. Measures are usually numeric additive values that are used for quantitative evaluation of different aspects about organization. Dimensions provide different analysis perspectives while hierarchies allow to analyze measures on different levels of detail. Nevertheless, currently, designers as well as users find difficult to specify multidimensional elements required for analysis. One reason for that is the lack of conceptual models for DW and OLAP system design, which would allow to express data requirements on an abstract level without considering implementation details. Another problem is that many kinds of complex hierarchies arising in real-world situations are not addressed by current DW and OLAP systems.In order to help designers to build conceptual models for decision-support systems and to help users in better understanding the data to be analyzed, in this thesis we propose the MultiDimER model - a conceptual model used for representing multidimensional data for DW and OLAP applications. Our model is mainly based on the existing ER constructs, for example, entity types, attributes, relationship types with their usual semantics, allowing to represent the common concepts of dimensions, hierarchies, and measures. It also includes a conceptual classification of different kinds of hierarchies existing in real-world situations and proposes graphical notations for them.On the other hand, currently users of DW and OLAP systems demand also the inclusion of spatial data, visualization of which allows to reveal patterns that are difficult to discover otherwise. The advantage of using spatial data in the analysis process is widely recognized since it allows to reveal patterns that are difficult to discover otherwise. However, although DWs typically include a spatial or a location dimension, this dimension is usually represented in an alphanumeric format. Furthermore, there is still a lack of a systematic study that analyze the inclusion as well as the management of hierarchies and measures that are represented using spatial data. With the aim of satisfying the growing requirements of decision-making users, we extend the MultiDimER model by allowing to include spatial data in the different elements composing the multidimensional model. The novelty of our contribution lays in the fact that a multidimensional model is seldom used for representing spatial data. To succeed with our proposal, we applied the research achievements in the field of spatial databases to the specific features of a multidimensional model. The spatial extension of a multidimensional model raises several issues, to which we refer in this thesis, such as the influence of different topological relationships between spatial objects forming a hierarchy on the procedures required for measure aggregations, aggregations of spatial measures, the inclusion of spatial measures without the presence of spatial dimensions, among others. Moreover, one of the important characteristics of multidimensional models is the presence of a time dimension for keeping track of changes in measures. However, this dimension cannot be used to model changes in other dimensions. Therefore, usual multidimensional models are not symmetric in the way of representing changes for measures and dimensions. Further, there is still a lack of analysis indicating which concepts already developed for providing temporal support in conventional databases can be applied and be useful for different elements composing a multidimensional model. In order to handle in a similar manner temporal changes to all elements of a multidimensional model, we introduce a temporal extension for the MultiDimER model. This extension is based on the research in the area of temporal databases, which have been successfully used for modeling time-varying information for several decades. We propose the inclusion of different temporal types, such as valid and transaction time, which are obtained from source systems, in addition to the DW loading time generated in DWs. We use this temporal support for a conceptual representation of time-varying dimensions, hierarchies, and measures. We also refer to specific constraints that should be imposed on time-varying hierarchies and to the problem of handling multiple time granularities between source systems and DWs. Furthermore, the design of DWs is not an easy task. It requires to consider all phases from the requirements specification to the final implementation including the ETL process. It should also take into account that the inclusion of different data items in a DW depends on both, users' needs and data availability in source systems. However, currently, designers must rely on their experience due to the lack of a methodological framework that considers above-mentioned aspects. In order to assist developers during the DW design process, we propose a methodology for the design of conventional, spatial, and temporal DWs. We refer to different phases, such as requirements specification, conceptual, logical, and physical modeling. We include three different methods for requirements specification depending on whether users, operational data sources, or both are the driving force in the process of requirement gathering. We show how each method leads to the creation of a conceptual multidimensional model. We also present logical and physical design phases that refer to DW structures and the ETL process.To ensure the correctness of the proposed conceptual models, i.e. with conventional data, with the spatial data, and with time-varying data, we formally define them providing their syntax and semantics. With the aim of assessing the usability of our conceptual model including representation of different kinds of hierarchies as well as spatial and temporal support, we present real-world examples. Pursuing the goal that the proposed conceptual solutions can be implemented, we include their logical representations using relational and object-relational databases., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

In this thesis we focus on Stochastic combinatorial Optimization Problems (SCOPs), a wide class of combinatorial optimization problems under uncertainty, where part of the information about the problem data is unknown at the planning stage, but some knowledge about its probability distribution is assumed.Optimization problems under uncertainty are complex and difficult, and often classical algorithmic approaches based on mathematical and dynamic programming are able to solve only very small problem instances. For this reason, in recent years metaheuristic algorithms such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others, are emerging as successful alternatives to classical approaches.In this thesis, metaheuristics that have been applied so far to SCOPs are introduced and the related literature is thoroughly reviewed. In particular, two properties of metaheuristics emerge from the survey: they are a valid alternative to exact classical methods for addressing real-sized SCOPs, and they are flexible, since they can be quite easily adapted to solve different SCOPs formulations, both static and dynamic. On the base of the current literature, we identify the following as the key open issues in solving SCOPs via metaheuristics: (1) the design and integration of ad hoc, fast and effective objective function approximations inside the optimization algorithm;(2) the estimation of the objective function by sampling when no closed-form expression for the objective function is available, and the study of methods to reduce the time complexity and noise inherent to this type of estimation;(3) the characterization of the efficiency of metaheuristic variants with respect to different levels of stochasticity in the problem instances. We investigate the above issues by focusing in particular on a SCOP belonging to the class of vehicle routing problems: the Probabilistic Traveling Salesman Problem (PTSP). For the PTSP, we consider the Ant Colony Optimization metaheuristic and we design efficient local search algorithms that can enhance its performance. We obtain state-of-the-art algorithms, but we show that they are effective only for instances above a certain level of stochasticity, otherwise it is more convenient to solve the problem as if it were deterministic.The algorithmic variants based on an estimation of the objective function by sampling obtain worse results, but qualitatively have the same behavior of the algorithms based on the exact objective function, with respect to the level of stochasticity. Moreover, we show that the performance of algorithmic variants based on ad hoc approximations is strongly correlated with the absolute error of the approximation, and that the effect on local search of ad hoc approximations can be very degrading.Finally, we briefly address another SCOP belonging to the class of vehicle routing problems: the Vehicle Routing Problem with Stochastic Demands (VRPSD). For this problem, we have implemented and tested several metaheuristics, and we have studied the impact of integrating in them different ad hoc approximations., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

The goal of the research activities presented in this thesis is the design of intelligent behaviours for a complex robotic system, which is composed of a swarm of autonomous units. Inspired by the organisational skills of social insects, we are particularly interested in the study of collective behaviours based on self-organisation.The problem of designing self-organising behaviours for a swarm of robots is tackled resorting to artificial evolution, which proceeds in a bottom-up direction by first defining the controllers at the individual level and then testing their effect at the collective level. In this way, it is possible to bypass the difficulties encountered in the decomposition of the global behaviour into individual ones, and the further encoding of the individual behaviours into the controllers' rules. In the experiments presented in this thesis, we show that this approach is viable, as it produces efficient individual controllers and robust self-organising behaviours. To the best of our knowledge, our experiments are the only example of evolved self-organising behaviours that are successfully tested on a physical robotic platform.Besides the engineering value, the evolution of self-organising behaviours for a swarm of robots also provides a mean for the understanding of those biological processes that were a fundamental source of inspiration in the first place. In this perspective, the experiments presented in this thesis can be considered an interesting instance of a synthetic approach to the study of collective intelligence and, more in general, of Cognitive Science., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

La synthèse d'images, qui consiste à développer des algorithmes pour générer des images à l'aide d'un ordinateur, est devenue incontournable dans de nombreuses disciplines. Les méthodes d'affichage interactives permettent à l'utilisateur d'explorer des environnements virtuels en réalisant l'affichage des images à une cadence suffisamment élevée pour donner une impression de continuité et d'immersion. Malgré les progrès réalisés par le matériel, de nouveaux besoins supplantent toujours les capacités de traitement, et des techniques d'accélération sont nécessaires pour parvenir à maintenir une cadence d'affichage suffisante. Ce travail s'inscrit précisemment dans ce cadre. Il est consacré à la problématique de l'élimination efficace des objets masqués, en vue d'accélérer l'affichage de scènes complexes. Nous nous sommes plus particulièrement intéressé aux méthodes de précalcul, qui effectuent les calculs coûteux de visibilité durant une phase de prétraitement et les réutilisent lors de la phase de navigation interactive. Les méthodes permettant un précalcul complet et exact sont encore hors de portée à l'heure actuelle, c'est pourquoi des techniques approchées leur sont préférée en pratique. Nous proposons trois méthodes de ce type.La première, présentée dans le chapitre 4, est un algorithme permettant de déterminer de manière exacte si deux polygones convexes sont mutuellement visibles, lorsque des écrans sont placés entre eux. Nos contributions principales ont été de simplifier cette requête, tant du point de vue théorique que du point de vue de l'implémentation, ainsi que d'accélérer son temps moyen d'exécution à l'aide d'un ensemble de techniques d'optimisation. Il en résulte un algorithme considérablement plus simple à mettre en oeuvre que les algorithmes exacts existant dans la littérature. Nous montrons qu'il est également beaucoup plus efficace que ces derniers en termes de temps de calcul.La seconde méthode, présentée dans le chapitre 5, est une approche originale pour encoder l'information de visibilité, qui consiste à stocker l'ombre que générerait chaque objet de la scène s'il était remplacé par une source lumineuse. Nous présentons une analyse des avantages et des inconvénients de cette nouvelle représentation. Finalement, nous proposons dans le chapitre 6 une méthode de calcul de visibilité adaptée aux scènes d'intérieur. Dans ce type d'environnements, les graphes cellules-portails sont très répandus pour l'élimination des objets masqués, en raison de leur faible coût mémoire et de leur grande efficacité. Nous reformulons le problème de la génération de ces graphes en termes de segmentation d'images, et adaptons un algorithme classique, appelé «watershed», pour les obtenir de manière automatique. Nous montrons que la décomposition calculée de la sorte est proche de la décomposition classique, et qu'elle peut être utilisée pour l'élimination des objets masqués., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

With the emergence of the Internet and of the World Wide Web, the Web site has become a key communication channel in organizations. To satisfy the objectives of the Web site and of its target audience, adapting the Web site content to the users' expectations has become a major concern. In this context, Web usage mining, a relatively new research area, and Web analytics, a part of Web usage mining that has most emerged in the corporate world, offer many Web communication analysis techniques. These techniques include prediction of the user's behaviour within the site, comparison between expected and actual Web site usage, adjustment of the Web site with respect to the users' interests, and mining and analyzing Web usage data to discover interesting metrics and usage patterns. However, Web usage mining and Web analytics suffer from significant drawbacks when it comes to support the decision-making process at the higher levels in the organization.Indeed, according to organizations theory, the higher levels in the organizations need summarized and conceptual information to take fast, high-level, and effective decisions. For Web sites, these levels include the organization managers and the Web site chief editors. At these levels, the results produced by Web analytics tools are mostly useless. Indeed, most of these results target Web designers and Web developers. Summary reports like the number of visitors and the number of page views can be of some interest to the organization manager but these results are poor. Finally, page-group and directory hits give the Web site chief editor conceptual results, but these are limited by several problems like page synonymy (several pages contain the same topic), page polysemy (a page contains several topics), page temporality, and page volatility.Web usage mining research projects on their part have mostly left aside Web analytics and its limitations and have focused on other research paths. Examples of these paths are usage pattern analysis, personalization, system improvement, site structure modification, marketing business intelligence, and usage characterization. A potential contribution to Web analytics can be found in research about reverse clustering analysis, a technique based on self-organizing feature maps. This technique integrates Web usage mining and Web content mining in order to rank the Web site pages according to an original popularity score. However, the algorithm is not scalable and does not answer the page-polysemy, page-synonymy, page-temporality, and page-volatility problems. As a consequence, these approaches fail at delivering summarized and conceptual results. An interesting attempt to obtain such results has been the Information Scent algorithm, which produces a list of term vectors representing the visitors' needs. These vectors provide a semantic representation of the visitors' needs and can be easily interpreted. Unfortunately, the results suffer from term polysemy and term synonymy, are visit-centric rather than site-centric, and are not scalable to produce. Finally, according to a recent survey, no Web usage mining research project has proposed a satisfying solution to provide site-wide summarized and conceptual audience metrics. In this dissertation, we present our solution to answer the need for summarized and conceptual audience metrics in Web analytics. We first described several methods for mining the Web pages output by Web servers. These methods include content journaling, script parsing, server monitoring, network monitoring, and client-side mining. These techniques can be used alone or in combination to mine the Web pages output by any Web site. Then, the occurrences of taxonomy terms in these pages can be aggregated to provide concept-based audience metrics. To evaluate the results, we implement a prototype and run a number of test cases with real Web sites. According to the first experiments with our prototype and SQL Server OLAP Analysis Service, concept-based metrics prove extremely summarized and much more intuitive than page-based metrics. As a consequence, concept-based metrics can be exploited at higher levels in the organization. For example, organization managers can redefine the organization strategy according to the visitors' interests. Concept-based metrics also give an intuitive view of the messages delivered through the Web site and allow to adapt the Web site communication to the organization objectives. The Web site chief editor on his part can interpret the metrics to redefine the publishing orders and redefine the sub-editors' writing tasks. As decisions at higher levels in the organization should be more effective, concept-based metrics should significantly contribute to Web usage mining and Web analytics., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

Ce document porte sur l'extraction d'attributs géométriques présents sur les modèles 3D résultant de l'acquisition numérique de fragments archéologiques. Ces attributs sont ensuite exploités à des fins de classifications, de reconstructions et de remontages., Doctorat en sciences appliquées, info:eu-repo/semantics/published

A metaheuristic is a generic algorithmic template that, once properly instantiated, can be used for finding high quality solutions of combinatorial optimization problems.For obtaining a fully functioning algorithm, a metaheuristic needs to be configured: typically some modules need to be instantiated and some parameters need to be tuned. For the sake of precision, we use the expression parametric tuning for referring to the tuning of numerical parameters, either continuous or discrete but in any case ordinal. On the other hand, we use the expression structural tuning for referring to the problem of defining which modules should be included and, in general, to the problem of tuning parameters that are either boolean or categorical. Finally, with tuning we refer to the composite structural and parametric tuning.Tuning metaheuristics is a very sensitive issue both in practical applications and in academic studies. Nevertheless, a precise definition of the tuning problem is missing in the literature. In this thesis, we argue that the problem of tuning a metaheuristic can be profitably described and solved as a machine learning problem.Indeed, looking at the problem of tuning metaheuristics from a machine learning perspective, we are in the position of giving a formal statement of the tuning problem and to propose an algorithm, called F-Race, for tackling the problem itself. Moreover, always from this standpoint, we are able to highlight and discuss some catches and faults in the current research methodology in the metaheuristics field, and to propose some guidelines.The thesis contains experimental results on the use of F-Race and some examples of practical applications. Among others, we present a feasibility study carried out by the German-based software company SAP, that concerned the possible use of F-Race for tuning a commercial computer program for vehicle routing and scheduling problems. Moreover, we discuss the successful use of F-Race for tuning the best performing algorithm submitted to the International Timetabling Competition organized in 2003 by the Metaheuristics Network and sponsored by PATAT, the international series of conferences on the Practice and Theory of Automated Timetabling., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

In ant societies, and, more in general, in insect societies, the activities of the individuals, as well as of the society as a whole, are not regulated by any explicit form of centralized control. On the other hand, adaptive and robust behaviors transcending the behavioral repertoire of the single individual can be easily observed at society level. These complex global behaviors are the result of self-organizing dynamics driven by local interactions and communications among a number of relatively simple individuals.The simultaneous presence of these and other fascinating and unique characteristics have made ant societies an attractive and inspiring model for building new algorithms and new multi-agent systems. In the last decade, ant societies have been taken as a reference for an ever growing body of scientific work, mostly in the fields of robotics, operations research, and telecommunications.Among the different works inspired by ant colonies, the Ant Colony Optimization metaheuristic (ACO) is probably the most successful and popular one. The ACO metaheuristic is a multi-agent framework for combinatorial optimization whose main components are: a set of ant-like agents, the use of memory and of stochastic decisions, and strategies of collective and distributed learning.It finds its roots in the experimental observation of a specific foraging behavior of some ant colonies that, under appropriate conditions, are able to select the shortest path among few possible paths connecting their nest to a food site. The pheromone, a volatile chemical substance laid on the ground by the ants while walking and affecting in turn their moving decisions according to its local intensity, is the mediator of this behavior.All the elements playing an essential role in the ant colony foraging behavior were understood, thoroughly reverse-engineered and put to work to solve problems of combinatorial optimization by Marco Dorigo and his co-workers at the beginning of the 1990's.From that moment on it has been a flourishing of new combinatorial optimization algorithms designed after the first algorithms of Dorigo's et al. and of related scientific events.In 1999 the ACO metaheuristic was defined by Dorigo, Di Caro and Gambardella with the purpose of providing a common framework for describing and analyzing all these algorithms inspired by the same ant colony behavior and by the same common process of reverse-engineering of this behavior. Therefore, the ACO metaheuristic was defined a posteriori, as the result of a synthesis effort effectuated on the study of the characteristics of all these ant-inspired algorithms and on the abstraction of their common traits.The ACO's synthesis was also motivated by the usually good performance shown by the algorithms (e.g. for several important combinatorial problems like the quadratic assignment, vehicle routing and job shop scheduling, ACO implementations have outperformed state-of-the-art algorithms).The definition and study of the ACO metaheuristic is one of the two fundamental goals of the thesis. The other one, strictly related to this former one, consists in the design, implementation, and testing of ACO instances for problems of adaptive routing in telecommunication networks.This thesis is an in-depth journey through the ACO metaheuristic, during which we have (re)defined ACO and tried to get a clear understanding of its potentialities, limits, and relationships with other frameworks and with its biological background. The thesis takes into account all the developments that have followed the original 1999's definition, and provides a formal and comprehensive systematization of the subject, as well as an up-to-date and quite comprehensive review of current applications. We have also identified in dynamic problems in telecommunication networks the most appropriate domain of application for the ACO ideas. According to this understanding, in the most applicative part of the thesis we have focused on problems of adaptive routing in networks and we have developed and tested four new algorithms.Adopting an original point of view with respect to the way ACO was firstly defined (but maintaining full conceptual and terminological consistency), ACO is here defined and mainly discussed in the terms of sequential decision processes and Monte Carlo sampling and learning.More precisely, ACO is characterized as a policy search strategy aimed at learning the distributed parameters (called pheromone variables in accordance with the biological metaphor) of the stochastic decision policy which is used by so-called ant agents to generate solutions. Each ant represents in practice an independent sequential decision process aimed at constructing a possibly feasible solution for the optimization problem at hand by using only information local to the decision step.Ants are repeatedly and concurrently generated in order to sample the solution set according to the current policy. The outcomes of the generated solutions are used to partially evaluate the current policy, spot the most promising search areas, and update the policy parameters in order to possibly focus the search in those promising areas while keeping a satisfactory level of overall exploration.This way of looking at ACO has facilitated to disclose the strict relationships between ACO and other well-known frameworks, like dynamic programming, Markov and non-Markov decision processes, and reinforcement learning. In turn, this has favored reasoning on the general properties of ACO in terms of amount of complete state information which is used by the ACO's ants to take optimized decisions and to encode in pheromone variables memory of both the decisions that belonged to the sampled solutions and their quality.The ACO's biological context of inspiration is fully acknowledged in the thesis. We report with extensive discussions on the shortest path behaviors of ant colonies and on the identification and analysis of the few nonlinear dynamics that are at the very core of self-organized behaviors in both the ants and other societal organizations. We discuss these dynamics in the general framework of stigmergic modeling, based on asynchronous environment-mediated communication protocols, and (pheromone) variables priming coordinated responses of a number of ``cheap' and concurrent agents.The second half of the thesis is devoted to the study of the application of ACO to problems of online routing in telecommunication networks. This class of problems has been identified in the thesis as the most appropriate for the application of the multi-agent, distributed, and adaptive nature of the ACO architecture.Four novel ACO algorithms for problems of adaptive routing in telecommunication networks are throughly described. The four algorithms cover a wide spectrum of possible types of network: two of them deliver best-effort traffic in wired IP networks, one is intended for quality-of-service (QoS) traffic in ATM networks, and the fourth is for best-effort traffic in mobile ad hoc networks.The two algorithms for wired IP networks have been extensively tested by simulation studies and compared to state-of-the-art algorithms for a wide set of reference scenarios. The algorithm for mobile ad hoc networks is still under development, but quite extensive results and comparisons with a popular state-of-the-art algorithm are reported. No results are reported for the algorithm for QoS, which has not been fully tested. The observed experimental performance is excellent, especially for the case of wired IP networks: our algorithms always perform comparably or much better than the state-of-the-art competitors.In the thesis we try to understand the rationale behind the brilliant performance obtained and the good level of popularity reached by our algorithms. More in general, we discuss the reasons of the general efficacy of the ACO approach for network routing problems compared to the characteristics of more classical approaches. Moving further, we also informally define Ant Colony Routing (ACR), a multi-agent framework explicitly integrating learning components into the ACO's design in order to define a general and in a sense futuristic architecture for autonomic network control.Most of the material of the thesis comes from a re-elaboration of material co-authored and published in a number of books, journal papers, conference proceedings, and technical reports. The detailed list of references is provided in the Introduction., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

Les filtres non-linéaires de rang sont souvent utilisés dans le but de rehausser la qualité d'une image numérique. Leur application permet de faciliter l'interprétation visuelle et la compréhension du contenu des images que ce soit pour un opérateur humain ou pour un traitement automatique ultérieur. Dans le pipeline d'une chaîne habituelle de traitement des images, ces filtres sont appliqués généralement dans la phase de pré-traitement, juste après l'acquisition et avant le traitement et l'analyse d'image proprement dit.Les filtres de rang sont considérés comme un important goulot d'étranglement dans la chaîne de traitement, à cause du tri des pixels dans chaque voisinage, à effectuer pour tout pixel de l'image. Les temps de calcul augmentent de façon significative avec la taille de l'image à traiter, la taille du voisinage considéré et lorsque le rang approche la médiane.Cette thèse propose deux solutions à l'accélération du temps de traitement des filtres de rang.La première solution vise l'exploitation des différents niveaux de parallélisme des ordinateurs personnels d'aujourd'hui, notamment le parallélisme de données et le parallélisme inter-processeurs. Une telle approche présente un facteur d'accélération de l'ordre de 10 par rapport à une approche classique qui fait abstraction du matériel grâce aux compilateurs des langages évolués. Si le débit résultant des pixels traités, de l'ordre d'une dizaine de millions de pixels par seconde, permet de travailler en temps réel avec des applications vidéo, peu de temps reste pour d'autres traitements dans la chaîne.La deuxième solution proposée est basée sur le concept de calcul reconfigurable et réalisée à l'aide des circuits FPGA (Field Programmable Gate Array). Le système décrit combine les algorithmes de type bit-série et la haute densité des circuits FPGA actuels. Il en résulte un système de traitement hautement parallèle, impliquant des centaines d'unités de traitement par circuit FPGA et permet d'arriver à un facteur d'accélération supplémentaire de l'ordre de 10 par rapport à la première solution présentée. Un tel système, inséré entre une source d'image numérique et un système hôte, effectue le calcul des filtres de rang avec un débit de l'ordre de centaine de millions de pixels par seconde., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

Le développement de la Théorie du Calcul Quantique provient de l'idée qu'un ordinateur est avant tout un système physique, de sorte que ce sont les lois de la Nature elles-mêmes qui constituent une limite ultime sur ce qui peut être calculé ou non. L'intérêt pour cette discipline fut stimulé par la découverte par Peter Shor d'un algorithme quantique rapide pour factoriser un nombre, alors qu'actuellement un tel algorithme n'est pas connu en Théorie du Calcul Classique. Un autre résultat important fut la construction par Lov Grover d'un algorithme capable de retrouver un élément dans une base de donnée non-structurée avec un gain de complexité quadratique par rapport à tout algorithme classique. Alors que ces algorithmes quantiques sont exprimés dans le modèle ``standard' du Calcul Quantique, où le registre évolue de manière discrète dans le temps sous l'application successive de portes quantiques, un nouveau type d'algorithme a été récemment introduit, où le registre évolue continûment dans le temps sous l'action d'un Hamiltonien. Ainsi, l'idée à la base du Calcul Quantique Adiabatique, proposée par Edward Farhi et ses collaborateurs, est d'utiliser un outil traditionnel de la Mécanique Quantique, à savoir le Théorème Adiabatique, pour concevoir des algorithmes quantiques où le registre évolue sous l'influence d'un Hamiltonien variant très lentement, assurant une évolution adiabatique du système. Dans cette thèse, nous montrons tout d'abord comment reproduire le gain quadratique de l'algorithme de Grover au moyen d'un algorithme quantique adiabatique. Ensuite, nous montrons qu'il est possible de traduire ce nouvel algorithme adiabatique, ainsi qu'un autre algorithme de recherche à évolution Hamiltonienne, dans le formalisme des circuits quantiques, de sorte que l'on obtient ainsi trois algorithmes quantiques de recherche très proches dans leur principe. Par la suite, nous utilisons ces résultats pour construire un algorithme adiabatique pour résoudre des problèmes avec structure, utilisant une technique, dite de ``nesting', développée auparavant dans le cadre d'algorithmes quantiques de type circuit. Enfin, nous analysons la résistance au bruit de ces algorithmes adiabatiques, en introduisant un modèle de bruit utilisant la théorie des matrices aléatoires et en étudiant son effet par la théorie des perturbations., Doctorat en sciences appliquées, info:eu-repo/semantics/published

Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization.* A survey of metaheuristics. Chapter 1 gives an extensive overview on the nowadays most important metaheuristics. This overview points out the importance of two important concepts in metaheuristics: intensification and diversification. * The hyper-cube framework. Chapter 2 introduces a new framework for implementing ACO algorithms. This framework brings two main benefits to ACO researchers. First, from the point of view of the theoretician: we prove that Ant System (the first ACO algorithm to be proposed in the literature) in the hyper-cube framework generates solutions whose expected quality monotonically increases with the number of algorithm iterations when applied to unconstrained problems. Second, from the point of view of the experimental researcher, we show through examples that the implementation of ACO algorithms in the hyper-cube framework increases their robustness and makes the handling of the pheromone values easier.* Deception. In the first part of Chapter 3 we formally define the notions of first and second order deception in ant colony optimization. Hereby, first order deception corresponds to deception as defined in the field of evolutionary computation and is therefore a bias introduced by the problem (instance) to be solved. Second order deception is an ACO-specific phenomenon. It describes the observation that the quality of the solutions generated by ACO algorithms may decrease over time in certain settings. In the second part of Chapter 3 we propose different ways of avoiding second order deception.* ACO for the KCT problem. In Chapter 4 we outline an ACO algorithm for the edge-weighted k-cardinality tree (KCT) problem. This algorithm is implemented in the hyper-cube framework and uses a pheromone model that was determined to be well-working in Chapter 3. Together with the evolutionary computation and the tabu search approaches that we develop in Chapter 4, this ACO algorithm belongs to the current state-of-the-art algorithms for the KCT problem.* ACO for the GSS problem. Chapter 5 describes a new ACO algorithm for the group shop scheduling (GSS) problem, which is a general shop scheduling problem that includes among others the well-known job shop scheduling (JSS) and the open shop scheduling (OSS) problems. This ACO algorithm, which is implemented in the hyper-cube framework and which uses a new pheromone model that was experimentally tested in Chapter 3, is currently the best ACO algorithm for the JSS as well as the OSS problem. In particular when applied to OSS problem instances, this algorithm obtains excellent results, improving the best known solution for several OSS benchmark instances. A final contribution of this thesis is the development of a general method for the solution of combinatorial optimization problems which we refer to as Beam-ACO. This method is a hybrid between ACO and a tree search technique known as beam search. We show that Beam-ACO is currently a state-of-the-art method for the application to the existing open shop scheduling (OSS) problem instances., Doctorat en sciences appliquées, info:eu-repo/semantics/nonPublished

We look at robotic systems made of separate discrete components that, by self-assembling, can organize into physical structures of growing size. We review 22 such systems, exhibiting components ranging from passive mechanical parts to mobilerobots. We present a taxonomy of the systems, and discuss their design and function. We then focus on a particular system, the swarm-bot. In swarm-bot, the components that assemble are self-propelled modules that are fully autonomous in power, perception, computation, and action. We examine the additional capabilities and functions self-assembly can offer an autonomous group of modules for the accomplishment of a concrete task: the transport of an object. The design of controllers is accomplished in simulation usingtechniques from biologically-inspired computing. We show that self-assembly can offer adaptive value to groups that compete in an artificial evolution based on their fitness in task performance. Moreover, we investigate mechanisms that facilitate the design of self-assembling systems. The controllers are transferred to the physical swarm-bot system, and the capabilities of self-assembly and object transport are extensively evaluated in a range of different environments. Additionally, the controller for self-assembly is transferred and evaluated on a different robotic system, a super-mechano colony. Given the breadth and quality of the results obtained, we can say that the swarm-bot qualifies as the current state of the art in self-assembling robots. Our work supplies some initial evidence (in form of simulations and experiments with the swarm-bot) that self-assembly can offer robotic systems additional capabilities and functions useful for the accomplishment of concrete tasks., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished