Optimal search strategies of run-and-tumble walks

Smart active particles learn and transcend bacterial foraging strategies

Throughout evolution, bacteria and other microorganisms have learned efficient foraging strategies that exploit characteristic properties of their unknown environment. While much research has been devoted to the exploration of statistical models describing the dynamics of foraging bacteria and other (micro-) organisms, little is known, regarding the question of how good the learned strategies actually are. This knowledge gap is largely caused by the absence of methods allowing to systematically develop alternative foraging strategies to compare with. In the present work, we use deep reinforcement learning to show that a smart run-and-tumble agent, which strives to find nutrients for its survival, learns motion patterns that are remarkably similar to the trajectories of chemotactic bacteria. Strikingly, despite this similarity, we also find interesting differences between the learned tumble rate distribution and the one that is commonly assumed for the run and tumble model. We find that these differences equip the agent with significant advantages regarding its foraging and survival capabilities. Our results uncover a generic route to use deep reinforcement learning for discovering search and collection strategies that exploit characteristic but initially unknown features of the environment. These results can be used, e.g., to program future microswimmers, nanorobots, and smart active particles for tasks like searching for cancer cells, micro-waste collection, or environmental remediation.

Size-dependent self-avoidance enables superdiffusive migration in macroscopic unicellulars

Many cells face search problems, such as finding food, mates, or shelter, where their success depends on their search strategy. In contrast to other unicellular organisms, the slime mold Physarum polycephalum forms a giant network-shaped plasmodium while foraging for food. What is the advantage of the giant cell on the verge of multicellularity? We experimentally study and quantify the migration behavior of P. polycephalum plasmodia on the time scale of days in the absence and presence of food. We develop a model which successfully describes its migration in terms of ten data-derived parameters. Using the mechanistic insights provided by our data-driven model, we find that regardless of the absence or presence of food, P. polycephalum achieves superdiffusive migration by performing a self-avoiding run-and-tumble movement. In the presence of food, the run duration statistics change, only controlling the short-term migration dynamics. However, varying organism size, we find that the long-term superdiffusion arises from self-avoidance determined by cell size, highlighting the potential evolutionary advantage that this macroscopically large cell may have.

Active search for a reactive target in thermal environments

We study a stochastic process where an active particle, modeled by a one-dimensional run-and-tumble particle, searches for a target with a finite absorption strength in thermal environments. Solving the Fokker-Planck equation for a uniform initial distribution, we analytically calculate the mean searching time (MST), the time for the active particle to be finally absorbed, and show that there exists an optimal self-propulsion velocity of the active particle at which MST is minimized. As the diffusion constant increases, the optimal velocity changes from a finite value to zero, which implies that a purely diffusive Brownian motion outperforms an active motion in terms of searching time. Depending on the absorption strength of the target, the transition of the optimal velocity becomes either continuous or discontinuous, which can be understood based on the Landau approach. In addition, we obtain the phase diagram indicating the passive-efficient and the active-efficient regions. Finally, the initial condition dependence of MST is presented in limiting cases.

Optimal escapes in active matter

The out-of-equilibrium character of active particles, responsible for accumulation at boundaries in confining domains, determines not-trivial effects when considering escape processes. Non-monotonous behavior of exit times with respect to tumbling rate (inverse of mean persistent time) appears, as a consequence of the competing processes of exploring the bulk and accumulate at boundaries. By using both 1D analytical results and 2D numerical simulations of run-and-tumble particles with different behaviours at boundaries, we scrutinize this very general phenomenon of active matter, evidencing the role of accumulation at walls for the existence of optimal tumbling rates for fast escapes.

Searching for a partially absorbing target by a run-and-tumble particle in a confined space

A random search of a partially absorbing target by a run-and-tumble particle in a confined one-dimensional space is investigated. We analytically obtain the mean searching time, which shows a nonmonotonic behavior as a function of the self-propulsion speed of the active particle, indicating the existence of an optimal speed, when the absorption strength of the target is finite. In the limit of large and small absorption strengths, respectively, asymptotes of the mean searching time and the optimal speed are found. We also demonstrate that the first-passage problem of a diffusive run-and-tumble particle in high dimensions can be mapped into a one-dimensional problem with a partially absorbing target. Finally, as a practical application exploiting the existence of the optimal speed, we propose a filtering device to extract active particles with a desired speed and evaluate how the resolution of the filtering device depends on the absorption strength.

