## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

# The topography of the environment alters the optimal search strategy for active particles

Edited by David A. Weitz, Harvard University, Cambridge, MA, and approved September 18, 2017 (received for review June 26, 2017)

## Significance

Adopting the right search strategy is of critical importance in a broad range of natural and man-related activities. For example, when foraging in an environment with scarce resources, the search strategy used by animals to look for nourishment is a matter of life or death. It is generally accepted that, under most conditions, the optimal strategy alternates ballistic and diffusive steps. This, however, does not take into account that many search spaces feature complex topographies with boundaries, barriers, and obstacles. Here, we show that the presence of such complexity shifts the optimal strategy toward less ballistic and more diffusive searches.

## Abstract

In environments with scarce resources, adopting the right search strategy can make the difference between succeeding and failing, even between life and death. At different scales, this applies to molecular encounters in the cell cytoplasm, to animals looking for food or mates in natural landscapes, to rescuers during search and rescue operations in disaster zones, and to genetic computer algorithms exploring parameter spaces. When looking for sparse targets in a homogeneous environment, a combination of ballistic and diffusive steps is considered optimal; in particular, more ballistic Lévy flights with exponent

What is the best strategy to search for randomly located resources? This is a crucial question for fields as diverse as biology, genetics, ecology, anthropology, soft matter, computer sciences, and robotics (1, 2). To describe and analyze how a searcher browses the search space, many different plausible models have been proposed, including Brownian motion and intermittent search patterns as well as Lévy flights and walks (1⇓–3). In particular, Lévy statistics, among others models (1), have been successfully used to describe the emergence of optimal search strategies in natural systems at different length scales, from molecular entities (4, 5) to swimming and swarming microorganisms (6⇓–8) to crawling eukaryotic cells (9) to different species of foraging animals (10⇓⇓⇓⇓⇓–16) to human motion patterns (17⇓–19), although in the field of movement ecology there is some controversy on how universal Lévy searches are (20⇓⇓⇓⇓–25). Lévy statistics have also found applications in science and engineering [e.g., for defining the optimal search strategy for robots (26) and for describing anomalous diffusion and navigation on networks (27, 28)].

The strategies based on Lévy statistics can be described under a unified framework, where the searcher is an active particle (29) that performs random jumps (blind search) with lengths

These studies have limited their analysis to landscapes characterized by a barrier-free homogenous topography. However, in realistic scenarios, the environment is often characterized by a more complex topography, where boundaries, barriers, and obstacles play a crucial role in determining the searcher’s motion. Examples of complex search spaces include cytoplasm for molecules within cells (36), biological tissue (or soil) for motile bacteria (37), and patchy landscapes for foraging animals (38). This complexity can significantly influence the long-term behavior of the system under study (39). As it has been recently shown, even a small perturbation, such as an external drift, can shift the optimal search strategy toward more Brownian strategies (40).

Here, by considering a searcher performing a blind cruise search for uniformly distributed nonregenerating sparse targets, we show with numerical simulations and simple scaling arguments that the exponent that optimizes the search strategy depends on the topography of the environment. In particular, we show that, different from the homogeneous case where typically

## Results

### Search in a Homogenous Topography.

We start by analyzing an active particle of radius *A*. The number of targets caught in each run is proportional to the area swept by the capture region surrounding the active particle. We assume the targets to be uniformly distributed, nonregenerating, and scarce (i.e., with density

The active particle performs a run-and-tumble motion (i.e., it has a fixed speed *B*) (2). Asymptotically, this distribution tends to a power law with exponent *A*) (2). Examples of trajectories for various values of *C*: as *D* plots the average number of caught targets

### Search in a Porous Topography.

To understand how the complexity of the environment influences the optimal search strategy, we now consider an active particle looking for targets in a medium with a heterogeneous topography (Fig. 2*A*). Specifically, the search space is now a 2D porous medium composed of uniformly distributed circular interconnected pores with average radius

As it can be seen in Fig. 2*B*, moving in such a porous environment shifts the optimal search strategy toward a more Brownian strategy (*C*). This distribution is well-approximated by a power law with an exponential cutoff at *B*, the boundaries effectively limit the maximum run length, leading the particles to perform a subdiffusive motion rather than a superdiffusive one as in the homogenous environment (Fig. S1*B*); this behavior is in accordance with observations on persistent random walkers in the presence of obstacles (43). Qualitatively, this can also be appreciated by looking at some sample trajectories for different values of *D*): when

