## Abstract

Optimal foraging theory shows how fitness-maximizing foragers can use information about patch quality to decide how to search *within* patches. It is amply supported by empirical studies. Nonetheless, the theory largely ignores the fact that foragers may need to search *for* patches as well as for the targets within them. Here, using an exact but simple mathematical argument, it is shown how foragers can use information about patch quality to facilitate the execution of Lévy walk movement patterns with *μ* = 2 at inter-patch scales. These movement patterns are advantageous when searching *for* patches that are not depleted or rejected once visited but instead remain profitable. The analytical results are verified by the results of numerical simulations. The findings bring forth an innovative theoretical synthesis of searching for and within patches and, suggest that foragers' memories may be adaptive under spatially heterogeneous reward schedules.

## 1. Introduction

Foraging behaviour has been a central concern of ecology. Our current understanding of foraging behaviours owes much to the ground-breaking work of MacArthur & Pianka [1], who established the field of optimal foraging theory. The development of this theory and its empirical verifications have been charted by Pyke *et al*. [2] and Stephens & Krebs [3]. The theory posits that animals forage in a way that maximizes their rate of energy intake. Foraging for patchily distributed resources has been a focus of attention [4–12], as virtually every ecosystem will exhibit patchiness on a range of spatial, temporal and organizational scales [13]. When foraging for patchily distributed resources, it is initially advantageous to search within a patch because resources are present there in relatively high abundance. The benefit of remaining within a patch will, however, generally diminish with time because of the gradual depletion of resources due to foraging. Central to optimal foraging theory has been the marginal value theorem, which dictates that a forager should leave a particular patch when the expected energy gained from staying drops to the expected net gain from travelling to and foraging within a new patch. The durations of patch-foraging episodes can also be chosen to balance the conflicting demands for food and safety from predation [14]. Factors influencing this trade-off include the encounter rate with predators, predator lethality in the absence of vigilance, effectiveness of vigilance in reducing predator lethality, the marginal value of energy to the forager and the forager's survivor's fitness. Thus, patches are not necessarily depleted or rejected once visited but can instead remain profitable and so warrant repeated visits.

Most models of patch use assume that foragers assess spatial heterogeneity in feeding or fitness opportunities and respond accordingly. Prescient foragers use sensory cues or memory in predicting patch quality [9]. Bayesian foragers, on the other hand, estimate patch quality from: (i) an *a priori* knowledge of the distribution of patch qualities throughout the environment; (ii) time spent thus far in searching for food items within the patch; and (iii) the number of food items thus far encountered and harvested ([4–12] and see Valone [15], for a review of empirical data). Optimal foraging theory has identified how fitness-maximizing foragers should use this information to decide how thoroughly to use each food patch. The theory has, however, tended to ignore the large-scale search problem (i.e. patch detection). Most models of optimal foraging theory assume that foragers have information about patch locations so that time spent between patches is attributed to travelling rather than to searching. There has been a failure to recognize that foragers may need to search *for* patches as well as for the targets *within* them [16]. The need to search for patches will arise if the environment is new, highly dynamic or if foragers have limited perceptual/cognitive abilities [17].

To come closer to actuality, optimal foraging theory needs to improve the integration of search components at different scales of the foraging process [16]. This might be achieved by drawing on Lévy walk (LW) search theory, which has been concerned with identifying movement patterns that are advantageous when searching for randomly and sparsely distributed patches ([18–20], reviewed in Reynolds & Rhodes [21] and Viswanathan *et al*. [22]).

LW comprise clusters of relatively short step lengths with longer steps between them. This pattern is repeated across all scales, with the resultant scale-free clusters creating fractal patterns. Step lengths, *l*, are drawn from distributions with inverse power-law tails: *p*_{l}(*l*)∼*l ^{−μ}*, where 1 <

*μ*≤ 3. Distributions of total displacements (i.e. sums of many individual step lengths) tend to Lévy stable distributions by virtue of a generalized central limit theorem due to Gnedenko & Kolmogorov [23]. Directions of movement are uniformly distributed between 0° and 360°. As

*μ*→ 1, the fraction of steps with length less than the typical spacing between patches becomes negligible, so that an LW forager effectively moves along a straight line until it detects a patch [18]. Movement patterns with

*μ*> 3 are effectively Brownian at large spatio-temporal scales because total displacements (i.e. sums of many individual step lengths) eventually become Gaussian distributed.

