Search in unknown random environments

Abstract

$N$ searchers are sent out by a source in order to locate a fixed object which is at a finite distance $D$, but the search space is infinite and $D$ would be in general unknown. Each of the searchers has a finite random lifetime, and may be subject to destruction or failures, and it moves independently of other searchers, and at intermediate locations some partial random information may be available about which way to go. When a searcher is destroyed or disabled, or when it “dies naturally,” after some time the source becomes aware of this and it sends out another searcher, which proceeds similarly to the one that it replaces. The search ends when one of the searchers finds the object being sought. We use $N$ coupled Brownian motions to derive a closed form expression for the average search time as a function of $D$ which will depend on the parameters of the problem: the number of searchers, the average lifetime of searchers, the routing uncertainty, and the failure or destruction rate of searchers. We also examine the cost in terms of the total energy that is expended in the search. DOI: http://dx.doi.org/10.1103/PhysRevE.82.061112 ©2010 The American Physical Society