Swarm Intelligence Intelligence En Essaim

Swarm Intelligence By : abdou OUGHLIS CHAPITRE1 Les techniques d’optimisation inspirées de l'intelligence en essaim sont devenues de plus en plus populaire au cours de la dernière décennie. Ils sont caractérisés par un mode de fonctionnement décentralisé qui imite le comportement des essaims d'insectes sociaux, les troupeaux d'oiseaux, les écoles de poissons. L'avantage de ces approches par rapport aux techniques traditionnelles est leurs robustesses et flexibilités. Ces propriétés en font le succès de l'intelligence en essaim paradigme pour la conception des algorithmes de plus en plus face à des problèmes complexes. Dans ce chapitre, nous nous concentrons sur deux des exemples les plus réussis de l'optimisation des techniques inspirées de l'intelligence en essaim: Optimisation en essaim de la particule et Optimisation de la colonie de fourmis. Swarm Intelligence (SI), qui est une discipline de l’intelligence artificielle (AI), est la conception intelligente de systèmes multi-agents en prenant l'inspiration de comportement collectif des insectes sociaux comme les fourmis, les termites, les abeilles et les guêpes, ainsi que d'autres animaux tels que les sociétés des troupeaux d'oiseaux ou les écoles de poissons. Les colonies d'insectes sociaux ont fasciné les chercheurs depuis de nombreuses années, et les mécanismes qui régissent leur comportement sont restés inconnu pendant longtemps. Même si les membres de ces colonies ne sont pas des individus sophistiqués, ils sont en mesure de réaliser des tâches complexes en matière de coopération. Ce comportement Coordonné ressort des actions relativement simples ou interactions entre les membres individuels des colonies. De nombreux aspects des activités collectives des insectes sociaux sont auto-organisés en travaillant sans un centre de contrôle. Par exemple, les fourmis apportent les morceaux de feuilles à leur nid. Les fourmis ouvrières construisent des chaînes de leur corps afin de franchir les écarts entre deux feuilles. Les bords des deux feuilles sont ensuite rassemblés et successivement connectés par des fils de soie qui est émis par une larve mûre tenue par un ouvrier. Un autre exemple concerne le recrutement d'autres membres de la colonie pour la recherche de proies (voir, par exemple, Fig. 1).

1er janvier 2009

1. Introduction

Swarm Intelligence

D'autres exemples comprennent les capacités de termites et les guêpes sophistiqués pour construire des nids, ou la capacité des abeilles et des fourmis pour s'orienter dans leur environnement. Le terme « intelligence en essaim » a été utilisé pour la première fois par Beni dans le cadre de systèmes robotiques cellulaires où de simples agents s’organisent par le biais d'interaction avec le plus proche voisin. Pendant ce temps, le terme intelligence en essaim est utilisé pour un champ de recherche beaucoup plus large. Les méthodes de l'intelligence en essaim ont été très fructueuses dans le domaine de l'optimisation, qui est d'une grande importance pour l'industrie et la science. Ce chapitre vise à donner une introduction à l'intelligence en essaim et des méthodes d'optimisation. Les Problèmes d'optimisation sont de grande importance tant pour le monde industriel ainsi que pour le monde scientifique. Exemples de problèmes pratiques d'optimisation : les horaires de train, optimisation de la forme, la conception de réseaux de télécommunications, et les problèmes de biologie computationnelle. La communauté des chercheurs a simplifié beaucoup de ces problèmes afin d'obtenir des cas de tests scientifiques, tels que le célèbre problème des voyageurs de commerces (TSP). Le TSP modélise la situation d'un voyageur de commerce qui nécessite de passer à travers un certain nombre de villes. L'objectif du voyageur de commerce est de traverser ces villes (la visite de chaque ville exactement une fois), de sorte que le total des voyages à distance est minime. Un autre exemple est le problème du repliement des protéines, qui est l'un des problèmes les plus difficiles en biologie

1er janvier 2009

Fig. 1. Coopération des fourmis pour rapporter une lourde proie.

Swarm Intelligence computationnelle, de la biologie moléculaire, biochimie et physique. Il consiste à trouver la forme ou la conformation fonctionnelle d'une protéine dans deux ou trois dimensions, par exemple, dans le cadre simplifié de modèle lattice tels que le modèle d'hydrophobie polaires.

2. Comportement biologique collectif Le comportement en essaim peut être vu dans les troupeaux d'oiseaux, écoles de poissons, ainsi que dans les insectes comme les moustiques et les moucherons. De nombreux groupes d'animaux tels que les écoles de poissons et les troupeaux d'oiseaux exposent clairement un ordre structurel, avec un comportement d’organismes intégrés de façon qu’elles puissent changer de forme et de direction, ils semblent se déplacer comme une seule entité cohérente. Les grands principes du comportement collectif, tel que présenté dans la Figure 2 sont les suivants:

Fig. 2.1 Les grands principes du comportement collectif.

1er janvier 2009

• Homogénéité: chaque oiseau dans la volée a le même modèle de comportement. Le troupeau se déplace sans chef de file, même si temporairement des dirigeants semblent apparaître. • Région: le mouvement de chaque oiseau est seulement influencé par ses plus proches camarades de troupeau. La vision est considérée comme le sens le plus important pour l’organisation du troupeau. • Actions d’éviter les collisions : éviter la collision avec les compagnons à proximité. • Vélocité d'équivalence: essayer de trouver des correspondances de Vélocité avec les compagnons à proximité. • Centrage du troupeau: tenter de rester près du troupeau le plus proche.

Swarm Intelligence

Les individus tentent de maintenir une distance minimale entre eux et les autres à tout moment. Cette règle a la priorité la plus élevée et correspond à un comportement souvent observé chez les animaux dans la nature. Si ces individus ne performent pas une manœuvre d'éviter les collisions, ils ont tendance à être attirés vers d'autres individus (pour éviter d'être isolé), et s’alignent avec les voisins. COUZIN a identifié quatre comportements dynamiques collectifs comme illustré dans la figure 2.1:

1er janvier 2009

• essaim: une totale cohésion, mais un faible niveau de polarisation (alignement parallèle) entre les membres • Tore: les individus sont en rotation perpétuelle autour d'une base vide (broyage). Le sens de rotation est aléatoire. • Dynamique parallèle de groupe: les individus sont polarisés et passes comme un groupe cohérent, mais ils peuvent circuler dans l'ensemble du groupe dont la densité et la forme peut fluctuer. • Groupe hautement harmonisé: beaucoup plus statique en termes d'échange de positions au sein du groupe que le groupe parallèle dynamique et la variation de la densité et la forme sont minimales. A un haut niveau, un essaim peut être considéré comme un groupe d'agents qui coopèrent en vue de réaliser certains comportement et objectifs déterminés (voir Figure 2.3). Cette intelligence collective semble se dégager de ce qui est souvent des groupes larges qui sont relativement des simples agents.

Swarm Intelligence

Ces agents utilisent des règles simples pour régir leurs actions et par les interactions de l'ensemble du groupe, l'essaim atteint ses objectifs. Un type d'auto-organisation ressort d’une collection d’actions du groupe. Un agent autonome est un sous-système qui interagit avec son environnement, qui contient probablement d'autres agents, mais agit de façon relativement indépendante de tous les autres agents. L'agent autonome ne suit pas les commandes à partir d'un chef de file, ou de certain plan global. Par exemple, un oiseau pour participer à un troupeau, il règle seulement ses mouvements pour assurer la coordination avec les mouvements de son troupeau, généralement ses voisins qui sont proches de lui. Un oiseau dans un troupeau tente simplement de rester proche de ses voisins, mais en évitant les collisions avec eux. Chaque oiseau ne prend pas les commandes d’un chef d'oiseaux car ce dernier n'existe pas. Le comportement en essaim contribue à tirer les oiseaux de plusieurs choses, y compris la protection contre les prédateurs (surtout pour les oiseaux au milieu du troupeau), et la recherche de nourriture.

1er janvier 2009

Fig. 2.2. Plusieurs modèles de comportement collectif: (a) essaim (b) tore (c) dynamique de groupe parallèle et (d) des groupes parallèles.

Swarm Intelligence

Fig. 2.3. Le système simple d'un essaim.

2.1 Les essaims et la Vie Artificielle Depuis 1990, plusieurs comportement collectif (comme les insectes sociaux, les troupeaux d’oiseaux) inspiré des algorithmes ont été proposés. Les domaines d'application de ces algorithmes se référer bien à l'étude des problèmes d'optimisation comme les problèmes difficiles tel que (les problèmes de voyages, les problèmes Affectation quadratique, problèmes graphiques, réseau de routage, le regroupement et l’extraction des données, la planification d'emploi… etc.) (PSO) et Optimisation de la colonie des fourmis (ACO) sont actuellement les plus populaires des algorithmes dans le domaine de l'intelligence en essaim.

Les recherches sur les comportements collectifs des insectes sociaux fournissent aux informaticiens des méthodes puissantes pour la conception d'algorithmes d'optimisation. Les chercheurs informaticiens ont pu transformer des modèles du comportement collectif des insectes sociaux en méthodes utiles pour l'optimisation et le contrôle. Un nouveau domaine de recherche a vu le jour qui a pour objet de transformer la connaissance que les éthologistes en ont sur les capacités collectives de résolution de problèmes chez les insectes sociaux en techniques artificielles de résolution de problèmes : c'est l'intelligence en essaim. Parmi les techniques de l'intelligence en essaim, certaines sont arrivées à maturité. Les algorithmes de contrôle et d'optimisation inspirés de modèles de recherche collective de nourriture chez les fourmis en particulier, ont connu un succès inattendu et portent le nom "d'optimisation par colonie de fourmis".

1er janvier 2009

2.2 Optimisation de la colonie de fourmis (ACO) 2.2.1 Introduction

Swarm Intelligence Dans ce travail de recherche nous allons présenter une vision de l’état de l’art des algorithmes de colonies de fourmis. Nous commençons d’abord par expliquer l’origine biologique de ces algorithmes. Nous présentons en suite le cadre ACO (optimisation par colonie de fourmis), Puis les diverses variantes algorithmiques sont présentées au travers de leur application au problème du voyageur de commerce. L’avant dernière section présenter quelque applications des algorithmes d’optimisation par colonies de fourmis, et décrit le cas des problèmes dynamiques de routage dans les réseaux, puis montre le principe général de l’algorithme AntNet : la solution ACO pour ce type de problèmes. Enfin la dernière section, nous présentons d’autres algorithmes, autre le cadre ACO, inspirés des comportements collectif des fourmis.

