#explorebycreative Episode hors-série : Acceptation RA-L
L'article d'aujourd'hui est dédié à notre actualité, avec une nouvelle importante : notre article, soumis à la prestigieuse revue IEEE RA-L et qui sera présenté à ICRA 2024, a été accepté par les relecteurs et sera présenté au Japon en mai !
Intitulé “Skeleton Disk-Graph Roadmap: A Sparse Deterministic Roadmap For Safe 2D Navigation and Exploration” (Graphe de disques basé squelette: un graphe déterministe et économe pour une navigation et une exploration sûres en 2D), cet article est le fruit des travaux menés sur le projet Explore, qui vise à l’exploration et la reconstruction 3D d’un environnement intérieur, en autonomie par un robot.
La méthode que nous présentons dans cet article porte sur la planification des mouvements du robot, c’est-à-dire sur la détermination de ses objectifs d’exploration et du chemin pour y parvenir en fonction de sa connaissance actuelle de l’environnement. Ici, l’environnement est représenté par une carte en 2D (fournie par le module de perception) où apparaissent les obstacles, à la manière d’un plan.
Planification de chemins
Intéressons-nous dans un premier temps à la planification des chemins, en supposant que le robot ait déterminé un objectif. Les méthodes actuelles dans ce domaine sont généralement limitées par une balance nécessaire entre leur coût en termes de puissance de calcul (limitant les possibilités d’embarquer ces méthodes) et leur fiabilité (garanties de découverte et d’optimalité des chemins). Dans un cadre d’exploration, nous avons choisi de prioriser, dans l’ordre, les objectifs suivants:
- couverture : notre algorithme doit être capable de fournir des chemins vers toute zone accessible
- sûreté : les chemins calculés doivent respecter une distance de sécurité minimale avec les obstacles
- longueur : les chemins calculés doivent être le plus courts possibles
Pour atteindre ces objectifs, nous nous sommes appuyés principalement sur des méthodes de traitement géométriques de la carte. Les grandes lignes de notre algorithme peuvent être résumées de la manière suivante:
- extraction du squelette géométrique de la carte, c’est-à-dire l’ensemble des points équidistants d’au moins 2 obstacles;
- compression du squelette sous forme de graphe où chaque sommet représente une bulle d’espace libre (disque navigable de manière sûre dans l’environnement)
- recherche rapide de chemins sur le graphe (Dijkstra, A*)
La nouveauté de notre méthode réside dans la combinaison de l’extraction du squelette, très rapide mais difficilement exploitable telle quelle, avec la notion de bulles d’espace libre, qui permettent de structurer l’information du squelette sous forme de graphe léger. Nous montrons dans l’article que cet algorithme couvre bien la totalité des zones accessibles, et qu’il fournit des chemins plus sûrs que les méthodes actuelles tout en sacrifiant très peu de longueur comparé à un chemin de longueur optimale.
Stratégie d’exploration
Revenons à la détermination des objectifs du robot: une approche souvent utilisée pour l’exploration autonome est l’exploration basée frontières. La carte de l’environnement est utilisée pour déterminer les limites entre les zones libres et inconnues; la plus proche est alors sélectionnée comme prochain objectif. Cette approche peut être raffinée par d’autres critères (sûreté, observations attendues) mais restent souvent coûteuses car basées sur la carte de l’environnement, qui tend à devenir de plus en plus grande au cours de l’exploration.
Or, les bulles d’espace libre de notre graphe de navigation permettent de vérifier simplement si la zone correspondante dans l’environnement contient une frontière et de limiter localement les recherches si nécessaire. Notre méthode a donc le double avantage de fournir des chemins de haute qualité pour n’importe quelle tâche de navigation, tout en étant facilement étendue à une stratégie d’exploration basée frontières qui tire directement profit du graphe de navigation.
La méthode et les résultats d’exploration, obtenus dans 2 environnements simulés de grande taille et 3 environnements réels, sont illustrés dans la vidéo ci-dessus !
Pour en savoir plus:
- L’article au complet : https://hal.science/hal-04282634
- Plus d'articles sur Explore :
- https://blog.groupe-creative.fr/explorebycreative-episode-6-le-robot-operating-system-ros/
- https://blog.groupe-creative.fr/explorebycreative-episode-5/