Minimum time search for lost targets using cross entropy optimization

This paper formulates and proposes a discrete solution for the problem of finding a lost target under uncertainty in minimum time (Minimum Time Search). Given a searching region where some information about the target is known but uncertain (i.e. location and dynamics), and a searching agent with constrained dynamics, we provide two decision making algorithms that optimizes the agent actions to find the target in a minimum time. The problem is faced as a discrete optimization: the actions and the sensor are discrete, and the target probabilistic model is described over a graph, where each vertex contains the target's location probability information and each edge defines the agent possible actions. We revisit the mathematical model of the optimal search problem and we propose a novel approach to include the time into the decision making by reinterpreting it as a maximum discounted time reward problem. The optimal decision plan for the agent is obtained by solving this non convex discrete problem using the cross entropy method. By performing statistical simulations we show how the target is found in minimum time.