Les stratégies d’implémentation robotique révèlent une avancée fascinante dans la couverture d’environnements inconnus. En s’inspirant du comportement des insectes, cette recherche propose un algorithme novateur qui améliore significativement les performances des robots autonomes, avec des implications cruciales pour l’intelligence artificielle distribuée.
Les algorithmes de couverture pour un seul robot :
Plusieurs méthodes sont trouvées dans la littérature pour la couverture par un seul robot et multi robot. Une méthode de base qui a reçu une attention considérable est la méthode présentée par Gabriely et Rimon, où les auteurs décrivent un Spanning algorithme de couverture d’arbre, connu comme l’algorithme SC. Dans cette méthode, trouver un cycle hamiltonien couvrant terrain qui répond à certaines hypothèses.
En particulier, ils ont supposé que le robot est équipé d’un outil de forme carrée de la taille D, d’où la zone a été divisée en N cellules de taille D placés sur une grille. La grille était alors en gros de sorte que chaque nouvelle cellule est de taille 2D X 2D, et un arbre couvrant été construit selon cette nouvelle grille.
Après un tel arbre a été construit, le robot suit l’arbre autour, créant un cycle hamiltonien pour visiter toutes les cellules de la grille d’origine. [Noam et al, 05]
De nombreux algorithmes de couverture utilisent des graphes pour représenter l’environnement. L’algorithme de base de couverture sur un graphe est le DFS (depth-first- search), qui explore en profondeur dans le graphe chaque fois que possible, et retourne en arrière sinon. Cet algorithme tente d’abord d’atteindre la solution le plus vite possible en explorant immédiatement les successeurs de tout noeud généré, alors que la seconde étend l’arbre en générant les nœuds couchent par couche.
A chaque étape, l’algorithme met à jour la file des nœuds non explorés. C’est toujours le premier nœud de la file qui est étendu. Les nœuds résultants sont ajoutés en tête de la file de sorte qu’ils soient explorés en premier dans les étapes ultérieures.
Les avantages de la stratégie profondeur d’abord sont la simplicité de son implémentation et le fait que l’algorithme ne requiert que très peu de mémoire. L’un des problèmes majeurs de cet algorithme se pose lorsque le graphe contient des cycles. Cette possibilité est donnée lorsque les opérateurs permettent des opérations réversibles.
Spanning trees (ST) :
La méthode proposée par [Gabriely et al, 01] est une heuristique reposant sur l’utilisation de spanning trees et permettant de construire des cycles hamiltoniens. En théorie des graphes, les spanning trees permettent la représentation de graphes par des arbres de taille finie. Cette représentation en arbre permet de représenter l’ensemble des nœuds du graphe sans risquer de rencontrer d’éventuels boucles ou cycles.
[7_strategies-implementation-pour-la-couverture-robotique_11]
Figure 2.2 : Un spanning tree (arcs bleus) d’un graphe grille
La méthode proposée repose donc sur l’utilisation de tels arbres. Considérant un environnement grille avec des cellules de côté de longueur n, les auteurs lui superposent une seconde grille, de granularité plus importante, avec des cellules de côté de longueur 2n. Ainsi, à chaque cellule du graphe grossier sont associées 4 cellules du graphe original. Un algorithme de construction de spanning tree est ensuite exécuté sur le graphe grossier. L’agent n’a alors plus qu’à suivre le spanning tree (chemin fléché, Figure 2.2) pour effectuer une patrouille optimale de l’environnement.
[7_strategies-implementation-pour-la-couverture-robotique_12]
Figure 2.3 : Un cycle hamiltonien réalisé à partir d’un spanning tree sur un environnement grille de 8×8 nœuds.
Si cette méthode permet de planifier une couverture optimale très rapidement (en temps linéaire O(N), N étant le nombre de cellules de l’environnement), elle reste cependant assez limitée et pose des contraintes fortes sur l’environnement :
_ Le graphe est contraint à être une grille à voisinage de Von Neumann (chaque nœud à au plus 4 voisins) dont les côtés sont de longueurs paires.
_ Les obstacles présents dans l’environnement peuvent rendre cette méthode inopérante si leur densité est importante.
Algorithme Spanning Tree Couvrant (STC) :
La structure du Spanning Tree a un rôle essentiel dans le temps de la couverture obtenue par des algorithmes qui utilisent l’arbre comme base pour la couverture. N’importe quel algorithme de couverture, ne peut pas atteindre le temps de couverture bas que l’on peut obtenir en utilisant un arbre différent. Une Spanning Tree, ce qui en soi obtient le temps d’une couverture optimale, il n’existe pas nécessairement, par conséquent, le temps d’une couverture optimale théorique peut rester inaccessible dans certains cas.
L’environnement que les robots fonctionnent en est représentée comme une grille 2D de grandes cellules carrées, qui peut être soit complètement bloqué ou totalement débloqué. Chacune de ces grandes cellules ont composé de quatre petites cellules. Tous les robots sont de la taille d’une petite cellule, et peut être situé dans une de ces cellules à tout moment, si elle est débloquée.
Un robot qui se trouve dans une cellule non bloqué peut se déplacer à une cellule adjacente, s’il est débloqué (ce qui signifie que le robot peut se déplacer vers le haut, bas, gauche et droit, mais pas dans les mouvements en diagonale). Une telle démarche suppose de prendre le temps de l’unité (le temps est le même pour tous les robots). Il est possible que plus d’un robot puisse occuper la même cellule à la fois.
[7_strategies-implementation-pour-la-couverture-robotique_13]
(A) une représentation de l’environnement (b) une représentation de Spanning Tree Figure 2.4 : Exemple de l’algorithme STC
Gabriely et Rimon ont introduit trois versions de l’algorithme Spanning Tree covering (STC), qui assurent une couverture optimale : les algorithmes off-line, on-line, et Ant-like STC.
Algorithme STC off-line :
En premier temps, le robot est équipé d’un outil couvrant rectangulaire de taille D et peut se déplacer seulement dans les quatre directions orthogonales à côté de l’outil. Un arbre recouvrant est construit en utilisant DFS sur une grille sans obstacles d’une taille 2D. Finalement, chaque cellule 2D est subdivisé en quatre cellules de taille D. et le robot fait le tour de cette arbre jusqu’à ce qu’il atteint le point de départ, ce qui implique une couverture complète. [Sarid.2011]
Cellule de départ S
[7_strategies-implementation-pour-la-couverture-robotique_14]
Chemin de couverture dans le sens trigonométrique trigonométrique
Figure 2.5 Un exemple d’exécution de l’algorithme STC off ligne.[Gabriely et al, 1999]
- Algorithme STC On-Line:
Dans la version en ligne de STC le robot n’a pas de connaissance préalable de l’environnement, sauf que les obstacles sont fixes. Au contraire, le robot doit utiliser ses capteurs embarqués pour détecter les obstacles et de planifier son chemin couvrant en conséquence. [Gabriely et al,99] le robot a capteurs de position et d’orientation, ce qui lui permet de reconnaître les cellules 2D de taille comprenant la zone de travail.
Et aussi que le robot a un détecteur de gamme, capable d’identifier les obstacles dans les quatre cellules voisines cellule actuelle. Les questions pratiquement importants de sélection des capteurs, des erreurs de mesure du capteur, et la fusion de capteurs ne sont pas considérés. Au contraire, ils ont suppuosé que les capteurs sont idéales, et qu’ils fournissent des lectures parfaites.
Dans l’algorithme STC en ligne, le robot construit progressivement un arbre de recouvrement de la grille représentant la zone de travail. Lors de la construction d’arbre couvrant, le robot subdivise chaque cellule qu’il rencontre en quatre sous-cellules identiques de taille D, chacune étant identique à la taille de robot. Cet outil de couverture suit le chemin de la partie de cellule qui contoure l’arbre couvrant progressivement, jusqu’à ce que l’ensemble de la grille de région est couverte.
ANT-like STC Algorithme:
Chang et al ont utilisé une fourmi robot mobile comme un modèle de robot simplifié d’une vraie fourmi. Dans ce modèle, les robots de fourmi et de l’environnement ont plusieurs caractéristiques importantes :
- Une fourmi robot vit dans le domaine discret.
- La carte et les obstacles sont constitués de carreaux qui peuvent être considéré comme sommets dans un graphe non orienté G.
- L’environnement est fini et limité.
- Dans chaque cycle de temps, les robots-fourmis n’effectuent aucune action à des instants identiques. Ils se déplacent de façon aléatoire dans la période de temps afin d’éviter le conflit d’occuper la même case dans le même laps de temps.
- Une fourmi ne peut se déplacer à quatre tuiles voisines ou sommets. En cas d’égalité, la fourmi fera une spiralmovement décision.
- Chaque mouvement coûte une unité de temps et une unité de énergie.
- La communication entre les fourmis sont basées sur l’ phéromone (marques) a laissé sur les carreaux.
- Une fourmi a une mémoire limitée.[ Jacky et al]
(a) (b)
Figure 2.6 : La fourmi peut se déplacer à carreaux ou des sommets, T1, T2, T3 et T4. (a)Le cercle est la plage du capteur efficace de la fourmi. (b) La forme équivalente dans un graphe non orienté. [Jacky et al]
La version Ant-Like STC est aussi un algorithme on-line, elle utilise les mêmes capteurs décrits ci-dessus. Cependant, maintenant que le robot a la capacité de laisser des marques dans les sous-cellules qu’elle couvre, en utilisant la couleur, l’odeur, la chaleur, ou des marqueurs de galets. Les Auteurs ont supposés en outre la disponibilité d’un dispositif de détection, capable d’inspecter les marques sous-cellules dans la cellule actuelle et ses quatre voisins immédiats.
Utilisant cette dispositif de détection, le robot identifie une cellule voisine en tant que nouveau lorsque ses quatre sous-cellules sont toutes non marqué. Tout comme l’algorithme STC on-line, ici aussi, le robot utilise DFS pour construire progressivement un arbre couvrant de la région. Cependant, plutôt que de stocker le couvrant arbre dans sa mémoire, le robot utilise les marques sous-cellules pour identifier des cellules-mères le long de spanning tree comme suit.
Par construction, le Robot traite et marque les sous-cellules d’une case donnée dans le sens trigonométrique. Par conséquent, tant que les quatre sous-cellules de la cellule actuelle ne sont pas tous marqués, le robot n’a qu’à analyser les sous-cellules dans l’ordre anti-horaire et d’identifier la transition entre sous-cellules non marqué et marqué.
Les deux sous-cellules qui bordent cette transition ont un bord extérieur en commun. cet avantage est nécessairement le bord de la frontière entre la cellule active et sa cellule-mère dans le spanning tree. En outre, le robot n’a pas besoin d’identifier une cellule mère d’une cellule dont les quatre sous-cellules sont déjà marqué, car une fois que le robot couvre les quatre sous-cellules d’une cellule donnée, il ne revient jamais à cette cellule à nouveau.[ Gabriely ,99].
Algorithme Spiral STC :
Les auteurs [Gabriely et al,02] démarrent par une version préliminaire de l’algorithme appelé 2D-Spiral-STC. L’algorithme préliminaire ne couvre que les cellules de taille 2D qui sont complètement sans obstacles. Ces cellules sont couvertes par un chemin optimal induite par un arbre couvrante dont les noeuds sont des cellules de taille 2D libres. L’algorithme complet couvre grilles généraux en traitant les cellules de taille 2D qui sont partiellement occupés par des obstacles comme des nœuds spéciaux du Spanning Tree qui effectué une couverture répétitive.
Le spiral STC améliore l’algorithme préliminaire par une couverture des cellules 2D partiellement occupée. Ces derniers sont définies comme les cellules qui contient au moins une sous cellule (D-size) sans obstacle. cet algorithme, utlie la structure de graphe augmenté suivante : les nœuds sont les centres des cellules libres et occupées, les bords du graphe connectent les centres des cellules adjacentes qui contient des sous-cellules sans obstacles avec des frontières communes. Cette construction donne naissance à deux types de bords :
Le premier type, appelé bords recto-verso, ne possèdent qu’un sous-cellules libres sur les deux côtés (Figure2.7 (a)). L’autre type, appelé bords simple face, possèdent au moins une sous-cellule occupée de chaque côté (Figure2.7 (b)). Spiral-STC construit progressivement un arbre couvrant du graphe augmentée, le tour d’un bord simple face aboutit à une couverture répétitive de certains sous-cellules associées à ce bord. Voici un example représenté une telle cellule avec deux noeuds, chacun ayant des bords de cellules adjacentes à partir de laquelle une sous-cellule libre peut être consulté (FigureI.14 (c)). [ Gabriely et al ,02]
Cellule
Cellule libre
Cellule
Cellule libre
Cellule
Partiellement Occupé
Partiellement Occupé
Localement déconnecté
(a) Bords recto-verso (b) bords simple face (c) doubler nœud
Figure 2.7 : (a) une seule face, (b) à double face bord, (c) doublement de nœud à une cellule déconnectée.
L’algorithme complet Spiral-STC a la même structure que l’algorithme préliminaire. Par conséquent, ils ont décrit seulement la fonction récursive, appelé STC2 (w, x), qui est modifiée afin de tenir compte des deux types de bords qui se produisent dans la grille graphique augmentée.[Gabriely et al ,02].
________________________
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
Quelles sont les méthodes de couverture pour un robot autonome ?
Plusieurs méthodes sont trouvées dans la littérature pour la couverture par un seul robot et multi robot, y compris l’algorithme SC proposé par Gabriely et Rimon.
Comment fonctionne l’algorithme de couverture DFS ?
L’algorithme DFS explore en profondeur dans le graphe chaque fois que possible et retourne en arrière sinon, mettant à jour la file des nœuds non explorés à chaque étape.
Quels sont les avantages et inconvénients de l’algorithme de couverture basé sur les arbres couvrants ?
Les avantages incluent la simplicité de l’implémentation et une couverture rapide, tandis que les inconvénients incluent des contraintes sur l’environnement, comme la nécessité d’une grille à voisinage de Von Neumann.