Over much iteration an LW will be distributed much further from its starting position than a Brownian walk of the same length (same sum of step lengths) because there are relatively more long steps and so less meandering. The fractal and ‘superdiffusive’ properties of LW can be advantageous when searching for randomly and sparsely distributed patches that are not depleted or rejected once visited but instead remain profitable and so targets for later searches. Foragers may be unable to return directly to the last patch visited if they have become satiated or leave the area after feeding or are taken outside the patch by an extended but unsuccessful bout of intensive (within patch) searching. Theoretical studies [18–20] have shown that LW with *μ* = 2 can increase the patch encounter probability compared with simple Brownian, straight line and LW with *μ* ≠ 2 moments.

LW first entered the literature on animal movement patterns when it was proposed that their characteristics may be observed in foraging ants [24]. Escalating empirical support for LW movement patterns (reviewed in Reynolds & Rhodes [21]) subsequently faulted when methodological shortcomings in some approaches to determining the goodness of fits of power-laws to movement pattern data were identified [25]. More recent studies have, however, provided compelling evidence that basking sharks along with bigeye tuna, Atlantic cod, leatherback turtles, and Magellanic penguin use a movement strategy approximated by LW with *μ* = 2 when they are searching for resources [26,27]. These marine predators feed on patchily distributed prey. Spider monkeys (*Ateles geoffroyi*), fruit flies (*Drosophila*), microzooplankton (*Oxyrrhis marina*), and bacteria (*Escherichia coli*) appear to use the same movement strategy when foraging [28–32].

Here, using an exact but simple mathematical argument, it is shown that how foragers can use information about patch quality to facilitate the execution of LW movement patterns with *μ* = 2 and thereby enhance their net energy intake by reducing the average time spent searching for patches. In this picture, the lower quality (smaller) patches act as ‘signposts’ that help guide foragers to the most profitable patches: the lower quality patches indicate that the forager should ‘keep going forward’ whilst the high-quality patches indicate that the forager should ‘turn’. The results of this theoretical analysis reveals that the mechanism could operate whenever patch encounters occur with unchanging likelihood and are independent of one another, i.e. whenever patch encounters are described by a Poisson process. The analysis, which draws upon the previous work of Eliazar & Klafter [33] for the temporal generation of power-law distributions, is described in §2. The findings are subsequently supported by the results of numerical simulations presented in §3. This is followed by a discussion in §4.

## 2. Lévy walk inter-patch movement patterns from the basic attributes of classic optimal foraging theory

Here it is shown that foragers will execute LW movement patterns with *μ* = 2 at inter-patch scales if patch quality is continuously rather than discretely distributed and if the foragers adopt the following movement strategy: (i) randomly select a direction of travel, and travel in a straight line along that direction for some time, *T* (exclusive of any time spent foraging at patches encountered on the way). (ii) Take note of the quality, *Q*_{max}, of the best patch encountered. This is set to zero if no patches are encountered. (iii) Continue to move in a straight line until coming across a patch whose quality is perceived to be greater than or the same as *Q*_{max} (which is always possible when patch quality is continuously distributed). Foraging can take place at patches encountered on the way. After leaving a patch with quality *Q* ≥ *Q*_{max}, a new direction of travel is chosen at random and the cycle is repeated. The results of numerical simulations presented in §3 reveal that the LW movement patterns with *μ* = 2 arise if instead of (i) the forager keeps moving until encountering a patch and then uses the quality of that patch when subsequently assessing patch quality along that direction of travel. An example of such a movement pattern is illustrated in figure 1.

