«

»

Oct 06

High-Speed Navigation through Clutter

1. Background: High-performance Robotics and Biology

Agile robots that can autonomously navigate through cluttered environments has long been a focal direction in robotics research, although little could have been established in realizing them so far. Yet, nature is home to various species of birds that can fly through dense forests with an incredibly high speed. The following BBC video, which has largely motivated this work, shows a hawk’s high-speed flight through a dense forest.


A hawk flies through a dense forest.

Although biologist have extensively studied the behavior of birds during various activities involving steady flight, the analysis of birds’ behavior in cluttered environments has received relatively little attention. Harvard University biologist Biewener and co-workers argue in a recent paper (published in the Journal of Experimental Biology) that the historical focus on steady flight may be due to its theoretical and experimental tractability, rather than its importance. In their paper, Biewener and co-workers also present one of the first experimental results involving pigeons engaging in tight turns.

2. Phase Transitions in High-performance Flight

In this work (see [1]), we study the theoretical foundations of high-performance navigation in randomly-generated obstacle fields, where the statistics of the obstacle generation process are known, but the precise locations and the sizes of the obstacles are not known a priori. Inspired by the related literature in biology, we consider a bird trying to explore new regions in a randomly-generated planar forest environment where the locations and the sizes of the trees are determined by a spatial point process, a statistical model that is widely used in the context of forestry. We show that, when the forest generating process is ergodic, the existence of infinite collision-free trajectories of the bird exhibits a phase transition. More precisely, there exists a critical speed such that

  • on one hand, if the bird flies with a speed that is slightly above the critical, then the bird is doomed to crash into a tree eventually, with probability one,
  • on the other hand, if the bird flies with a speed that is slightly less than the critical, then there exists a trajectory of the bird that avoids collision with the trees indefinitely, with probability one.

Moreover, through novel applications of percolation theory, we thoroughly study the special case when the forest generating process is Poisson and the bird is governed by a simple single-integrator dynamics. In particular, we derive lower and upper bounds on the critical speed. We also show that, when the bird flies with a speed that is above the upper bound, the probability that a collision does not occur for T time units is exponentially small in T. That is, in this regime, the bird crashes into some tree very soon with high probability. On the other hand, when the bird flies with a speed that is below the lower bound, we show that the probability that there does not exist an infinite collision-free trajectory starting from a point that is within a distance of l to the origin is exponentially small in l. In other words, in this regime, there are many infinite collision-free trajectories that are nearby, with high probability. These results suggest a sudden change in the existence of long collision-free trajectories right at the critical speed.

The following two videos illustrate the single-integrator bird’s flight through a Poisson forest in two different regimes. The regions of inevitable collision (the set of points starting from which collision is inevitable) are also shown. The first video shows flight at a speed that is very close to the critical. The second video shows flight at a smaller speed. Notice the difference between the sizes of the inevitable collision regions.


Flight in a Poisson forest at a speed that is very close to the critical speed.


Flight in a Poisson forest at a speed that is close to the critical speed.

In fact, the following figure shows views of the Poisson forest in three different speeds as the speed is gradually increased. The density of the inevitable collision regions increase rapidly as the speed increases gradually.


A look at the Poisson forest at the same tree density but at different speeds. As the speed gradually increases, the inevitable collision become larger very rapidly.

This behavior is observed in Monte-Carlo simulations also. In our simulation study, we have considered many velocity and tree density (intensity of the Poisson process generating the locations of the trees). For each pair, we have generated 200 independent instances of the Poisson forest and calculated the regions of inevitable collision. We have noted the normalized width of the inevitable collision region with maximum width, which we call normalized maximum width. This quantity is an easily-calculable measure of how dense the inevitable collision regions are. Moreover, a normalized maximum width that is close to one indicates that the inevitable collision region is very dense, whereas that close to zero indicates that the region is very sparse. In the latter case, the bird can survive by flying straight most of the time and making small lateral corrections when necessary.

The figure below shows the “phase diagram” obtained by averaging the results obtained through 200 experiments for each velocity and tree density pair.


Normalized maximum width for several velocity and tree density pairs, averaged over 200 trials for each such pair. The black line in the 3D plot on the left shows linearly interpolated data points. The surface is a linear interpolation of the black curves. The plot on the right shows the same surface from above. The x-axis is the tree density, the y-axis is the velocity. A legend for the color code is shown on the very left.

Notice the sharp phase transition right at the critical speed! For a particular tree density, when the speed is gradually increased, the normalized maximum width suddenly increases from zero to one. In other words, just below the critical speed, the inevitable collision regions are very sparse. However, just above the critical it suddenly becomes equal to one; the collision is inevitable.

These results suggest the following. Firstly, the hawk must be flying with a speed that is below the critical, otherwise it must crash into some tree pretty soon, with very high probability. Second, once the hawk is flying with a some speed that is just below the critical, the inevitable collision regions are so sparse that the hawk can fly straight most of the time and make small lateral corrections when necessary.

Now take another look at the video showing the hawk flying through woodland. You will notice that the bird in fact seems to exhibit this kind of behavior. It flies straight most of the time, and makes small lateral corrections only when necessary. The only exception to this comes in when the bird needs to fly between two trees that are very close to each other. In that case, the bird maneuvers by lifting its wings up and opening its tail, using it as a third wing. This allows the bird to continue its flight without loosing much altitude and speed.

3. Conclusions and The Challenges Ahead

Although motivated by birds’ flight through clutter, the analysis presented in our paper is broadly applicable to a novel class of motion planning problems: a robot navigating through a complex environment knows a priori the statistics of the obstacle generating process, but not necessarily the precise locations and sizes of the obstacles.

In this context, our work implies strong negative results. It shows that, when flying with a speed that is larger than the critical, the robot is doomed to crash into some obstacle eventually, with probability one, regardless of the planning algorithm governing its motion. In fact in the case when the locations of the trees are Poisson distributed, on one hand, it is unlikely that the robot can navigate for a long time when flying with a supercritical speed. On the other hand, when flying with a subcritical speed, the robot can maneuver around the obstacles without much effort.

To the best of our knowledge, this work constitutes the first application of ergodic theory and continuum percolation to solve challenging problems of robot motion planning. Moreover, this work is among just a handful of examples where such theory is used not in the context of science, i.e., to analyze physical, social, or economic phenomena, but rather in the context of engineering, for instance, to build agile Unmanned Aerial Vehicles (UAVs).

Currently, we are working on establishing a deeper understanding of the “phase diagram” of high-speed flight under various conditions. In particular, the impact of the perception range as well as perception uncertainty on the chances of the survival of the bird is a subject of future research. Our analysis also has applications in a wide range problems, including the analysis of large-scale mobile robotic networks. We are currently exploring these applications and developing a broadly applicable theory of navigation through randomly-generated clutter.

[1] S. Karaman and E. Frazzoli, “High-speed Flight in an Ergodic Forest,” in IEEE Conference on Robotics and Automation, 2012.
[Bibtex]
@inproceedings{Karaman.Frazzoli:ICRA12,
  Author = {S. Karaman and E. Frazzoli},
  Booktitle = {{IEEE} Conference on Robotics and Automation},
  Date-Added = {2011-10-05 18:50:37 +0000},
  Date-Modified = {2012-12-27 21:13:32 +0000},
  Title = {High-speed Flight in an Ergodic Forest},
  Year = {2012}}