Levy Foraging in a Dynamic Environment – Extending the Levy Search

Abstract

A common task for robots is the patrolling of an unknown area with inadequate information about target locations. Under these circumstances it has been suggested that animal foraging could provide an optimal or at least sub-optimal search methodology, namely the Levy flight search. Although still in debate, it seems that predators somehow follow this search pattern when foraging, because it avoids being trapped in a local search if the food is beyond the sensory range. A Levy flight is a particular case of the random walk. Its displacements on a 2-D surface are drawn from the Pareto-Levy probability distribution, characterized by power law tails. The Levy flight search has many applications in optical material, ladars, optics, large database search, earthquake data analysis, location of DNA sites, human mobility, stock return analysis, online auctions, astronomy, ecology and biology. Almost all studies and simulations concerning the Levy flight foraging examine static or slowly moving (with respect to the forager) uniformly distributed resources. Moreover, in recent works a small swarm of underwater autonomous vehicles has been used to test the standard Levy search in the underwater environment, with good results. In this paper we extend the classical Levy foraging framework taking into consideration a moving target allocated on a 2-D surface according to a radial probability distribution and comparing its performance with the random walk search. The metric used in the numerical simulations is the detection rate. Simulations include the sensor resolution, intended as the maximum detection distance of the forager from the target. Furthermore, contrarily to the usual Levy foraging framework, we use only one target. Results show that Levy flight outperforms the random walk if the sensor detection radius is not too small or too large. We also find the Levy flight in the velocity of the center of mass model of a fish school according the Kuramoto equation, a famous model of synchronization phenomena. Finally, a discussion about the controversy concerning the innate or evolutionary origin of the Levy foraging is given.

Keywords

Levy foraging Levy flight random walk blind search

1. Introduction

In this paper, we extend the standard Levy search and show that the center of mass of a biological or of a robot swarm is able to move following a Levy statistics if coordinated by the Kuramoto equation. A random walk with steps (spatial displacements) from a Pareto-Levy distribution [1] is called a Levy flight (LF). Visually it is a set of many small displacements with just a few very large “jumps”. In the Levy flight the steps are considered instantaneous, i.e. the velocity is high with respect to other motions, otherwise we have a Levy walk (finite velocity steps). It has been speculated that a Levy flight (LF) is used by predators to locate the prey, if the food is rare in the predator's environment [1]. As a matter of fact, this claim has been criticized several times, advancing that on the field records do not confirm the Levy flight statistics, rather approximate an innate composite correlated random walks [2, 12].

Nevertheless, LF is an appealing working hypothesis for naturalists, while it is an interesting hint for technicians.

The blind search for targets resembles closely the animal foraging and therefore one tries to apply this biological inspired methodology to optimize the search, when no a priori information is available. Recently, a generalization of LF has been proposed by Zhao [14]. Foraging is considered a cognitive process to find sparse and revisitable targets using an exploration-return mechanism to mimic the spatial memory. The forager switches randomly between two step-based movements, which are modelled as exploration and return. In the exploration phase, the forager tries to locate targets in the landscape following the setting of a truncated Levy-flight and then moves back to a previously visited site.

Usually the Levy search scenario consists of a number of non-mobile targets uniformly distributed on a surface. Here we extend these scenarios to a single mobile target initially positioned according to non-uniform probability distributions, with a given sensor resolution, testing the performance of the Levy flight search and of the random walk. We focus on the marine environment with explicit reference to the underwater autonomous vehicles (AUV), robots used to patrol marine areas possibly in groups called swarms. Einarsson [15] has investigated real fish schools moving according to the Kuramoto model (KM). Here we show in numeric simulations how the Kuramoto model spontaneously generates the Levy statistics, therefore we can ascertain that a biological school is led to a Levy search. Some advantages appear immediately: a distributed control governs the swarm or school, i. e. no leader is necessary, the amount of energy dissipated during the search is reduced.

Finally, we provide a short discussion the evolutionary nature of the Levy foraging [1, 2, 11, 12]. We refer to the term “evolutionary” in the sense of “learned behaviour”, to avoid tautologies and philosophical speculations. Is the Levy foraging pattern of living individuals and groups innate or learned during centuries? Has the environment modified the organisms or vice-versa?

