Les implications politiques de l’exploration robotique révèlent des enjeux cruciaux pour l’avenir de l’humanité. En intégrant des algorithmes inspirés de la nature, cette recherche ouvre la voie à des stratégies innovantes pour naviguer dans des environnements inconnus, transformant notre compréhension des interactions homme-machine.
L’exploration d’un environnement inconnu
L’exploration d’un environnement par un groupe d’entités est un problème algorithmique fondamental ayant des applications directes dans plusieurs domaines, soient-ils physiques ou virtuels.
En effet, on peut penser à l’exploration d’un labyrinthe par plusieurs personnes à la recherche d’un trésor, l’exploration d’un environnement inhabitable (tel qu’une planète lointaine) par un groupe de robots, la planification des meilleures routes pour la livraison de biens par une flotte de véhicules, l’inspection d’un bâtiment par un groupe de pompiers à la recherche de victimes ou l’exploration de nœuds dans un réseau informatique.
Nous cherchons une stratégie permettant aux robots de visiter toutes les zones de l’environnement le plus rapidement possible. Dans ce contexte, l’utilisation de plusieurs robots est avantageuse mais le gain est conditionné par le niveau de coopération entre les robots.
Définition
Un environnement inconnu est défini par le fait que l’information nécessaire à l’exploration à coût optimal n’est pas disponible lors de l’exécution de l’algorithme d’exploration. Par exemple, dans l’étude faite par Rao et al. [Rao et al], un terrain inconnu est défini par le manque d’information sur le modèle du terrain (les obstacles, les chemins, la carte du terrain, etc.). D’autres auteurs utilisent cette même classification.
De même, le manque de connaissances dans un environnement non géométrique, tel un graphe, peut être défini par le manque d’information sur l’identification des sommets ou des arêtes (p. ex. [2, 6, 7, 8, 17, 21, 18]).
Dans son sens le plus large, l’exploration se définit par le fait de percevoir (soit physiquement, visuellement, virtuellement, ou avec un capteur quelconque dans le cas d’un robot) tous les éléments de l’environnement dans un but donné. Le but de l’exploration peut être, par exemple : la découverte d’un objet, l’exécution d’une tâche à un endroit dans l’environnement, la cartographie de l’environnement, etc. [Frédérick, 13]
Les algorithmes d’exploration
Dans cette section nous présentons les principaux types d’approches existantes pour l’assignation de frontières aux robots pour l’exploration d’environnements inconnus.
Les premières méthodes d’exploration étaient basées sur une navigation aléatoire [Lopez et al, 97] ou le suivi de mur [Tom, 97]. En mono-robot, comme en multirobot, une technique admise comme efficace est l’exploration successive des frontières créées entre les zones non- explorées et les zones explorées accessibles [Brian, 97]. Les robots se déplacent vers les frontières et collectent ainsi de nouvelles informations sur les zones inexplorées de l’environnement.
Frontière la plus proche
Yamauchi est le premier à avoir développé une stratégie multi-robot d’exploration de frontière [Brian, 97]. Les robots partagent les informations locales récoltées afin que chacun d’entre eux produise une carte similaire fournissant une liste de frontières similaires.
Chaque robot se dirige vers la frontière la plus proche de lui, effectue une observation et en diffuse (broadcast) Aucune communication n’est nécessaire pour coordonner les robots. C’est un système asynchrone, distribué et robuste aux pannes de robots.
[9_implications-politiques-de-exploration-robotique-innovante_20]
Source: Figure 2.13. Coordination implicite avec l’algorithme frontière la plus proche [Bautin et al, 11]
Lors de son application, une coopération implicite s’effectue (voir la figure 2) mais elle est limitée car les robots peuvent choisir les mêmes frontières ne tirant pas avantage de leur nombre.
Description de l’image (du haut vers le bas) : quand le premier robot R1 atteint l’intersection des couloirs il découvre 3 frontières équidistantes et choisi aléatoirement la frontière F1, quand R2 atteint l’intersection, il reste 2 frontières plus proches équidistantes et choisit aléatoirement F0 entre F0 et F2, quand le 3ième robot R0 arrive sur l’intersection une seule frontière est plus proche de lui et il choisit donc F2.
[9_implications-politiques-de-exploration-robotique-innovante_21]
Source: Figure 2.14. Résultat de l’assignation avec l’algorithme Frontière la plus proche [Bautin et al, 11]
- Glouton
L’algorithme Glouton tente d’optimiser le coût total de l’exploration en fixant à chaque itération la paire robot-frontière ayant le coût minimum. Comme il itère sur les robots .Cet algorithme est en général appliqué de manière centralisée mais si chaque robot dispose de la matrice de coût, son exécution décentralisée est possible (chaque agent exécute l’algorithme jusqu’à obtenir son assignation), [Bautin et al, 11]
[9_implications-politiques-de-exploration-robotique-innovante_22]
Source: Figure 2.15. Illustration de l’allocation de frontière avec l’algorithme glouton [Bautin et al, 11]
Problème d’exploration
L’exploration d’un environnement inconnu est un problème fondamental en robotique mobile.
Elle permet en particulier de construire une carte utile dans de nombreuses applications (reconnaissance, sécurité, assistance, etc). La création d’une carte nécessite la résolution de trois sous-problèmes, la localisation du ou des robots, la cartographie des zones explorées et l’exploration, au sens de la découverte d’un espace inconnu. Nous nous intéressons dans cette partie à ce dernier problème. [ Frédérick, 13]
Les problèmes d’exploration peuvent être classés selon plusieurs aspects : la connaissance de l’environnement, le type d’environnement, le synchronisme des opérations faites par les entités, le nombre d’entités en action, les qualités propres aux entités (p. ex. la capacité sensorielle d’un type d’entité), etc.
Pour les besoins du sujet du présent mémoire, à savoir l’exploration par deux agents mobiles d’un environnement simple et connu, l’état des connaissances sera présenté en utilisant les trois aspects suivant : la connaissance de l’environnement, le nombre d’entités en action, ainsi que le type d’environnement.
La revue de littérature qui suit divisera les travaux connexes à ce mémoire, d’abord selon le niveau de connaissance disponible sur l’environnement et ensuite selon le nombre d’entités en action pour exécuter l’exploration. Finalement, la littérature pertinente sera divisée à nouveau selon le type d’environnement (soit un terrain géométrique, soit un graphe).
Conclusion
Dans ce chapitre, on a basé beaucoup plus sur un état de l’art sur les algorithmes de couverture robot. Nous avons commencé par une définition de couverture, puis nous avons présenté les types des algorithmes existants qui sont classés en général en deux groupes : les algorithmes de couverture pour un seul robot et les algorithmes de couverture pour multi robots, à partir de ces deux types des algorithmes nous avons présenté les plus importants algorithmes de chaque type, en passant par un rappel sur la définition de méthode Spanning trees (ST), puis les définitions et principes des algorithmes Spanning Tree Couvrant (STC) avec ses trois versions ( STC off-line Algorithme STC On-line Algorithme STC Ant-like), passant par Algorithme Spiral, ensuite nous avons présenté les principaux des algorithme MSTC et MRSAM et MCF .
Puis nous avons identifié Les champs de potentiels artificiels, Enfin nous avons terminé par une comparaison des résultats des algorithmes de couverture mono-robot et multi-robots.
L’efficacité des algorithmes d’exploration est souvent évaluée par rapport au chemin le plus court menant au but désiré. Un algorithme d’exploration est dit optimal si le coût du chemin produit par ce dernier n’est pas plus élevé que celui du chemin visitant tous les endroits à explorer à coût minimal.
D’autre part, un algorithme d’exploration est dit « compétitif », si le ratio du coût de ce dernier par rapport au plus petit coût d’un tel chemin est borné par une constante
Questions Fréquemment Posées
Qu’est-ce qu’un environnement inconnu dans le contexte de l’exploration robotique?
Un environnement inconnu est défini par le fait que l’information nécessaire à l’exploration à coût optimal n’est pas disponible lors de l’exécution de l’algorithme d’exploration.
Comment les robots coopèrent-ils pour explorer des environnements inconnus?
Les robots partagent les informations locales récoltées afin que chacun d’entre eux produise une carte similaire fournissant une liste de frontières similaires.
Quelle est la stratégie d’exploration la plus efficace pour les robots dans des environnements inconnus?
Une technique admise comme efficace est l’exploration successive des frontières créées entre les zones non-explorées et les zones explorées accessibles.