The movement rules have resonance with the solution of the ‘secretary problem’ (also known as the marriage or best choice problem). In this problem, there is a single secretarial position to fill and *n* applicants that can be ranked from best to worst. The applicants are interviewed sequentially in a random order, with each order being equally likely. After each interview, the applicant is accepted or rejected. The decision to accept or reject an applicant can be based only on the relative rank of the applicants interviewed so far. For large *n*, the optimal policy is to interview and reject the first *n*/*e* applicants (where *e* is the base of the natural logarithm) and then to accept the next candidate who is better than these interviewed candidates [34].

Mathematical analysis of the movement rules proceeds under the assumptions that patch quality is continuously rather than discretely distributed between *Q*_{worst} and *Q*_{best}, and that patch-encounters occur continuously and stochastically in time and are independent of one another. The latter assumption is approximate because two-dimensional trajectories will overlap so that the same area can be searched many times. The appropriateness of this approximation is established later with the aid of numerical simulations. These assumptions imply that patch encounters are governed by a Poisson process with some continuous rate function *λ*(*Q*). That is, the number, *n*, of encounters with high-quality (*Q* > *Q*_{max}) patches made during time *T* is Poisson-distributed, with mean *Λ*(*Q*_{max})*T* where

The probability that the forager only encounters patches with quality *Q* < *Q*_{max} during time *T* (i.e. the probability that *n* = 0) is therefore given by
2.1

Differentiating equation (2.1) with respect to *Q*_{max} yields the probability density function for the quality of the best patch found during the initial movement phase being in the range, *Q*_{max} < *Q* < *Q*_{max} + d*Q*_{max}:
2.2

Having come across a patch with quality *Q*_{max} during the initial movement phase the *conditional* probability that the forager travels for a time *t* > *τ* before encountering a better patch with quality *Q* > *Q*_{max} is
2.3

The *unconditional* probability is obtained by combining equations (2.2) and (2.3) and then using the change variables of *x* = *TΛ*(*Q*):
2.4

If the patch-encounter rate is independent on patch quality then, equation (2.4), can be deduced using a simple, intuitive argument: if at least one patch has been found at time *T* + *τ* then the probability that the best (or the only) patch was found before time *T* is just *T/*(*T* + *τ*).

It follows from equation (2.4) that the probability density function of travel times to path-changing patches is 2.5

Notice that this probability distribution function is independent of the Poissonian rate function, *λ*(*Q*), and so independent of the average target density. The probability distribution function of travel times, equation (2.5), is therefore applicable whenever patch encounters can be described by a Poisson rate function. A probability density function directly analogous to that given in equation (2.5) is also obtained when it is assumed that patches are encountered at discrete times (*t* = 1, 2, 3, … in arbitrary time units) rather than continuously in time.

The probability density function of travel times between consecutive turns (i.e. the probability density function of distances travelled between consecutive turns when moving at constant speed) therefore has an inverse-square power-law tail (irrespective of the duration, *T*, of initial patch quality assessment periods). This is indicative of LW movement patterns with *μ* = 2. This is a general result that holds true for all time-homogeneous Poisson patch-encounter processes possessing a rate function. Selection pressures for LW with *μ* = 2 will, however, decrease as the target density increases, because the advantageous that these movement patterns have over other movement patterns when randomly searching decreases as the target density increases [18]. The reorientation mechanism that gives rise to LW with *μ* = 2 is therefore not expected to arise in animals that dwell within stable food-rich environments.

## 3. Emergent Lévy walk movement patterns are advantageous

The emergence of *μ* = 2 LW movement patterns from the aforementioned movement rules is here examined with the aid of numerical simulations. Also examined is the effectiveness of these Lévy foragers in locating randomly distributed patches compared with the effectiveness of foragers that maintained their direction of travel or randomly change their direction of travel only after leaving a patch.

The search arena in these numerical simulations had size 5000 × 5000 in arbitrary space units and contained 250 000 randomly placed patches. All patches were circular with radius one and patch quality was exponentially distributed with mean arbitrary quality units. Simulation data were pooled from 500 independent simulations for the movement patterns of individual foragers moving with unit speed for 10^{7} time steps. The initial directions of travel are chosen at random. Each forager then moves continuously without interruption in a straight line until encountering a patch that is better in quality than the first patch encountered along that direction of travel. The first patch is typically encountered after 50 time steps. A new direction of travel is then chosen at random and the cycle repeats. Periodic boundary conditions were applied at the edges of the search arena to keep the foragers within the search arena. The target distribution was randomized after each application of this condition to prevent the foragers from encountering the same set of patches.

The Akaike information criterion (AIC) was used to test whether the simulation data provided more evidence for distances, *l*, travelled between successive turns coming from power-law distributions

exponential distributions

or gamma distributions

where *Γ*(*s*) is a gamma function. Power-law distributions are consistent with the presence of LW patterns. Exponential and gamma distributions are not. The Akaike weight for a power-law distribution can be considered as the weight of evidence in favour of a power-law distribution being the better model of the simulation data, i.e. the Akaike weight for a power-law can vary from 0 (no support) to 1 (complete support) [25]. A power-law probability distribution function of move-lengths is indicative of LW movement patterns. The exponential probability distribution function of move-lengths corresponds to a simple uncorrelated Poisson random process. Plots of the survival function (the complement of the cumulative distribution function) were also used to further examine the form of the tails and to determine the extent of any power-law scaling: an approach that is more reliable than probability density function plots [35]. To construct the survival function, the simulation data {*l _{i}*} are first ranked from largest to smallest {

*i*= 1 …

*n*}. The probability that a length is greater than or equal to

*l*(the survival function) is then estimated as

_{i}*i/n*. The fractal dimension,

*D*, of the turning points in the simulated movement patterns was also used to test for the presence of LW. The fractal dimension,

*D*, of the turning points in an LW approaches

*μ*− 1 asymptotically for sufficiently long sequences [36]. Here the fractal dimension,

*D*, was computed by calculating the average number,

*n*, of boxes of size

_{l}*l*arbitrary space units required to enclose all of the turning points in a simulated movement pattern. A power-law relationship of the form would be indicative of fractal scaling with fractal dimension

*D*.

The Akaike weight for power-law distribution is 1 and the maximum-likelihood estimate for the Lévy exponent *μ* = 2 (*a* = 1000 arbitrary space units). The Akaike weights for the exponential and gamma distributions are 0. The power-law scaling extends from about the mean-free path length (i.e. the average straight line distance between targets, *λ* = 100 arbitrary space units) to about the total length of the search path (figure 2). These estimates for the Lévy exponents, *μ*, are consistent with the estimate, *D* *≈* 1, for the fractal dimension shown in figure 3. The maximum-likelihood estimates for the parameters, *λ*, *r* and *s*, in the exponential and gamma distributions are 6.9 × 10^{−}^{5} reciprocal arbitrary space units, 1.3 × 10^{−}^{4} reciprocal arbitrary space units and 0.33, respectively. Model predictions do not change significantly when, as in the theory (§2), preliminary patch quality is assessed during a period of duration *T* = 50 arbitrary time units rather at the first patch encountered (figure 2). If no patches were located during this time then the threshold patch quality was set to zero. Comparable results (not shown) were obtained for other values of *T* ranging between 10 and 1000.

The same estimates for *μ* and *D* were obtained for other patch densities, when patch quality was uniformly rather than exponentially distributed, and when turns were instigated by patches whose quality was better than the qualities of either the first 2 or first 3 patches encountered along the current direction of travel. In all cases, a power-law distribution of step lengths was convincing and favoured over exponential and gamma distributions.

Foragers with LW movement patterns located on average about 20 per cent more of the relatively scarce high-quality patches (with qualities ) than foragers that maintained their direction of travel or randomly changed their direction of travel every time they left a patch (figure 4*a*). This remained the case when patches were patchily distributed rather than randomly and uniformly distributed (figure 4*b*).

## 4. Discussion

Optimal foraging theory has until now been almost exclusively concerned with understanding how fitness-maximizing foragers should use information about patch quality to decide how to search *within* patches. The emphasis has been on prey choice and patch residence time. The theory has largely ignored the fact that foragers may need to search *for* patches as well as for the targets within them. Searching for patches will be of importance when the environment is new, dynamic or cannot be mapped in its entirety because the foragers have limited cogitative/perceptual capabilities. LW theory, on the other hand, has been principally concerned with identifying advantageous large-scale movement patterns *for* the location of patches [18–20]. This theory has revealed that LW with *μ* = 2 can increase the patch-encounter probability compared with simple Brownian, straight line and LW with *μ* ≠ 2 when patches are randomly and sparsely distributed, prompting the suggestion that LW with *μ* = 2 represent an evolutionary optimal searching strategy [37,38].

In this article, it was shown how foragers can use information about patch quality to facilitate the execution of LW movement patterns with *μ* = 2 and thereby search effectively for patches. In this novel picture, the low-quality (smaller) patches act as signposts that guide foragers to the most profitable patches.

It has become apparent that other mechanisms (e.g. conspecific odour trail avoidance and re-orientating at odour trails left by correlated random walkers) can also lead to the emergence of LW with *μ* = 2 movement patterns [39–43]. However, when competing hypotheses are equal in other respects, the law of parsimony recommends selection of the hypothesis that introduces the fewest assumptions and postulates the fewest entities while still sufficiently answering the question. Therefore, searching *for* and *within* patches, should, so far as possible, be attributed to similar causes and cogitative abilities.

Whether or not foragers actually use patch quality when searching *for* patches is an open question that has not been explored in the literature. Nonetheless, a candidate exemplar may be found in the classic observational study made by Heinrich [44] of bumblebee (*Bombus terricola*) movements (distances and turning angles) at clover (*Trifolium repens*) patches. Heinrich [44] observed that bumblebees tend to approach the nearest flower but then often depart without landing or probing it, if it has been visited previously; unvisited flowers (high-quality resources) are not rejected in this manner. Patch quality is assessed through the detection of scent marks [45,46] and learnt by experiencing that recently visited flowers are unrewarding [47]. Heinrich [44] also observed that on successive flower-head visits in depleted areas, bumblebees moved more forward than backward (82% versus 18%). These observations are consistent with the theoretical expectation that fitness-maximizing foragers will move in a straight line until encountering a high-quality patch, neglecting any poor patches encountered on route. The theoretical prediction that such foragers will have LW movement patterns with *μ* = 2 is consistent with Edwards *et al*. [25] re-examination of Heinrich's [44] data. Edwards *et al*. [25] found tentative evidence of LW flight patterns with *μ* ≈ 2, reporting that these LW were marginally favoured over an alternative model in which step lengths were exponentially distributed.

The theoretical expectation that foragers adapt to local variations in patch quality is also consistent with observations of the nectar-gathering foraging behaviours of bumblebees (*Bombus flavifrons* and *B. bifarius*) on control and nectar-enriched inflorescences of three Rocky Mountain herbs [48]. Cibula & Zimmerman [48] observed that bumblebees encountering a series of enriched plants initially increased the number of flowers per inflorescence that they visited relative to the control inflorescences. After the blossoms from a small number of enriched racemes were probed, the average number of flowers visited per plant then returned to control levels.

Spider monkeys (*Ateles geoffroyi*) may be another candidate organism. The travel paths of spider monkeys are composed of highly linear ‘beeline’ segments, each typically ending at a place where some resource (fruiting trees) is exploited [49]. The monkeys can travel up to 1.5 km in a straight line before stopping at a resource [49]. Even when food is scarce, a number of fruiting trees would typically be found along a straight transect of this length (G. Ramos-Fernández, personal communication). The monkeys do not generally continue in the same ranging direction after exploiting a resource: travel paths are likely to deviate at the site of resource exploitation rather than between such sites [49]. Ramos-Fernández *et al*. [29] reported that a power-law with *μ* ≈ 2 provides a good fit to the distribution of distances travelled by spider monkeys between successive foraging bouts. Each of these observations is consistent with model expectations and with the emergence of LW with *μ* = 2.

The simulations of Boyer *et al*. [39] and Santos *et al*. [50] provide alternative explanations of the power-law scaling reported for spider monkeys. Boyer *et al*. [39] suggested that the movement patterns are, in fact, an emergent property of the *deterministic* way in which spider monkeys interact with their environment. The suggestion of Boyer *et al*. [39] stems from simulations of foragers that move so that the quantity *l _{ij}/Q_{j}* is minimal among previously unvisited patches

*j*, where

*l*is the distance between patches

_{ij}*i*(the current location of the forager) and patch

*j*, and

*Q*is the quality of patch

_{j}*j*. The quantity

*l*roughly represents a cost/gain ratio for a movement segment. Boyer

_{ij}/Q_{j}*et al*. [39] found that a power-law with

*μ*=

*β*− 1 provides a good fit to the distribution of simulated movement lengths when resources are randomly distributed and when resource-qualities are power-law distributed with exponent

*β*. The latter is consistent with observations of Ramos-Fernández

*et al*. [29] because a power-law with

*β*= 2.6 ± 0.2 provides a good fit to the distribution of the tree sizes at the observation site [39] and because tree size is commonly regarded as one of the most accurate methods for estimating fruit abundance of tropical tress species [51]. The fitting

*β*= 2.6 ± 0.2 is consistent with previous studies of tree size distributions [50,51]. The simulations of Santos

*et al*. [50] show that power-law distributions of path length will arise in animals that forage within narrow strips and always move to the nearest previously unvisited resource. This is pertinent because the spider monkeys studied by Ramos-Fernández

*et al*. [29] resided within a strip-like region of land constrained by a lake.

It remains to be seen whether spider monkeys assess patch quality as in the current model, or minimize *l _{ij}/Q_{j}* as in the model of Boyer

*et al*. [39], or whether some other mechanism [50] is operating.

The findings reported here show how the basic ingredients of optimum foraging theory could enable foragers to execute LW searches with *μ* = 2 for patches and thereby integrates search components at two different scales. It is hoped that this potential synthesis of searching for and within patches will be examined experimentally. It would also be interesting to examine whether there is empirical support for some of the theory's wider ramifications. The theory does, for instance, suggest that foragers could use visual, olfactory or other sensorial stimuli rather than patches as signposts to facilitate execution of LW searches with *μ* = 2.

## Acknowledgements

This research is funded by the Biotechnology and Biological Sciences Research Council (BBSRC). I thank Don Reynolds for his careful reading of an earlier version of the manuscript and for his encouraging remarks. I thank Richard Green for providing the simple, intuitive argument for the validity of equation (2.4).

- Received November 23, 2011.
- Accepted December 20, 2011.

- This Journal is © 2012 The Royal Society