L’innovation en exploration robotique révèle des avancées surprenantes dans la couverture d’environnements inconnus. En s’inspirant des comportements d’insectes, cette étude propose un algorithme réactif qui transforme notre compréhension des interactions multi-robots, avec des implications significatives pour l’intelligence artificielle distribuée.
Algorithmes de couverture multi-robots :
Tandis que les algorithmes de protection mono-robots ont reçu beaucoup d’attention, il existe actuellement de nombreux algorithmes de moins pour le problème de couverture multi-robots. La plupart des algorithmes de couverture multi-robots sont des robots qui interagissent et prévoient que localement, souvent appelés robots de fourmis.
Naturiellement, la planification globale peut conduire à un significativement petit moment de couverture, car il permet aux robots de coordonner leurs trajectoires beaucoup mieux.
Algorithme MSTC :
La généralisation de l’algorithme STC pour un système multi-robots a été introduite par Hazon et Kaminka. [Noam et al, 05] Ils ont présenté plusieurs algorithmes pout une couverture multi-robots d’un terrain, qui garantissent une couverture robuste, temps complet et efficace.
Ils ont dérivé deux versions de l’algorithme MSTC: MSTC de non backtracking et MSTC backtracking, ci-après dénommé NB-MSTC et B-MSTC, respectivement. Dans l’algorithme MSTC NB les robots se déplacent simplement dans le sens antihoraire ou long du chemin de Spanning Tree jusqu’à la position initiale du robot suivante si aucune panne ne se produit, ou de prendre sur le trajet de la couverture du robot consécutive contraire.
Dans le B-MSTC les robots peuvent revenir en arrière sur certaines parties de leur trajectoire de couverture, c’est à dire, ils peuvent aller à la fois dans le sens horaire et antihoraire. Ils ont montré que si le robot marche arrière, le pire des cas effectue jusqu’à deux fois plus rapide que dans le cas de non backtracking, malgré la redondance.
[Hazon et al,]
[Sarid et al ,11] Ils ont explorés un problème de planification de mouvement en ligne pour un groupe de robots à la recherche d’une cible dont la position inconnue.
Récemment, la STC a été généralisé à Multi-Robot couverture Spanning Tree (MSTC), un polynôme-temps multi-robots heuristique de couverture. MSTC première calcule le même arbre couvrant que STC, et considère que la tournée qui fait le tour de l’arbre couvrant.
Chaque robot suit le segment de la tournée dans le sens horaire devant lui, à une exception près: Pour améliorer le temps de couverture, le segment le plus long est divisé à parts égales entre les deux robots adjacents.
Quelques petits ajustements, alors assurez-vous que MSTC réduit le temps de couverture du STC par un facteur d’au moins 2 (ou 3/2) pour k >= 3 robots (ou deux robots, respectivement). Chaque petite cellule est visitée par un seul robot, donc il n’y a jamais eu de collisions ou des blocages.
[8_innovation-en-exploration-robotique-strategies-avancees_16]
- Figure 2.8 : exemple de MSTC en fonctionnement.
Algorithme MRSAM :
L’algorithme MRSAM lance plusieurs robots à partir d’un point de départ commun S et attribue chaque robot j à un disque à la recherche de la cible T, tous les disques sont concentriques, et S est leur centre.
Dans [Sarid et al ,11], Ils ont introduit un nouvel algorithme de navigation en ligne, appelé MRSAM (le Multi-Robot Search Time multiplication), qui est basée sur le doublement de la superficie de l’algorithme SAD1 (Navigation à une cible inconnue). L’idée principale de SAD1 est comme suit : Le robot sélectionne un disque initial de rayon R0 centré à S, et recherche dans la partie de ce disque accessible à partir de S.
Si la cible est détectée l’algorithme se termine. Sinon, le robot répète le processus sur les disques de rayons 2i = 2R0 pour i = 1; 2; jusqu’à ce que la cible est détectée, ou toute la région accessible à partir de S est explorée sans trouver T (Figure 2.9). Le processus de recherche dans chaque disque est comme suit.
Le robot impose une discrétisation en ligne de la région continue en une grille de cellules de taille D. La grille se compose uniquement de cellules libres et est entourée par des cellules partiellement occupés. Le robot exécute un tour de la zone de couverture de série sur la grille de cellules libres, tout en balayant chaque nouvelle cellule de la cible.
A l’entrer d’une nouvelle cellule, le robot analyse en plus les cellules voisins partiellement occupées pour T. Si la discrétisation préserve la connectivité de la région accessible (cette hypothèse peut être assouplie par un algorithme plus complexe qui surveille la rupture de la connectivité locale), il est clair que toutes les cellules libres et partiellement occupé dans la région accessible à partir de S sont finalement inspectées par le robot.
[8_innovation-en-exploration-robotique-strategies-avancees_17]
Figure 2.9: La région du disque recherché par SAD1 doublé à chaque étape.
Il nécessite de la mémoire linéaire et a un rendement concurrentiel quadratique. En outre, il est démontré que de façon générale tout algorithme de navigation en ligne doit avoir au moins une performance compétitive quadratique. L’algorithme MRSAM atteint des limites inférieures donc il a une compétitivité optimale. MRSAM lancer un groupe de robots à partir d’un point de départ commun pour effectuer la recherche de la cible.
Chaque robot est du type D et a un système de positionnement qui est supposé être idéal, un tactile ou un capteur de vision restreint qui détecte des obstacles dans l’environnement et un capteur de reconnaissance de cible, qui peut être n’importe quel capteur selon le type de la cible qu’il est l’objet.
[8_innovation-en-exploration-robotique-strategies-avancees_18]
Figure 2.10 : Un groupe de deux robots lancés par MRSAM à la recherche de la cible
Chaque robot est attribué à un disque, pour rechercher la cible, chaque disque a une taille différente (voir Figure 2.10).
Le premier robot est affecté à un disque avec surface S0 et chaque robot conséquente est affecté à un disque de surface supérieure à la surface du robot précédente par un facteur de multiplication α > 1, qui ne dépend que de n, le nombre de robots allouée à la tâche.
Chaque robot cherche la cible dans son disque jusqu’à ce qu’il trouve la cible ou jusqu’à ce qu’il finit la couverture de tous les secteurs liés au disque, dans ce dernier cas, le robot est affecté à poursuivre à la recherche dans un autre disque libre.
les auteurs (Shahar Sarid et Amir Shapir) font quelques remarques informelles sur l’algorithme. Tout d’abord, lors de la section d’initialisation, après l’obtention des valeurs de n et r0, chaque robot peut calculer sa future Disques de recherche et les rayons correspondants, ce qui signifie que les robots n’ont pas besoin de communiquer les uns avec les autres, à l’exception d’un signal d’arrêt lorsque la cible est trouvée.
Cela implique une approche décentralisée avec pas ou peu de communication. Deuxièmement, un robot qui a terminé la recherche d’un disque procédera immédiatement à l’autre disque qui lui est assignée. La visite de la couverture peut être exécuté avec un algorithme DFS trivial en utilisant la mémoire linéaire.
Performance moyenne de l’algorithme peut être améliorée si chaque robot couvre à chaque étape seules les cellules qui se trouvent dans le cycle ajoutés au disque précédent.
Quatrièmement, si la cible est inaccessible à partir de S, l’algorithme ne s’arrête que lorsqu’il est complètement couvert la composante connexe de l’environnement contenant S. [Sarid et Shapir,].
Multi-Robot Forest Coverage (MCF) :
Les auteurs [Zheng et al,] ont décris la couverture forestière Multi-Robot (MFC). Il est basé sur l’algorithme de Even et al. qui donne un four approximation pour le problème de trouver une couverture d’arbre avec des racines donnés, en minimisant le poids de l’arbre le plus lourd.
MFC fonctionne sur le graphe dont les sommets sont les grandes cellules, et dont les bords se connectent aux grandes cellules bloquées adjacentes. Si les robots commencent dans une grande cellule, puis MFC fait r copies identiques de ce sommet. MFC trouve un couvert végétal racines de ce graphique en temps polynomial, où les racines sont les sommets qui contiennent des robots. (Le graphique est autorisé à être déconnecté, aussi longtemps que chacun de ses composants contient au moins un robot.) Chaque robot contourne alors son arbre.
En conséquence, la couverture forestière donne un quatre-approximation pour la couverture forestière. Il fonctionne comme suit:
- Retirer toutes les arêtes avec des coûts de pointe supérieures à celles B.
- Contracter tous les racines dans un seul sommet, Trouver un arbre recouvrant minimal pour le graphe résultant, puis à nouveau sur la uncontract seul sommet, diviser le spanning tree dans les arbres |R|.
- Décomposer chaque arbre en sous-arbres qui peuvent partager sommets, mais pas les bords. Le poids de chaque sous-arbre est dans l’intervalle [B; 2B], à l’exception possible d’une sous-arborescence qui contient les restes de la racine de l’arbre, et dont le poids est inférieur à B.
- Trouvez un couplage maximum de tous les sous-arbres non restes des racines, sous la contrainte que non seulement les restes de sous-arbre peut être associé à une racine si le non-restes arbre arborescence et restes de la racine (root ou lui-même) sont à distance au plus B. Si certains sous-arbres non restes ne peuvent être jumelés, c’est la preuve qu’aucune couverture arbre enraciné de poids au plus B existe.
- Pour chaque racine, retourner un arbre constitué de la racine, les restes de sous-arborescence de la racine (le cas échéant) de poids au plus B, le seul non-restes arborescence adaptée à la racine (le cas échéant) de poids au plus 2B, et un chemin coût minime de poids au plus B de la non-restes-arbre à la restes arborescence (ou root). Le poids de chaque arbre est dans la plupart des 4B, résultant en un couvercle d’arbre ancré de poids d’au plus 4B. [Xiaoming et al,]
[8_innovation-en-exploration-robotique-strategies-avancees_19]
Figure 2.11 : exemple de l’algorithme MFC
Les champs de potentiels artificiels :
Les champs de potentiel [Khatib ,86] est une méthode assez originale qui assimile le robot à une particule soumise à un champ de forces répulsives et attractives. Un obstacle génère un champ de potentiel répulsif tandis que l’objectif à atteindre génère un champ de potentiel attractif. L’algorithme calcul donc un vecteur résultant qui indiquera au robot comment effectuer son déplacement.
Cet algorithme est totalement réactif et peut donc être très facilement implémenté en temps réel. Cependant, comme l’environnement est très peu souvent totalement convexe, cette méthode plonge facilement le robot dans des minimas locaux. De plus, les problèmes d’oscillation peuvent, dans certain cas, être constatés.
Comparaison des résultats des algorithmes de couverture mono-robot et multi-robots :
MFC & STC & MSTC :
-S’il y a un seul robot, MFC réduit à STC et réduit ainsi le temps de couverture. S’il y a plus d’un robot, rappeler que MSTC réduit le temps de couverture du STC par un facteur d’au moins 2 (ou 3/2) pour k >= 3 robots (ou deux robots, respectivement). MFC ne peut pas prendre une telle garantie solide de pire des cas sur la façon dont son temps de couverture est bon et concernant le plus petit temps de couverture d’un seul robot.
-Le temps de couverture du MFC ne peut pas être plus mauvais que celle de STC parce que MFC rend chaque robot un arbre qui peut être étendue à un arbre couvrant. D’autre part, la figure 4 montre un exemple où le temps de couverture du MFC est égale à la durée de couverture du STC (où, dans le cas du STC, le deuxième robot ne bouge pas), peu importe combien de temps le corridor est, même si le temps de couverture du MSTC est seulement la moitié du temps de couverture du STC. [Zheng et al,]
STC et MFC (le temps de couverture = 18) MSTC (le temps de couverture) = 9
Figure 2.12. MFC et MSTC contre STC
-Les résultats expérimentaux des auteurs [Xiaoming al , 05] montrent que le temps de couverture du MFC est plus petit que celui de Multi-Robot couverture Spanning Tree (MSTC) et proche de l’optimum dans tous les scénarios testés.
Off-line STC & On-line STC & Ant-like STC :
-Les trois algorithmes STC: Off-line STC, On-line STC, et Ant-like STC, ne couvrent pas de manière répétitive tout moment la zone de couverture.
-Les trois algorithmes STC couvrent chaque cellule qui est accessible à partir de la cellule de départ S.
-Les trois algorithmes STC couvrent complètement une grille connectée représentant une zone de couverture continue. De plus, le revêtement est optimal en ce sens qu’il n’y a pas de couverture répétitive d’un point quelconque de la zone continue sous-jacente à la grille.
-L’On-line STC maintient une structure de données de l’arbre couvrant construit progressivement, tandis que l’Ant-like STC utilise des marques de sous-cellule pour identifier localement l’arbre couvrant.
________________________
2 Définition donnée par l’article 62 de la loi sur les nouvelles régulations économiques (NRE) du 15 mai 2001. ↑
3 Auchan Les 4 Temps, La Défense. ↑
Questions Fréquemment Posées
Qu’est-ce que l’algorithme MSTC dans la couverture multi-robots?
L’algorithme MSTC est une généralisation de l’algorithme STC pour un système multi-robots, garantissant une couverture robuste, temps complet et efficace.
Comment fonctionne l’algorithme MRSAM pour la recherche de cibles?
L’algorithme MRSAM attribue chaque robot à un disque concentrique à la recherche d’une cible, en doublant la superficie de l’algorithme SAD1 jusqu’à ce que la cible soit détectée.
Quelle est l’importance de la planification globale dans les algorithmes de couverture multi-robots?
La planification globale permet aux robots de coordonner leurs trajectoires beaucoup mieux, conduisant à un moment de couverture significativement plus court.