Markovian robots: Minimal navigation strategies for active particles

We explore minimal navigation strategies for active particles in complex, dynamical, external fields, introducing a class of autonomous, self-propelled particles which we call Markovian robots (MR). These machines are equipped with a navigation control system (NCS) that triggers random changes in the direction of self-propulsion of the robots. The internal state of the NCS is described by a Boolean variable that adopts two values. The temporal dynamics of this Boolean variable is dictated by a closed Markov chain—ensuring the absence of fixed points in the dynamics—with transition rates that may depend exclusively on the instantaneous, local value of the external field. Importantly, the NCS does not store past measurements of this value in continuous, internal variables. We show that despite the strong constraints, it is possible to conceive closed Markov chain motifs that lead to nontrivial motility behaviors of the MR in one, two, and three dimensions. By analytically reducing the complexity of the NCS dynamics, we obtain an effective description of the long-time motility behavior of the MR that allows us to identify the minimum requirements in the design of NCS motifs and transition rates to perform complex navigation tasks such as adaptive gradient following, detection of minima or maxima, or selection of a desired value in a dynamical, external field. We put these ideas in practice by assembling a robot that operates by the proposed minimalistic NCS to evaluate the robustness of MR, providing a proof of concept that is possible to navigate through complex information landscapes with such a simple NCS whose internal state can be stored in one bit. These ideas may prove useful for the engineering of miniaturized robots.

Figure 1

Illustration of the general dynamics of Markovian robots. A robot that had initially moved from left to right in an external field $c\left(x\right)$ changed its direction of active motion after some time $\mathrm{\Delta }t$. The navigation control system (NCS) controls the moving direction of the robot, by triggering reorientation events. It is connected to a sensor which measures the local field values. The internal state of the NCS is given by a single Boolean variable adopting the values 1 or 2. The NCS dynamics obeys a closed Markov chain, with transition rates that may depend on the value of the external field as measured by the sensor. The red arrow corresponds to the transition that triggers a reorientation event.

Figure 2

Flowcharts of the algorithms for bacterial chemotaxis, according to Ref. [14], and Markovian robots (MR), motifs 1 and 2. The initial condition is not explicitly shown. Notice the presence of two continuous variables, $A$ and $B$, for bacterial chemotaxis, which are absent for MRs. Further, we point out that the dynamics of $A$ and $B$ evolves toward a fixed point for constant $c\left(x\right)$, implying that the internal state in the bacterial chemotaxis model reaches a steady state. In MR, on the other hand, the internal state always oscillates. The symbols $Q$, $\alpha$, $\beta$, and $\gamma$ refer to transition rates, $\mathrm{\Delta }t$ to the time step, $c\left(x\right)$ to the value of the external field at position $x$, $v_0$ to the speed, and $s$ to the moving direction ($+1$ or $-1$) in one dimension; $\text{rnd}\left(\right)$ is a uniformly distributed, random number between 0 and 1. The definitions of $\alpha$, $\beta$, and $\gamma$ are provided in the main text; notice that these rates do only depend on $c\left(x\right)$. On the other hand, $Q(A,B)$ is a function of the internal state itself, $Q(A,B)=d_{1}A-d_{2}B$, where $d_1$ and $d_2$ as well as $a$ and $b$ are constant; for details on the bacterial chemotaxis algorithm see Ref. [14].

Figure 3

The motility response of MR—controlled by NCS motif 1 as shown, cf. Fig. 1—to an external field $c\left(x\right)=x/L$ (see inset). The main figure illustrates the stationary probability distributions $P_s\left(x\right)$ for two variants of the internal robot dynamics. In the first case ($\alpha \left[c\right]=9c+1$, $\beta \left[c\right]=5$), robots tend to accumulate upgradient in the long-time limit (circles). In contrast, robots accumulate on the opposite side if the two transitions are interchanged ($\alpha \left[c\right]=5$, $\beta \left[c\right]=9c+1$) as shown by squares. Points denote individual-based model simulations (robot number $N={10}^4$). Lines correspond to the approximative analytical solution [Eq. (7)] where the respective functional forms of $f\left(x\right)$ and $D\left(x\right)$ were inserted [Eqs. (12)]. Further parameters: $L=1$, $v_0=0.01$, $D_0=0$, reflecting boundary conditions.

Figure 4