It is not only a theoretical issue: practical implications concern how to implement the LF in the AUV driving logic. In fact, determining that the LF in nature has been learned could direct the research of the driving logic towards cognitive models such as neural networks.

On the other hand, an innate LF would imply a build-in structure, maybe a hardware device, that in the case of a swarm could be as simple as an oscillating electronic circuit.

2. The Levy Distribution

Let us consider the Levy distribution expression [11]:

P_{r} (x) \cdot \sim x^{-}^{α} w i t h 1 \leq α \leq 3

(1)

where the random variable x is the displacement (see in Fig. 1 the Levy histogram).

Figure 1.

The Levy flight histogram (with α =1.9 and 1000 samples

Note in Fig. 2 some large displacements and clusters on a plane representing the foraging area. The large jumps allow a more complete exploration of the plane with respect to the random walk, (see Fig. 3).

Figure 2.

Example of a Levy flight on a plane. “Jumps” are the longer straight lines connecting the cluster formed by shorter lines.

Figure 3.

Example of a random walk on a plane

The random walk (RW) concentrates its search in a more reduced area, as the step size is constant and the direction is random.

The number of RW steps is larger than the LF case to keep a fair comparison, as the LF step is not restricted to a fixed euclidean distance.

3. Radial Probability and Moving Target

Usually it is assumed that targets are uniformly distributed in the plane (Fig. 4), are static or moving with a speed very low with respect to the forager and no a priori information is available.

Figure 4.

Example of the classic Levy foraging; the probability distribution is uniform. The red circles are the actual multiple targets.

Although this is a common circumstance in animal foraging, it is not a unique possibility: for example, in [3] an information biased Levy flight is investigated, but in a static environment with a Gaussian probability distribution and a large number of targets. Recently, the standard Levy search mini-AUV has been tested successfully in patrolling activities with mini-AUV [4].

However, the robot foraging may require a different point of view, i.e. moving targets, radial probability distributions and sensor's resolution: here we study these different possibilities that were not taken into consideration in the literature, at the best of our knowledge.

Moreover, targets often are reduced to just one. These needs often arise during surveillance tasks or rescue activities in the marine environment. Sometimes it is necessary to find a target whose position is previously known to be close to a certain point, while departures can be considered less probable proportionally to the distance from the point (Fig. 5).

Figure 5.

The probability decreases from the Origin

In other cases, targets could move inside a circular ring centered on a point (Fig. 6). More complex radial distribution are also possible, see Fig. 7.

Figure 6.

Here the probability is uniform inside the ring centered on the Origin. The red circle is the single target.

Figure 7.

A composite probability distributions; the colours indicate various uniform distributions. The red circle is the single target.

The Levy and the random walk search start from a randomly chosen point inside the allowed area. The operating autonomy is limited by the available number of steps. The velocities of the patrol and the target are not taken into consideration. Targets move linearly (Fig. 8) or along an open curve as Fig. 9, in a surface area of 400×400 meters.

Figure 8.

From the blue square, the target is directed towards a point (in red) on the dotted blue circumference, following the straight line. The search starts from a random point inside the circumference. The arrow indicates the motion direction of the single target.

Figure 9.

From the blue square the target (the red point) follows the curve, while the search starts from a random point, in this case close to the Origin. The green dotted circle represents the detection sensor range. The arrows indicate the motion direction of the single target.

The sensor resolution, meaning the maximum detection distance of the forager/patrol from the target, is usually neglected in the simulations.

However, the same concept of locality search depends from it: when the range of detection is very large or very small, the advantages of the Levy search tend to disappear and the random search may even result a better strategy.

Therefore we are interested in investigating this rule of thumb in the case of extended Levy flights as specified before. The search is considered successful if the patrol meets the target within a radius R, see Fig. 9.

The radial probability distribution has no particular effect on the LF/RW search. This means that the detection of moving targets follows the pattern of the static case and it is even more emphasized, as shown in Fig. 13.

4. Simulation Results

For each scenario of Table I a minimum of 10000 numerical simulation have been completed to determine the successful target detection operated by the LF or RW patrol. The patroller has an autonomy of N = 6400 steps (but the euclidean path is the same for LF and RW). The starting point of the patrol's search has been selected randomly. From Table I and Fig. 10, 11, 12, 13 it is clear that the Levy Flight finds the target more easily than the Random Walk search if 5 < R < 100 m, because out of this range we have a local search and the RW is favored. In fact, if the search range R is very large with respect to the search area (400×400 surface units) any search strategy is almost optimal, because the area can be patrolled completely within a few simulation steps. We can see from Table 1 on the row indicating one moving target on a curve that for R=100 to R=300 success percentage for RW and LW are close or equal. On the other hand, when R < 5, LF success rate is 1.3% while RW is 0.5%, that is a very small advantage. This is due to the non-local characteristic of the LF search. The more the search is reduced to a local search, the less the LF is an optimal strategy (of course till saturation occurs for R > 100). These results are somewhat new. In the intermediate range, say 5 < R < 150, the Levy Flight search of a moving target following a generic trajectory outperforms the Random Walk, as showed in Table 1 in the “one moving target on a curve” case. In the Table 1 are reported only the intermediate range R = 10 and R = 100, but other intermediate ranges show similar results. As said many times before, this is due to the capability of LF to cover a larger surface “jumping”. Here we do not discuss the mathematical properties of LF and RW, simply we affirm that simulations in the intermediate range of the sensor resolution show an advantage for LF.

Figure 10.

Ring probability distribution with one static target. Plot of success rates vs. detection ranges. On the right the same plot but with a logarithmic scale (LF, black continuous, RW, blue dotted).

Table 1.

Simulation Results: the extended LF outperforms RW

Patrol search scenario	Successful search percentage / Detection Radius (meters)
	R	1	5	10	20	30	50	100	150	200	300
Levy Flight, one static target, ring probability distribution	%	1.6		6.6	9.9			36.3		74	99
Random Walk, one static target, ring probability distribution	%	2.1		4.94	6.1			30.3		67	99
	R	1	5	10	20	30	50	100	150	200	300
Levy Flight, multiple static targets, radial decreasing probability istribution	%	7		26.5				89.5		99.9
Random Walk, multiple static targets, radial decreasing probability distribution	%	6.21		12.7				76		100
	R	1	5	10	20	30	50	100	150	200	300
Levy Flight, one static target, circle probability distribution	%	2.32		9				42			100
Random Walk, one static target, circle probability distribution	%	3.2		4				28			100
	R	1	5	10	20	30	50	100	150	200	300
Levy Flight, one moving target on a curve	%	1.3		6.7				41		74	100
Random Walk, one moving target on a curve	%	0.5		2.4				30		80	100
	R	1	5	10	20	30	50	100	150	200	300
Levy Flight, one moving target on a line	%	1.74		7.45				34.86		60
Levy Flight, one moving target on a trajectory	%	1.64		8.17				32.86		54.4

5. Innate or Evolutionary

The debate on the evolutionary nature of the Levy foraging has been discussed by several Authors [1, 2, 11, 12, 17]. In [11] Authors claim that the empirically measured Levy behavior turns out to be not only a Nash equilibrium, but also an evolutionary stable strategy and argue that the ubiquity of the Levy pattern, both in behavior and cognition of humans and animals, suggests that the brain regions responsible for implementing it are likely to be evolutionarily old. Less recently, Humphries [17] claims that «Levy movements of albatrosses can yield high energy gains in resource sparse habitats, raises the question of whether an innate stochastic search process based on Levy flight foraging has naturally evolved in organism». Although a clear definition of evolutionary is not given, Humphries decisively supports that biological Levy flight may have naturally evolved as a search strategy in presence of sparse resources and no a priori information. However, we have an alternative emerging hypothesis [2]: some organisms may approximate Levy walks as an innate composite correlated random walks (CCRW). Note that here we refer to the term “evolutionary” in the sense of “learned behaviour”.

Figure 11.

Same as left, but with a log-log plot (LF, black continuous, RW, blue continuous)

Figure 12.

Moving target, symbols as above. (LF, black continuous, RW, blue dotted)

Figure 13.

Same as left, log-log plot. Levy search has a higher performance (LF, black continuous, RW, blue continuous).

It is not only a theoretical issue: practical implications concern how to implement the LF in the AUV driving logic. In fact, due to the complexity of the AUV motion model, the LF implementation is not straightforward [4]. In [5] this driving logic is inspired by the Central Pattern Generator (CPG) paradigm that controls the animal locomotion, but the procedure in [5] introduces errors, even in the experimental environment.

Determining that the LF in nature has been learned could direct the research of the driving logic towards cognitive models such as neural networks. On the other hand, an innate LF would imply a build-in structure, maybe a hardware device. Following the actual bio-inspired model would save time and work, but unfortunately it is unclear what the model is like.

In this paper we suggest an innate model for the LF search. Firstly, the evolutionary-cognitive alternative would require a bio-neural network to learn, at least to some extent, the stochastic relation (1). This is hard task and would be very energetically expensive for mammalians, therefore we reject the evolutionary-cognitive hypothesis. Instead, we conjecture that the brain can be modelled as a set of non linear oscillators able to produce a LF pattern spontaneously. In [6, 7] the CPG has been modelled by the Kuramoto equation and we follow this choice, rather than [5].

Other non linear oscillator models should provide the same results, although we do not provide any formal demonstration for this assumption.

It has been reported that the human brain uses LF to accomplish some high level activities [11], so let us consider the brain divided in several regions as in Fig. 14. Each region is modelled as an oscillator, connected one another to form a network. While this simplification may look excessive, it may be reasonable to group the 10¹¹ nodes of the net in 66 weakly coupled regions [6].

Figure 14.

The brain as a collection of regions modelled by non linear coupled oscillators. The resulting network is a Kuramoto differential system, able to phase synchronize itself.

Now we show briefly how to obtain a LF statistics from this network. Each region i is modelled as a Kuramoto non linear oscillator [8]:

d θ_{i} / d t = W_{i} + k_{i j} / N \sum_{j} s i n (θ_{j} - θ_{i})

(2)

where θ₁ is the i-^th phase of the oscillating quantity (an electrical signal in our case), W_i the natural frequency of the i-th oscillator, k the coupling constant, N the overall number of coupled oscillators in the networks k_ij is 0 or 1, 1 indicating a coupling between agent i and j, 0 the absence of coupling. Kuramoto showed that for N → ∞ the network synchronizes the oscillations (here we have N = 24 oscillators). The Kuramoto equation is widely used to study synchronization phenomena. A single agent is described as a first order dynamics:

d θ_{i} / d t = W_{i}

but when N oscillators are coupled by a connection graph the overall dynamics emerges as (2). The very rich behaviour depends on the competition between each oscillator's tendency to align with its natural frequency and the synchronization-enforcing coupling [16].

Relation (2) indicates the non linear reaction of each oscillator related to the rest of the network with a certain topology (see Fig. 14). (2) is widely used to describe the non linear synchronization phenomena because can be solved exactly using a complex-valued parameter (in the next expression i is the imaginary unit), called order parameter:

Φ (t) = | 1 / N \sum_{j} e^{i θ}^{j} |

(3)

When Φ = 1 the synchronization is complete, otherwise it degrades to random oscillations (Φ = 0). Large values of the coupling parameter k push the network toward synchronization, small k values produce a weak synchronization.

Interestingly, the very same (2) equation can be used to model a swarm or a school. Formally, we consider a set of N points in the complex plane C (call them agents or fishes or robots), whose position and heading angle are:

\cdot r_{i} = e^{i θ}^{i}

d θ_{i} / d t = u_{i} (r, θ_{i})

where i is the imaginary number and the point is the time derivative.

The u parameter is the control law governing the linear or circular motion for the point i. If:

u_{i} (r, θ_{i}) = 0

the motion is linear, following the angle θ_i(0) direction; while if:

u_{i} (r, θ_{i}) = W_{i}

the point i moves following a circle with radius 1/W_i [16]. We shall see a similar mathematical treatment applied to the swarm' center of mass, meaning that a distributed control is theoretically achievable by the KM (2).

Thus the global direction and speed are realized through the local non-linear interactions of the nearest neighbours agent, preventing the overall swarm data collection-elaboration-restitution scheme. In the following pages, we will use this framework to reveal the Levy statistics in the motion of the swarm' center of mass.

In our simulation of (2) k has a low value, in order to implement the weak coupling required in [6]. In fact, Fig. 15 shows the order parameter close to the unity, but not exactly 1.

Figure 15.

The order parameter θ(t) time series oscillates around 0.96. The small k produces the loss of synchronization visible after t=1600 time units.

Fig. 15, 16, 17, and 18 show the value of the order parameter and one of the N solutions of the differential system (2) in the time domain, as well as their histograms. Fig. 16 and Fig. 18 resemble clearly the Levy histogram (Fig. 18 is the histogram of the differentiated time series θ10(n) − θ10(n-1)).

Figure 16.

Histogram of the order parameter θ(t) time series

Figure 17.

All the time series solutions θ(t) of the Kuramoto equation

Figure 18.

Histogram of the θ₁₀(n) − θ₁₀(n−1) time series

Although these are only qualitative evidences, it seems that (2) is a LF generator. As a consequence, no learning is needed, thus evolution is not mandatory.

On the other hand, the innate alternative is simpler with respect to the slow and difficult learning process dependent on the local environment. Interestingly, it is also a convenient solution to the problem of generating a low-cost Levy search control in AUV robots based on simple electronic oscillating circuits.

Recently an interesting contribution to the debate was provided. In [2] Reynolds suggests that the mussels movement pattern approximate very well a composite correlated random walk. According to Reynolds, the CCRW is a better approximation than LF to the real data.

A CCRW occurs when frequently movements with relatively short steps are interspersed with less frequent longer steps, switching between two or more patterns. These movements allow mussels to minimize the time required to form patterned beds. The same movement patterns are present in Mesozoic deep sea strata that are therefore a record of ancient organisms, persisting nowadays [2].

Although these organisms are very different from the mammalians, the innate nature of the movement pattern generation is nevertheless supported, whether it is a Levy flight, a Levy walk, a truncated Levy walk or a composite correlated random walks.

Of course it could be argued that, in a more extensive meaning, also the brain oscillating structure may result from an evolutionary process.

However, the biological oscillating structure needed to produce a Levy flight bio-generator in simple organisms (such as the lamprey [9] and invertebrates [10]), is not particularly complex. Therefore evolution does not seem to play the major role, since no sophisticated mechanism was developed.

Finally, we point out that the very same Kuramoto equation (2) can model also the center of mass velocity of a fish school, as investigated in [13]. In fact, in the complex notation, the expressions of position (4) and of the velocity (5) of the i-^th element are:

r_{i} = x_{i} + i y_{i}

(4)

e^{i θ}^{i} = c o s θ_{i} + i s i n θ_{i}

(5)

It rums out [13] that:

\cdot r_{i} = e^{i θ}^{i}

(6)

and from the expression of the center of mass:

P (t) = 1 / N Σ_{j} r_{j} (t)

(7)

differentiating P(t) and replacing (6)

d P / d t = 1 / N Σ_{j} d r_{j} / d t = 1 / N Σ_{j} e^{i θ}^{j}

(8)

that is, the Kuramoto order parameter Φ(t):

d P / d t = Φ (t)

(9)

This is the velocity of the fish school center of mass. The result seems confirmed by real fish data [13].

We have used this model to simulate the circular movement of the school with a small number (N = 24) of elements. Results in Fig. 19 and Fig. 20 demonstrate how actually the Kuramoto model is able to represent the basic patterns of the swarm motion as a whole as well as a single element.

Figure 19.

Simulation of the fish school 2D circular motion around a fixed center in the x-y plane. Black points are the initial positions, green points are the final positions. Note the small irregularities of the trajectories.

Figure 20.

Simulation of the fish school circular motion. The z-axis represents the velocity. Black points are the initial positions, the green points are the final positions. The irregularities produce the poor alignment here and in Fig. 19, depending on the limited number N of elements in the school.

Moreover, the velocity pattern follows the Levy flight statistics (Fig. 16). This means that a group of animals is able to reproduce the same Levy foraging strategy used by the single organism. The swarm or school synchronizes its movements and so doing generates something that looks like a Levy flight, at least qualitatively.

6. Conclusions

The Levy flight search has been suggested as the animal foraging strategy, because large areas are covered with a minimum energy expenditure. Since in many technological fields similar problems are encountered, the same methodology could be used, for example in marine robot patrolling tasks.

In this paper, we have extended the Levy paradigm to one moving target positioned according to a radial probability density function, considering also the detection range, i.e. the resolution of an onboard sensor. Numerical simulations confirm the Levy flight superiority compared to the random walk, if the search is in the intermediate range of the sensor resolution.

We have also shown that the center of mass of a swarm modelled by the Kuramoto equation shows a Levy flight pattern.

Footnotes

7.

This article is a revised and expanded version of a paper entitled “Levy flight search of moving objects” presented at IARP 2014 Frascati Conference.

References

Edwards

(2007) Revisiting Levy flight patterns. Nature. Vol. 449. pp. 1044–1048.

Reynolds

(2014) Mussels realize Weierstrassian Levy walks as composite correlated random walks. Nature Sci. Rep. Vol. 4. pp. 32.

Marthaler

Bertozzi

, and Schwartz

(2004) Levy searches based on a priori information: the Biased Levy Walk. UCLA CAM Reports.

Sutantyo

and Levi

Moslinger

Read

, Collective-Adaptive Levy Flight for Underwater Multi-Robot Exploration. ICMA IEEE Int. Conf, 2013.

Ijspeert

(2008) Central pattern generation for locomotion. Neural Networs. Vol. 21. pp. 642–653.

Manson

(2012) Characterizing Brain Activity at the Mesoscopic Scale, http://www.ucl.ac.uk/~ucbpdma/sp.pdf. Accessed on 10 Aug 2014.

Ekeberg

R. O.

and Grillner

(1999) Simulations of neuromuscular control in lamprey swimming. Philos. Trans. R. Soc. Lond. B. Biol. Sci. Vol. 354(1385), pp. 895–902.

Kuramoto

, Chemical Oscillations, Waves, and Turbulence, Springer-Verlag, New York, 1984, p. 164.

Cohen

Holmes

Rand

(1982) The nature of the coupling between segmental oscillators of the lamprey spinal generator for locomotion: a mathematical model. J. Math. Biol. Vol. 13(3), pp. 345–369.

10.

Lamb

and Calabrese

(2012) Small is beautiful: models of small neuronal networks. Curr. Opin. Neurobiol. Vol 4, p. 22.

11.

Baronchelli

and Radicchi

(2013) Levy flights in human behavior and cognition. Chaos, Solitons & Fractals, Vol. 56, p. 101.

12.

James

Plank

and Edwards

(2011) Assessing Lévy walks as models of animal foraging, J. R. Soc. Interface, Vol. 8, pp. 1233–1247.

13.

Paley

Leonard

Sepulchre

Grünbaum

And Parrish

(2007) Oscillator models and collective motion. IEEE Control Systems Magazine, pp. 89–105.

14.

Zhao

, rXiv:1406.1649v1 [cond-mat.stat-mech]. Accessed on 06 Jul 2014.

15.

Einarsson

Birnir

Bonilla

, “Ordered, disordered synchronized schools of fish”. https://escholarship.org/uc/item/3ppln231. Accessed on 07 Feb 2014.

16.

Dörfler

, and Bullo

, “Exploring Synchronization in Complex Oscillator Networks”, In Proceedings of the IEEE Conference on Decision and Control, Maui, Hawaii, USA, pp. 7157–7170, 2012.

17.

Humphries

N. E.

, “Foraging success of biological Lévy flights recorded in situ”, Proc. Natl Acad. Sci. 109(19), pp. 7169–7174, 2012.