By Bard Ermentrout
In part 1 of this article, published in the September issue of SIAM News, the author described issues involved with the development of algorithms that animals utilize to locate and follow odor sources and trails. Here, he presents some specific algorithms and explains how one can regard them as interesting dynamical systems.
Bacteria move in response to chemical stimuli, a process known as chemotaxis. The molecular mechanisms underlying bacterial chemotaxis are complex, but not well understood. Bacteria shift between directed swimming and “tumbling,” a random diffusion-like motion. This is a common strategy among organisms that exhibit odor search; they use exploitation (directed motion) when “confident” about odor location and switch to exploration (a random search strategy) when they are not. For example, moths pursuing the scent of a mate make big swooping flights (casting) orthogonal to the direction of the wind to locate the odor plume, and then exploit the upwind direction to follow the plume to the source. Animals also exploit other cues, such as rushing water, in addition to cues from the odor itself.
The partial differential equations (PDEs) modeling chemotaxis are well known in the applied mathematics community:
\[\frac{\partial b}{\partial t} = \nabla\left( D \nabla b -\chi b \nabla C(\mathbf{x},t)\right), \qquad (\mathbf{x},t)\in R^n\times R^+, \tag{1} \]
where \(b(\mathbf{x},t)\) is the density of bacteria, \(c(\mathbf{x},t)\) is the concentration of an attractant or repellant, \(D\) is the diffusion constant, and \(\chi\) is the chemotactic coefficient. If \(\chi>0\), then the bacteria will move toward the peak of the concentration.
Since \((1)\) does not account for birth or death, it represents the density of bacteria and is proportional to the probability of a given cell being at position \(x\) at time \(t\). Thus, \((1)\) is the corresponding Fokker-Planck equation at the single cell level for the following stochastic differential equation:
\[d \mathbf{x} = \chi \nabla c(\mathbf{x},t) dt + \sqrt{2D} d\mathbf{W},\]
where \(\mathbf{W}\) is a vector of independent white noise. Thus, the motion of an individual acts as a deterministic strategy (exploitation) that dominates when the gradient of the attractant is large, and as a random walk strategy (exploration) that dominates when the attractant is weak. At the microscopic scale of a single bacterium, the attractant is not a simple smooth function of space. This equation is therefore a very simple idealization.
Imagine a macroscopic organism, like a mouse or a fruit fly, moving continuously in a plane. Its position is \((x,y)\) and its orientation is \(\theta\). Its orientation and speed will determine its position:
\[\frac{dx}{dt}=V(x,y,t)\cos\theta \\
\frac{dy}{dt}=V(x,y,t)\sin\theta \\
\frac{d\theta}{dt}=F(\theta,x,y,t).\tag{2} \]
The functions \(F,V\) may only be piecewise-defined and are likely stochastic (hence the explicit time-dependence). The three-dimensional case would involve a third spatial variable, \(z\), and an additional heading angle. The goal of an odor navigation algorithm is to provide details about \(F\) and \(V\). In a perfect world, where odor concentration is smooth, the gradient ascent will work quite nicely:
\[\frac{d\mathbf{x}}{dt} = - K \frac{\nabla C(\mathbf{x})}{C(\mathbf{x})},\]
which normalizes the concentration field \(C(\mathbf{x})\). Obviously an animal cannot actually compute the gradient, but animals can and do make spatiotemporal comparisons. For example, comparing the odor concentration at spatially-separated sensors (such as the nares (nostrils) of a mouse or the antennae of a lobster) can work nicely in a smooth enough environment. Alternatively, the animal could move its head in a new direction, sniff, and make a comparison to what he sniffed the last time. This is effectively a spatial comparison, just like the two-sensor mechanism. Odor normalization (dividing by the concentration) has a biological correlate: the receptors in the noses of many animals have a logarithmic range of binding constants [1]. Furthermore, the negative feedback circuitry in the olfactory bulb (where the olfactory signals are first processed in mammals) emphasizes differences in concentrations [2]. However, we will not use this normalization in subsequent models as there is a threshold below which odor cannot be detected.
We first consider a simple spatial comparison model where the animal moves with constant speed and only adjusts its heading based on the difference between a left-hand and right-hand sensor:
\[x'=v \cos\theta\]
\[y'=v \sin\theta\]
\[\theta'=\beta (C_L(x,y)-C_R(x,y)). \tag{3} \]
We assume that the sensors are separated by a distance proportional to \(l\) and oriented on either side of the head at angles \(\pm\phi\), with respect to the midline (see Figure 1a). Thus, \(C_{L,R}(x,y)=C[x+l\cos(\theta\pm \phi),y+l\sin(\theta\pm\phi)]\). As a very simple task, we will have the animal follow an infinite trail along the \(y\)-axis with a concentration that depends on distance from the trail. For convenience, choose \(C(x)=e^{-x^2}\). In this case, \(y\) does not enter into the equation for \(\theta\) and we can study the \((x,\theta)\) system via the phase plane:
\[x'=v\cos\theta\]
\[\theta' = \beta \left[e^{-(x+l\cos(\theta+\phi))^2}-e^{-(x+l\cos(\theta-\phi))^2}\right].\]
The only equilibria are \(\theta =\pm \pi/2\) and \(x=0;\) they are both stable if \(\phi\in(0,\pi/2)\). These correspond with following the trail upward and downward respectively. In this case, \(dy/dt=\pm v\) and the mouse runs up or down the trail forever. The sets \(\theta=0\) and \(\theta=\pi\) are invariant and form the separatrices between the stable equilibria. If an animal gets “stuck” on either of these two lines, it will never reach the stable equilibrium and will move away from the trail forever. More importantly, once \(x\) is large enough, \(C(x)\) becomes exponentially small, so that \(\theta\) asymptotically approaches a constant value and the mouse will run off to infinity along that asymptotic heading.
Figure 1a. Schematic of (3). 1b. Phase plane for this algorithm. 1c. Same algorithm coupled with a correlated random walk. Image credit: James Hengenious.
Figure 1b shows several trajectories starting at different initial conditions in the \((x,\theta)\) phase-plane; two of them are attracted to the stable equilibrium while others head away, never to return. When the distance is too great, the concentration becomes so small that no corrections in the trajectory are possible. There is a roughly-elliptical region that serves as the basin of attraction to the fixed point. One can understand the approximate shape of this basin by letting \(l\), the sensor distance, get smaller. At the lowest order in \(l\), the resulting equations are integrable and there is an energy contour (shown in Figure 1) that provides a sufficient condition for convergence to the trail:
\[v \ln|\sin\theta|+2\beta \sin\phi e^{-x^2}=0.\] Even this simple algorithm invites questions. For example, how well would it perform in a noisy odor environment? How robust is it to sensory noise? How can an animal losing the trail avoid going off to infinity?
As was aforementioned, there is no simple way to model the noisy environment, but we can liken the inputs in the model to what we see in the real world. A simple model for a noisy environment assumes that at each time step, a random event is generated at a rate proportional to the concentration at the sensor position. This position will be either \(0\) or \(1\), and the algorithm now becomes driven by the sensor difference \((\pm 1, 0)\). Even the simple left-right differencing algorithm will do quite well if the rate is high enough to ensure that events are not too rare, assuming the initial conditions are near the deterministic basin of attraction. In fact, because of the stochasticity, it is possible to pick up the trail even when the initial data is outside the deterministic basin; the noise causes occasional random turns that may bring the trajectories into the basin. But this advantage works only if the mouse is initially close to the basin. As in the deterministic case, once the distance from the trail is too great, the heading will never change since the events are too rare.
How can we avoid completely losing the trail? As noted above, animals use an “exploration” strategy when they lose the odor or when it becomes too infrequent. Adding a completely random term (not directly related to the concentration) to the deterministic ODE can introduce this type of behavior. For example, we could replace the equation for \(\theta\) with:
\[d\theta = \beta (C_L-C_R) dt + \sigma dW. \tag{4}\] When \(x\) is large and the deterministic portion vanishes, \(\theta\) undergoes a random walk and the variables \(x(t),y(t)\) undergo a correlated random walk (CRW) since the heading \(\theta(t)\) is now a continuous process. The CRW is a search strategy that allows an animal to possibly get back into the basin of attraction of the deterministic dynamics; \((4)\) represents an extremely simple search strategy. One could replace this local exploration with a more general type of search, such as a Levy flight. Figure 1c depicts a correlated random walk, which gets close enough to the trail to be followed. Here we portray the trajectories in the \((x,y)\) plane to clarify the motion. There are four other trajectories without the “noise,” starting at the same spatial location but with four different headings. None of them manage to find the trail! The trajectory with the CRW term finds the trail quite readily.
This example considers the simplest spatial comparison model that is continuous in time. A model that incorporates regular casting (moving the head and sampling) yields similar results, except that time is discrete with respect to the sniff cycle. The animal compares the concentration at each sniff to the previous sniff, and then chooses the direction that is towards the greater concentration. This is physiologically different from but mathematically similar to the two-sensor model. Both the two-sensor (or binaral, for animals with noses) mechanism and the alternate sniffing (or casting) model involve odor comparison; in one case comparison is between left and right inputs, while the other case requires some short-term memory. Picking the more salient (in this case, the stronger) stimulus is a task for which the nervous system, and in particular the olfactory system, is well-suited. There is plenty of inhibition (negative feedback) in the early stages of olfactory processing, which can be used to improve contrast between stimuli and even implement a competition in which there is only one winner [2].
In the future, my group wants to determine the underlying neural processes that allow animals to implement various search strategies required to locate food sources, mates, and so on. In summation, locating odor sources in a complex environment is a difficult task with many interesting mathematical features.
see “Algorithmically Defining Olfactory Responses in Animals” in the September 2016 issue of SIAM News.
References
[1] Hopfield, J.J. (1999). Odor space and olfactory processing: collective algorithms and neural implementation. Proceedings of the National Academy of Sciences, 96(22), 12506-12511.
[2] Urban, N.N. (2002). Lateral inhibition in the olfactory bulb and in olfaction. Physiology & Behavior, 77(4), 607-612.
Further Reading
Viswanathan, G.M., da Luz, M.G.E., Raposo, E.P., & Stanley, H.E. (2011). The Physics of Foraging: An Introduction to Random Searches and Biological Encounters. New York, NY: Cambridge University Press.
Bard Ermentrout is a professor of mathematics at the University of Pittsburgh. He works in many areas of mathematical biology, with a focus on neuroscience.