Illustration of complex tasks performed by suitably tuned robots controlled by the adaptive NCS motif 2. The detection of maxima and minima in a complex landscape $c\left(x\right)$ is shown at the bottom of panel (b) $\left[c\right(x)$ is displayed at the top of panel (b)]. The corresponding functional dependencies of $\beta \left[c\right]$ are shown in panel (a): For increasing $\beta \left[c\right]$, minima are detected (black, solid curves), whereas robots accumulate around maxima for decreasing $\beta \left[c\right]$ (red, dashed lines). Moreover, the accumulation of robots around a preferred external field value [dotted line in panel (d)] is demonstrated for the functional dependence $\beta \left[c\right]$ shown in panel (c). As a third example, robots chasing a moving signal (white, dashed line) are depicted in panels (e)–(i). Spacetime plots (f)–(i) reveal that robots become less responsive to a moving signal above a critical speed $v_c$, estimated by Eq. (17), which is shown by a vertical red (dashed) line in panel (e). Further, the performance is quantified in panel (e), where $\mathrm{\Delta }$ denotes the deviation of the robot density from the spatially homogeneous distribution. Parameters: $c^{*}=1$, $w=0.5$, ${\beta }^{-}=1$, ${\beta }^{+}=10$, $v_0=0.01$, $L=1$, $D_0=0$; see main text for the functional forms of the rate $\beta \left[c\right]$. Boundary conditions: reflecting in panels (b) and (d), periodic in panels (e)–(i).

Figure 5

Illustration of adaptive MR in two dimensions. In the left panel, the external field $c\left(\mathbf{r}\right)=1+0.5sin\left(2\pi x\right)cos\left(3\pi y\right)$ is shown. The middle panel represents the stationary probability density $P_s\left(\mathbf{r}\right)$ obtained from individual-based model (IBM) simulations. On the right, several cross sections as indicated in the middle panel by white (dashed) lines are shown in comparison to predictions of the drift-diffusion approximation [Eq. (28)]. Model specification: upon reorientation, a robot chooses a new direction of motion from the uniform probability distribution $g\left(\phi \right)=1/\left(2\pi \right)$, such that $\mathcal{G}=0$; adaptive NCS motif 2, cf. Eqs. (14); $\beta \left[c\right]$ as shown in Fig. 4 (red line) and the corresponding comments in the main text (${\beta }_{-}=1$, ${\beta }_{+}=10$). Other parameters: $L=1$, $v_0=0.01$, $D_0=0$, $D_r=0$, $N={10}^4$ robots in IBM simulations; reflecting boundary conditions.

Figure 6

Comparison of the stationary probability density $P_s\left(\mathbf{r}\right)$ of MR controlled by NCS motif 2 as obtained from individual-based model (IBM) simulations and the corresponding drift-diffusion approximation, cf. Eq. (38), in three spatial dimensions. A Gaussian modulation is used as an external signal: $c\left(\mathbf{r}\right)=c_0\left[1+\varepsilon exp\left(-\frac{{\left|\mathbf{r}-{\mathbf{r}}_0\right|}^2}{2{\sigma }^2}\right)\right]$. The data points in the main panel (IBM) were reconstructed from the radial distribution function $g\left(R\right)=\int d^{3}r{P}_s\left(\mathbf{r}\right)\delta \left(R-\left|\mathbf{r}-{\mathbf{r}}_0\right|\right)$ shown in the inset via division by the angular measure factor. The inset on the left represents a three-dimensional histogram of the position of MR, where the color code indicates the value of $P_s\left(\mathbf{r}\right)$. The main panel is a cut of $P_s\left(\mathbf{r}\right)$ along $\mathbf{r}={\left(x,1/2,1/2\right)}^T$. Parameters: $c_0=1/2$, $\varepsilon =2$, $\sigma =\sqrt{3/2}/10\approx 0.12$, ${\mathbf{r}}_0={\left(1/2,1/2,1/2\right)}^T$. Further parameters as in Fig. 5; reflecting boundary conditions have been used.

Figure 7

(a) A photo of the robot, a Lego Mindstorms EV3. (b) Binomial distribution $B_{40}\left(n\right|\mathrm{\Gamma })$ determining the probability that the robot leaves the system $n$ times via the right boundary in 40 realizations of the experiment, whereby the robot was initially placed at the center of the system, given that the probability for the same event in one realization is $\mathrm{\Gamma }$; cf. Eq. (39). The black circles correspond to an unbiased random walker ($\mathrm{\Gamma }=0.5$), and the red squares show the Binomial distribution for the theoretically predicted value ($\mathrm{\Gamma }=0.65$). The experimentally observed situation—in $n=28$ cases the robot touched the right boundary first—is indicated by a vertical blue line. A representative trajectory is shown in panel (c), on top of which the robot is depicted moving on the printed gray scale. The probability distribution $P_{40}\left(\mathrm{\Gamma }\right|n=28)$ for $\mathrm{\Gamma }$ given the experimental result ($n=28$), inferred from the Bayesian theorem [Eq. (41)], is shown as an inset of panel (b); the experimental observation is in line with the theoretical prediction.