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.

Abstract

This thesis addresses the problem of optimal search for a static target randomly hidden in a discrete environment, and whose location is correlated with another static object. We propose a model-based framework to solve this problem optimally. The objects’ correlation is modeled as a joint probability distribution, representing the searcher’s belief about the objects’ possible locations. We use Bayesian inference to update the searcher’s belief after each unsuccessful search. We propose a solution based on dynamic programming to compute the theoretically optimal policy, which leverages the information gain from detecting the related object during the search. While the proposed dynamic programming method provides a benchmark, it is computationally intractable for large-scale problems due to the curse of dimensionality. This motivates the development and the use of scalable approximate methods for practical purposes. We investigate two distinct heuristic approaches: an online planning method based on k−step lookahead and an offline, model-free Deep Q-Network algorithm. By comparing performances of these heuristics against both the DP solution and a baseline myopic (greedy) policy, this study analyzes the trade-offs between optimality and computational efficiency in the two-object search problem with correlated objects.