Robots en essaims
Dans une autre vie, j’ai fait de la recherche, impliquant notament des algoritmes d’optimisation issues de l’intelligence artificielle (à une époque où l’on n’en parlait pas à chaque journal télévisé). Parmis ces algoritmes, il y avait les PSO (Particles Swarm Optimization), soit de l’optimisation par essaims particulaires. Le principe était le suivant : l’algorithme simulait le comportement très basique de chaque particule, dont le mouvement était déterminé en fonction des autres particules dans l’espace. Au fil du temps, l’essaim constitué de plusieurs dizaines de particules se mouvait dans l’espace, à la recherche de leur but. Cette vidéo n’est pas de moi, mais elle illustre tout à fait ce que je faisais à l’époque sous MATLAB. Dans mon cas, l’espace et le but étaient liées à un problème à résoudre, mais peu importe.
Ce qu’il faut retenir, c’est que ce genre d’algorithmes permet de faire émerger une intelligence collective (ou intelligence de l’essaim) alors que chaque individu dans l’essaim ne dispose que d’un comportement limité, d’une intelligence basique et d’une compréhension très partielle de son environnement.
En marge de cela, peut-être savez-vous que j’aime bien les robots :
- Il y a très longtemps, je m’étais amusé à programmer un robot sur Twitter, qui était capable d’interragir avec les utilisateurs, et qui avait surtout pour but de me dénicher des informations interessantes (avec un certain succès). Celui-ci est tombé en panne il y a quelques années.
- Plus récemment, je me suis amusé à coder et fabriquer des robots physiques, celle fois, dotés de diverses capacités à commencer par celle de se mouvoir et d’éviter les obstacles.
Et puis, l’un des youtubeurs que j’affectionne a posté récemment une vidéo qui est la synthèse parfaite de mes paragraphes précédents. Mehdi Moussaid est vidéaste, vulgarisateur et chercheur, et étudie les mouvements de foules de divers sortes, au travers de sa chaine Fouloscopie. Dans sa dernière vidéo, il propose une optimisation par l’intelligence de l’essaim (ici : trouver et détruire une cible dans une zone en deux dimensions) mais déclinée sur des robots physiques et bien réels !
Je vous laisse regarder la vidéo, très pédagogique, bien illustrée, avec même un tournois, et un poil d’humour. En bref, passionnante !
La vidéo qu’il évoque, publiée par une des participantes à son tournois est ici.
Si ses recherches vous interessent, sachez qu’il vient de créer une campagne de financement participatif, afin de réaliser des expériences sur les foules en comportement réel.
J’avais déjà vu la vidéo.
Très intéressante, le seul défaut que je lui trouve, c’est que pour l’expérience en question, l’espace à chercher est assez petit, et je crois qu’il ne fait que 10 simulations par algorithme pour déterminer le temps moyen pour trouver la cible, hors en fonction des algorithme, il peut y avoir une très grande variabilité du temps. Pareil, il serait super intéressant de tester les cas aux limites, comme par exemple la cible complètement dans un coin, ou alors tout au milieu de la zone (les robots ont tendance à s’éloigner de leur lieu de départ sur la plupart des algo).
Avec un grand espace à chercher, de nouvelles questions passionnantes se posent, comme savoir s’il est plus optimal d’aller chercher de l’aide, ou d’attaquer la cible seul.
Et quid de si la cible se déplace ?
Bref, la vidéo est super et m’a laissé avec l’esprit en pleine cogitation sur plein de « si » intéressants.
Ah sympa j’avais pas vu sa nouvelle vidéo. Du coup ton article me donne envie de chercher + d’expériences.
Ce qui manque ici à mon sens, c’est davantage les obstacles que l’espace. Comment les essaims réagissent pour gérer les obstacles, trouver le chemin le + court, et si les obstacles bougent ?
(Une fois que les fourmis ont trouvé le chemin le + court et l’ont marqué à grands coups de phéromones elles semblent ne plus en changer même si un raccourci apparaît).
Comment gérer les encombrements ? Je pense notamment à Waze qui paradoxalement augmente la durée des embouteillages en créant de nouveaux micros bouchons sur les chemins alternatifs d’après certaines études.
Si vous avez des liens à partager ça m’intéresse ^^
Lyr à écrit :
Je ne suis pas sûr que ça changerait grand chose que la cible toi en plein milieu. Pour la cible aux extrémités, je pense que ça rallongerait juste le temps de recherche.
Lyr à écrit :
Logiquement, la taille de l’essaim doit être agrandie en fonction de la taille de l’espace…
Lyr à écrit :
Thörist à écrit :
Ca, c’est une très bonne question ! Quand j’avais travaillé sur le sujet, c’était un peu différent de ce qui est présenté dans la vidéo de Fouloscopie… Lui, il a un espace parfaitement plat, avec une cible ponctuelle à localiser. Moi, j’avais ce que l’on pourrait voir comme une géographie (montagnes, collines, vallées…) et l’essaim recherchait le point le plus bas (où on pourrait imaginer une rivière).
Dans son cas, si la cible se déplace, je ne suis pas certain que ça changerait grand chose. Globalement, le principe est de trouver la cible puis de s’en rapprocher. La notion de « se rapprocher » (ie. minimiser la distance entre les particules et la cible) reste applicable même si la cible bouge.
Dans mon cas, il y a deux possiblités :
Dans les deux cas, l’essaim à tendance à s’agglutiner sur sa cible (cf. la vidéo que j’ai mise en lien en début d’article). Pour gérer un espace qui change, il faudrait ajouter à l’essaim des espèces « d’explosions » qui relanceraient les particules un peu dans tous les sens, de la même manière que l’essaim est initialisé au tout début de l’algo.
Thörist à écrit :
Si l’on reprend mon analogie, les essaims particulaire peuvent normalement bien gérer les obstacles : il les voit comme des zones qui l’éloignent de sonbut, et les contournent donc naturellement.
Thörist à écrit :
Tout à fait ! Je pense que les algos basés sur les colonies de fourmis ne sont vraiment pas les plus pertinents en environnement changeant.
Thörist à écrit :
Sauf erreur, ici, il n’y a pas de notion d’encombrement. Dans mon cas, c’était du purement virtuel. Dans le cas de Fouloscopie, il y a une sécurité de non rapprochement des robots qui prédomine sur tout autre comportement, je pense.
Et de manière plus générale, il n’y a pas de notion de goulot d’étranglement…
C’est compliqué de le savoir juste avec la vidéo et sans voir le code mais à part le codeur qui avait une approche militaire cadrillant la zone en ligne de façon méthodique, les autres me semblaient avoir une trajectoire « aléatoire » sans nécessairement empêcher de balayer une zone déjà explorée. Si la cible bouge, ça change pas grand chose du coup non ? Ou il suffirait de ne pas empêcher les robots de repasser sur un même point.
Thörist à écrit :
Certes mais il y a une limite de ressources à un moment. C’est vrai que sur une surface de 10m2 c’est facile de ratisser la zone, sur 10.000m2 tu peux pas trop imaginer avoir une quantité de robots suffisante pour la couvrir entièrement ^^’