2.2.2 Inspiration biologique Les algorithmes de colonies de fourmis sont nés à la suite d’une constatation faite par des biologistes : les insectes sociaux en général, et les fourmis en particulier, sont capables de résoudre collectivement des problèmes complexes, comme trouver le chemin le plus court entre une source de nourriture et leur nid, bien que celles-ci ont individuellement des capacités cognitives limitées. Dans cette section, on présente un certain nombre d'observations faites à travers des expériences avec de vraies fourmis et termites.

2.2.2.1 La théorie de stigmergie

 La stigmergie est une forme indirecte et non symbolique de communication, passant par le biais de modification de l’environnement, ainsi on peut utiliser le terme « interaction sociale indirecte » [Dreo, 03] pour décrire le même phénomène.  L’information stigmergique a une portée locale, seuls les insectes visitant l’endroit où elle a été communiquée (ou son voisinage immédiat) peuvent en avoir accès.

1er janvier 2009

Un des premiers chercheurs étudiant le comportement social des insectes était l'entomologiste français Pierre-Paul Grassé. Entre les années 40 et 50, il observait le comportement des termites, en particulier chez les espèces Bellicositermes natalensis et les Cubitermes. Il a découvert [Grassé, 44] qu’en construisant une termitière, ces insectes commencent leur activité par déposer les boulettes de boue mais de façon très aléatoire, et sans aucune coordination. Cependant, une fois ces boulettes ramassées atteignent une certaine densité dans un espace limité, elles deviennent un stimulus significatif [Grassé, 46] qui motivera de plus en plus de termites à déposer ce matériau de sorte que les piliers et les voûtes, et par la suite le nid entier, soient construits. Grassé a employé le terme stigmergie [Grassé, 59] pour décrire ce type particulier de communication indirecte dans lequel “La coordination des tâches et la régulation des constructions ne dépendent pas directement des ouvriers, mais des constructions elle-même. L'ouvrier ne dirige pas son travail, il est guidé par lui”1. Les deux caractéristiques principales [Dorigo, 06] de stigmergie qui le différencient d'autres formes de communication sont les suivantes.

Swarm Intelligence Des exemples de stigmergie peuvent être observés dans les colonies de fourmis. Chez certaines espèces de fourmis, pour chercher la nourriture, au départ un grand nombre de fourmis se déplacent à l'extérieur du nid, plus ou moins au hasard. Tout au long de leur chemin, elles déposent une légère trace d’une substance chimique appelée la phéromone. Si l'une d'entre elles découvre une ressource quelconque, elle retourne au nid en déposant une trace beaucoup plus intense (cette intensité dépend éventuellement de la richesse de la ressource) [Rennard, 03]. D'autres fourmis perçoivent la présence de phéromone et ont tendance à suivre des chemins où la concentration de phéromone est plus haute. Par ce mécanisme, les fourmis sont capables de transporter la nourriture à leur nid d'une manière remarquablement efficace. [Dorigo, 06]

Fig. 1- Des fourmis suivent une piste de phéromone [Dreo, 03]

2.2.2.2 Les expériences du pont à double branche

1er janvier 2009

Deneubourg et Goss [Goss, 90][Goss, 89] ont observé qu’une colonie de fourmis1 ayant le choix entre deux chemins d’inégale longueur menant à une source de nourriture avait tendance à utiliser le chemin le plus court. Ils ont aboutit à cette observation en ont effectuant une série d'expériences dans lesquelles ils ont changé le rapport entre la longueur des deux branches d’un pont qui relie un nid de fourmis avec une source de nourriture. Ce résultat peut être expliqué comme suit [Dorigo, 02].

Swarm Intelligence

Fig. 2 - Expérience du pont à double branche [Dorigo, 99]. (a) Les fourmis commence à explorer le double pont(b) Par la suite la plupart des fourmis choisissent le plus court chemin. (c) Distribution du pourcentage des fourmis qui ont choisi le chemin plus court. D’après Goss et autres.

1er janvier 2009

Au début de l’expérience, il n'y a aucune trace de phéromone sur les deux branches. Par conséquent, les fourmis n'ont pas une préférence et elles choisissent avec la même probabilité l'unes des de deux branches. Cependant, parce qu'une branche est plus courte que l'autre, les fourmis choisissant la branche courte sont les premières qui atteindre la nourriture et par la suite commencent leur voyage de nouveau vert le nid. Et par conséquent la plus courte branche, dans le même temps, sera parcourue par plus de fourmis que la longue piste, donc la phéromone commence à s'accumuler plus rapidement sur la branche courte qui sera par la suite de plus en plus attractive et donc choisie par la grande majorité des fourmis. Tandis que la phéromone dans la longue branche commence à s’évaporer.

Swarm Intelligence

Fig. 3 - Comment les vraies fourmis trouvent le chemin le plus court [Dorigo, 97]. A) Les fourmis arrivent à unpoint de décision. B) Quelques fourmis choisissent le chemin supérieur et d’autres choisissent le chemin inférieurLe choix est aléatoire. C) Puisque les fourmis se déplacent approximativement avec une vitesse constante, les fourmis qui choisissent la courte branche (l’inferieure), atteignent le point de décision opposé plus rapidemenque celles qui choisissent la longue branche (la supérieure). D) Le phéromone s'accumule à un taux plus élevésur le chemin le plus court. (Le nombre de lignes représente approximativement la quantité de phéromone déposée par des fourmis).

2.2.2.3 L’auto-organisation et la rétroaction Le mécanisme permettant de résoudre un problème trop complexe pour être abordé par des fourmis seules est un bon exemple de système auto-organisé. Ce système repose sur des rétroactions positives : le dépôt de phéromone attire d’autres fourmis qui vont la renforcer à leur tour, et des rétroactions négatives : la disparition de la piste par évaporation empêche le système de s'emballer. Théoriquement, si la quantité de phéromone restait identique au cours du temps sur toutes les branches, aucune piste ne serait choisie. Or, du fait des rétroactions, une faible variation sur une branche va être amplifiée et permettre alors le choix d’une branche.

Les fourmis résolvent des problèmes complexes par des mécanismes assez simples à modéliser. Il est ainsi assez simple de simuler leur comportement par des algorithmes. Dans cette section nous allons monter comment les chercheur ont exploité le comportement des vraies fourmis (décrit dans la section précédente), pour développer des algorithmes d’optimisation.

1er janvier 2009

2.2.3 Optimisation par colonie de fourmis 2.2.3.1 Définition et historique

Swarm Intelligence Le modèle proposé par Deneubourg et ses collègues pour expliquer le comportement des fourmis était la source principale d'inspiration [Dorigo, 06] pour le développement des algorithmes de colonie de fourmi : Le double pont a été substitué par un graphe et les trace de phéromone par des traces de phéromone artificielle. Ces algorithmes constituent une famille de métaheuristiques pour résoudre des problèmes d’optimisation difficile. Cette méta-heuristique est relativement récente. Elle a été introduite pour la première fois dans la thèse de doctorat du chercheur italien Marco Dorigo [Dorigo, 92] pour résoudre le problème du Voyageur de commerce. Elle s’est popularisée, puis a été l’objet d’améliorations dès 1995 et a été appliquée avec succès à d’autres problèmes d’optimisation combinatoire dès 1994.

Fig4 Chronologie des algorithmes de colonies de fourmis

La métaheuristique ACO peut être définie comme la combinaison d’une méthode de construction et d’un mécanisme d’apprentissage fondé sur la mémorisation d’informations et la communication de ces informations au sein d’une population. On peut donc voir ACO comme un processus : ❏ Distribué car basé sur une population de fourmis parcourant un graphe ; ❏ Utilisant une forme indirecte de mémorisation car chaque fourmi modifie des pistes de phéromones sur le graphe selon son expérience passée, c’est-à-dire selon la qualité des solutions trouvées (par exemple, la longueur du chemin parcouru) ;

1er janvier 2009

En anglais, le terme consacré à cette classe d’algorithme est « Ant Colony Optimization » (ACO). Il existe cependant plusieurs familles de méthodes s'inspirant du comportement des fourmis. En français, ces différentes approches sont regroupées sous les termes : algorithmes de colonies de fourmis, optimisation par colonies de fourmis, fourmis artificielles, ou diverses combinaisons de ces variantes.

Swarm Intelligence ❏ Stochastique et constructif car chaque fourmi construit son chemin en choisissant la prochaine étape selon une probabilité déterminée par des pistes de phéromones laissées sur le graphe et représentant l’expérience passée des fourmis. Ainsi, la structure d’un algorithme ACO est la suivante : 1. Construire la solution ; 2. Mettre à jour les pistes de phéromones ; 3. Optionnel : exécuter des actions centralisées (daemon actions) telles que le lancement d’une procédure d’amélioration locale des solutions trouvées par les fourmis. Dans ACO, les fourmis agissent indépendamment et de manière concurrente, de plus en raison de la simplicité de chaque fourmi, les solutions ne peuvent émerger que des interactions entre chacune d’entre elles. Nous allons tout d’abord exposer les différences et les points communs entre les fourmis virtuelles et les fourmis réelles [Dorigo, 07] [Dorigo, 96] [Dorigo, 02], avant d’exposer les différents algorithmes.

2.2.3.2 Similarités et différences avec les fourmis réelles Les fourmis virtuelles ont une double nature. D’une part, elles modélisent les comportements abstraits de fourmis réelles, comme nous l’avons signalé précédemment, et d’autre part, elles peuvent être enrichies par des capacités que ne possèdent pas les fourmis réelles, afin de les rendre plus efficaces que ces dernières. Nous allons maintenant présenter une synthèse [Costanzo, 06] de ces ressemblances et différences.

2.2.3.2.1 Points communs Colonie d’individus coopérants. Comme pour les fourmis réelles, une colonie virtuelle est composée d’une population des individus qui travaillent ensemble pour réaliser un certain but. Une colonie est un ensemble d’entités simples, indépendants, asynchrones qui se coopèrent pour trouver une bonne solution au problème considéré.