Optimizing search processes with stochastic resetting on the pseudofractal scale-free web

The pseudofractal scale-free web (PSFW) is a well-known model for a scale-free network with small-world characteristics. Understanding the dynamic properties of this network can provide valuable insights into dynamic processes occurring in general scale-free and small-world networks. In this study we investigate search processes using discrete-time random walks on the PSFW to reveal the impact of the resetting position on optimizing search efficiency, as measured by the mean first-passage time (MFPT). At each step the walker has two options: with a probability of 1-γ, it moves to one of the neighboring sites, and with a probability of γ, it resets to the predefined resetting position. We explore various choices for the resetting position, present rigorous results for the MFPT to a given node of the network, determine the optimal resetting probability γ^{*} where the MFPT reaches its minimum, and evaluate the ratio of the minimum for MFPT to the MFPT without resetting for each case. Results show that, in large PSFWs, both the degree of the resetting position and the distance between the target and the resetting position significantly affect the search efficiency. A higher degree of the resetting position leads to a slower convergence of the walker to the target, while a greater distance between the target and the resetting position also results in a slower convergence. Additionally, we observe that resetting to a vertex randomly selected from the stationary distribution can significantly expedite the process of the walker reaching the target. The findings presented in this study shed light on optimizing stochastic search processes on large networks, offering valuable insights into improving search efficiency in real-world applications, where the target node's location is unknown.

Target searches of interacting Brownian particles in dilute systems

We study the target searches of interacting Brownian particles in a finite domain, focusing on the effect of interparticle interactions on the search time. We derive the integral equation for the mean first-passage time and acquire its solution as a series expansion in the orders of the Mayer function. We analytically obtain the leading order correction to the search time for dilute systems, which are most relevant to target search problems and prove a universal relation given by the particle density and the second virial coefficient. Finally, we validate our theoretical prediction by Langevin dynamics simulations for the various types of the interaction potential.

First encounters on Watts-Strogatz networks and Barabási-Albert networks

The Watts-Strogatz networks are important models that interpolate between regular lattices and random graphs, and Barabási-Albert networks are famous models that explain the origin of the scale-free networks. Here, we consider the first encounters between two particles (e.g., prey A and predator B) embedded in the Watts-Strogatz networks and the Barabási-Albert networks. We address numerically the mean first-encounter time (MFET) while the two particles are moving and the mean first-passage time (MFPT) while the prey is fixed, aiming at uncovering the impact of the prey's motion on the encounter time, and the conditions where the motion of the prey would accelerate (or slow) the encounter between the two particles. Different initial conditions are considered. In the case where the two particles start independently from sites that are selected randomly from the stationary distribution, on the Barabási-Albert networks, the MFET is far less than the MFPT, and the impact of prey's motion on the encounter time is enormous, whereas, on the Watts-Strogatz networks (including Erdős-Rényi random networks), the MFET is about 0.5-1 times the MFPT, and the impact of prey's motion on the encounter time is relatively small. We also consider the case where prey A starts from a fixed site and the predator starts from a randomly drawn site and present the conditions where the motion of the prey would accelerate (or slow) the encounter between the two particles. The relation between the MFET (or MFPT) and the average path length is also discussed.

Efficiency of random search with space-dependent diffusivity

We address the problem of random search for a target in an environment with a space-dependent diffusion coefficient D(x). Considering a general form of the diffusion differential operator that includes Itô, Stratonovich, and Hänggi-Klimontovich interpretations of the associated stochastic process, we obtain and analyze the first-passage-time distribution and use it to compute the search efficiency E=〈1/t〉. For the paradigmatic power-law diffusion coefficient D(x)=D_{0}|x|^{α}, where x is the distance from the target and α<2, we show the impact of the different interpretations. For the Stratonovich framework, we obtain a closed-form expression for E, valid for arbitrary diffusion coefficient D(x). This result depends only on the distribution of diffusivity values and not on its spatial organization. Furthermore, the analytical expression predicts that a heterogeneous diffusivity profile leads to a lower efficiency than the homogeneous one with the same average level within the space between the target and the searcher initial position, but this efficiency can be exceeded for other interpretations.

