Transcript
Dynamical Robustness of Le´vy Search Strategies E. P. Raposo, 1 Sergey V. Buldyrev, 2 M.G. E. da Luz, 3 M.C. Santos, 3 H. Eugene Stanley, 2 and G. M.Viswanathan 2,4 1 Laborato´ rio de Fı´ sica Teo´ rica e Computacional, Departamento de Fı´ sica, Universidade Federal de Pernambuco,50670-901, Recife-PE, Brazil 2 Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts 02215, USA 3 Departamento de Fı´ sica, Universidade Federal do Parana´ , 81531-990, Curitiba-PR, Brazil 4 Departamento de Fı´ sica, Universidade Federal de Alagoas, 57072-970, Maceio´ -AL, Brazil (Received 3 September 2002; published 12 December 2003)We study the role of dynamical constraints in the general problem of finding the best statisticalstrategy for random searching when the targets can be detected only in the limited vicinity of thesearcher.We find that the optimal search strategy depends strongly on the delay time during which apreviously visited site becomes unavailable. We also find that the optimal search strategy is alwaysdescribed for large step lengths ‘ by a power-law distribution P ‘ ‘ ÿ , with 1 < 2 . Ourfindings appear to remain valid even if arbitrary energy costs of locomotion are considered. DOI: 10.1103/PhysRevLett.91.240601 PACS numbers: 05.40.Fb Quantifying random search patterns has been a chal-lenging interdisciplinary problem [1,2] that is attractinggrowing interest [3–9]. The practical relevance of theproblem spans areas that include theoretical physics, in-formation technology (information foraging theory [10]),industrial processes, and theoretical ecology [1,2,5].Fundamental aspects of random search problems canbe explained in terms of Le´vy walks and Le´vy flights[11,12]. In particular, the random search problem of find-ing the most efficient strategy of searching for randomlylocated objects (targets) whose exact locations are notknown a priori has motivated several studies [3–5,13]. Aconventional way of modeling random search is to as-sume the searcher performs a random walk in which thedirection of each step is independent of previous steps andthe length ‘ of each step is taken from a distribution P ‘ .In the biological literature, studies usually tend toassume that P ‘ is a Poisson or some other short-taileddistribution with finitevariance. In this case the motion of the searcher becomes equivalent to regular diffusion asdescribed by a Gaussian probability density. A recentstudy [4] proposed that P ‘ , for many species, mayhave long power-law tails: P ‘ ‘ ÿ : (1)In the case 1 < < 3 , the variance of this distributiondiverges, extremely long steps dominate the motion of thesearcher, and the probability density of its displacementconverges in the asymptotic ‘ !1 limit to a Le´vy stabledensity with index ÿ 1 . In stable probability den-sities, after a large number of steps the distribution of theresulting composed step has the same step distribution asthe srcinal distribution, with identical behaviors in thetails. Le´vy stable densities thus provide a generalizationof the Gaussian stable density. In addition, an importantparameter of P ‘ is the characteristic length ‘ 0 , whichdetermines the lower cutoff of the power-law distribution(1), below which it becomes essentially constant. In thiscase, ‘ 0 is related to the proportionality coefficient in thepower-law decay by ‘ 0 lim ‘ !1 P ‘ ‘ ÿ 1 1 = ÿ 1 ; (2)and represents the persistence length of the random walk,being also associated, in the context of animal foraging,with the inertia of the animal motion.Here we assume that in general a forager can be mod-eledbya randomwalk inwhichthe distributionofstepsisgiven by Eq. (1), with the parameter 1 < 3 [14]. Thenatural question that arises concerns how to determinethe optimal value of that provides the maximal amountof targets(e.g., food) foundper unit lengthtraveledby thesearcher.The studies in Refs. [4, 5, 13, 16, 17] have shownthat if target sites are sparse and can be visited anynumber of times (unrestricted, nondestructive search),then opt 2 leads to the optimal search strategy.However if a target site can be visited only once (destruc-tive search), then takes on an optimal value opt ! 1 ,corresponding essentially to rectilinear ballistic motionbetween targets, since there is no advantage in returningto a previously visited site. In addition, experimental dataon foraging for different animal species appear to agreewith the theoretical predictions [3–5,13].One advantage of a statistical analysis approach relatesto how it can lead to general and robust results, indepen-dently of the peculiarities of the particular systemstudied. For the random search problem, the findingsconcerning the optimal strategy appear to be valid forany dimension of the foraging space [5,13] and seem to bemainly independent of the presence of short-range corre-lations arising from phenomena such as learning andpredator-prey relationships [16]. Nevertheless, only fromPH YSICA L R EVI EW L ET T ERS week ending12 DECEMBER 2003 V OLUME 91, N UMBER 24240601-1 0031-9007 = 03 = 91(24) = 240601(4)$20.00 2003 The American Physical Society 240601-1 the dynamical details of specific real systems can oneinfer relevant parameters that may be important for theircharacterization. For animal foraging especially, the dy-namical search details can give the biologist studying aparticular species information about the environment ormetabolic aspects of the species. Hence, in this work weinvestigate the influence of two dynamical aspects rele-vant to the general random search problem.We first study the role of the delay time during whicha previously visited site becomes unavailable for futurevisits.There are two general kinds of strategies. If a foundsite regenerates very quickly, then the best strategy in-volves waiting near the site for it to regenerate, leading toBrownian motion. However, if there is no advantage inwaiting for the previously found site to regenerate, and if target sites are not likely to be found in the immediatevicinity of the searcher, then we find that the best searchstrategy always involves power laws, with the optimalexponent restricted to the interval 1 < opt 2 .Specifically, we find that 2 for ! 0 (nondestruc-tive limit) and ! 1 for !1 (destructive limit). Inthis regime we also find that space-limited Gaussianstrategies [14] (corresponding to 3 ) lead to ratherinefficient searches. In the context of animal foraging thisresult is also related to the problem of target revisitabilityand accounts for the fact that realistic targets cannot berevisited an infinite number of times, nor do they neces-sarily disappear forever in nature.We then also show thatthe introduction of an arbitrary (energetic) cost functionassigned to the search trajectory does not change theoptimal value opt , although in some cases its presencesignificantly limits the range of physically meaningfulvalues for [17].To introduce the delay time , we modify the foragingmodel proposed in Ref. [4] by allowing the searcher tolook for randomly distributed sites according to the fol-lowing three locomotion rules:(A) If there are target sites located within a ‘‘directvision’’ distance r (which in principle can be larger than ‘ 0 ), the forager detects one of them with some probabilityand then moves on a straight line to the detected site.(B) If no target sites within r are detected, the searcherchooses a direction at random and a step length ‘ j fromthe probability distribution (1), and then moves withconstant velocity v to the new point, constantly look-ing for a target site within a distance r along its way. If the searcher does not detect a site, it stops after traversingthe distance ‘ j and chooses a new direction and a newdistance ‘ j 1 ; otherwise, it proceeds to the target as inRule (A).(C) In the case a target site is detected by applyingRules (A) or (B), it becomes unavailable for future visitsduring a time , after which it regenerates.Rule (A) is essentially based on a short-range detectionmechanism of target sites, constituting the short flightlength regime. On the other hand, Rule (B) actuallyinvolves a random search and governs the intermediateand long flight regimes. So, for Rule (B) to apply thecharacteristic spacing of the target-site Poisson distri-bution should considerably exceed r , i.e., r . Thisrepresents the cases of low and intermediate concentra-tions of target sites. In contrast, when target sites areplentiful, searches of type (B) become rare and the for-aging process is driven by the detection events (A), with aPoisson distribution.In Rule (B) the searcher truncates its path if it finds atarget site within the distance r along its way, so theeffective probability distribution in fact corresponds toa so-called ‘‘truncated Le´vy distribution’’ [18] with finitemoments, the cutoff length being associated with [4,18], even though the convergence to Gaussian behavioroccurs only after an extremely large number of steps [18].Indeed, this upper cutoff emerges naturally in real sys-tems, due to their finite sizes, or, in the case of animalforaging, due to biological constraints which, e.g., canlead the animal to starve to death if no food site is locatedwithin a certain maximum range.As was shown in the one-dimensional case (see p. 155of Ref. [15]), for any power-law tailed distribution, if theforager starts from a point x z of an interval 0 ; ,where 0 < z< 1 , and if =‘ 0 !1 , then the optimalstrategy is achieved provided opt 2 2ln z o 1ln z : (3)We can relate the distance z to thevelocity of the foragerand the time of recovery of the target site, where z v: (4)If ! 0 , then z ! 0 , ln z !ÿ1 , and therefore opt 2 .When z > 1 =e 2 , Eq. (3) gives < 1 , which correspondsto the motion along a straight line with constant velocity(nonlocalized regime).In the case of d dimensions, the exact solution of theaverage total flight distance is not known; however, theresults obtained in the one-dimensional case should stillhave validity, since in d dimensions the forager movesalong a one-dimensional corridor of cross section propor-tional to r d ÿ 1 . The average length of this corridorbetween two target sites plays the role of the length of the one-dimensional interval 1 r d ÿ 1 ; (5)where is the density of the target sites. This quantity isequivalent to the mean free path in the problem of gasdiffusion.Equation (3) was obtained in Ref. [15] using hyper-geometric functions. To illustrate the one-dimensionalderivation in simple terms, we approximate the aver-age length of the step by the expression calculated [4]PH YSICA L R EVI EW L ET T ERS week ending12 DECEMBER 2003 V OLUME 91, N UMBER 24240601-2 240601-2 for a power-law distribution P ‘ > x ‘ 0 =x ÿ 1 for x > ‘ 0 , P ‘ > x 1 for x ‘ 0 , h ‘ i 2 ÿ ‘ 1 ÿ 0 ÿ 12 ÿ 2 ÿ ÿ ‘ 2 ÿ 0 ‘ 1 ÿ 0 ; (6)truncated at larger distances by and at small dis-tances by ‘ 0 . For < 2 this expression is dominated bythe upper cutoff . For > 2 it is dominated by thelower cutoff ‘ 0 . We take the d -independent scaling of the average number of steps before the forager finds atarget site as [15] N s x ÿ x ‘ 20 ÿ 1 = 2 ; (7)where the initial position of the forager is x v .The average length h L i traveled by the forager before itreaches a target site can be approximated as a product of the average step length and the average number of steps h L i N s h ‘ i ; (8)so that, by introducing Eq. (7) with z x= , we get h L i 1 ÿ =‘ 0 ÿ 2 ÿ 1 2 ÿ z ÿ z 2 ÿ 1 = 2 : (9)If z=‘ 0 1 and < 2 , then h L i can be approximated as h L i 2 ÿ z ÿ z 2 ÿ 1 = 2 ; (10)which has a minimum at 2 2ln z ÿ z 2 ; (11)thus coinciding with Eq. (3) for small z [19].Figure 1 displays two-dimensional simulation resultsas a function of . When target sites are allowed to bevisited at any time ( ! 0 ; unrestricted, nondestructivelimit), a power-law long-distance Le´vy distribution with opt 2 optimizes the search, in agreement withEqs. (3) and (11). In contrast, for 1 the maximum in tends to downshift towards 1 ; corresponding torectilinear ballistic motion between targets (destructivelimit). Qualitatively similar results are found for one-dimensional searches.An entirely different strategy arises if r ‘ 0 or r ,in which cases Rule (A) fairly dominates over Rule (B),thus leading to optimal Gaussian searches opt 3 . Inparticular, for r ‘ 0 waiting near the old site until itregenerates becomes competitive. Therefore, opt 2 arises as a compromise between the 1 (by exploringnew sites without trying to return to visited sites) and the 3 (wait near the visited site for it to regenerate)strategies.The above discussion, based on a statistically definedefficiency function, does not take into account the influ-ence of dissipative phenomena that might be important inrealistic searches such as animal foraging. We thereforeintroduce an arbitrary locomotion energy cost function f h L i , assigned to the average distance traveled betweentwo target sites and conditioned only by being monotoni-cally increasing.The new efficiency function is now E h E i = h L t i , where the average total length of the walk, h L t i ,can be approximated [20] by the product N h L i , where N denotes the mean number of visited sites. The mean netenergy h E i gained by the searcher in finding randomlydistributed target sites (e.g., calories, nutrients, etc. in thecase of animal foraging) is similarly written as h E i N h E s i , with h E s i ÿ f h L i the net mean energygained per target site found, and the gross mean energygained per target. Here a natural constraint, h E i > 0 ,emerges since the average energy cumulated in the forag-ing must be positive.By writing E ÿ f ; (12)where 1 = h L i is the statistical efficiency (defined asthe number of targets found divided by total distancetraveled [4]), the extremization of E implies F d=d 0 , with F ÿ f ÿ df=d . Thepossible extrema of E thus arise either from the extremaof or from the zeros of F . Regarding the latter, werecall the energy constraint h E s i ÿ f > 0 and ob-serve that df=d < 0 , since f is an increasing function 1 1.5 2 2.5 µ 1.01.52.02.53.0 η x 1 0 4 τ =0 τ =1 τ =2 τ =3 τ =4 τ =10 τ =16 τ =32 τ =64 FIG. 1. Efficiency vs in two-dimensional searches, forseveral values of , r ‘ 0 1 , v 1 , and target area density 10 ÿ 4 r . When target sites are allowed to be visitedat any time ! 0 , a power-law long-distance Le´vy distribu-tion with opt 2 optimizes the search, in agreementwith Eqs. (3) and (11). In contrast, for 1 , the maximum in tends to downshift towards 1 , corresponding to recti-linear ballistic motion between targets. Qualitatively similarresults are found for one-dimensional searches. PH YSICA L R EVI EW L ET T ERS week ending12 DECEMBER 2003 V OLUME 91, N UMBER 24240601-3 240601-3 of h L i 1 = . Therefore, F > 0 and the extrema of E coincide with those of the statistical efficiency . Finally,since d 2 E =d 2 < 0 at the extrema points, they are char-acterized as maxima of the energy efficiency. However,although the introduction of an arbitrary cost functiondoes not change the results for the optimal value opt , itspresence might significantly limit the range of acceptablevalues for due to the energy constraint h E i > 0 .In summary, we have found that the best search strat-egy for a searcher to follow is strongly dependent on thetarget-site revisitability delay time during which apreviously visited site becomes unavailable for futurevisits. When there is no advantage in waiting for thepreviously found site to regenerate, and when target sitesare not likely to be found in the immediate vicinity of thesearcher, then we find that the best search strategy alwaysinvolves power laws, with the optimal exponent restrictedto the interval 1 < opt 2 . Specifically, we find that 2 for ! 0 (nondestructive limit) and ! 1 for !1 (destructive limit). In this regime we also find thatspace-limited Gaussian strategies [14] (corresponding to 3 ) lead to rather inefficient searches. The optimalvalue opt remains robust with respect to the introductionof an arbitrary cost function assigned to the search tra- jectory so long as ‘ 0 r and does not depend on thedetails of the dissipative process. Nevertheless, the pres-ence of such energetic constraints significantly limits therange of acceptable values for .We thank CNPq, FAPEAL, and NSF for financialsupport. G. M.V. also thanks C.R. Silva for useful dis-cussions. [1] D.W. Stephens and J.R. Krebs, Foraging Theory (Princeton University Press, Princeton, 1987).[2] Foraging Behavior , edited by A.C. Kamil, J.R. Drebs,and H.R. Pulliam (Plenum, New York, 1987).[3] G. M. Viswanathan, V. Afanasyev, S.V. Buldyrev, E.J.Murphy, P. A. Prince, and H. E. Stanley, Nature(London) 381 , 413 (1996).[4] G. M. Viswanathan, S.V. Buldyrev, S. Havlin, M.G. E.da Luz, E. P. Raposo, and H. E. Stanley, Nature(London) 401 , 911 (1999).[5] F. Bartumeus, J. Catalan, U. L. Fulco, M. L. Lyra, andG. M. Viswanathan, Phys. Rev. Lett. 88 , 097901 (2002); 89 , 109902(E) (2002).[6] M. Levandowsky, J. Klafter, and B.S. White, Bull.Marine Sci. 43 , 758 (1988).[7] F. L. Schuster and M. Levandowsky, J. Euk. Microbiol. 43 , 150 (1996).[8] B.J. Cole, Anim. Behav. 50 , 1317 (1995).[9] M. F. Shlesinger and J. Klafter, in On Growth and Form ,edited by H. E. Stanley and N. Ostrowsky (Nijhoff,Dordrecht, 1986).[10] P. Pirolli and S. Card, in Proceedings of the 1995Conference on Human Factors in Computing Systems (ACM Press, New York, 1995), p. 51.[11] C. Tsallis, Phys. World 10 , 42 (1997).[12] Le ´ vy Flights and Related Topics in Physics , editedby M. F. Shlesinger, G. M. Zaslavsky, and U. Frisch(Springer, Berlin, 1995); I. Peterson, The Jungle of Ran-domness: A Mathematical Safari (Wiley, New York,1997).[13] G. M. Viswanathan, V. Afanasyev, S.V. Buldyrev, S.Havlin, M.G. E. da Luz, E. P. Raposo, and H. E.Stanley, Physica (Amsterdam) 282A , 1 (2000).[14] The case < 1 does not correspond to normalizabledistributions. In the long-distance regime and due tothe central limit theorem, the Gaussian is the stabledistribution for 3 . The advantage of the distribution(1) lies in the fact that the parameter naturally selectsthe optimal asymptotic distribution as being Gaussian( 3 ) or long-distance Le´vy type ( 1 < < 3 ).[15] S.V. Buldyrev, M. Gitterman, S. Havlin, A. Ya. Kazakov,M.G. E. da Luz, E. P. Raposo, H. E. Stanley, and G. M.Viswanathan, Physica (Amsterdam) 302A , 148 (2001).[16] G. M. Viswanathan, V. Afanasyev, S.V. Buldyrev, S.Havlin, M.G. E. da Luz, E. P. Raposo, and H. E.Stanley, Physica (Amsterdam) 295A , 85 (2001).[17] M.G. E. da Luz, S.V. Buldyrev, S. Havlin, E. P. Raposo,H. E. Stanley, and G. M. Viswanathan, Physica(Amsterdam) 295A , 89 (2001).[18] R. N. Mantegna and H. E. Stanley, Phys. Rev. Lett. 73 ,2946 (1994).[19] Note that these results for a single searcher may re-quire modification if there is a flock of N searchers.See, e.g., G. Berkolaiko et al. , Phys. Rev. E 53 , 5774(1996); G. Berkolaiko and S. Havlin, ibid. 55 , 1395(1997).[20] S.V. Buldyrev, S. Havlin, A. Ya. Kazakov, M.G. E. daLuz, E. P. Raposo, H. E. Stanley, and G. M.Viswanathan,Phys. Rev. E 64 , 41108 (2001). PH YSICA L R EVI EW L ET T ERS week ending12 DECEMBER 2003 V OLUME 91, N UMBER 24240601-4 240601-4
