Trouver de nouvelles façons de collaborer ensemble pour un essaim intelligent

De nouveaux algorithmes montrent comment un essaim de robots simples peut fonctionner pour fonctionner ensemble dans son ensemble

Au laboratoire du Georgia Institute of Technology, les physiciens expérimentent des robots qui semblent avoir été achetés dans un magasin «tout pour 1 $». Les robots ne peuvent pas se déplacer dans l'espace ou communiquer entre eux. Fondamentalement, ils agitent leurs petites mains, comme des coléoptères tournés sur le dos.

Mais si vous assemblez beaucoup de ces appareils, vous pouvez tirer quelque chose de rien: ils se poussent, se poussent et s'emboîtent. Et en conséquence, ils commencent à travailler dans leur ensemble.

Les chercheurs étudient comment contrôler de tels systèmes afin qu'ils fonctionnent de manière similaire à un essaim d'abeilles ou à une colonie de fourmis: chaque individu agit sur la base du même ensemble de règles, mais plusieurs individus réunis peuvent présenter un comportement complexe sans contrôle central.

«Notre approche est la suivante: savoir quel est le modèle de calcul le plus simple nécessaire pour réaliser ces tâches complexes? Dit Dana Randall , spécialiste informatique chez Georgettech, l'un des chefs de file du projet. «Nous recherchons l'élégance et la simplicité.»

Randol, en tant que programmeur, aborde la tâche du point de vue des algorithmes: quel est le jeu d'instructions le plus simple sur la base duquel les unités individuelles de l'essaim peuvent travailler, sur la base des maigres données qu'elles peuvent collecter, conduira inévitablement au comportement conjoint complexe nécessaire aux chercheurs? En novembre dernier, Randall et ses collègues ont publié un algorithme pour garantir qu'un essaim idéal de particules puisse se déplacer de manière contrôlée.

Travailler avec de tels robots, que les scientifiques ont appelés «smarticles» [smarticles; intelligent - intelligent, particule - particule / env. transl.] - partie de la recherche dans le domaine de la possibilité de créer et de l'utilité des robots auto-organisateurs. D'autres exemples similaires incluent des robots de la taille d'une goutte en cours de développement à l'Université du Colorado, des essaims de " kilobots " de l'Université de Harvard et la svarmanoidy du laboratoire belge. Dans de nombreux cas, l'idée est d'imiter un phénomène naturel, comme un mouvement hautement organisé d'une colonie de fourmis décentralisée ou un assemblage inconscient et auto-programmé de molécules d'ADN.

"Nous savons ce que nous voulons d'un essaim entier, mais pour le programmer, vous devez comprendre ce que chaque agent doit faire séparément", a déclaré Melvin Gauchi , chercheur à Harvard qui travaille en robotique de groupe . "La partie la plus difficile se situe entre ces deux niveaux."


Dana Randall et Dan Goldman au Goldman Lab

Attention aux dirigeants

Daniel Goldman est un physicien de Georgetch qui dirige l'expérience Smarticle. Il s'intéresse principalement à la physique des matériaux granulaires actifs qui peuvent changer leur forme. Parmi ses diapositives de conférence se trouve un moment du film Spider-Man 3, démontrant l' émergence d'un supervillain Sandman - des grains de sable individuels dispersés à travers le désert se rassemblent sous la forme d'un homme. Les smartphones sont le moyen utilisé par Goldman pour tester les matériaux granulaires actifs dans un laboratoire.

«Ils nous donnent l'opportunité d'utiliser la géométrie pour contrôler les propriétés des matériaux. Si vous défocalisez vos yeux, vous pouvez imaginer que ce tas de smartphones est un vrai matériau », a déclaré Goldman.

Les smarticles ont des membres courts qu'ils peuvent balancer d'avant en arrière. Ils réagissent à la lumière et au son de différentes fréquences. Ils peuvent être programmés pour modifier la vitesse de l'ondulation des membres en réponse aux actions d'autres smartphones à proximité d'eux.

Les smartphones peuvent être conçus pour effectuer plusieurs actions: composer (empiler), étendre (distribuer) et se déplacer. Ces manœuvres peuvent servir de base à l'exécution de fonctions plus complexes, mais même de telles tâches sont assez difficiles à résoudre, car les smartphones ne comprennent pas comment ils se situent par rapport à l'ensemble du groupe.

Afin de comprendre les possibilités et les difficultés associées à la programmation d'un comportement complexe, résultant de parties simples, il convient de garder à l'esprit ce qui est connu de chaque smarticle individuel. Pas tellement. Il ne peut pas voir, sa mémoire est limitée et tout ce qu'il sait sur les autres smartphones avec lesquels il doit coordonner ses actions, il apprend quand il rencontre ses voisins immédiats.

"Imaginez un homme lors d'un concert de rock les yeux fermés", a déclaré Joshua Damad, un étudiant diplômé en informatique de l'Université de l'Arizona qui travaille sur un projet de smartphones.



Une stratégie peut être de nommer un chef pour gérer l'essaim - mais cette approche est vulnérable. Si le chef souffre, l'essaim entier échouera. L'autre consiste à confier à chaque robot une tâche unique dans l'essaim, mais à grande échelle, cette approche n'est pas pratique. «La programmation de 1000 robots individuellement est presque impossible», a déclaré Jeff Dasek , chercheur au Harvard College of Engineering à Olin et ancien membre du groupe de recherche sur les systèmes auto-organisés de Harvard travaillant sur un essaim de robots sous - marins . «Mais lorsque chaque membre du groupe travaille selon les mêmes règles, votre code ne change pas, que vous ayez 10 robots, 1 000 ou 10 000.»

