Planification de chemins couvrants
Exemple d’une grille 9x14 résolue grâce à l’algorithme du front d’onde.Un problème étudié en planification est le problème de planification de chemins couvrants (Coverage Path Planning, CPP). Ce problème consiste à trouver un chemin qui permet d’explorer l’entièreté d’une région en respectant des contraintes (ex.: éviter des obstacles fixes, utiliser des mouvements simples, etc.), et ce, en minimisant le temps de parcours (ou le nombre de mouvements). Ce problème apparaît dans plusieurs contextes, comme la recherche et sauvetage (search and rescue), le déminage, la reconstitution en 3D de régions survolées par un drone, l’exploration sous-marine avec des véhicules sous-marins autonomes (Autonomous Underwater Vehicles, AUV), le nettoyage de planchers ou de fenêtres, et l’impression 3D.
Malheureusement, aucun planificateur optimal n’existe dans la littérature (autre que la solution naïve). De plus, aucun planificateur de chemins couvrants ne considère l’incertitude, la gestion de ressources et les environnements dynamiques. Dans ce projet, nous avons développé une Librairie C++ de CPP qui contient des algorithmes classiques, tel que l’algorithme du front d’onde, de même que notre planificateur optimal qui utilise la recherche heuristique ainsi que des méthodes séparation-évaluation (branch-and-bound).