An Overview of Algorithmic Methods for Search Optimization. Un Panorama des Méthodes D'Optimisation de L'Effortde Rechercheen Détection

Knowing the probabilities of an object possible positions in a certain space and the constraints relative to the search resource, our aim is to optimize the (spatial, temporal) distribution of the elementary search efforts in order to maximize the (total) probability of target detection. This type of problems is at the origin of many developments, in the field of operations research and is known under the name of "Search Theory". The aim of this article is to provide a panorama of existing methods under assumptions of increasing complexity : fixed target, moving target (e.g. with Markovian trajectory), multi-period search. Finally, we deal with the optimization of the searcher trajectory. 

Résumé 

Connaissant les probabilités de présence d'un objet dans un certain espace et les contraintes sur les efforts de recherche disponibles, on cherche à optimiser la répartition (spatiale, temporelle) des efforts élémentaires afin d'optimiser la probabilité (globale) de détection de cet objet. Ce type de problème est à l'origine de nombreux développements, dans le domaine de la recherche opérationnelle et est connu sous le nom de «Search Theory » (théorie de la recherche). Le but de cet article est de fournir un panorama des méthodes existantes pour résoudre ce problème d'optimisation sous des hypothèses de complexité croissante: cible fixe, mobile, à trajectoire markovienne, recherche simple ou multi-périodes. Enfin, on examine le problème de l'optimisation de la trajectoire de l'observateur (chercheur) . Dans ce cas, la répartition de l'effort de recherche dépend directement de la trajectoire du chercheur.