Évaporation des phéromones. La méta-heuristique ACO comprend aussi la possibilité d’évaporation des phéromones. Ce mécanisme permet d’oublier lentement ce qui s’est passé avant. C’est ainsi qu’elle peut diriger sa recherche vers de nouvelles directions, sans être trop contrainte par ses anciennes décisions. Recherche du plus petit chemin. Les fourmis réelles et virtuelles partagent un but commun : recherche du plus court chemin reliant un point de départ (le nid) à des sites de destination (la nourriture).

1er janvier 2009

Communication stigmergique. La communication stigmergique se produit par l'intermédiaire de la phéromone. Cette forme de communication joue un grand rôle dans le comportement des fourmis : son rôle principal est de changer la manière dont l’environnement est perçu par les fourmis, en fonction de l’historique laissé par ces phéromones.

Swarm Intelligence Déplacement local. Les vraies fourmis ne sautent pas des cases, tout comme les fourmis virtuelles. Elles se contentent de se déplacer entre sites adjacents du terrain. Choix aléatoire au départ des transitions. Lorsqu’elles sont sur un site, les fourmis réelles et virtuelles doivent décider sur quel site adjacent doivent se déplacer. Au départ cette décision se fait au hasard car aucune information local (la phéromone) n’est disponible.

2.2.3.2.2 Différences Les fourmis virtuelles possèdent certaines caractéristiques que ne possèdent pas les fourmis réelles : Elles vivent dans un monde non-continu. Leurs déplacements consistent en des transitions d’état. Mémoire (état interne) de la fourmi. Les fourmis virtuelles mémorisent l’historique de leurs actions. Elles peuvent aussi retenir des données supplémentaires sur leurs performances. Les critères du choix d’un chemin à suivre. La probabilité pour qu’une fourmi artificielle choisisse un chemin ne dépend généralement pas uniquement des traces de phéromone, mais aussi de l’heuristique dépendante du problème permettant d’évaluer localement la qualité du chemin. Le type de problème. Dans le cas de vraies fourmis, le problème est de trouver la nourriture, alors que dans le cas des fourmis artificielles, il s’agit de trouver une bonne solution à un problème donné d'optimisation.

Qualité de la solution. Les fourmis virtuelles déposent une quantité de phéromone proportionnelle à la qualité de la solution qu’elles ont découverte. (Un comportement semblable est observé également dans quelques vraies espèces de fourmis dans lesquelles la quantité de phéromone déposée de est proportionnel à la qualité de la source de nourriture trouvée [Beckers, 93]). Retard dans le dépôt de phéromone. Les fourmis virtuelles peuvent mettre à jour les pistes de phéromones de façon non immédiate : souvent elles attendent d’avoir terminé la construction de leur solution. Ce choix dépend du problème considéré bien évidemment. Autre capacités. En plus des capacités citées ci-dessus, les fourmis artificielles peuvent en avoir d’autres selon le problème traité. Voici des exemples.

1er janvier 2009

Nature des phéromones déposées. Les fourmis réelles déposent une substance physique de phéromone sur la piste qu’elles parcourent. Cependant la phéromone virtuelle n’est qu’un ensemble de variables d’états associées au problème. Ainsi, le dépôt/l’évaporation des phéromones est une simple incrémentation/décrémentation de la valeur des variables d’états à chaque itération.

Swarm Intelligence ❏ L’anticipation : la fourmi étudie les états suivants pour faire son choix et non seulement l’état local. ❏ Le retour en arrière : une fourmi peut revenir à un état déjà parcouru car la décision qu’elle avait prise à cet état a été mauvaise.

2.2.3.3 Algorithmes Les algorithmes de colonies de fourmis sont pour l’essentiel appliqués à des problèmes combinatoires, notamment du type du voyageur de commerce. Cependant, devant le succès rencontré par ces algorithmes, d’autres pistes commencent à être explorées : par exemple, l’utilisation de ces algorithmes dans des problèmes continus [Dreo, 04] et/ou dynamiques [DiCaro, 98], ou encore l’exploitation de ce type d’algorithmes dans un cadre d’intelligence en essaim [Bonabeau, 99] et avec d’autres métaheuristiques.

2.2.3.3.1 Ant system Historique [Dorigo, 02] Ant system est le premier algorithme de colonies de fourmis proposé dans la littérature. En fait, ant system à l'origine est l’ensemble de trois algorithmes appelés ant-cycle, ant-density, et ant-quantity. Ces trois algorithmes ont été proposés en 1992 dans la dissertation doctorale de Marco Dorigo [Dorigo, 92] et d'abord apparus dans le rapport technique [Maniezzo, 91] [Dorigo, 91] qu’il a été publié quelques années après dans « IEEE Transactions on Systems, Man, and Cybernetics »[Dorigo, 96]. Une autre publication est [Colorni, 92]. Dans les algorithmes ant-density et ant-quantity les fourmis mettaient à jour la phéromone directement après un déplacement d'une ville à une autre adjacente, Tandis que dans le ant-cycle la phéromone est déposé à la fin de la tournée, et sa quantité dépond de la qualité du chemin. Puisque ant-cycle est plus performant que les deux autres variantes, plus tard on l’a nommé simplement ant system. Le problème du voyageur de commerce (TSP1) est un problème d'optimisation combinatoire N-difficile qui a attiré une énorme quantité d'effort de recherches. Le TSP est un problème très important également dans le contexte de l'optimisation de colonie de fourmi parce que c'est le problème auquel l'original ant system (AS) a été appliqué la première fois [Dorigo, 91] [Dorigo, 92], 38], et plus tard celui-ci a été souvent employé comme repère pour examiner de nouvelles idées et variantes algorithmiques.

1er janvier 2009

Ant system et le problème du voyageur de commerce

Swarm Intelligence

Fig. 5 - L’algorithme « Ant System » optimisant le problème du voyageur de commerce : 1) une fourmi choisi un trajet, et trace une piste de phéromone. 2) l’ensemble des fourmis parcourt un certain nombre de trajets, chaque fourmi déposant une quantité de phéromone proportionnelle à la qualité du parcours. 3) chaque arête du meilleur chemin est plus renforcée que les autres. 4) l’évaporation fait disparaître les mauvaises solutions.

Le problème du voyageur de commerce (TSP) consiste à trouver le chemin le plus court qui permet de visiter un certain nombre de villes une seule fois puis de revenir à la ville de départ. La modélisation du TSP repose sur un graphe G = (N, A), où N représente un ensemble de noeuds (les villes) et A représente l’ensemble des arcs connectant les noeuds. A chaque arc (i, j) est associé un poids dij égal à la distance entre les villes i et j. Dans l’algorithme du Ant System (AS), à chaque itération1, chaque fourmi parcourt le graphe et construit un trajet complet de n étapes. Pour chaque fourmi, le trajet entre une ville i et une ville j dépend de :

La règle de déplacement appelée “règle aléatoire de transition proportionnelle” contrôle l’importance relative de l’intensité de la piste et de la visibilité, est écrite mathématiquement sous la forme suivante :

(4.1) Où a et b sont deux paramètres contrôlant l’importance relative de l’intensité de la piste, tij(t), et de la visibilité, ηij. Avec a = 0, seule la visibilité de la ville est prise en compte; la ville la plus proche est donc choisie à chaque pas. Au contraire, avec b= 0, seules les pistes de phéromone jouent. Pour éviter une

1er janvier 2009

1. la liste des villes déjà visitées, qui définit les mouvements possibles à chaque pas, quand la fourmi k est sur la ville i : Jik, 2. l’inverse de la distance entre les villes : ηij = 1/dij , appelé visibilité. Cette information statique est utilisée pour diriger le choix des fourmis vers des villes proches, 3. la quantité de phéromone déposée sur l’arête reliant les deux villes, appelée l’intensité de la piste. Ce paramètre définit l’attractivité d’une partie du trajet global et change à chaque passage d’une fourmi. C’est, en quelque sorte, une mémoire globale du système, qui évolue par apprentissage.

Swarm Intelligence sélection trop rapide d’un trajet, un compromis entre ces deux paramètres, jouant sur les comportements de diversification et d’intensification (voir Glossaire), est nécessaire. Après un tour complet, chaque fourmi laisse une certaine quantité de phéromones Dζijk(t) sur l’ensemble de son parcours, quantité qui dépend de la qualité de la solution trouvée : (4.2) Où Tk(t) est le trajet effectué par la fourmi k â l’itération t, Lk(t) la longueur du tour et Q un paramètre fixé. L’algorithme ne serait pas complet sans le processus d’évaporation des pistes de phéromone. En effet, pour éviter d’être piégé dans des solutions sousoptimales, il est nécessaire de permettre au système “d’oublier” les mauvaises solutions. À la fin de l'itération, on a la somme des phéromones qui ne se sont pas évaporées et de celles qui viennent d'être déposées. La règle de mise à jour des pistes est donc : (4.3) Où m est le nombre de fourmis utilisées pour l’itération t et ρ un paramètre de réglage. La quantité initiale de phéromone sur les arêtes est une distribution uniforme d’une petite quantité t0 r 0.

Fig. 6 - Algorithme de base de colonies de fourmis : le “Ant System” [Dreo, 03]

1er janvier 2009

La figure 6 présente un pseudo-code de l’algorithme AS pour optimisé le problème du voyageur de commerce.

Swarm Intelligence

Comparaison avec d’autres algorithmes

2.2.3.3.2 Principales variantes

Ainsi, différentes améliorations ont été apportées à l’algorithme initial, donnant naissance à différentes variantes de Ant System, dont les plus performantes sont ACS (Ant Colony System) [Dorigo, 97] et MMAS (MAX – MIN Ant System) [Stützle, 00] qui obtiennent en pratique des résultats vraiment compétitifs, parfois meilleurs que les approches les plus performantes.

Ant Colony System (ACS) Une autre amélioration de AS est le Ant Colony System (ACS), introduit par Gambardella et Dorigo [Gambardella, 96][Dorigo, 97]. Les contributions les plus intéressantes d'ACS sont : [Dorigo, 04]

1er janvier 2009

Malgré des premiers résultats encourageants, montrant que les performances de Ant System sont comparables à celles d’autres approches « généralistes » comme les algorithmes génétiques, l’algorithme Ant System n’est pas compétitif avec des approches spécialisées, développées spécialement pour le problème du voyageur de commerce.

Swarm Intelligence ❏ La règle utilisée lors de la construction de la solution est inspirée de l’apprentissage par renforcement. ❏ L’introduction d’un mécanisme de mise à jour locale des pistes de phéromones : dès qu’un arc est emprunté par une fourmi, il voit sa quantité de phéromones diminuer. ❏ Il est possible d’utiliser, au cours de la construction du chemin, des listes des noeuds voisins les plus prometteurs (une liste des plus proches villes voisines) : cette liste de candidats permet de réduire le temps de calcul.

