Decentralized multi-tasks distribution in heterogeneous robot teams by means of ant colony optimization and learning automata

This paper focuses on the general problem of coordinating multiple robots. More specifically, it addresses the self-election of heterogeneous specialized tasks by autonomous robots. In this paper we focus on a specifically distributed or decentralized approach as we are particularly interested on decentralized solution where the robots themselves autonomously and in an individual manner, are responsible of selecting a particular task so that all the existing tasks are optimally distributed and executed. In this regard, we have established an experimental scenario to solve the corresponding multi-tasks distribution problem and we propose a solution using two different approaches by applying Ant Colony Optimization-based deterministic algorithms as well as Learning Automata-based probabilistic algorithms. We have evaluated the robustness of the algorithm, perturbing the number of pending loads to simulate the robot’s error in estimating the real number of pending tasks and also the dynamic generation of loads through time. The paper ends with a critical discussion of experimental results.

Automatic design of Ant Colony Optimization for permutation problems

In this study, we present a framework based on ant colony optimization (ACO) for tackling combinatorial problems. ACO algorithms have been applied to many diferent problems, focusing on algorithmic variants that obtain high-quality solutions. Usually, the implementations are re-done for various problem even if they maintain the same details of the ACO algorithm. However, our goal is to generate a sustainable framework for applications on permutation problems. We concentrate on understanding the behavior of pheromone trails and specific methods that can be combined. Eventually, we will propose an automatic offline configuration tool to build an efective algorithm. ---RESUMEN---En este trabajo vamos a presentar un framework basado en la familia de algoritmos ant colony optimization (ACO), los cuales están dise~nados para enfrentarse a problemas combinacionales. Los algoritmos ACO han sido aplicados a diversos problemas, centrándose los investigadores en diversas variantes que obtienen buenas soluciones. Normalmente, las implementaciones se tienen que rehacer, inclusos si se mantienen los mismos detalles para los algoritmos ACO. Sin embargo, nuestro objetivo es generar un framework sostenible para aplicaciones sobre problemas de permutaciones. Nos centraremos en comprender el comportamiento de la sendas de feromonas y ciertos métodos con los que pueden ser combinados. Finalmente, propondremos una herramienta para la configuraron automática offline para construir algoritmos eficientes.

An Ant Colony System adaptation to deal with accessibility issues after a disaster

One of the main problems relief teams face after a natural or man-made disaster is how to plan rural road repair work tasks to take maximum advantage of the limited available financial and human resources. Previous research focused on speeding up repair work or on selecting the location of health centers to minimize transport times for injured citizens. In spite of the good results, this research does not take into account another key factor: survivor accessibility to resources. In this paper we account for the accessibility issue, that is, we maximize the number of survivors that reach the nearest regional center (cities where economic and social activity is concentrated) in a minimum time by planning which rural roads should be repaired given the available financial and human resources. This is a combinatorial problem since the number of connections between cities and regional centers grows exponentially with the problem size, and exact methods are no good for achieving an optimum solution. In order to solve the problem we propose using an Ant Colony System adaptation, which is based on ants? foraging behavior. Ants stochastically build minimal paths to regional centers and decide if damaged roads are repaired on the basis of pheromone levels, accessibility heuristic information and the available budget. The proposed algorithm is illustrated by means of an example regarding the 2010 Haiti earthquake, and its performance is compared with another metaheuristic, GRASP.

Multi-objective ant colony optimization for requirements selection

The selection of a set of requirements between all the requirements previously defined by customers is an important process, repeated at the beginning of each development step when an incremental or agile software development approach is adopted. The set of selected requirements will be developed during the actual iteration. This selection problem can be reformulated as a search problem, allowing its treatment with metaheuristic optimization techniques. This paper studies how to apply Ant Colony Optimization algorithms to select requirements. First, we describe this problem formally extending an earlier version of the problem, and introduce a method based on Ant Colony System to find a variety of efficient solutions. The performance achieved by the Ant Colony System is compared with that of Greedy Randomized Adaptive Search Procedure and Non-dominated Sorting Genetic Algorithm, by means of computational experiments carried out on two instances of the problem constructed from data provided by the experts.

Social and temporal organization in an ant colony

