Mathematics of optimal foraging

[shkrobius]

Suppose there is a random, sparse distribution of "food" that needs be gathered (it can be 2D or 3D). It can be either depletable of regrowing, but it is stationary. You move at a constant speed taking random turns (uniform distribution) but the time interval for forward motion is taken from a pre-set distribution. It can either be fixed or

Comments

[nassims]

looking at my Roomba vacuum - isn't a spiral movement the most optimal?

[shkrobius]

Certainly not (just think about the case when it is VERY sparse). If the food is not regrowing they say the (nearly?) best strategy is a Levy walk with mu=1. BTW in many cases the foragers physically cannot maintain spiral motion. Eg, bacteria can only produce biased random walks. Marine animals rely mainly on short-distance cues; a deer in dense forest also has to move more-or-less randomly. Some systematic motion is, actually, hard to implement in reality anyway.

[rwalk]

Поскольку пространство состояний во всех этих примерах очевидным образом компактно, то не совсем понятно, как вообще можно говорить о распределниях с тяжелыми хвостами - если априори известно, что длины прыжков равномерно ограничены. Т.е., в любом случае речь может идти о степенном убывании только на каком-то промежутке значений длины.

[shkrobius]

Do not think about these "jumps" as jumps. You move with the constant speed going straight in a given direction and then you decide to change the direction at random. There are no physical limits on this length, the path can be as long as you wish. This is, actually, how the bacteria move: they beat their flagella and go in a straight line for a while, and then stop beating some of these flagella, tumble, and then resume the motion. All directionality comes from the control of the timing when the flight stops and nothing else. They cannot sustain forward motion. I wrote about it in the previous post; there are a few references there. Interestingly, it seems that for bacteria it is Brownian motion.

[rwalk]

I understand your description of the process. From mathematical point of view this is what is called geodesic random walk - I would refrain from calling it "Brownian motion". The point I wanted to make is that identification of heavy tail distributions from empirical samples (let alone estimation of their parameters) is a very delicate statistical problem and I would be extremely cautious concerning any conslusions made "at the physical level of rigor" - this is more or less what the last reference you quote is about.

[chaource]

It seems that Nature has chosen some implementation that is half-way efficient; there is no guarantee that a neurological mechanism could exist that is actually capable of implementing the "mathematically best" strategy (if any), and that this mechanism (if it exists) could evolve.

Experiments were made on humans who were supposed to bet on red or green light, where the frequency of red to green was 3:1 but otherwise the red and the green light appeared completely randomly. Humans figured out that red was more likely, but they did not bet on red all the time (which is the optimal strategy). Humans randomly switch between red and green, of course giving preference to red, but also giving "some chance" to green. This strategy is suboptimal, but it seems that all living beings do this kind of thing.

[shkrobius]

I am not sure it is nonoptimal. One can think about it this way (intuitively). Suppose we have an optimal strategy. Let's rescale (say, zero in). Then it must be optimal again. This consideration suggests that it must be scale invariant. Levy flights are scale invariant. So it seems reasonable that the answer is a Levy flight. On the other hand if you rescale you can rescale your Brownian dispersion. So it all boils down to your ability to rescale during the search. If you can do it, then you can be rescaling, but this requires some kind of intelligence and knwoledge of the surroundings. If you never need to rescale, Brownian motion must be OK. If there is need to rescale but no hard-wired possibility of rescaling, Levy walks could be your answer. I, actually, think that foraging has to be nearly optimal, if only because it is such an important concern for survival. However, it could be constrained both by design and necessity. What surprises me is that there is no mathematical solution to such a simply formulated problem with a

[chaource]

Perhaps, it is far from obvious that the mathematically "best" solution must be scale-invariant. If you add the extra condition that the strategy must be scale-invariant (because the bacteria is too simple to implement a strategy where some parameters vary depending on the length of path already searched, for example), then you get the scale-invariant solution (Levy flights).

Also, it is far from obvious that the foraging strategy implemented in a particular species has to be nearly optimal in the mathematical sense. The strategy just needs to provide enough food for survival, and not be too suboptimal so that other individuals can get significantly ahead of you. Basically, the strategy is about as optimal as you can get given all other constraints imposed on your species (e.g., whether a nervous system or a memory facility is available).

[shkrobius]

I guess you mean that if one retains memory of gathering along the trajectory, there could be a better strategy than simply Levy flights, because, for example one can stay away from already grazed areas. Yes, now I see the difficulty: I tacitly assumed that the organism has no memory or analytical capabilities, whereas in reality it does, and it is difficult to specify how much of it is available. Perhaps the chief difficulty must be formulating the problem in a meaningful way. It might be hard even for the bacteria, because they do have memory of food gradients (about a few seconds) and enough intelligence to use it for biased random walks. So this fuzziness is present from the start