Today I read a paper titled “High-speed Flight in an Ergodic Forest”
The abstract is:
Inspired by birds flying through cluttered environments such as dense forests, this paper studies the theoretical foundations of a novel motion planning problem: high-speed navigation through a randomly-generated obstacle field when only the statistics of the obstacle generating process are known a priori
Resembling a planar forest environment, the obstacle generating process is assumed to determine the locations and sizes of disk-shaped obstacles
When this process is ergodic, and under mild technical conditions on the dynamics of the bird, it is shown that the existence of an infinite collision-free trajectory through the forest exhibits a phase transition
On one hand, if the bird flies faster than a certain critical speed, then, with probability one, there is no infinite collision-free trajectory, i.e., the bird will eventually collide with some tree, almost surely, regardless of the planning algorithm governing the bird’s motion
On the other hand, if the bird flies slower than this critical speed, then there exists at least one infinite collision-free trajectory, almost surely
Lower and upper bounds on the critical speed are derived for the special case of a homogeneous Poisson forest considering a simple model for the bird’s dynamics
For the same case, an equivalent percolation model is provided
Using this model, the phase diagram is approximated in Monte-Carlo simulations
This paper also establishes novel connections between robot motion planning and statistical physics through ergodic theory and percolation theory, which may be of independent interest