Ant colonies are known for their complex and efficient social organization that com-pletely lacks hierarchical structure. However, due to methodological difficulties in follow¬ing all ants of a colony, it was until now impossible to investigate the social and temporal organization of colonies. We developed a tracking system that allows tracking the posi¬tions and orientations of several hundred individually labeled ants continuously, providing for the first time quantitative long term data on all individuals of a colony. These data permit reconstructing trajectories, activity patterns and social networks of all ants in a colony and enable us to investigate ant behavior quantitatively in previously unpreceded ways. By analyzing the spatial positions and social interactions of all ants in six colonies for 41 days we show that ant colonies are organized in groups of nurses, nest patrollers and foragers. Workers of each group were highly interconnected and occupied similar spa¬tial locations in the nest. Groups strongly segregated spatially, and were characterized by unique behavioral signatures. Nurses spent most of their time on the brood. Nest patrollers frequently visited the rubbish pile, and foragers frequently visited the forag¬ing arena. In addition nurses were on average younger than nest patrollers who were, in turn, younger than foragers. We further show that workers had a preferred behav¬ioral trajectory and moved from nursing to nest patrolling, and from nest patrolling to foraging. By analyzing the activity patterns of all ants we show that only a third of all workers in a colony exhibit circadian rhythms and that these rhythms shortened by on av¬erage 42 minutes in constant darkness, thereby demonstrating the presence of a functional endogenous clock. Most rhythmic workers were foragers suggesting that rhythmicity is tightly associated with task. Nurses and nest patrollers were arrhythmic which most likely reflects plasticity of the circadian clock, as isolated workers in many species exhibit circadian rhythmicity. Altogether our results emphasize that ant colonies, despite their chaotic appearance, repose on a strong underlying social and temporal organization. - Les colonies de fourmis sont connues pour leur organisation sociale complexe et effi-cace, charactérisée par un manque absolu de structure hiérarchique. Cependant, puisqu'il est techniquement très difficile de suivre toutes les fourmis d'une colonie, il a été jusqu'à maintenant impossible d'étudier l'organisation sociale et temporelle des colonies de four-mis. Nous avons développé un système qui permet d'extraire en temps réel à partir d'images vidéo les positions et orientations de plusieurs centaines de fourmis marquées individuellement. Nous avons pu ainsi générer pour la première fois des données quanti-tatives et longitudinales relatives à des fourmis appartenant à une colonie. Ces données nous ont permis de reconstruire la trajectoire et l'activité de chaque fourmi ainsi que ses réseaux sociaux. Ceci nous a permis d'étudier de manière exhaustive et objective le com-portement de tous les individus d'une colonie. En analysant les données spatiales et les interactions sociales de toutes les fourmis de six colonies qui ont été filmées pendant 41 jours, nous montrons que les fourmis d'une même colonie se répartissent en trois groupes: nourrices, patrouilleuses et approvisionneuses. Les fourmis d'un même groupe interagis-sent fréquemment et occupent le même espace à l'intérieur du nid. L'espace propre à un groupe se recoupe très peu avec celui des autres. Chaque groupe est caractérisé par un comportement typique. Les nourrices s'affairent surtout autour du couvain. Les pa-trouilleuses font de fréquents déplacements vers le tas d'ordures, et les approvisionneuses sortent souvent du nid. Les nourrices sont en moyenne plus jeunes que les patrouilleuses qui, à leur tour, sont plus jeunes que les approvisionneuses. De plus, nous montrons que les ouvrières changent de tâche au cours de leur vie, passant de nourrice à patrouilleuse puis à approvisionneuse. En analysant l'activité de chaque fourmi, nous montrons que seulement un tiers des ouvrières d'une colonie présente des rythmes circadiens et que ces rythmes diminuent en moyenne de 42 minutes lorsqu'il y a obscurité constante, ce qui démontre ainsi la présence d'une horloge endogène. De plus, la plupart des approvi¬sionneuses ont une activité rythmique alors que les nourrices et patrouilleuses présentent une activité arythmique, ce qui suggère que la rythmicité est étroitement associée à la tâche. L'arythmie des nourrices et patrouilleuses repose probablement sur une plasticité de l'horloge endogène car des ouvrières de nombreuses espèces font preuve d'une ryth¬micité circadienne lorsqu'elles sont isolées de la colonie. Dans l'ensemble nos résultats révèlent qu'une colonie de fourmis se fonde sur une solide organisation sociale et tem¬porelle malgré son apparence chaotique.

Algoritmos de alinhamento múltiplo e técnicas de otimização para esses algoritmos utilizando Ant Colony

Pós-graduação em Ciência da Computação - IBILCE

Sequenzierung mit Ant-Colony-Systemen am Beispiel Querverteil-Wagen

Dieser Beitrag zeigt die Anwendung des Ant-Colony-System (ACS) Algorithmus auf die Sequenzierung von Querverteil-Wagen in einem Lager. Wir erweitern den Basisalgorithmus der Ant-Colony-Optimierung (ACO) für die Minimierung der Bearbeitungszeit einer Menge von Fahraufträgen für die Querverteil-Wagen. Im Vergleich zu dem Greedy-Algorithmus ist der ACO-Algorithmus wettbewerbsfähig und schnell. In vielen Lagerverwaltungssystemen werden die Fahraufträge nach dem FIFO-Prinzip (First-in-First-out) ausgeführt. In diesem Beitrag wird der ACO-Algorithmus genutzt, um eine optimale Sequenz der Fahraufträge zu bilden.

