Abstract FR:

Nous présentons une méthode générale de planification en robotique: l'algorithme Fil d’Ariane. Cet algorithme est composé de deux sous-algorithmes SEARCH et EXPLORE. L'algorithme EXPLORE collecte des informations sur l'espace accessible depuis la position initiale en posant des balises dans l'espace de recherche. SEARCH utilise une méthode locale pour atteindre la position finale à partir des balises posées. Apres la présentation de quelques définitions de base nous présentons les fondements théoriques de l'algorithme Fil d’Ariane et nous montrerons que SEARCH et EXPLORE sont exprimés tous les deux comme des algorithmes d'optimisation. Nous montrons que EXPLORE permet d'approcher l'espace accessible avec une résolution arbitraire en un nombre fini d'itérations. Nous présentons deux planificateurs basés sur l'algorithme Fil d’Ariane: le premier est un planificateur de trajectoires pour un robot mobile holonome, et le deuxième, notre expérimentation principale, un planificateur de trajectoires pour un bras manipulateur a six degrés de liberté. Pour ce dernier, nous avons réalisé une implantation de notre algorithme sur une machine massivement parallèle