Séminaire départemental – Recherche locale pour la planification de chemins de couverture avec visibilité étendue imparfaite – Vendredi 28 février 2025 – Dominik Richard

Vendredi 28 février 2025

Recherche locale pour la planification de chemins de couverture avec visibilité étendue imparfaite
Dominik Richard
Étudiant au doctorat, laboratoire de programmation par contraintes

Heure: 13h30
Local: PLT-3775

Résumé: La planification des chemins de couverture en robotique mobile et la théorie de la recherche optimale en recherche opérationnelle partagent un même objectif : optimiser la trajectoire d’un chercheur ou d’une équipe de chercheurs. Cependant, le manque d’échanges entre ces deux communautés limite le transfert de connaissances et l’adoption d’algorithmes compatibles. Nous illustrerons ce lien en formulant le problème de planification de chemin de couverture avec visibilité étendue imparfaite, un problème d’optimisation combinatoire formulé pour l’optimisation des chemins de couverture dans le cadre de recherche de mines sous-marines, du point de vue de la recherche optimale. Nous montrons comment des heuristiques développées pour des problèmes théoriques permettent d’améliorer les méthodes de planification. Notamment, nous aborderons:

• Introduction aux concepts de recherche locale stochastique et présentation de l’heuristique LKH, référence pour le célèbre problème du voyageur de commerce.
• Application de LKH à la résolution de sous-problèmes de planification, permettant une réduction de 15 à 25% de la longueur des chemins de couverture.
• Perspectives d’intégration des méthodes heuristiques pour une planification plus efficace en robotique mobile et théorie de la recherche optimale.