Search in unknown random environments

$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.

Figure 1

Monte Carlo simulation of the average search time $E\left[T^{\ast }\right]$ until the object sought is found by a single search agent or packet $N=1$; the $x$ axis is the average time-out value of the time-out $r^{-1}$. The packet travels reliably (so that it cannot be destroyed other than at the time out), and from any location it can reach any neighboring location North-East-South-West in one time unit. All nodes operate under “perfect ignorance” $\left(b=0\right)$ so that the packet is equally likely to get further or closer to the destination in one hop. The total distance between the starting point of the search and the location of the object that is sought is $D=10$. After the time out, the sender at the origin where the search initiates will wait on average ten more time units $\left(\mu =0.1\right)$, before sending out another packet. Each point on the curve is the average of 20 simulation runs with the same parameter set.

Figure 2

Monte Carlo simulation results for the average travel time from source to destination for the first among $N$ packets to arrive at the destination, versus $N$ the number of packets that are simultaneously sent. The initial distance is $D=50$, and the average time out is $r^{-1}=600$. Each point on the curve is the average of 40 simulation runs. The intermediate transceivers are placed in a regular rectangular unit grid, and the one time step transmission range of a packet is varied from 6 (top curve) to 16 (bottom curve) hops.

Figure 3

(Color online) The average search time $E\left[T^{\ast }\right]$ until the object is found by a single searcher $\left(N=1\right)$ is plotted using the theoretical analysis (solid line) and Monte Carlo simulations on a rectangular unit grid. There are no losses $\lambda =0$, and $D=10$, $b=0.5$, $c=1$, $\mu =0.1$. Each simulation point on the curve is the average of 20 simulation runs with the same parameter set.

Figure 4

Average search time to find the object versus the average time out $1/r$ for $D=10,\mu =0.1,\lambda =0.1$ and $b=0$ and different values of $N$.

Figure 5

Average search time to find the object versus the average time out $1/r$ for $D=10,\mu =0.1,c=3$ and $b=0.5$ with varying $N$.

Figure 6

Average search time to find the object versus the number of searchers $N$ with $D=10$, $\mu =0.1$, $c=1$, $\lambda =0.01$, and $r=0.02$.

Figure 7

Average search time to find the object versus the number of searchers $N$ with $D=10$, $\mu =0.1$, $b=0.5$, and $r=0.02$.

Figure 8

Lower bound to the expected energy consumption versus the number of searchers. The parameters are $b=0$, $c=1$, $\mu =0.05$, $D=10$ for different values of $\lambda$.

Figure 9

The average energy consumption $J\left(N\right)$ versus the average time out $1/r$ with $b=0.1$, $c=2$, $\lambda =0.01$, $\mu =0.05$, and $D=10$.

Figure 10

(Color online) The average energy consumption $J\left(N\right)$ versus the average time-out $1/r$ with $D=10$, $b=0$, $c=1$, $\mu =0.05$, and $\lambda =0.2$.

Figure 11

The average energy consumption $J\left(N\right)$ versus the average time-out $1/r$ with $D=10$, $b=-0.1$, $c=1$, $\mu =0.01$, and $\lambda =0.05$.

Figure 12

The locus of the average effective packet delay $E\left[T^{\ast }\right]$ and the energy consumption $J\left(N\right)$ when the average time-out $1/r$ is varied. The parameters are $D=10$, $b=0.2$, $c=1$, $\mu =0.05$, and $\lambda =0.01$. For these low packet loss rates, the minimum energy consumption is obtained when the average travel time is also with minimum.

Figure 13

The locus of the average effective packet delay $E\left[T^{\ast }\right]$ and the energy consumption $J\left(N\right)$ when the average time-out $1/r$ is varied. The parameters are $D=10$, $b=0$, $c=1$, $\mu =0.05$, and $\lambda =0.15$. For such high packet loss rates, the minimum effective travel time does not coincide with minimum energy consumption.