Response threshold models, stochastic learning automata and ant colony optimization-based decentralized self-coordination algorithms for heterogeneous multi-tasks distribution in multi-robot systems

In recent decades, there has been an increasing interest in systems comprised of several autonomous mobile robots, and as a result, there has been a substantial amount of development in the eld of Articial Intelligence, especially in Robotics. There are several studies in the literature by some researchers from the scientic community that focus on the creation of intelligent machines and devices capable to imitate the functions and movements of living beings. Multi-Robot Systems (MRS) can often deal with tasks that are dicult, if not impossible, to be accomplished by a single robot. In the context of MRS, one of the main challenges is the need to control, coordinate and synchronize the operation of multiple robots to perform a specic task. This requires the development of new strategies and methods which allow us to obtain the desired system behavior in a formal and concise way. This PhD thesis aims to study the coordination of multi-robot systems, in particular, addresses the problem of the distribution of heterogeneous multi-tasks. The main interest in these systems is to understand how from simple rules inspired by the division of labor in social insects, a group of robots can perform tasks in an organized and coordinated way. We are mainly interested on truly distributed or decentralized solutions in which the robots themselves, autonomously and in an individual manner, select a particular task so that all tasks are optimally distributed. In general, to perform the multi-tasks distribution among a team of robots, they have to synchronize their actions and exchange information. Under this approach we can speak of multi-tasks selection instead of multi-tasks assignment, which means, that the agents or robots select the tasks instead of being assigned a task by a central controller. The key element in these algorithms is the estimation ix of the stimuli and the adaptive update of the thresholds. This means that each robot performs this estimate locally depending on the load or the number of pending tasks to be performed. In addition, it is very interesting the evaluation of the results in function in each approach, comparing the results obtained by the introducing noise in the number of pending loads, with the purpose of simulate the robot's error in estimating the real number of pending tasks. The main contribution of this thesis can be found in the approach based on self-organization and division of labor in social insects. An experimental scenario for the coordination problem among multiple robots, the robustness of the approaches and the generation of dynamic tasks have been presented and discussed. The particular issues studied are: Threshold models: It presents the experiments conducted to test the response threshold model with the objective to analyze the system performance index, for the problem of the distribution of heterogeneous multitasks in multi-robot systems; also has been introduced additive noise in the number of pending loads and has been generated dynamic tasks over time. Learning automata methods: It describes the experiments to test the learning automata-based probabilistic algorithms. The approach was tested to evaluate the system performance index with additive noise and with dynamic tasks generation for the same problem of the distribution of heterogeneous multi-tasks in multi-robot systems. Ant colony optimization: The goal of the experiments presented is to test the ant colony optimization-based deterministic algorithms, to achieve the distribution of heterogeneous multi-tasks in multi-robot systems. In the experiments performed, the system performance index is evaluated by introducing additive noise and dynamic tasks generation over time.

Ant Colony Optimization for Requirement selection in Incremental Software development

This proposal shows that ACO systems can be applied to problems of requirements selection in software incremental development, with the idea of obtaining better results of those produced by expert judgment alone. The evaluation of the ACO systems should be done through a compared analysis with greedy and simulated annealing algorithms, performing experiments with some problems instances

'A Bayesian Optimisation Algorithm for the Nurse Scheduling Problem'

Abstract- A Bayesian optimization algorithm for the nurse scheduling problem is presented, which involves choosing a suitable scheduling rule from a set for each nurse's assignment. Unlike our previous work that used GAs to implement implicit learning, the learning in the proposed algorithm is explicit, i.e. eventually, we will be able to identify and mix building blocks directly. The Bayesian optimization algorithm is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated by using the corresponding conditional probabilities, until all variables have been generated, i.e. in our case, a new rule string has been obtained. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed approach might be suitable for other scheduling problems.

'Artificial Immune Systems: A new Decision Making Paradigm for Operational Research'

Over the last few years, more and more heuristic decision making techniques have been inspired by nature, e.g. evolutionary algorithms, ant colony optimisation and simulated annealing. More recently, a novel computational intelligence technique inspired by immunology has emerged, called Artificial Immune Systems (AIS). This immune system inspired technique has already been useful in solving some computational problems. In this keynote, we will very briefly describe the immune system metaphors that are relevant to AIS. We will then give some illustrative real-world problems suitable for AIS use and show a step-by-step algorithm walkthrough. A comparison of AIS to other well-known algorithms and areas for future work will round this keynote off. It should be noted that as AIS is still a young and evolving field, there is not yet a fixed algorithm template and hence actual implementations might differ somewhat from the examples given here