### Scaling Arguments.

To formalize the shift in the optimal search strategy caused by the topography of the environment, we define the efficiency *C*), which contribute with higher probability to the capture of new targets. As a consequence, to a first approximation, we obtain that the target capture rate is proportional to the average step length for a given topography and a given *Materials and Methods* discusses their calculation).

While Eq. **4** explicitly depends on the particle’s speed

Using Eq. **5**, we can, therefore, estimate the shift in the optimal search strategy caused by the topography of the environment by finding the maximum of *A*, Eq. **5**, where *y* is the only fitting parameter, reproduces very well the simulated data, and allows us to predict correctly the optimal value for the capture rate in the porous medium from *B*). By comparing model predictions (Fig. 3*C*) with simulated data (Fig. 3*D*), Fig. 3 *C* and *D* shows how, after

For additional confirmation of the fact that the shift in optimal search strategy is caused by the upper spatial cutoff introduced by the topography of the environment, we now consider a porous medium with a convex topography instead of the concave topography considered previously (Fig. 2*A*). In this topography, the particle searches for uniformly distributed targets within an interconnected space containing convex obstacles where there is no upper cutoff (i.e., *A*). Also, in this case, the average radius of the obstacles *B*) as for a particle searching in a homogenous space (Fig. 1*D*). In qualitative terms, these results can be interpreted by observing sample trajectories for various values of *C*): in fact, as can be appreciated from these trajectories, the convex porosity does not prevent the particles from moving ballistically over long distances when the value of

### Search in the Presence of Brownian diffusion.

The results shown so far apply to most length scales as long as properly rescaled to the particle’s radius *A* shows how the optimal search strategy (i.e., the optimal value of *A*, as it shows a clear deviation from the homogenous case (Fig. 1). For a given *C* (Fig. 5 *A* and *B*). However, when *A* and *C*). This shift happens, because the increased rotational diffusion leads to a reduction of the time that the particle spends at the boundaries. This effectively reduces the penalization that boundaries have on more ballistic strategies, thus allowing for the exploration of a greater inner area of the porous structure compared with more diffusive strategies. Reducing *D*). Finally, for even smaller values of *E*), as the increase in rotational diffusion makes persistent motion negligible (29).

## Discussion

Our results show the critical role played by the topography of the environment in determining the optimal search strategy for an active particle with run lengths that are drawn from a Lévy distribution. In particular, the presence of physical boundaries, barriers, and obstacles can introduce a cutoff on the distribution of steps that can penalize more ballistic strategies over more Brownian ones depending on different geometrical parameters connected to the topography of the environment and its interaction with the particle’s motion.

In our model, we assumed that the particle is performing a cruise search with continuous visibility for targets and perfect hitting probabilities. While we do not expect imperfect hitting probabilities to affect the optimality of the search strategy in our case as long as they affect all

Another aspect that can influence the optimal search strategy is the interaction between the searcher and the obstacles encoded in the boundary conditions. In this work, we have implemented reflective boundary conditions, which imply that the searcher stays at the boundary until a random reorientation event makes it point away from the obstacle. This scenario is realistic at the macroscopic and microscopic scales, as, for example, both elementary robots and microswimmers (biological and nonbiological) have been reported to behave in this way (29, 42). Alternatively, different responses can be considered in the presence of boundaries, when information obtained from sensing the surroundings, for example, leads to a voluntary switch in the strategy adopted by the searcher.

As the search time is generally a limiting factor in many realistic search scenarios (1), the searcher was allowed to explore the search space for a finite time in our simulations. Nevertheless, from a fundamental point of view, it would be interesting to study how the optimal search strategy is influenced by the topography of the environment in the limit of infinite search times. In the case of infinite searches, interesting behaviors could emerge as a result of the interplay between the fractal dimensionality of the searcher’s trajectory and that of the environment in a porous topography at the percolation threshold or in a network of channels.

Our findings are mostly scale-invariant and only partially break down at the nanoscopic scale (*E*). This issue can be overcome by reducing the dimensionality of the environment: for example, by introducing a preferential direction of motion with molecular rails. In fact, Lévy-type statistics emerge for molecular motors performing searches on polymer chains, such as DNA (4), or on 1D molecular rails, such as microtubules (5). Similarly, increasing the dimensionality of the system to a 3D space will alter the probability that the searcher goes back to the same point compared with a 2D space, and thus, its optimal search strategy in a complex 3D environment can also be affected.

