Optimal searcher distribution for parallel random target searches

We consider a problem of finding a target located in a finite $d$-dimensional domain, using $N$ independent random walkers, when partial information about the target location is given as a probability distribution. When $N$ is large, the first-passage time sensitively depends on the initial searcher distribution, which invokes the question of the optimal searcher distribution that minimizes the first-passage time. Here, we analytically derive the equation for the optimal distribution and explore its limiting expressions. If the target volume can be ignored, the optimal distribution is proportional to the target distribution to the power of one third. If we consider a target of a finite volume and the probability of the initial overlapping of searchers with the target cannot be ignored in the large $N$ limit, the optimal distribution has a weak dependence on the target distribution, with its variation being proportional to the logarithm of the target distribution. Using Langevin dynamics simulations, we numerically demonstrate our predictions in one and two dimensions.

Figure 1

Schematic picture of a random target search by multiple searchers as the partial information of target position is given. When a target (bigger circle in blue) is located according to a probability distribution (solid line), various distributions of initial searcher positions (dashed and dotted lines, with searchers as red smaller circles) can be considered to minimize the search time.

Figure 2

The inverse of the search times for various target and searcher distributions in one dimension. The symbols are obtained by averaging the search times recorded in the Langevin dynamics simulations over many realizations of the target and the searcher initial positions. The lines are analytic results obtained using Eq. (17). The parameters used are $N={10}^4$, $\sigma =0.35L$ (Gaussian), and $\sigma =0.2L$ (Lorentz). The search times are obtained by taking averages over ${10}^3$ independent samples. The system size is $L=100a$, where $a$ is a unit length, and typical step size of the random walk is $0.01a$. For comparison, a system with periodic boundary conditions, instead of reflective boundary conditions, is also considered for the Gaussian initial distribution with the same parameters (blue triangles).

Figure 3

The inverse of the search times vs $\gamma /N$ for a finite-sized target in a two-dimensional circular domain. The symbols indicate average search times measured from the Langevin dynamics simulations for various values of $N$. The dotted line indicates the value of $\gamma /N$ specified by Eq. (23). Inset: The inverse of the search times with respect to $\gamma$. The parameters used are as follows: the target radius $a=1$ (taken as a unit length), the domain radius $L=20$, and $\sigma =0.5L$ for the target distribution. To obtain the average search time by $N$ searchers, we gathered the search times of independent realizations of initial configurations until ${10}^7/N$ nonzero search times were recorded. The typical step size of searchers per each time step is $0.01a$.