Models for Coordinated and Random Searches

Let us now be more specific in describing our search system and application. Our system consists of some number N of identical robotic elements, each of which can move about while carrying an imperfect sensor (in the sense of section 2.3) of nominal range r and detection probability p: any target which lies within a distance r of an element's track is detected with probability p as the element passes by. Targets farther than r are never detected, false alarm detections do not occur, and what action the element might take with detected targets is of no concern. Each element is capable of traveling a total distance d during the mission; this limitation may be due to limited energy storage, or to operational constraints on the duration of the mission, coupled with the maximum speed which can be achieved while operating the sensor payload. Let S be the average number of times that each point in the search area (whose area is A) is sensed; we call S the "sweep fraction" of the search, and calculate it as

S = 2r d N / A (1)

If we let D represent the probability that any given target is detected, or, equivalently, the expected fraction of targets detected, then our first step is to calculate D as a function of S for two candidate search strategies: in the first case, the elements execute a perfectly coordinated search pattern -- we may have only one element following a "lawn-mower" pattern, perhaps by employing a very accurate navigational system, or we may have a number of elements moving in a tightly coordinated formation; in the second case, we employ less expensive elements, capable only of staying within the designated search area, but otherwise wandering completely randomly.

We can also express these two archetypal search strategies in abstract and discretized form to provide the basis for further probabilistic analysis:

We are given an urn containing a very large number of otherwise identical marbles, a small percentage of which bear an invisible mark. We have a machine that can tell us if a marble presented to it is one that bears a mark. The machine is not perfect: it detects a marked marble only with probability p, but it never indicates a false positive. The task is to separate out the marked marbles by running the marbles through the testing machine. The two candidate strategies are:

Coordinated search: we pull marbles at random from the urn and test them on the machine. After testing, we place the unmarked marbles into a second urn. When all the marbles have been tested, we pour these marbles back into the first urn and repeat the process.

Random search: we pull marbles at random from the urn and test them on the machine. After testing, we return each unmarked marble to the urn and mix it thoroughly.

What can we say about these two abstract strategies? First, the coordinated search is clearly superior, since we never test a marble for the nth time until all marbles have been tested n - 1 times (and the more times a marble has been tested, the less likely that it is an undetected marked marble). If p = 1, we will find all the marked marbles by making just one pass (testing each marble just once). On the other hand, with a random search we can never guarantee that we will find all the marked marbles, no matter how many passes we make. The second thing to note is that in order to perform the coordinated search we have to have a second urn; in real life as well, implementing a coordinated search will generally entail additional costs.

In fact, a coordinated search is the best strategy you can employ, and most real world search tactics are designed to achieve a coordinated search. Unfortunately, real world constraints (such as navigation inaccuracies) mean that the results actually achieved usually more closely reflect those of a random search. On the other hand, a random search is not the worst strategy that can be employed, and it is not readily obvious how to realize a deliberately random search of a two dimensional or three dimensional space.

In the marble world abstraction, S measures the average number of times each marble has been tested: the total number of tests we have made divided by the number of marbles in the urn. For the coordinated case, we calculate

D_c = 1 - (1 - p)^Sc (2)

In fact, this equation is true only for integer S, with straight line interpolation between integers, but we won't worry about this approximation for now -- it provides an upper bound on the performance of the coordinated strategy, and the approximation gets very good for large S. On the other hand, we find for the random case (in the limit of infinitely many marbles)

D_r = 1 - e^{- p Sr} (3)

Unlike equation (2), equation (3) is accurate for non-integer S. Figure 2 shows the behaviors of equations (2) and (3) when p = 0.8.

Figure 2. Detect Fraction (D) as a function of Sweep Fraction (S) for sensor probability of detection (p) equal to 0.8. (a) Completely coordinated search strategy, equation (2). (b) Completely random search strategy, equation (3).

Up to Many Robot Systems

Robotics home page

Please address all questions and comments to: robo-web@spawar.navy.mil
Last update: 1 December 1998.