Model for active particles confined in a two-state micropattern

We propose a model, based on active Brownian particles, for the dynamics of cells confined in a two-state micropattern, composed of two rectangular boxes connected by a bridge, and investigate the transition statistics. A transition between boxes occurs when the active particle crosses the center of the bridge, and the time between subsequent transitions is the dwell time. By assuming that the rotational diffusion time τ is a function of the position, some experimental observations are qualitatively recovered as, for example, the shape of the survival function. τ controls the transition from a ballistic regime at short time scales to a diffusive regime at long time scales, with an effective diffusion coefficient proportional to τ. For small values of τ, the dwell time is determined by the characteristic diffusion timescale which is constant for very low values of τ, when the rotational diffusion is much faster than the translational one and decays with τ for intermediate values of τ. For large values of τ, the interaction with the walls dominates and the particle stays mostly at the corners of the boxes increasing the dwell time. We find that there is an optimal τ for which the dwell time is minimal and its value can be tuned by changing the geometry of the pattern.

Escape kinetics of self-propelled particles from a circular cavity

We numerically investigate the mean exit time of an inertial active Brownian particle from a circular cavity with single or multiple exit windows. Our simulation results witness distinct escape mechanisms depending on the relative amplitudes of the thermal length and self-propulsion length compared to the cavity and pore sizes. For exceedingly large self-propulsion lengths, overdamped active particles diffuse on the cavity surface, and rotational dynamics solely governs the exit process. On the other hand, the escape kinetics of a very weakly damped active particle is largely dictated by bouncing effects on the cavity walls irrespective of the amplitude of self-propulsion persistence lengths. We show that the exit rate can be maximized for an optimal self-propulsion persistence length, which depends on the damping strength, self-propulsion velocity, and cavity size. However, the optimal persistence length is insensitive to the opening windows' size, number, and arrangement. Numerical results have been interpreted analytically based on qualitative arguments. The present analysis aims at understanding the transport controlling mechanism of active matter in confined structures.

Optimal escape-and-feeding dynamics of random walkers: Rethinking the convenience of ballistic strategies

Excited random walks represent a convenient model to study food intake in a media which is progressively depleted by the walker. Trajectories in the model alternate between (i) feeding and (ii) escape (when food is missed and so it must be found again) periods, each governed by different movement rules. Here, we explore the case where the escape dynamics is adaptive, so at short times an area-restricted search is carried out, and a switch to extensive or ballistic motion occurs later if necessary. We derive for this case explicit analytical expressions of the mean escape time and the asymptotic growth of the depleted region in one dimension. These, together with numerical results in two dimensions, provide surprising evidence that ballistic searches are detrimental in such scenarios, a result which could explain why ballistic movement is barely observed in animal searches at microscopic and millimetric scales, therefore providing significant implications for biological foraging.

Universal properties of a run-and-tumble particle in arbitrary dimension

We consider an active run-and-tumble particle (RTP) in d dimensions, starting from the origin and evolving over a time interval [0,t]. We examine three different models for the dynamics of the RTP: the standard RTP model with instantaneous tumblings, a variant with instantaneous runs and a general model in which both the tumblings and the runs are noninstantaneous. For each of these models, we use the Sparre Andersen theorem for discrete-time random walks to compute exactly the probability that the x component does not change sign up to time t, showing that it does not depend on d. As a consequence of this result, we compute exactly other x-component properties, namely, the distribution of the time of the maximum and the record statistics, showing that they are universal, i.e., they do not depend on d. Moreover, we show that these universal results hold also if the speed v of the particle after each tumbling is random, drawn from a generic probability distribution. Our findings are confirmed by numerical simulations. Some of these results have been announced in a recent Letter [Phys. Rev. Lett. 124, 090603 (2020)10.1103/PhysRevLett.124.090603].

Narrow-escape time and sorting of active particles in circular domains

