Two-Object Search: Optimal Search of a Correlated Target

Ce mémoire aborde le problème de la recherche optimale d’une cible statique cachée aléatoirement dans un environnement discret, et dont l’emplacement est corrélé avec un deuxième objet également statique. Nous proposons une approche basée sur des modèles pour résoudre ce problème de manière optimale. La corrélation entre objets est modélisée comme une distribution de probabilité conjointe, représentant la croyance du chercheur sur les emplacements possibles des objets. Nous utilisons l’inférence bayésienne pour mettre à jour cette croyance après chaque recherche infructueuse. Nous utilisons la programmation dynamique pour déterminer la politique optimale, qui tire parti du gain possible d’information que le deuxième objet peut fournir, s’il est détecté au cours de la recherche. Bien que cette approche basée sur la programmation dynamique fournisse un point de référence, elle est computationnellement difficile pour les problèmes à grande échelle en raison du fléau de la dimensionnalité. Cet écart entre l’optimalité théorique et la faisabilité pratique motive le développement et l’évaluation de méthodes approximatives. Nous étudions deux approches heuristiques distinctes : une méthode de planification en ligne de type k-steps (anticipation de k étapes) et une méthode hors ligne, sans modèle, utilisant l’algorithme Deep Q-Network. En comparant ces heuristiques à la solution optimale de la programmation dynamique et à une politique myope de base (gloutonne), cette étude fournit une analyse des compromis entre l’optimalité et l’efficacité computationnelle dans le problème de recherche de deux objets corrélationnels.