Le MAX – MIN Ant System (MMAS) Le système de fourmi de MAX-MIN Ant System est une amélioration de l'idée originale de AS idée. MMAS a été proposé par StÄutzle et Hoos [Stützle, 00], qui ont présenté un certain nombre de changements dont les plus importants sont les suivants : [Dorigo, 07], [Costanzo, 06] ❏ Seulement la meilleure fourmi peut mettre à jour la quantité de phéromone, ❏ Les valeurs des phéromones sur chaque arc sont bornées par tmin et tmax ❏ Les valeurs des phéromones sur chaque arc sont initialisées à la valeur maximum tmax, ❏ La quantité de phéromones que l’on fait évaporer est proportionnelle à sa valeur au moment de la modification, plus les pistes sont fortes plus ses phéromones seront diminués. L’intérêt de ces améliorations est : [Costanzo, 06] ❏ Empêcher la monopolisation de certains arcs qui ont été tellement imprégnés au début du processus de recherche qu’ils sont systématiquement parcourus par les fourmis. ❏ Permettre, grâce à cette façon de gérer l’évaporation, de tirer vers le bas les arcs chargés fortement en phéromones afin de vérifier si leur importance est pertinente. De ce fait si ce n’est pas le cas, les pistes plus faiblement chargés pourront leur prendre le pas.

Dans un chapitre du livre [Dorigo, 04], les auteurs montrent la puissance des algorithmes d’optimisation par colonies de fourmis dans le cas des problèmes de routage dans des réseaux de type Internet. Dans cette section nous allons présenter une brève description du problème de routage, et en suite l’algorithme AntNet : la solution ACO pour ce type de problèmes.

2.2.4.1.1 Description du problème La particularité des problèmes de routage dans les réseaux provient de leur nature dynamique. En effet, les données et les paramètres varient continuellement avec le temps, parfois sur des durées très courtes. La problématique est la suivante : lorsqu’une communication est établie entre deux noeuds d’un réseau, le message est découpé en plusieurs paquets de

1er janvier 2009

2.2.4 Application de ACO 2.2.4.1 ACO pour les problèmes de routage dans les réseaux

Swarm Intelligence données qui vont circuler dans le réseau. Ce réseau est constitué de voies de transmission (les arcs), dont les débits varient au cours du temps, et de routeurs (les noeuds). Les routeurs ont pour fonction de diriger les paquets de données vers un routeur jusqu’à ce qu’ils atteignent leur destination. De plus, chaque routeur doit tenir compte de la quantité d’information circulant sur les arcs auxquels il est relié afin d’éviter l’engorgement des arcs. Ainsi, des paquets de données issus du même message peuvent emprunter des chemins complètement différents.

2.2.4.1.2 L’algorithme AntNet La nature distribuée et souple de la méthode ACO semblant adaptée à ce type de problèmes, l’algorithme AntNet développé par Di caro et Dorigo [DiCaro, 97] [DiCaro, 98] a été conçu pour résoudre les problèmes de routage dans les réseaux.

Principe Dans cet algorithme, le graphe de construction des solutions est identifié au réseau. De plus, contrairement aux algorithmes ACO vus précédemment, les fourmis se déplacent de manière asynchrone. Ainsi, le principe de AntNet est de faire circuler, en parallèle avec les paquets de données, des fourmis qui analysent en temps-réel l’état des voies de transmission et qui fournissent ensuite ces états aux routeurs. Les fourmis calculent le temps qu’elles mettent pour aller d’un noeud à un autre puis déposent une trace de phéromones sur la voie empruntée en respectant la règle suivante : plus le temps nécessaire pour parcourir la voie est court, plus la quantité de phéromones déposée est grande. Une fois arrivé à un routeur, un paquet de données sera orienté avec la probabilité la plus importante sur la voie présentant la piste de phéromones la plus intense. L’algorithme d’AntNet est très proche de ceux utilisé pour le TSP, les routeurs pouvant être associés aux villes, ceci dit il y a quelques différences notables : ❏ Il n’y a aucune contrainte sur les villes à visiter, c’est-à-dire qu’une fourmi n’est pas obligé de visiter tous les noeuds. ❏Il y a une piste de phéromone différente pour chaque noeud de destination. ❏la dimension temporelle du problème rend plus délicate son évaluation. En situation de charge peu importante, les résultats obtenus par AntNet sont comparables à ceux des algorithmes de l’état de l’art. Dans des situations de charge importante, proches de la saturation ou en cas de saturation temporaire, les résultats obtenus par AntNet sont supérieurs à ceux des autres algorithmes de routage lorsque l’on prend en compte le retard moyen subi par les paquets de données.

1er janvier 2009

Comparaison avec d’autres algorithmes

Swarm Intelligence

Fig. 8 - Résultat typique d'une comparaison entre AntNet, un algorithme de routage par colonie de fourmis, avec d'autres algorithmes de routage répandus pour la commutation de paquets. Daemon est une approximation d'un algorithme idéal et offre une borne à la meilleure performance possible. Le réseau est simulé en condition de fotrafic avec des caractéristiques de trafic stochastiques. Au temps t = 400, on simule un accroissement soudain du trafic qui dure 120 secondes et amène le réseau à saturation. Le graphe du haut compare le flux du réseau pour les différents algorithmes, tandis que le graphe du bas compare les retards moyens des messages sur une fenêtre de 5s. AntNet offre le même flux de paquets que les meilleurs algorithmes tout en maintenant un retard moyen bien inférieur à tous les autres algorithmes de routage. [Cnrs, 00] Cet algorithme a été testé sur l’opérateur téléphonique japonais NTT, ainsi que sur le réseau de la Fondation Nationale Américaine des Sciences : il a montré des résultats plus que prometteurs. Les algorithmes de colonies de fourmis sont beaucoup étudiés depuis quelques années et il serait trop long de faire ici une liste exhaustive de toutes les applications et variantes qui ont été produites. Dans les deux principaux champs d’application (problèmes NP-difficiles et problèmes dynamiques), certains algorithmes ont cependant donné de très bons résultats. On peut notamment retenir des performances particulièrement intéressantes dans le cas de l’affectation quadratique [Stüzle et al. 00], de problêmes de planification [Merkle et al. 00], de l’ordonnancement séquentiel [Gambardella et al. 00], du routage de véhicule [Garnbardella et al. 99b], ou du routage sur réseau [DiCaro, 98] (voir aussi pour cette application la section 3.1.2). Il existe une littérature importante sur toutes sortes de : problèmes voyageur de commerce, coloriage de graphes, affectation de fréquence, affectation généralisée, sac à dos multi-dimensionnel, satisfaction de contraintes, etc.

1er janvier 2009

2.2.4.2 Autres problèmes combinatoires

Swarm Intelligence 2.2.5 Autres algorithmes inspirés du comportement des fourmis [Dorigo] Autre le cadre ACO, il existe d’autres algorithmes inspirés des comportements collectifs des fourmis.

2.2.5.1 Tri et classification Le tri de la couvée est une activité qui peut être observée dans beaucoup d'espèces de fourmi (par exemple, dans fourmis de Pheidole pallidula [Deneubourg, 91]). Ces fourmis groupent de manière compacte leurs oeufs et les plus petites larves au centre du secteur de couvée de nid et les larves plus grandes à la périphérie de ce groupement de couvée. Deneubourg et autres. [Deneubourg, 91] ont proposé un modèle de ce phénomène dans lequel une fourmi prend et laisse tomber un article selon le nombre d'articles environnants semblables. Les règles élémentaires suivantes est une brève description du modèle de Deneubourg : � Une fourmi reconnaît toujours les objets immédiatement en face d’elle � Si un objet est situé près d’autres objets, la probabilité que la fourmi le ramasse est faible ; sinon la probabilité est grande � Si une fourmi transportant un objet voit des objets similaires à proximité, elle a tendance à lâcher l’objet. �Il n’existe aucune communication directe entre les fourmis ! � On observe néanmoins un comportement émergent :

Ce modèle peut servir dans des applications en robotique. Dans les colonies de fourmis, chaque ouvrier a sa spécialité [Robinson, 92]. Cependant, les fourmis peuvent adapter leur comportement selon les circonstances : par exemple une fourmi de soldat peut devenir une chercheuse de nourriture. Cette combinaison de spécialisation et de flexibilité est un dispositif souhaitable pour l'optimisation et la commande multi-agent, particulièrement dans les problèmes d'allocation de ressource qui exigent l'adaptation continue aux conditions changeantes. Beaucoup d'approches inspirées de la division de travail dans les vraies colonies de fourmis sont basées sur un modèle de seuil développé par Robinson [Robinson, 92], dans

1er janvier 2009

2.2.5.2 La division du travail

Swarm Intelligence

lequel les ouvriers avec de bas seuils de réponse répondent aux faibles degrés des stimulus que les ouvriers avec les seuils de réponse élevés. Un tel modèle de réponse-seuil a été appliqué au problème de choisir une cabine de peinture pour des camions sortant d'une chaîne de montage dans une usine de camion [Bonabeau, 99], [Campos, 00] - [Nouyan, 05].

2.2.5.3 Le transport coopératif Une fourmi peut recruter d’autres fourmis afin de déplacer et de rapporter au nid des nourritures volumineuses. Ce comportement de colonies de fourmi a aussi inspiré la recherche dans la robotique, en particulier pour la conception d'algorithmes de contrôle distribués pour les groupes de robots [Martinoli, 97]. Un exemple d'une tâche qui a été utilisée comme un point de référence pour des algorithmes de fourmi appliqués aux problèmes de robotique distribués est la boîte coopérative poussant [Kubei, 94]. Un autre exemple d'application des algorithmes de fourmi est celui au problème relatif de tirer un objet. Ceci a été réalisé [Trianni, 04] dans le projet Swarm-bots (www.swarmbots. org), un projet consacré à l'étude des algorithmes de fourmis pour des applications autonomes de robotique.

