Flight of Robotic Aircraft Among Obstacles

Single frame from video showing simulation of navigation in an unknown forest combining the mapping algorithm with a potential field obstacle avoidance routine. [AVI] [MPEG]

A key problem in the field of mobile robotics is navigation through an unknown environment. A particularly challenging instance of this problem is flight of a small fixed-wing Unmanned Aerial Vehicle (UAV) through a forest. The UAV must fly from its starting position to a goal position (or series of goal positions) while avoiding collisions with trees.

One approach is to generate a model of the environment (a map) and then plan a safe, feasible trajectory based on the map. This has a few features: (a) a map is available to the next aircraft to fly through the forest; (b) points of interest which are discovered along the way can be localized; and (c) it is fairly easy to incorporate higher level goals into the system. My research is focussed on the problem of generating a map which is compatible with generic path planning algorithms.

Since the UAV is flying under the forest canopy we cannot rely on the availability of GPS signals, hence there is no direct measurement of aircraft position. To generate a map we must simultaneously obtain an estimate of the aircraft's position based solely on on-board sensors. This is an instance of a Simultaneous Localization and Mapping (SLAM) problem, which has been the subject of a great deal of research by the robotics community.

Small fixed-wing UAVs present several challenges that make this a very interesting problem. The first (and arguably most important) is the small size and limited payload capacity of the aircraft, which limits available sensing to a single camera and an inertial measurement unit (IMU). The second is effect of non-linearities in the observation model, which is exacerbated by the close proximity of the UAV to the obstacles being observed. The third is the uncertainty in the predicted state of the aircraft, which is caused by the likelihood of significant external disturbances (such as gusts) and the likelihood of significant drift and bias errors in the IMU. Other challenges include constraints on the trajectory (the aircraft must maintain forward speed to maintain flight) and highly non-linear system dynamics.

For a more detailed description of the problem and the approach used to address the issues please see our paper presented at the 2004 AIAA Guidance, Navigation and Control Conference (available here in PDF). For the latest results describing autonomous navigation of a small RC car through a forest-like environment see our paper presented at the 2005 AIAA GNC Conference (available here in PDF). A video showing the view from the car next to a reconstruction of the environment based on the current estimate can be found in this MPG (warning: 39Mb).

Once an algorithm for mapping and localization is in place the vehicle must still navigate safely through the forest. In some situations a variation of a potential field obstacle avoidance routine can be implemented. Here the aircraft's desired turn rate is calculated based on the distance between the aircraft and the 3-sigma error ellipsoid of nearby obstacles. Potential field obstacle avoidance routines have the advantages of simple implementation and fast calculation of desired vehicle inputs, but they are subject to local minima when obstacle spacing is small. A second approach is to generate safe, feasible trajectories using randomized approaches. Randomized motion planners are probabilistically complete (i.e. if a solution exists it will eventually be found) but there is no guarantee that the solution will be found in a reasonable amount of time. In practice heuristics to speed up the solution process are implemented, and these randomized approaches have been very successful for motion planning in many applications.

Potential Field Obstacle Avoidance

Single frame from video showing simulation of navigation in an unknown forest combining the mapping algorithm with a potential field obstacle avoidance routine. [AVI] [MPEG]

This video [AVI] [MPEG] shows a simulation of localization, mapping and navigation in a 2D environment using a potential field obstacle avoidance routine. The vehicle is equipped with an IMU and a monocular camera, allowing it to measure acceleration and obtain bearings to obstacles. The aircraft enters the initially unknown forest from the left. Trees are represented as green dots. Estimated locations of trees are represented by the red "+" centered in the associated 3-sigma error ellipsoid. The estimated aircraft position is shown by the blue "wings", the error in estimated aircraft position is shown by the blue 3-sigma error ellipsoid. True aircraft position is shown by the green "wings". As the aircraft flies through the forest trees are mapped with greater and greater accuracy, and the aircraft is able to maintain a good estimate of its own state. Notice that near the end of the trajectory the uncertainty in aircraft state begins to grow: this occurs because there are no trees in view of the camera as the aircraft exits the forest.

Randomized Trajectory Planning

Single frame from video showing simulation of navigation in an unknown forest combining the mapping algorithm with a randomized trajectory generator. [AVI] [MPEG]

In this video [AVI] [MPEG] a randomized motion planner is used to generate control inputs. Again trees are represented by green dots, estimated locations of trees are represented by the red "+" centered in the associated 3-sigma error ellipsoid. The estimated aircraft position is shown by the blue "wings", the error in estimated aircraft position is shown by the blue 3-sigma error ellipsoid. True aircraft position is shown by the green "wings". The dotted blue line shows the path the aircraft is following. A new path is generated when the map of the forest changes (the change is calculated based on the change in uncertainty of the tree locations).

Passive GPS-Free Navigation

This video shows a full 3D simulation of autonomous navigation using only an inertial measurement unit and a monocular camera. The aircraft is flying a circular trajectory of radius 200m at an altitude of 100m. The true aircraft position is shown in blue (note that the viewpoint follows the aircraft), the estimated aircraft position is shown in red. The "soap bubble" denotes the 3-sigma uncertainty associated with the position estimate. [70Mb MPEG]

Note that the bearings-only SLAM algorithm developed in this research can also be used for navigation of small UAVs when GPS signals are unavailable (either through jamming or because they are obscured by obstacles). In this situation error growth in the navigation solution is an important parameter which must be examined.

The video at right shows results of a full 3-D simulation of a small UAV flying a circular trajectory of radius 200m at an altitude of 100m. Note the excellent agreement between the estimated navigation solution and the true location of the aircraft. As described in previous sections, the position estimate is obtained by fusing data from a low-cost inertial measurement unit and a monocular camera. The estimator begins with no knowledge of the environment: including a priori knowledge greatly improves the navigation solution.

For a more detailed description of the problem and the approach used to address the issues please see our paper presented at the 2005 IEEE Aerospace Conference (available here in PDF).