Búsqueda de objetivos móviles en tiempo mínimo sobre entornos con incertidumbre. Minimum time search of moving targets in uncertain environments

摘要

Esta tesis aborda el desarrollo de un sistema autónomo para buscar un objetivo móvil en el menor tiempo posible sobre un entorno con incertidumbre, es decir, para resolver el problema de búsqueda de tiempo mínimo, que se presenta como un problema especial dentro de la teoría de búsqueda óptima. Se propone una solución Bayesiana para encontrar el objetivo utilizando varios agentes móviles con dinámica restringida provistos de sensores que proporcionan información del entorno. La búsqueda de tiempo mínimo involucra dos procesos: la estimación de la ubicación del objetivo a partir de la información recogida por los agentes que cooperan en la búsqueda, y el diseño de la planificación de las rutas que deben seguir los agentes para encontrar el objetivo. La estimación de la ubicación del objetivo se aborda utilizando técnicas Bayesianas, más específicamente, el filtro recursivo Bayesiano. Además, se propone un filtro de información, basado en el filtro de Kalman extendido, que afronta el problema de los retrasos en la comunicación (problema de medidas desordenadas). La planificación de las trayectorias de los agentes se plantea como un problema de decisión secuencial donde, a partir de la estimación de la ubicación del objetivo, se calculan las mejores acciones que los agentes tienen que realizar. Para ello se proponen tres estrategias Bayesianas: minimización del tiempo local de detección esperado, maximización de la probabilidad de detección descontada por una función dependiente del tiempo, y optimización de una función probabilística que integra una heurística que aproxima la observación esperada. Para implementar las estrategias se proponen tres soluciones. La primera, basada en la programación con restricciones, ofrece soluciones exactas para el caso discreto cuando el objeto es estático y el número de variables de decisión pequeño. La segunda es un algoritmo aproximado construido a partir del método de optimización de entropía cruzada que aborda el caso discreto para objetos dinámicos. La tercera es un algoritmo descentralizado basado en el método del gradiente que calcula decisiones en un horizonte limitado, teniendo en cuenta el futuro, en el caso continuo. Los problemas de búsqueda de tiempo mínimo se encuentran en el planteamiento de muchas aplicaciones reales, como son las operaciones de emergencia de búsqueda y rescate (p.e. rescate de náufragos en accidentes marítimos) o el control de la difusión de sustancias contaminantes (p.e. monitorización de derrames de petróleo). Esta tesis muestra cómo reducir el tiempo de búsqueda de un objeto móvil de forma eficiente, determinando qué estrategias de búsqueda tienen en cuenta el tiempo y bajo qué condiciones son válidas, y proporcionando algoritmos polinómicos que calculen las acciones que los agentes tienen que realizar para encontrar el objeto.udud[ABSTRACT]This thesis is concerned with the development of an autonomous system to search a dynamic target in the minimum possible time in uncertain environments, that is, to solve the minimum time search problem, which is presented as an especial problem within the optimal search theory. This work proposes a Bayesian approach to nd the target using several moving agents with constrained dynamics and equipped with sensors that provide information about the environment. The minimum time search involves two process: the target location estimation using the information collected by the agents, and the planning of the searching routes that the agents must follow to nd the target. The target location estimation is tackled using Bayesian techniques, more precisely, the recursive Bayesian lter. Moreover, an improved information lter, based on the extended Kalman lter, that deals with the team communication delays (i.e. out of sequence problem) is presented. The agents trajectory planning is faced as a sequential decision making problem where, given the a priori target location estimation, the best actions that the agents have to perform are computed. For that purpose, three Bayesian strategies are proposed: minimizing the local expected time of detection, maximizing the discounted time probability of detection, and optimizing a probabilistic function that integrates an heuristic that approximates the expected observation. To implement the strategies, three solutions are proposed. The rst one, based on constraint programming, provides exact solutions in the discrete case when the target is static and the number of decision variables is small. The second one is an approximated algorithm stood on the cross entropy optimization method that tackles the discrete case for dynamic targets. The third solution is a gradient-based decentralized algorithm that achieves non-myopic solutions for the continuous case. The minimum time search problems are found inside the core of many real applications, such as search and rescue emergency operations (e.g. shipwreck accidents) or pollution substances di usion control (e.g. oil spill monitoring). This thesis reveals how to reduce the searching time of a moving target e ciently, determining which searching strategies take into account the time and under which conditions are valid, and providing approximated polynomial algorithms to compute the actions that the agents must perform to find the target.