It is now well established that microswimmers can be sorted or segregated fabricating suitable microfluidic devices or using external fields. A natural question is how these techniques can be employed for dividing swimmers of different motility. In this paper, using numerical simulations in the dilute limit, we investigate how motility parameters (time of persistence and velocity) impact the narrow-escape time of active particles from circular domains. We show that the escape time undergoes a crossover between two asymptotic regimes. The control parameters of the crossover is the ratio between the persistence length of the active motion and the typical length scale of the circular domain. We explore the possibility of taking advantage of this finding for sorting active particles by motility parameters.

Pinning dislocations in colloidal crystals with active particles that seek stacking faults

There is growing interest in functional, adaptive devices built from colloidal subunits of micron size or smaller. A colloidal material with dynamic mechanical properties could facilitate such microrobotic machines. Here we study via computer simulation how active interstitial particles in small quantities can be used to modify the bulk mechanical properties of a colloidal crystal. Passive interstitial particles are known to pin dislocations in metals, thereby increasing resistance to plastic deformation. We extend this tactic by employing anisotropic active interstitials that travel super-diffusively and bind strongly to stacking faults associated with partial dislocations. We find that: (1) interstitials that are effective at reducing plasticity compromise between strong binding to stacking faults and high mobility in the crystal bulk. (2) Reorientation of active interstitials in the crystal depends upon rotational transitions between high-symmetry crystal directions. (3) The addition of certain active interstitial shapes at concentrations as low as 60 per million host particles (0.006%) can create a shear threshold for dislocation migration. This work demonstrates how active materials in a dense matrix can locally sense their environment and lead to bulk property changes.

Universal Survival Probability for a d-Dimensional Run-and-Tumble Particle

We consider an active run-and-tumble particle (RTP) in d dimensions and compute exactly the probability S(t) that the x component of the position of the RTP does not change sign up to time t. When the tumblings occur at a constant rate, we show that S(t) is independent of d for any finite time t (and not just for large t), as a consequence of the celebrated Sparre Andersen theorem for discrete-time random walks in one dimension. Moreover, we show that this universal result holds for a much wider class of RTP models in which the speed v of the particle after each tumbling is random, drawn from an arbitrary probability distribution. We further demonstrate, as a consequence, the universality of the record statistics in the RTP problem.

Swimming of bacterium Bacillus subtilis with multiple bundles of flagella

We characterize the bundle properties for three different strains of B. subtilis bacteria with various numbers of flagella. Our study reveals that, surprisingly, the number of bundles is independent of the number of flagella, and the formation of three bundles is always the most frequent case. We assume that this relates to the fact that different mutants have the same body length. There is no significant difference between the bundle width and length for distinct strains, but the projected angle between the bundles increases with the flagellar number. Furthermore, we find that the swimming speed is anti-correlated with the projected angle between the bundles, and the wobbling angle between the swimming direction and cell body increases with the number of flagella. Our findings highlight the impact of geometrical properties of bacteria such as body length and bundle configuration on their motility.

Persistent random motion with maximally correlated fluctuations

How often should a random walker change its direction of motion in order to maximize correlation in velocity fluctuations over a finite time interval? We address this optimal diffusion problem in the context of the one-dimensional persistent random walk, where we evaluate the correlation and mutual information in velocity trajectories as a function of the persistence level and the observation time. We find the optimal persistence level corresponds to the average number of direction reversals asymptotically scaling as the square root of the observation time. This square-root scaling law makes the relative growth between the average number of direction reversals and the persistence length invariant with respect to changes in the overall time duration of the random walk.

Flagellar number governs bacterial spreading and transport efficiency

Peritrichous bacteria synchronize and bundle their flagella to actively swim, while disruption of the bundle leads to a slow motility phase with a weak propulsion. It is still not known whether the number of flagella represents an evolutionary adaptation toward optimizing bacterial navigation. We study the swimming dynamics of differentially flagellated Bacillus subtilis strains in a quasi-two-dimensional system. We find that decreasing the number of flagella N f reduces the average turning angle between two successive run phases and enhances the run time and the directional persistence of the run phase. As a result, having fewer flagella is beneficial for long-distance transport and fast spreading, while having a lot of flagella is advantageous for the processes that require a slower spreading, such as biofilm formation. We develop a two-state random walk model that incorporates spontaneous switchings between the states and yields exact analytical expressions for transport properties, in remarkable agreement with experiments. The results of numerical simulations based on our two-state model suggest that the efficiency of searching and exploring the environment is optimized at intermediate values of N f. The optimal choice of N f, for which the search time is minimized, decreases with increasing the size of the environment in which the bacteria swim.