Our results are relevant for all random search problems where the searcher explores complex search spaces. Examples at various length scales include the rate of molecular encounters in the cytoplasm of cells, the localization of nutrients by motile bacteria in tissue or soil, and the foraging of animals in patchy landscapes as well as search and rescue operations in ruins after natural disasters. Furthermore, similar dynamics could also be applied to optimize navigation in topologically complex networks (27, 28).

## Materials and Methods

### Numerical Simulations.

In our numerical model, we consider active particles of radius

### Calculation of the Average Run Length in a Homogenous Topography.

The average run length in a homogenous environment **1**, can be calculated to be

### Calculation of the Average Run Length in a Porous Topography.

The average run length in a porous environment *C*). As for the homogenous case, the first integral gives a small contribution on the average run length, as it is smaller than **1** (Fig. 1*B*). In general, *C*) and thus, to treat differently the distribution of the run lengths in the porous environment **2**) in the two time intervals. We, therefore, obtain for the two integrals

## Acknowledgments

We thank Jan Wehr for useful discussions on the mathematical part of the manuscript and Erçağ Pinçe, Mite Mijalkov, Geet Raju, and Sylvain Gigan for useful discussions in the initial stages of the project. We also acknowledge the COST (European Cooperation in Science and Technology) Action MP1305 “Flowing Matter” for providing several meeting occasions. Giorgio Volpe acknowledges funding from the Wellcome Trust [204240/Z/16/Z]. Giovanni Volpe acknowledges funding from European Research Council Starting Grant ComplexSwimmers Grant 677511.

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. Email: g.volpe{at}ucl.ac.uk.

Author contributions: Giorgio Volpe designed research; Giorgio Volpe performed research; Giorgio Volpe and Giovanni Volpe analyzed data; and Giorgio Volpe and Giovanni Volpe wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1711371114/-/DCSupplemental.

Published under the PNAS license.

## References

- ↵
- ↵.
- Viswanathan G,
- da Luz M,
- Raposo E,
- Stanley H

- ↵.
- Shlesinger MF,
- Klafter J

- ↵
- ↵.
- Chen K,
- Wang B,
- Granick S

- ↵.
- Ariel G, et al.

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵.
- de Jager M,
- Weissing FJ,
- Herman PMJ,
- Nolet BA,
- van de Koppel J

- ↵
- ↵
- ↵.
- Raichlen DA, et al.

- ↵
- ↵.
- Mashanova A,
- Oliver TH,
- Jansen VAA

- ↵.
- Petrovskii S,
- Mashanova A,
- Jansen VAA

- ↵.
- Humphries NE,
- Weimerskirch H,
- Queiroz N,
- Southall EJ,
- Sims DW

- ↵.
- Jansen VAA,
- Mashanova A,
- Petrovskii S

- ↵
- ↵
- ↵.
- Riascos AP,
- Mateos JL

- ↵.
- Guo Q,
- Cozzo E,
- Zheng Z,
- Moreno Y

- ↵.
- Bechinger C, et al.

- ↵.
- Lomholt MA,
- Tal K,
- Metzler R,
- Joseph K

- ↵
- ↵
- ↵.
- James A,
- Plank MJ,
- Brown R

- ↵.
- Raposo E, et al.

- ↵
- ↵.
- Barkai E,
- Garini Y,
- Metzler R

- ↵.
- Kim MK,
- Ingremeau F,
- Zhao A,
- Bassler BL,
- Stone HA

- ↵.
- Boyer D, et al.

- ↵.
- Pinçe E, et al.

- ↵.
- Palyulin VV,
- Chechkin AV,
- Metzler R

- ↵.
- Volpe G,
- Gigan S,
- Volpe G

- ↵.
- Dimidov C,
- Oriolo G,
- Trianni V

- ↵.
- Chepizhko O,
- Peruani F

- ↵.
- Blumenthal RM,
- Getoor RK

- ↵.
- Haeufle DFB, et al.

- ↵
- ↵.
- Reichhardt C,
- Olson Reichhardt CJ

## Citation Manager Formats

### More Articles of This Classification

### Physical Sciences

### Related Content

- No related articles found.

### Cited by...

- No citing articles found.