Abstract:
The main contribution of this paper is an algorithm
for autonomous search that minimizes the expected time for
detecting multiple targets present in a known built environment.
The proposed technique makes use of the probability distribution
of the target(s) in the environment, thereby making it feasible to
incorporate any additional information, known a-priori or
acquired while the search is taking place, into the search
strategy. The environment is divided into a set of distinct regions
and an adjacency matrix is used to describe the connections
between them. The costs of searching any of the regions as well as
the cost of travel between them can be arbitrarily specified. The
search strategy is derived using a dynamic programming
algorithm. The effectiveness of the algorithm is illustrated using
an example based on the search of an office environment. An
analysis of the computational complexity is also presented.