Topology-dependent density optima for efficient simultaneous network exploration

A random search process in a networked environment is governed by the time it takes to visit every node, termed the cover time. Often, a networked process does not proceed in isolation but competes with many instances of itself within the same environment. A key unanswered question is how to optimize this process: How many concurrent searchers can a topology support before the benefits of parallelism are outweighed by competition for space? Here, we introduce the searcher-averaged parallel cover time (APCT) to quantify these economies of scale. We show that the APCT of the networked symmetric exclusion process is optimized at a searcher density that is well predicted by the spectral gap. Furthermore, we find that nonequilibrium processes, realized through the addition of bias, can support significantly increased density optima. Our results suggest alternative hybrid strategies of serial and parallel search for efficient information gathering in social interaction and biological transport networks.

Adiabatic elimination of inertia of the stochastic microswimmer driven by α-stable noise

We consider a microswimmer that moves in two dimensions at a constant speed and changes the direction of its motion due to a torque consisting of a constant and a fluctuating component. The latter will be modeled by a symmetric Lévy-stable (α-stable) noise. The purpose is to develop a kinetic approach to eliminate the angular component of the dynamics to find a coarse-grained description in the coordinate space. By defining the joint probability density function of the position and of the orientation of the particle through the Fokker-Planck equation, we derive transport equations for the position-dependent marginal density, the particle's mean velocity, and the velocity's variance. At time scales larger than the relaxation time of the torque τ_{ϕ}, the two higher moments follow the marginal density and can be adiabatically eliminated. As a result, a closed equation for the marginal density follows. This equation, which gives a coarse-grained description of the microswimmer's positions at time scales t≫τ_{ϕ}, is a diffusion equation with a constant diffusion coefficient depending on the properties of the noise. Hence, the long-time dynamics of a microswimmer can be described as a normal, diffusive, Brownian motion with Gaussian increments.

Spatial heterogeneity can facilitate the target search of self-propelled particles

A numerical investigation of the target search dynamics of self-propelled particles (SPPs) in heterogeneous environments is presented in this work. We show that the spatial heterogeneity has a dramatic effect on the target search dynamics of SPPs. The relative magnitude of the self-propulsion length l_p and the radius of the circular domain R_c determines how the mean search time of SPPs τ depends on the area fraction of fixed obstacles ϕ_ob. For l_p < R_c, the target search process is diffusion-dominated so that a monotonic increase in τ with increasing ϕ_ob is observed. For l_p > R_c, τ is shown to be a non-monotonic convex function as a function of ϕ_ob due to the interplay of the distribution-dominated and diffusion-dominated dynamic regimes. Furthermore, at fixed ϕ_ob, τ shows a minimum upon increasing the self-propulsion velocity v₀ of a SPP of a slow rotational diffusion when it searches for a target at low ϕ_ob, while it decreases monotonically at high ϕ_ob. The present work highlights that the introduction of spatial heterogeneity causes rich dynamic behaviors of a SPP searching for a target, and deepens our understanding of the transport of active matter in heterogeneous media.

Active Brownian particles and run-and-tumble particles separate inside a maze

A diverse range of natural and artificial self-propelled particles are known and are used nowadays. Among them, active Brownian particles (ABPs) and run-and-tumble particles (RTPs) are two important classes. We numerically study non-interacting ABPs and RTPs strongly confined to different maze geometries in two dimensions. We demonstrate that by means of geometrical confinement alone, ABPs are separable from RTPs. By investigating Matryoshka-like mazes with nested shells, we show that a circular maze has the best filtration efficiency. Results on the mean first-passage time reveal that ABPs escape faster from the center of the maze, while RTPs reach the center from the rim more easily. According to our simulations and a rate theory, which we developed, ABPs in steady state accumulate in the outermost region of the Matryoshka-like mazes, while RTPs occupy all locations within the maze with nearly equal probability. These results suggest a novel technique for separating different types of self-propelled particles by designing appropriate confining geometries without using chemical or biological agents.