2.2.6 Conclusion Les algorithmes de type ACO comptent parmi les plus performants pour résoudre certains problèmes combinatoires NP-difficiles. De plus, il existe une littérature abondante sur l’application de la métaheuristique ACO à ce genre de problèmes. Enfin, des propriétés de convergence ont pu être prouvées pour certaines variantes. On trouve même des applications industrielles (ordonnancement de chaînes de montage, tournées de flottes de véhicules) réalisées par des sociétés telles que EuroBios, AntOptima ou BiosGroup. Quant aux tendances actuelles de la recherche, elles se dirigent selon quatre grands axes : • l’application à des problèmes dynamiques, dont les caractéristiques changent avec le temps (par exemple, pour le routage dans les réseaux, ou dans le cas du TSP pour lequel de nouvelles villes peuvent apparaître ou disparaître avec le temps) ;

• l’application à des problèmes multi-objectifs ; • la parallélisation des codes implémentant des algorithmes de type ACO afin de réduire les temps de calcul et de profiter de la nature distribuée de la méthode.

1er janvier 2009

• l’application à des problèmes stochastiques présentant une incertitude, un bruit sur les données, ou une approximation des variables ;

Swarm Intelligence

PSO est une population basée sur un algorithme de recherche et est initialisé avec une population des solutions aléatoires, appelés particules. Contrairement à l'évolution d'autres techniques de calcul, chaque particule dans PSO est également associée à une vélocité. Les particules volent dans l'espace de recherche avec les vélocités qui sont ajustées dynamiquement d'après leurs comportements historiques. Par conséquent, les particules ont tendance à voler vers le mieux et la meilleure zone de recherche au cours du processus de recherche. PSO a d'abord été conçu pour simuler la recherche de nourriture des oiseaux qui est défini comme un «vecteur champ». Supposons le scénario suivant: un groupe d'oiseaux est à la recherche aléatoire de nourritures dans une zone. Il n'y a qu'un seul morceau de nourriture dans ce domaine de recherche. Les oiseaux ne savent pas où est la nourriture. Mais ils savent à quel point elle se trouve et les places de leurs pairs. Alors, quelle est la meilleure stratégie pour trouver la nourriture ? Une stratégie efficace est de suivre l'oiseau qui est le plus proche de la nourriture. PSO apprend du scénario et s'en sert pour résoudre les problèmes d'optimisation. Dans PSO, chaque solution est unique comme un "oiseau" dans l'espace de recherche, qui est appelé «Particules». Toutes les particules ont des valeurs qui sont évaluées par la fonction de mise en forme à optimisé, et qui ont des vélocités qui dirigent le vol des particules. (Les particules volent à travers l'espace du problème, en suivant les particules avec les meilleures solutions à jour). PSO est initialisé avec un groupe aléatoire de particules (solutions) et puis cherche des optima de chaque génération en faisant la mise à jour. Chaque individu est traité comme un volume de moins de particules (un point) dans un espace de recherche D-dimensionnelle. La iem particule est représentée comme Xi = (xi1, xi2,..., Xid). À chaque génération, chaque particule est mis à jour par les deux «meilleurs» valeurs. Le premier est le meilleur emplacement (la position qui a donné la meilleure valeur de justesse) d'une particule obtenue à ce jour. Cette valeur est appelée pBest. Le pBest de la ième particule est représenté comme Pi = (pi1, pi2,..., PiD). À chaque itération, le vecteur P de la particule avec les meilleurs valeurs dans le voisinage, désignée l ou g, et le vecteur P de la particule courante est combiné pour ajuster la vélocité le long de chaque dimension, et cette vélocité est alors, utilisé pour calculer une nouvelle position de la particule. La portion d'ajustement de vélocité est influencée par la précédente meilleure position individuelle (P) et est considéré comme la composante de cognition, et la portion influencé par les meilleurs dans le voisinage est la composante sociale. Avec l'ajout de facteur d'inertie ω, selon Shi et Eberhart, ces équations sont les suivantes:

1er janvier 2009

CHAPITRE3 3. Optimisation en essaim de la particule (PSO)

Swarm Intelligence

vid = ω∗vid +η1 *rand () ∗ (pid −xid) +η2∗Rand () ∗ (pgd −xid) (1.1) xid = xid +vid

(1.2)

1er janvier 2009

Où rand () et Rand () sont deux nombres aléatoires générés de façon indépendante dans l’intervalle [0,1] et η1 et η2 sont deux facteurs d'apprentissage qui contrôlent l'influence des composants sociaux et cognitifs. En (1.1), si la somme sur le côté droit est supérieure à une valeur constante, alors la vitesse sur cette dimension est attribué à être ± Vmax. Donc, les vitesses des particules sont serrées dans la gamme [- Vmax, +Vmax] laquelle sert comme une contrainte pour contrôler la capacité d'exploration globale en essaim de la particule. Ainsi, la probabilité des particules en laissant l'espace de recherche est réduite. Notez que ce n'est pas de limiter les valeurs de Xi dans la gamme [-V max, +V max]; qu’elle limite la distance maximale d'une particule qui se déplace au cours d'une itération. L’algorithme principal tel que décrit par Pomeroy est donné ci-dessous:

/ * Mettre en place les particules / for each particle p do { for d = 1 to dimensions do { p.next[d] = random() p.velocity[d] = random(deltaMin, deltaMax) } p.bestSoFar = initialFitness } /* set particles’ neighbors */ for each particle p do { for n = 1 to numberOfNeighbors do { p.neighbor[n] =getNeighbor(p,n) } } /* run Particle Swarm Optimizer */ while iterations ≤ maxIterations do { /* Make the ”next locations” current and then*/ /* test their fitness. */ for each particle p do { for d = 1 to dimensions do { p.current[d] = p.next[d] } fitness = test(p) if fitness > p.bestSoFar then do { p.bestSoFar = fitness for d = 1 to dimensions do { p.best[d] = p.current[d] } } if fitness = targetFitness then do { ... /* e.g., write out solution and quit */ } } /* end of: for each particle p */ for each particle p do { n = getNeighborWithBestFitness(p) for d = 1 to dimensions do { iFactor = iWeight * random(iMin, iMax) sFactor = sWeight * random(sMin, sMax) pDelta[d] = p.best[d] - p.current[d] nDelta[d] = n.best[d] - p.current[d] delta = (iFactor * pDelta[d]) + (sFactor * nDelta[d]) delta = p.velocity[d] + delta p.velocity[d] = constrict(delta) p.next[d] = p.current[d] + p.velocity[d] } } /* end of: for each particle p */

1er janvier 2009

Swarm Intelligence

Swarm Intelligence

1er janvier 2009

} /* end of: while iterations ≤ maxIterations */ end /* end of main program */ /* Return neighbor n of particle p */ function getNeighbor(p, n) { ... return neighborParticle } /* Return particle in p’s neighborhood */ /* with the best fitness */ function getNeighborWithBestFitness(p) { ... return neighborParticle } /* Limit the change in a particle’s */ /* dimension value */ function constrict(delta) { if delta < deltaMin then return deltaMin else if delta > deltaMax then return deltaMax else return delta }

Swarm Intelligence

Fig. 1.4. La structure de base de PSO. Une représentation graphique d'un essaim gbest et lbest respectivement est décrite dans la Figure 1.5. Si on considère les voisinages sociaux et

1er janvier 2009

Le schéma de base d'algorithme PSO est présenté dans la figure 1.4. L'algorithme PSO peut être vu comme un ensemble de vecteurs dont les trajectoires oscillent autour d'une région défini par chaque meilleure position individuelle antérieure et la meilleure position de quelques autres individus. Il y a plusieurs topologies de voisinage pour identifier quelles particules de l'essaim peut influencer les individus. Les plus communs sont connus comme gbest et lbest: Dans l'essaim du gbest, la trajectoire de chaque individu (particule) est influencée par le meilleur individu trouvé dans l'essaim tout entier. Il est supposé que les essaims du gbest convergent rapidement, comme toutes les particules sont attirées simultanément à la meilleure partie de l'espace de recherche. Cependant, si l'optimum global n'est pas proche de la meilleure particule, ça peut être impossible pour l'essaim d’explorer d'autres régions et, par conséquent, l'essaim peut être piégé dans un optimum local. Dans l'essaim du lbest, chaque individu est influencé par un plus petit nombre de ses voisins (lesquels sont vus comme des membres adjacents d’une série d’essaim). Typiquement, il y’a deux voisins de lbest, un à côté droite et un sur le côté gauche (un treillis de la bague). Ce type d'essaim convergera plus lentement mais peut localiser l'optimum global avec une plus grande chance. L’essaim du lbest est capable de circuler autour d'optimum local.

Swarm Intelligence géographiques tels que présentés dans la figure1.6, puis les deux gbest et lbest peuvent être considérés comme des formes de voisinage social.

(a) gbest essaim Fig. 1.5. Représentation graphique de

(b) lbest essaim.

Fig. 1.6. Exemples de (a) voisinage géographique (b) voisinage social dans un essaim. • La quantité de regroupement: le regroupement se réfère aux voisins en commun avec d'autres individus. Ils existent plusieurs types de topologies essaim qui peuvent être utilisés selon le problème à résoudre. Kennedy et Mendes ont testé quelques topologies pyramides comme modèle, pour quelques problèmes d'optimisation des fonctions.

1er janvier 2009

Watts a introduit un petit modèle de réseau qui permet d’interpoler entre les ressources ordinaires de faible dimensions des réseaux aléatoire, par l'introduction d'une certaine quantité de hasard dans un premier temps régulières. Watts identifie deux facteurs qui influent sur l'échange d'informations entre les petits- réseaux des membres : • le degré de connectivité: le comportement de chaque individu sera influencé par le comportement de ses k voisins.

Swarm Intelligence

CHAPITRE 4 4. Essaim Robotique Essaim Robotique est une nouvelle approche pour la coordination d'un grand nombre de robots et est apparue comme l'application de l'intelligence en essaim de systèmes multi-robots. Différents des autres études de l'intelligence en essaim, essaim robotique met l'accent sur la réalisation physique des individus et des interactions réalistes entre eux et entre les individus et l'environnement. Dans ce chapitre, nous présentons un bref aperçu de cette nouvelle approche. Nous avons d'abord présenté sa définition, l'examen des principales motivations qui sous-tendent l'approche, ainsi que ses caractéristiques et les principaux mécanismes de coordination. Ensuite, nous présentons un bref aperçu des recherches en robotique en essaim autour de quatre axes, à savoir la conception, de modélisation et d'analyse, et en fin les robots et les problèmes. Essaim Robotique représente une nouvelle approche pour la coordination d'un grand nombre de robots dont la principale inspiration provient de l'observation des insectes sociaux. Ces insectes, comme les fourmis, les guêpes et les termites, sont appelés à coordonner leurs comportements à accomplir les tâches qui sont au-delà des capacités d'un seul individu, les fourmis peuvent transporter de grandes proies à leur nid, les termites peuvent construire de grands monticules de boue dans lequel un niveau désirée de température et d'humidité est maintenue [5]. L'émergence de ces comportements synchronisés au niveau du système est plutôt impressionnant pour des chercheurs travaillant sur les systèmes multi-robots, car il apparaît, malgré les individus sont relativement incapables, malgré le manque de coordination centralisée et, malgré la simplicité des interactions. Le terme intelligence en essaim a été initialement conçu comme un "buzz word" par Beni, dans les années 1980 pour désigner une classe de systèmes robotiques cellulaire [2]. Plus tard, le terme est passé à couvrir un large éventail d'études de l'optimisation pour les études des insectes sociaux, la perte de son contexte, la robotique dans l'intervalle. Récemment, le terme Essaim Robotique a commencé à être utilisé comme l'application de l'intelligence en essaim des systèmes incorporés physiquement.

4.2 Qu'est-ce que Essaim Robotique? Compte tenu de la pléthore de termes utilisés pour décrire les différentes approches utilisées dans les systèmes multi-robots, comme " la robotique distribuée " ou "la robotique collective," les caractéristiques de la robotique en essaim en provenance du reste de besoin d'être clarifiés. Cette préoccupation a été explicitement énoncée dans [10] et une définition est fournie de la manière suivante.

1er janvier 2009

4.1Introduction

Swarm Intelligence Définition 1 " Essaim Robotique est l'étude de la façon dont un grand nombre d’agents physiques relativement simples peuvent être conçus de telle sorte que le comportement collectif désiré émerge de l'interaction entre les agents et entre les agents et l'environnement».

4.2.1 Propriétés du niveau de système Le système de fonctionnement au niveau d'un système robotique en essaim devrait présenter trois propriétés fonctionnelles qui sont observés dans des essaims et de rester en tant que propriétés des systèmes multi-robots. • Robustesse. Le système robotique en essaim devrait être en mesure de fonctionner en dépit des perturbations de l'environnement ou du mauvais fonctionnement de ses individus. Un certain nombre de facteurs peuvent être observés dans les insectes sociaux derrière la robustesse de leur fonctionnement. Tout d'abord, les essaims sont en soi des systèmes redondants, la perte d'une personne peut être immédiatement compensée par un autre. Deuxièmement, la coordination est décentralisée et donc la destruction d'une partie de l'essaim est peu probable de mettre fin à son opération. Troisièmement, les individus qui composent l'essaim est relativement simple, ce qui les rend moins vulnérables à l'échec. Quatrièmement, la détection est distribuée, d'où le système est robuste contre les perturbations dans l'environnement. • Flexibilité. Les personnes d'un essaim devraient être en mesure de coordonner leurs comportements pour lutter contre les tâches de nature différentes. Par exemple, les individus dans une colonie de fourmis peuvent collectivement trouver le chemin le plus court pour une source de nourriture ou d'une grande proie grâce à l'utilisation de différentes stratégies de coordination. • Extensibilité. Les essaims devraient être en mesure de fonctionner dans un large éventail de tailles de groupe et de soutenir un grand nombre d'individus sans impact sur la performance. C'est à dire, les mécanismes de coordination et les stratégies à développer pour les systèmes de robotique en essaim devraient assurer le fonctionnement de l'essaim dans différentes tailles.

Nous allons maintenant résumer les principales caractéristiques de l'essaim de recherche en robotique (voir [9] pour une discussion). Tout d'abord, la recherche doit être pertinente pour la coordination d'un essaim de robots. C'est à dire, les personnes doivent avoir une incarnation physique, se situer, et d'être physiquement capable d'interagir avec leur environnement. En outre, les mécanismes de coordination devraient être étudiés en promettant d'être évolutive pour un large éventail de tailles d’essaim. Deuxièmement, le système robotique à l'étude devrait être assez

1er janvier 2009

4.2.2Caractéristiques

Swarm Intelligence homogène. C'est à dire, les individus qui composent l'essaim devraient être assez identiques, du moins au niveau des interactions. Coordination des stratégies élaborées pour des systèmes hétérogènes multi-robots, qui sont composées d'individus qui diffèrent dans leurs interactions en raison de leur physique ou leur incarnation de contrôle du comportement, en dehors de l'approche de la robotique en essaim. Troisièmement, les individus devraient être relativement simples. Le critère de la simplicité dans la définition ne se réfère pas directement à la complexité du matériel et des logiciels des robots, mais plutôt pour but de souligner les limites de leurs capacités individuelles par rapport à la tâche. Les membres du système de l'essaim devraient être relativement incapables ou inefficaces seul en l'égard de la tâche à accomplir. C'est, soit (i) la tâche devrait être difficile, voire impossible, d'être menées par un seul robot, et la coopération d'un groupe de robots devrait être indispensable, ou (ii) le déploiement d'un groupe de robots devrait améliorer les performances et la robustesse de la manipulation de la tâche. Quatrièmement, les individus devraient avoir les capacités d'interaction locale. Cette contrainte assure que la coordination entre les robots est distribuée, et qu'il est plus probable à l'échelle de la taille de l'essaim. Les mécanismes qui s'appuient sur les capacités d'interaction sont susceptibles d'être limitées par la bande passante.

Les études en systèmes physiques et biologiques ont révélé qu'il existe un certain nombre de mécanismes de coordination qui sont à l'œuvre dans les systèmes naturels qui peuvent servir de sources d'inspiration pour la coordination de l'essaim des systèmes robotiques. Deux des principaux mécanismes de coordination sont: l'auto-organisation et stigmergy. Auto-organisation, définie comme «un processus dans lequel les formes à l'échelle mondiale émergent uniquement de nombreuses interactions parmi les bas niveaux des composantes du système» [5], est commun dans les systèmes naturels. Les études d'auto-organisation dans les systèmes naturels montrent que l'interaction des commentaires positifs et négatifs des interactions locales entre les individus est indispensable [4]. Dans ces systèmes, une évaluation positive est généralement généré par des comportements auto-catalytiques, c’est le changement infligé dans le système essaim de l’environnement par l'exécution d'un comportement augmente le déclenchement de même comportement. Ce cycle de rétroaction positive est contrebalancé par un mécanisme de rétroaction négative, qui résulte généralement d'un «épuisement des ressources physiques» [4]. En plus de ces mécanismes, l'auto-organisation dépend également de l'existence aléatoire et multiple interaction au sein du système. Les études d'auto-organisation dans les systèmes naturels se développent souvent des modèles qui sont construits avec une simplification des

1er janvier 2009

4.2.3 Mécanismes de coordination

Swarm Intelligence interactions dans l'environnement et le résumé des mécanismes de comportement chez les individus. Les modèles d'auto- organisation sociaux des insectes et des animaux ont déjà été utilisés comme sources d'inspiration, car, en un sens, la robotique en essaim peut être considérée comme l'ingénierie et l'utilisation d’auto-organisations en physique incorporée dans les essaims. Stigmergy, définie comme la communication indirecte des individus à travers l'environnement, a été proposée par Grasse [13] pour expliquer les mécanismes de coordination derrière la construction de nids de termites. Stigmergic communication est commune à de nombreux insectes sociaux, les fourmis sont appelés à déposer des phéromones sur le terrain pour marquer les chemins de sources de nourriture et ces phéromones comme attirant à suivre par les fourmis. Stigmergy est intéressant pour la robotique en essaim, car il fournit un mécanisme de communication qui est local, distribué et évolutif.

4.3 Orientations de la recherche Au cours des 4-5 dernières années, l'intérêt pour la robotique en essaim a été à la hausse. L'intérêt croissant dans cette nouvelle approche est actuellement alimentée par les progrès de la mécatronique et d'autres technologies, telles que les MEMS, qui ont commencé à réduire la taille et le coût des robots pour la production de masse et ouvert la voie vers le déploiement à grande échelle des systèmes essaim robotiques dans des applications Realworld. Dans la discussion ci-dessous, nous allons donner un bref examen de la robotique en essaim d'études en quatre catégories, à savoir la conception, de modélisation et d'analyse, les problèmes des robots Le principal problème d'un système robotique en essaim peut être le suivant: Comment doit-on concevoir des personnes, tant en termes de réalisation physique, ainsi que leur comportement de contrôle, tel que souhaité apparaître le niveau d’essaim d'interaction entre les individus et entre les individus et l'environnement? Cet objectif, qui peut également être considéré comme le "génie de l'auto-organisation" dans les systèmes multi-robots, est une tâche qui est difficile, sinon impossible, à résoudre en termes généraux. Les études au sein de cette catégorie peuvent être regroupées en deux: adhoc et des approches principales. Dans les approches ad hoc, les comportements des différents robots sont conçus manuellement pour réaliser le comportement désiré au niveau d’essaim. Dans cette approche, en général, mais pas toujours, les comportements des insectes sociaux sont généralement adaptés à des robots à portée de main. Ce processus suppose implicitement que les comportements utilisés comme source d'inspiration sont observés à un certain niveau d'abstraction qui saisit les paramètres essentiels qui doivent être

1er janvier 2009

4.3.1 Conception

Swarm Intelligence adaptés à des robots et encore de reproduire des comportements de niveau de l'essaim. En approches principales, au lieu de concevoir un essaim au niveau comportement, à travers une méthodologie générale auquel on désire des comportements de niveau d’essaim on peut les utilisés pour construire des comportements individuels nécessaires qui sont proposés ou utilisés. Une telle approche est l'utilisation de l'évolution artificielle. Des méthodes évolutionnaires ont été utilisées avec succès pour développer des comportements au sein du projet Swarm-Bots [12]. En particulier, le SwarmBot3D [22], est une simulation a base physique de l'environnement, le système robotique Swarm-Bots à différents niveaux de complexité, a été utilisé. Dans la plupart de ces études, la réaction simple ou les perceptrons multicouches récurrents ont été utilisés pour encoder les comportements. L'évolution des comportements dans l'environnement de simulation ont ensuite été transférés avec succès à la physique du système robot. Le comportement d'un système robotique en essaim au niveau du système émerge de l'interaction de ses individus. Ces interactions, déterminées par les comportements des individus et l'environnement, sont, par nature probabiliste. En conséquence de cela, le résultat du comportement de systèmes robotiques de l'essaim n'est pas simple et la modélisation et l'analyse de l'essaim est souhaitable pour au moins deux buts. Tout d'abord, pour des tâches désirées à accomplir, et pour un projet de conception de comportement au niveau individuel, on doit obtenir des garanties pour la performance au niveau système. Deuxièmement, dans la plupart des approches ad hoc, bien que la composition globale des comportements individuels puisse être connue, la valeur optimale des paramètres peut rester inconnue. Les expériences systématiques avec des robots physiques sont souvent difficiles à exécuter. En outre, ils peuvent ne fournir que peu de garanties limitées et un aperçu du fonctionnement du système. Les modèles qui peuvent être utilisés à cette fin peuvent être examinés en trois groupes. Dans la modélisation à base de capteurs, la détection et l'actionnement d’un robot bien que des interactions robot-robot et robot-environnement sont modélisées. Ce type de modélisation, principalement utilisé pour la construction réaliste des simulateurs de systèmes robotiques, nous permet de mener des expériences en simulation et encore d'obtenir des résultats qui sont en accord avec ceux obtenus à partir de robots physiques. Bien que ce type de modélisation est commun dans la construction de simulateurs robotique [21], les modèles à être utilisés dans la robotique en essaim ont besoin de plus de fidélité au niveau des interactions inter-robot. Toutefois, la construction de ces modèles est soumise à l'arbitrage entre le réalisme et la simplicité - les modèles et les interactions doivent être réalistes pour être utiles, et, pourtant, dans le même temps, ils doivent être aussi simples que possible pour la vitesse. Une plate-forme de simulation construite avec l'ensemble de ces questions à

1er janvier 2009

4.3.2 Modélisation et Analyse

l'esprit est Swarmbot3D [22], un simulateur basé sur la physique développé spécifiquement pour le système robotique swarm-bot. Le simulateur contient des modèles du s-bot robot à différents niveaux de complexité et a été vérifié contre les robots physiques. Le simulateur a été utilisé à la fois de générer des comportements pour les différents problèmes à l'aide des méthodes d'évolutions, ainsi que d'analyser systématiquement le système qui en résulte au niveau des comportements. Ces simulations, même au plus bas niveau de complexité, se sont révélées de calcul intensif, et un système qui peut paralléliser les simulations sur un cluster d'ordinateurs a été développé dedans. Ce type de modélisation peut être utilisé comme un moyen constructif de concevoir les comportements, et à donner un aperçu sur le comportement de l'essaim grâce à des expérimentations. Dans la modélisation microscopique, similaire à l'approche à base de capteurs, une modélisation effectuée au niveau individuel. Les états de l’individu et les transitions entre ces états sont modélisés analytiquement. Cette modélisation prend en compte les caractéristiques de l'environnement, de l'incarnation physique et comportementale de contrôle des robots. Grâce à ces modèles, au lieu de simuler les interactions individuelles au sein du système, le modèle évolue l'état des individus dans le temps. Un excellent exemple de ce type de modélisation dans la robotique en essaim peut être trouvé dans [16]. Les auteurs ont étudié le problème de traction bâton, dans laquelle deux robots doivent collaborer pour tirer des bâtons. Ils ont proposé un modèle probabiliste pour représenter les changements dans les Etats des robots. Le modèle, qui est essentiellement un ensemble d'équations de taux, a été construit avec les caractéristiques physiques des robots, tels que la forme du corps et la taille du robot, ainsi que l'emplacement et les caractéristiques des capteurs, et de l'environnement. Il a également pris en compte la conception du comportement de l'individu et de robots utilisés comme base pour les transitions entre les différents Etats. La modélisation Microscopique a été signalé à être beaucoup plus rapide que la modélisation à base de capteur et fourni encore les moyens de relier les paramètres de comportement du système au niveau des résultats. Dans la modélisation macroscopique, à la différence des deux approches, la modélisation se fait au niveau de l'essaim. Ce type de modélisation, dans laquelle le comportement de certaines quantités moyennes, qui représentent l'état du système est représenté, et est commune en physique et en chimie. Contrairement aux modèles à base de capteurs et microscopiques, les modèles macroscopiques doivent être résolus afin d'obtenir une seule fois l'état d'équilibre du modèle. Il permet de trouver les paramètres optimaux de comportement systématique, sans procéder à des expériences avec des robots et fournit un point de vue de garantie théorique sur le comportement de niveau système de l'essaim. Un exemple de ce type de modélisation peut être trouvé dans [19]. Dans cette étude, un modèle d'analyse macroscopique pour un problème de tirer des bâtons mentionné ci-dessus,

1er janvier 2009

Swarm Intelligence

Swarm Intelligence est proposé. Dans ce modèle, le nombre de robots dans un état ainsi que le nombre de bâtons non extraies sont utilisés pour représenter l'état du système et le taux d'équations décrivant le changement dans ceux-ci sont issus. En utilisant un tel modèle, les auteurs sont en mesure de déterminer les paramètres optimaux pour les comportements du robot sans faire de l'expérimentation systématique. L'une des principales orientations de recherche a été le développement de l'essaim des systèmes robotiques, depuis la construction d'un système robotique en essaim elle prend plus de rassembler un certain nombre de copies d'un robot de la plate-forme générique. Toutes les études à cette fin, ont été axées sur le développement de robots mobiles, qui visent à fournir une plate-forme de recherche et ne sont pas destinés à l'exploitation du monde réel. Ci-dessous, nous allons discuter les exigences supplémentaires (ou de la liste de souhaits de point de vue des chercheurs) attendus de robots qui seraient utilisés dans des systèmes robotiques en essaim. • Détection et signalisation. L'accent principal de la robotique en essaim est l'interaction entre les robots, ainsi que l'interaction entre les robots et leur environnement, entraînant des contraintes supplémentaires qui seront utilisées pour les robots. En particulier, (i) l'interférence entre les systèmes de détection des robots et de l'effet de facteurs environnementaux sur eux devrait être minimale, (ii) les robots devraient être capables de distinguer d'autres robots-parents (de préférence, aussi facilement que les capteurs de proximité), et (iii) les robots devraient être en mesure de laisser des "marques" dans l'environnement et être en mesure de leur sens. En outre, il est préférable que les robots soient équipés d’une certaine forme générique de capacité de détection afin de permettre aux chercheurs de tester de nouvelles stratégies de détection. • Communication. Contrairement aux systèmes robotiques autonomes, en branchant les câbles de communication dans les robots n’est plus une option faisable. Par conséquent, les robots doivent supporter la communication sans fil (i) entre une console et des robots, afin de faciliter le suivi et le débogage des algorithmes sur des robots, (ii) les robots comme dans la forme de réseaux ad-hoc. Les robots doivent également être programmable en parallèle par le biais d'un canal de communication sans fil depuis des algorithmes de contrôle qui sont pour la plupart les mêmes pour tous les robots et la programmation de l'essaim dans son ensemble serait un gros gain de temps. • interaction physique. Les robots devraient être capables d'interagir physiquement avec d'autre et avec l'environnement car cela est requis par les tâches éventuelles telles que l'auto-assemblage et l’auto-organisation de la construction. • puissance. Les robots devraient avoir une longue durée de vie des piles. Dans la plupart des études, l'essaim doit fonctionner pour une période qui est

1er janvier 2009

4.3.3 Robots

Swarm Intelligence • Coût. Les robots devraient être marché aussi bon que possible, puisque, contrairement aux robots autonomes, ils seront vendus au moins en groupes de plusieurs dizaines. • Taille. La dimension importe dans l'essaim des systèmes robotiques. Les robots doivent être suffisamment petits pour ne pas rendre nécessaire l'augmentation de la taille de la scène lors des essais d'expérimentations avec le système, et encore de ne pas limiter l'extensibilité du robot ou d'augmenter le coût de l'essaim de robots en raison de la miniaturisation des composants. • Simulation. Les essaims exigent des systèmes robotiques réalistes simulateurs. Ils sont essentiels pour accélérer le développement de nouveaux algorithmes de contrôle. Ces simulateurs ont besoin de modéliser les interactions entre les robots, ainsi que les interactions avec des robots à leur environnement de manière réaliste qui est aussi vérifié contre les robots physiques. Le Développement d'une plate-forme de robot unique, cela rendrait compte que la liste du souhait entière est difficile, sinon impossible. Le choix de conception réalisés en ce qui concerne l'une des conditions, telles que la taille, pose des contraintes à la réalisation d'autres conditions, telles que les centrales électriques et de communication. Dans le reste de cette section, nous passerons en revue certaines des plates-formes existantes de robot mobile qui sont développés (ou peut être utilisé) pour mener la recherche et de la robotique en essaim évaluer en fonction de la liste ci-dessus. • Alice est un petit robot mobile rectangulaire de dimensions 22 × 21 mm. Le robot, entraîné par deux moteurs à haut rendement SWATCH de locomotion, l'hôte d'un microcontrôleur PIC16F877 avec mémoire flash EPROM 8K mots. Alice dispose de quatre capteurs de proximité IR pour détection d'obstacles et une courte distance robot robot-à-module de communication ainsi que d'un récepteur infrarouge pour la télécommande. Il existe également une grande variété de modules, comme une caméra linéaire, RF, ou modules de préhension, d'extension de ses capacités. Dix heures d'autonomie sont signalées avec deux piles bouton et de 20 heures d'autonomie est atteinte avec une batterie supplémentaire LiPoly. Le robot modèle est disponible dans le simulateur Webots. • e-Puck est un robot circulaire d'un diamètre de 70 mm. Le robot, entraînés par deux moteurs pas à pas pour la locomotion, l'hôte d'un microcontrôleur dsPIC 30F6014A avec 144 Ko de mémoire programme et 8 Ko de RAM. IR ePuck a huit capteurs utilisés pour mesurer la proximité des objets, ainsi que la lumière ambiante. Il a un haut-parleur de commentaires sonores et de trois microphones directionnels qui peuvent être utilisés pour la localisation du son et d'un accéléromètre à trois axes. Le robot a une caméra couleur, un certain nombre de voyants pour signaler ou de montrer son état et Bluetooth comme le principal canal de communication sans fil. Les robots peuvent être programmés par l'intermédiaire de ce module Bluetooth. e-Puck prévoit également une extension de bus est en option et des modules de

1er janvier 2009

assez longue, pour emerger le comportement, et atteindre l'objectif.

Swarm Intelligence

• Swarmbot est un robot de forme carrée avec des dimensions 130 × 130 mm. Il a quatre roues de chaque côté par deux engins de tête des moteurs DC. Le robot est équipé d'un processeur ARM Thumb, un FPGA, huit capteurs de choc, quatre capteurs de lumière et une caméra. Le Swarmbot utilise ISIS, un système infrarouge qui peut capter la gamme, l'incidence et l'orientation des voisins d'autres robots. Des modules supplémentaires sont linéaires CCD, magnétiques et de la nourriture essaim-cam émetteurs qui peuvent être utilisés sur demande. Il ya une unité de communication RF pour le débogage et la programmation. La durée de vie des piles des robots ne sont pas déclarés. • Centibots sont des versions modifiées de Pioneer 2-A et Amigobots. Un système de navigation inertielle pour estimer les coordonnées des robots, un laser SICK pour la construction et carte d'une caméra CCD utilisé pour étendre les capacités de détection des robots. Un ordinateur de bord, webcam USB pour objet d'intrusion et de détection d'intérêt sont ajoutées à Amigobots. Il y a un Wi-Fi sans fil ad-hoc entre le réseau de robots. Une autonomie de trois à six heures est indiquée pour les pionniers et les deux

1er janvier 2009

communication ZigBee. Trois heures d'autonomie sont signalés au moyen d'un 5 Wh Li-Ion. Le robot modèle est disponible dans le simulateur Webots. •Jasmine est un petit robot rectangulaire avec des dimensions 23 × 23 mm. Le robot, grâce à deux petits moteurs d'engins de locomotion tête, dispose de six capteurs IR pour détection de proximité et de communication à proximité. Il ya une puissante LED IR pour l'analyse détaillée d'un objet d'intérêt et d'un module de communication infrarouge avec les hôtes. Jasmine III a une conception modulaire, dans lequel les différents modules de détection comme un capteur de lumière ambiante, un capteur de couleur et de la locomotion des différents modules peuvent être utilisés. Deux heures d'autonomie sont rapportés avec LiPoly batteries. Un simulateur appelé LaRoSim a été construit pour mener des expériences dans la simulation. • s-bot, a une forme circulaire d'un diamètre de 116 mm. Les robots ont une locomotion sous-système constitué de deux roues et des voies qui sont entraînés par deux moteurs DC engins de tête. s-robots sont équipés de deux pinces pour l'étude de problèmes tels que l'auto-assemblage et la coordination du mouvement. Les robots ont des capteurs de différentes modalités, dont 15 pour les capteurs de proximité infrarouge de détection d'obstacles, quatre capteurs IR en dessous du robot face au sol, capteurs de couple sur les roues, un capteur de force entre la base et les roues, d'un accéléromètre à trois axes, une caméra omnidirectionnelle et huit LEDs RGB pour la messagerie entre les s-bots. Le robot est équipé d'un custom XScale 400 MHz CPU bord, 32 Mo de mémoire flash et 64 Mo de RAM. Un module WiFi est utilisé pour la communication sans fil. Les robots ont de batterie d’une heure de vie (Li-Ion). Un sur mesure SwarmBot3D est appelé simulateur développé pour simuler s-bots à différents niveaux de complexité.

Swarm Intelligence heures

pour

Amigobots.

• Kobot est un robot mobile de plate-forme circulaire d'un diamètre de 120 mm. Deux engins de haute qualité de moteurs à courant continu sont utilisés pour la locomotion. Kobot IR modulé a un système qui peut fournir des lectures de la proximité d'objets et de distinguer les robots d'obstacles. Le système de télédétection, qui utilise des signaux IR modulée, est robuste contre l'environnement et des conditions d'éclairage réduit les interférences entre les robots. Kobots utilise le protocole IEEE 802.15.4/ZigBee comme canal de communication sans fil. Grâce à cette chaîne, les robots dans un essaim peuvent être programmés en parallèle. Dix heures d'autonomie de la batterie est signalé avec LiPoly batteries. Un simulateur sur mesure est disponible.

Jusqu'à présent, les recherches en robotique en essaim sont surtout limitées à l'élaboration de concept proof-of-études dans des simulateurs ou des systèmes robotiques et dans des environnements de laboratoire. Ci-dessous, nous allons décrire quelques-uns des problèmes qui ont été abordées dans un essaim de robotique de recherche et de décrire quelques-unes des études portant sur leur exemplaire. • Agrégation. Une agrégation Auto-organisé, le groupement de personnes d'un essaim dans un cluster sans utiliser des indices de l'environnement, est un comportement observé dans les organismes allant des bactéries aux mammifères et les insectes sociaux. En essaim des systèmes robotiques, il peut être considéré comme l'un des comportements qui peuvent agir comme un précurseur d'autres comportements tels que le flocage et l'auto-assemblage. Dans [11, 30], les comportements d'agrégation ont été développés pour des robots myopes, des robots capables de percevoir qu'une petite partie de l'ensemble de l'environnement, limitée à une grande scène, en utilisant l'évolution des approches ainsi que d'un contrôleur probabiliste inspirés par les insectes sociaux. • Dispersion. Une dispersion Auto-organisées peut être considérée comme le contraire de l'agrégation et est d'intérêt dans la surveillance des scénarios. Dans ce problème (voir, par exemple, [27, 26, 28]), le défi est d'obtenir la diffusion uniforme d'un essaim de robots dans un espace, la maximisation de la zone couverte reste encore reliés par une certaine forme de canal de communication. • Forage. Ce problème est inspiré par le comportement des fourmis qui recherche de sources de nourriture distribués autour de leur nid. Dans ce problème, le défi est de trouver les meilleures stratégies de recherche permettant de maximiser le taux de retour de la nourriture pour les ressources engagées (par exemple le nombre de personnes effectuant des stratégies d'alimentation ou de signalisation), dans un environnement. Différentes stratégies d'alimentation ont été étudiées et analysées [31, 17, 20], et des

