PhD Thesis: Minimum Time Search of Mobile Targets in Uncertain Environments

PhD Thesis: Minimum Time Search of Mobile Targets in Uncertain Environments

Lanillos, P. (2013). Minimum Time Search of Mobile Targets in Uncertain Environments. Systems Engineering, Control, Automatics and Robotics group. Computer Architecture and System Engineering Department. Faculty of Computer Science. Complutense University. July 2013.

Download link

Mirror_ English and Spanish version pdf format


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 find 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 processes: the target location estimation using the information collected by the agents, and the planning of the searching routes that the agents must follow to find the target.

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 a heuristic that approximates the expected observation.
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 diffusion control (e.g. oil spill monitoring).

This thesis reveals how to reduce the searching time of a moving target efficiently, 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.