Robustness of optimal random searches in fragmented environments

The random search problem is a challenging and interdisciplinary topic of research in statistical physics. Realistic searches usually take place in nonuniform heterogeneous distributions of targets, e.g., patchy environments and fragmented habitats in ecological systems. Here we present a comprehensive numerical study of search efficiency in arbitrarily fragmented landscapes with unlimited visits to targets that can only be found within patches. We assume a random walker selecting uniformly distributed turning angles and step lengths from an inverse power-law tailed distribution with exponent $\mu$. Our main finding is that for a large class of fragmented environments the optimal strategy corresponds approximately to the same value ${\mu }_{\mathrm{opt}}\approx 2$. Moreover, this exponent is indistinguishable from the well-known exact optimal value ${\mu }_{\mathrm{opt}}=2$ for the low-density limit of homogeneously distributed revisitable targets. Surprisingly, the best search strategies do not depend (or depend only weakly) on the specific details of the fragmentation. Finally, we discuss the mechanisms behind this observed robustness and comment on the relevance of our results to both the random search theory in general, as well as specifically to the foraging problem in the biological context.

Figure 1

Fragmented search space of area $A=M\times M$ with $N_p$ circular patches $(N_p=3$ in this example). The patch $n$ $\left(n=1,2,...,N_p\right)$ contains $N^{\left(n\right)}$ targets homogeneously distributed in an area $\pi {R^{\left(n\right)}}^2$. The average separation between neighbor targets in patch $n$ is denoted by $l_t^{\left(n\right)}$.

Figure 2

Illustration of a sequence of random steps evolving according to the search dynamical rules (i) and (ii), Sec. 2.

Figure 3

Average distance traversed $L$ and the number of steps $\nu$ necessary to detect for the first time the single patch $\left(R=0.2M\right)$ as a function of $\mu$ in log-linear plots. The ballistic dynamics $\mu \to 1^{+}$ emerges as the search strategy that minimizes both quantities, representing the most efficient way to find the patch (but not the targets). Here $L(\mu =2)/L(\mu =1.1)=2.87$ and $\nu (\mu =2)/\nu (\mu =1.1)=187$.

Figure 4

Average distances traversed (a) inside $L_{\mathrm{in}}$ and (b) outside $L_{\mathrm{out}}$ a single patch (with $R=0.2M$ and $l_t=10r_v)$ as function of $\mu$. The search task is to find $T={10}^4$ targets. (c) Average total distance traversed, $L=L_{\mathrm{in}}+L_{\mathrm{out}}$.

Figure 5

Average efficiency $\eta$ (multiplied by $l_t^2$ to put all curves in a same scale) to find $T={10}^4$ targets vs $\mu$, with $R=0.2M$ and different $l_t$. Inset: the same plot for $R=0.05M$ and $l_t=10r_v$. In each case, the ${\mu }_{\mathrm{opt}}$ value is indicated.

Figure 6

(a) Comparison between patches of same targets $\rho$ but with different radii $R$. Clearly, for smaller values of $R$ the searcher leaves the patch more often. (b) Patches of same $R$ but with different $\rho$. For higher densities, the truncation of a step $j$ due to an encounter [rule (ii) of Sec. 2] is more frequent, leading to a swept area in the form of a truncated (shorter than ${\ell }_j)$ strip [step (t)]. In lower densities, long “corridors” crossing the whole (or almost the whole) patch without a detection event [step (nt)] can take place, especially in the ballistic limit.

Figure 7

Search paths to find $T=100$ targets in a single patch, $R=0.2M$ and $l_t=10r_v$. (a),(b) In the ballistic limit, $\mu =1.1$, from the starting position (s.p.) in the empty region the searcher readily finds the patch (gray region). Subsequently, the searcher leaves the patch and returns to it frequently. The encounters of targets within the patch are indicated in (b) by small circles. (c),(d) For the optimal strategy, $\mu =2$, the search is completed with only one visit to the patch. Detail of the patch in (d) shows that the targets found are grouped in a small area. (e),(f) In the Brownian case, $\mu =3$, typical short steps make the first finding of the patch more difficult. The search process inside the patch, shown in (f), takes place in a rather small area, if compared to the scales in (b) and (d).

Figure 8

Locations of the $T={10}^4$ targets found (black dots) along a search with $R=0.2M$ for $\mu =1.1$, 2, 3, and average separations between targets (a) $l_t=10r_v$ and (b) $l_t=100r_v$.

Figure 9

Typical trajectories (along which the searcher finds $T={10}^3$ targets) for a fragmented landscape with $N_p=10$ identical patches (gray regions). Here, $R=0.1M$ and $l_t=10r_v$. (a) In the ballistic regime $\mu =1.1$, the searcher visits seven patches. This number gradually decreases as the Brownian limit approaches: (b) three visited patches in the optimal strategy with $\mu =2$ and (c) only one patch visited for $\mu =3$.

Figure 10

Trajectories in a fragmented landscape with $N_p=10$ heterogeneous patches (gray regions). The searcher finds $T=10$ targets using ballistic $\left(\mu =1.1\right)$, optimal $\left(\mu =2\right)$, and Brownian $\left(\mu =3\right)$ strategies. The darker the patch, the higher its target density. (a) Patches with same density, $l_t=10r_v$, and radii uniformly distributed in the range $0.03M\le R^{\left(n\right)}\le 0.3M$. (b) Patches with same radius, $R^{\left(n\right)}=0.1M$, and densities uniformly distributed in the interval $5r_v\le l_t\le 350r_v$. (c) Patches with distinct sizes, but fixed number of targets inside $\left({10}^3\right)$, so that the smallest (largest) patches are also the densest (scarcest) ones. In this case, neighbor targets distances vary uniformly in the range $17r_v\le l_t\le 170r_v$.

Figure 11

Average distances (along a search for $T={10}^4$ targets) traversed (a) inside $\left[L_{\mathrm{in}}\right]$ and (b) outside $\left[L_{\mathrm{out}}\right]$ $N_p=10$ identical patches $\left(R=0.1M,l_t=10r_v\right)$ as function of $\mu$. (c) $L=L_{\mathrm{in}}+L_{\mathrm{out}}$.

Figure 12

Percentage of distinct visited patches vs $\mu$ along a search for $T={10}^4$ targets in a landscape with $N_p=10$ and $N_p=5$ (inside) identical patches. Here $R=0.1M$.

Figure 13

Scaled average search efficiency $\eta l_t^2$ along a search for $T={10}^4$ targets as a function of $\mu$ in a fragmented landscape with $N_p=10$ and $N_p=5$ (inset) identical patches of $R=0.1M$. The ${\mu }_{\mathrm{opt}}$ values are also indicated.

Figure 14

Percentage of distinct visited patches vs $\mu$ along a search for $T={10}^4$ targets in a landscape with $N_p=10$ and $N_p=5$ (inside) heterogeneous patches. (a) Patches of a same ${ł}_t$, but radii uniformly drawn from $0.03M\le R\le 0.3M$. (b) Patches of radius $R=0.1M$, but neighbor targets distances uniformly drawn from $5r_v\le l_t\le 350r_v$. Due to the discussed mechanisms (main text), the $\%$ variation of visited patches in the entire range $1<\mu \le 3$ in (b) is much smaller than in (a).

Figure 15

Search efficiency $\eta$ vs $\mu$ along a search for $T={10}^4$ targets in a fragmented landscape with $N_p=10$ and $N_p=5$ heterogeneous patches [parameters as in Fig. 10]. For both $N_p^{\prime }s,{\mu }_{\mathrm{opt}}\approx 2$.