1er janvier 2009

4.3.4 Problèmes.

Swarm Intelligence • L'auto-assemblage. Ce comportement est observé dans les fourmis, où ils forment des chaînes par le biais de la connexion les unes aux autres pour construire des ponts ou des flotteurs, comme les structures pour rester audessus de l'eau. Le problème de l'auto-assemblage peut être défini comme la création de structures auto- organisées par la formation de connexions physiques au sein d'un essaim de robots différents. L'auto-assemblage a été étudié en physique des robots [7, 24] tel qu’une structure auto-assemblée désirée est formée. • Mouvement Connecté. Ce problème peut être décrit comme suit: Comment un essaim de robots mobiles, reliés physiquement les uns aux autres, coordonnes leurs mouvements tels que le groupe se déplace sans heurts dans un environnement et d'éviter les obstacles environnementaux, tels que des trous, d'une manière coordonnée. Ce problème a été étudié [32, 33] dans le cadre du projet Swarm-Bots. Dans ces études, l'évolution des approches ont été utilisées pour développer les comportements qui peuvent contrôler un certain nombre de robots connectés afin d'éviter les trous dans l'environnement. Les robots, qui sont physiquement reliés les uns aux autres par l'intermédiaire de leurs pinces, ont été en mesure de détecter les forces qui agissent sur le corps par le biais de capteurs et de traction ont été capables de détecter des trous en dessous. • Coopérative de Transport. Les fourmis sont connues de transporter de grandes proies à leur nid grâce à la coordination de leurs actions de pousser et de tirer. Une telle coordination est évidemment la capacité des systèmes robotiques de l'essaim, car il permet aux personnes d'unir leurs forces, générant une force suffisamment grande pour tirer un objet lourd. Ce problème est en partie lié à la circulation connectée, à la différence que comporte un objet passif qui doit être transporté. Dans [14], une série de réseaux de neurones s’est déroulé pour obtenir l'isolement du groupe et les comportements de transport dans un simulateur basé sur la physique. La position angulaire de l'objectif (marqués par une source de lumière) et de la distance ainsi que la position angulaire de la proie et d'une connexion du capteur indiquant si le robot est connecté à d'autres robots ou non ont été utilisés pour contrôler les moteurs du robot. • Formation de Structures. Il s'agit d'un terme générique et non pas le problème de la façon dont un motif géométrique souhaité peut être obtenu et maintenu par un essaim de robots sans aucune coordination centralisée. La formation du modèle peut se reporter soit à la géométrie ou à la formation de schéma fonctionnel. En formation géométrique, le défi est de développer des comportements tels que les personnes d'un essaim souhaité forment un motif géométrique, semblable à la formation de cristaux. Dans cette tâche, l'environnement est censé être uniforme et l'accent est mis sur l'utilisation des interactions inter-robot à créer de tels modèles. En schéma fonctionnel de formation, la tendance à se former est dictée par l'environnement. Dans des décors naturels d'essaims, les environs d'une proie par un groupe de prédateurs ou la formation des chaînes de traction par les tisseurs de fourmis

