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.

I. Introduction

The search of an object with uncertain location has been widely studied since in 1975 “Theory of Optimal Search” was published [1]. That mathematical analysis collected all the research derived from searching applications of the II world war. They solved with beauty two complementary objectives of the search: detect the target with (1) the smallest cost and (2) in minimum time. The approach has one main drawback because they assumed that the space is infinitely divisible (i.e. there is not searcher dynamics involved). Few years later a doctor on Naval engineering published a mathematical model adding constraints to the searcher path [2]. He set out the search as a Partially Observable Markov Decision Process (POMDP), leaving the grounds to some branch and bound algorithms and POMDP solutions [3], [4]. The algorithmic complexity is demonstrated to be NP-complete or NP-hard, depending on the problem formulation [5]. Afterwards, with the arrival of the swarms fever and the unmanned vehicles, and due to lower costs and miniaturization [6], a new research impulse appears where instead of one agent searching, there are many [7], [8], [9], [10]. Using a multi-agent set up, it is proved that the complexity rises up to NEXP-complete [11], but simplifying the communications and modeling the information as a common layer the problem has been partially solved by gradient base approaches [12].