Programme de doctorat Département d’informatique et de génie logiciel
Faculté des sciences et de génie
PROPOSITION DE RECHERCHE
de
Dominik Richard
Le mercredi 29 janvier 2025 à 9h00, Local PLT-3904, Pavillon Adrien-Pouliot
TITRE : Planification de chemin de recherche et de couverture
Sous-titre : Recherche de voisinage et décomposition de problème
Directeur :
Michael Morin
Co-directeur :
Claude-Guy Quimper
Autres membres du comité d’évaluation :
Irène Abi-Zeid
Philippe Giguère
Résumé
La planification des chemins de couverture, en robotique mobile, et la théorie de la recherche optimale, en recherche opérationnelle, sont deux disciplines qui s’intéressent à la planification du chemin d’un chercheur ou des chemins d’une équipe de chercheurs. Cependant, des conventions et un bagage différent entre ces deux communautés rendent les échanges de connaissances rares. Du point de vue modélisation et algorithmique, il en résulte un manque à gagner, de chaque côté, qui pourrait être comblé en unifiant les formalismes pour recourir à des algorithmes compatibles. Dans cette thèse, notre objectif est d’améliorer les méthodes heuristiques pour la planification des chemins de couverture et de recherche, en particulier pour des équipes de robots collaboratifs, et ce en exploitant les similarités de ces problèmes, même s’ils sont généralement traités par des communautés scientifiques différentes. Dans notre contexte d’application, des capteurs permettent la détection de l’objet recherché, mais divers facteurs techniques et environnementaux limitent leurs capacités. Plus spécifiquement, nous traiterons du problème du CPPIED, qui permet de planifier un chemin de couverture avec visibilité imparfaite et distante, et du problème de l’OSPV qui permet de planifier un chemin de recherche en considérant la visibilité distante. Un plan de couverture permet l’inspection exhaustive d’une région d’intérêt sans tenir compte de la présence ou de l’absence d’une cible, tandis qu’un plan de recherche utilise les informations disponibles sur la localisation et les mouvements de la cible afin d’en optimiser sa détection. Notre hypothèse est que, bien que l’OSPV ait été formulé en recherche opérationnelle et que le CPPIED provienne de la robotique, ces deux problèmes peuvent partager un même formalisme mathématique. Nous soutenons aussi que l’OSPV et le CPPIED sont étroitement liés aux problèmes de tournée de véhicules avec couverture spatiale de la recherche opérationnelle, où les heuristiques de recherche locale constituent des approches de référence pour de nombreux cas. Néanmoins, les heuristiques de recherche de voisinage sont peu développées dans le contexte des problèmes de couverture et de recherche optimale. Ainsi, le développement d’une recherche locale stochastique et d’une recherche à voisinage large pour ces problèmes pourrait bénéficier tant à la robotique mobile qu’à la recherche opérationnelle. Également, nous proposons d’associer ces heuristiques de recherche de voisinage à une méthode établie de décomposition de problèmes pour faire progresser l’état de l’art sur la résolution de leur généralisation au cas de plusieurs chercheurs homogènes.
Abstract
Coverage path planning and optimal search theory, as studied in the fields of mobile robotics and operational research, are both concerned with the path planning of a searcher or a team of searchers. Yet, different conventions make exchange of knowledge rare. From a modeling and algorithmic perspective, it leads to a gap that could be fulfilled by unifying the formalisms of both fields and designing compatible heuristics. Hence, in this thesis, our objective is to improve heuristic approaches to coverage and optimal search path planning for both single and multiple searchers, particularly for teams of collaborative robots. It will be done by exploiting the similarities of specific problems, even though they are generally treated by different communities. In our application field, robot sensors allow object detection, but their capacities are limited by technical and environmental factors. In particular, we deal with the coverage path planning with imperfect extended detection (CPPIED) problem, modeling of sidescan sonars’ imperfections in complex terrain, and the optimal searcher path with interregion visibility (OSPV) problem, modeling distant imperfect visibility while searching for a mobile target. A coverage plan allows for exhaustive inspection of one or multiple area of interest, while a search plan aim at optimizing the detection of a target by using prior information on its position and its movements. Despite their distinct origins, our hypothesis is that both problems can share a unified mathematical framework. We contend that both the OSPV and CPPIED relate closely to vehicle routing problems with spatial coverage inherent to the operational research community. Efficient local search heuristics frequently serve as reference algorithms for these problems. However, we observed that neighborhood search algorithms remain underdeveloped in the context of optimal search and coverage problems. As a result, the advancement of stochastic local search and large neighborhood search algorithms could significantly benefit both fields — mobile robotics and operational research. Moreover, we propose that integrating the effective neighborhood search heuristics developed in this project with established logic-based problem decomposition methods should push the boundaries of current methodologies in the case of a generalization to a team of homogenous searchers. Such decomposition methods have already shown great results in related search problems, as they allow tackling NP-Hard problems efficiently.
Bienvenue à tous !