1er janvier 2009

modèles de quête de nourriture ont été développés [18, 15].

Swarm Intelligence peuvent être considérés comme des exemples de modèle de formation fonctionnelle, où la forme géométrique ou la taille de la structure sont constitués en partie déterminée par la tâche à accomplir en main. • L'auto-construction organisée. Ce problème peut être formulé comme suit: Comment un certain nombre d'objets passifs, distribuées au hasard dans un environnement, peuvent être regroupés par un essaim de robots. Ce problème, parfois aussi appelé «agrégation», a été l'un des premiers problèmes étudiés. Beckers a étudié la façon dont un essaim de robots physique frisbees cluster peut se propager dans un environnement, et a montré que, malgré le manque de communication et de signalisation entre les robots, frisbee clusters peuvent être obtenues.

4.4 Conclusion

1er janvier 2009

Dans ce chapitre, on a fourni une brève revue de la robotique en essaim une nouvelle approche pour le contrôle et la coordination de systèmes multirobots. On a affirmé l'inspirateur de cette approche, les propriétés, et les exigences et clarifier la définition des caractéristiques de cette approche par rapport à d'autres études existantes. Ensuite, on a examiné les études dans ce nouveau domaine, en les regroupant en quatre catégories. En raison de l'absence d'un bon article de synthèse dans ce domaine relativement nouveau, on a choisi de présenter au lecteur une vue d'ensemble du champ en termes assez généraux et a souligné certaines des études les plus intéressantes.