L'algorithme swarm a deux propriétés. Tout d'abord, il est distribué, c'est-à-dire qu'il fonctionne séparément sur chacune des particules du système (car chaque fourmi nomade effectue le jeu d'actions le plus simple en fonction des informations reçues de l'environnement). Deuxièmement, il comprend un élément de chance. Cela signifie que si, par exemple, une fourmi nomade détecte la présence de cinq autres fourmis à proximité, alors avec une probabilité de 20%, elle se déplacera vers la gauche et avec 80% vers la droite. Les algorithmes diffèrent de manière aléatoire des algorithmes déterministes dans lesquels chaque étape est complètement déterminée par les précédentes.

L'aléatoire peut sembler inutile pour les algorithmes - après tout, lors de la mise en œuvre d'une procédure, vous souhaitez généralement obtenir un certain résultat. Mais le caractère aléatoire présente des avantages de performances inattendus, ce qui rend les algorithmes aléatoires bien adaptés à une utilisation dans les essaims.

Garanties aléatoires

En 2015, Goldman et Randall ont discuté de la possibilité de trouver des règles grâce auxquelles les smartphones pourraient fonctionner ensemble. Randall s'est rendu compte que le comportement que Goldman voulait diriger l'essaim était très similaire au comportement des systèmes de particules idéalisés étudiés en informatique.

"Et j'ai immédiatement pensé: je sais exactement ce qui doit être fait", a déclaré Randall.

Pour Randall, le comportement des smartphones ressemblait à un phénomène modélisé par les informaticiens dans de nombreux autres contextes. L'un des exemples les plus connus est l'émergence de zones ségréguées. À la fin des années 1960, l'économiste Thomas Schelling a voulu comprendre comment la ségrégation par zone se produit en l'absence d'une force centrale triant les personnes par couleur de peau. Il a imaginé une personne hypothétique regardant ses voisins et décidant de déménager en fonction du nombre de voisins qui lui ressemblaient. Lorsqu'une personne déménage, Schelling l'emmène dans un endroit aléatoire de la colonie, où le processus algorithmique d'observation et de prise de décision se répète. Schelling a constaté que, selon ses règles, l'émergence d'une ségrégation des résidents est presque garantie, même si certaines personnes préfèrent vivre dans des zones diverses.


William Savoy, étudiant diplômé au laboratoire de Goldman

Randall s'est rendu compte que les smartphones dans leur essaim ressemblent aux gens du modèle Schelling. Dans les deux cas, les unités individuelles doivent prendre des décisions sans connaître leur position sur le schéma global (elles ne savent que ce qu'elles voient dans le voisinage immédiat). Dans le modèle Schelling, les décisions peuvent être prises avec un élément de hasard - si les voisins sont différents de vous, alors il y a une chance que vous déménagiez et il y a une chance que vous restiez.

En 2016, Randol et ses collègues ont publié un ouvrage décrivant les particules idéalisées vivant sur un réseau et décidant de rester ou de se déplacer en fonction du nombre de particules observées autour d'elles. Les décisions prises étaient probabilistes - chaque fois que les particules «jetaient» un cube pondéré pour la sélection. Randall et al.ont montré que si vous affectez correctement le cube de poids, vous pouvez garantir la présence d'un essaim dense (tout comme Schelling pourrait prouver que si les habitants de la zone sont tolérés pour la diversité au bon niveau, une ségrégation apparaîtra certainement). En ajustant l'algorithme, ils pourraient également garantir qu'un essaim de particules se déplacerait dans un état étendu.

Le caractère aléatoire de l'algorithme aide les particules de l'essaim à éviter de se coincer dans les phoques locaux, lorsque de nombreux sous-groupes isolés s'accumulent ensemble, mais l'essaim dans son ensemble n'est pas densifié. L'aléatoire garantit que lorsque de petits phoques apparaissent, certaines unités décident toujours de se déplacer vers un autre endroit, et le processus se poursuit jusqu'à ce qu'un sceau général soit atteint. Pour éviter les phoques locaux, un peu de hasard est nécessaire; beaucoup plus est nécessaire pour passer d'un état globalement comprimé à un état étendu.

Vers le monde réel

Prouver que les particules du monde théorique peuvent, en exécutant un algorithme simple, atteindre un certain comportement dans un essaim est une chose. Pour mettre en œuvre l'algorithme à bon marché, sujet à l'échec, les vrais smartphones, en cliquant sur les membres dans une boîte - est complètement différent.

"Nos collègues théoriciens ont compris comment programmer ces choses, mais nous sommes encore au tout début du voyage et nous ne pouvons pas dire que ces programmes ont été transférés directement", a déclaré Goldman.

Un problème était de faire bouger les smartphones ensemble. Au début, lorsque les chercheurs ont enfermé les smartphones dans un espace limité, ce groupe a simplement accidentellement tremblé. Mais une fois, lorsque les physiciens ont observé ce mouvement chaotique, une batterie est morte dans l'un des smartphones. Goldman et ses collègues ont remarqué que l'essaim a soudainement commencé à se déplacer en direction d'une unité fixe. Les chercheurs ont rapporté cette découverte inattendue aux théoriciens et ils ont saisi cette allusion. Le travail a conduit à la création d'une nouvelle version de l'algorithme, permettant à l'essaim idéalisé de toujours se déplacer dans une direction donnée.

Peu à peu, les expériences en cours sur ordinateur et les expériences physiques se rapprochent. Les chercheurs espèrent enfin prouver théoriquement que l'algorithme de base, mis en œuvre par une méthode courante dans un grand essaim de petits robots bon marché, est garanti pour conduire au comportement d'essaim souhaité.

"Nous aimerions atteindre un état dans lequel nous ne détecterions pas simplement un phénomène lorsque la batterie se déchargera", a déclaré Daimad. «Nous voulons que ce soit quelque chose de la catégorie des réalisations intentionnelles.»