Path Planning for Optimal Mapping of Unknown, Urban Environments


Recent Micro Air Vehicle (MAV) research has focused on developing technologies for increasing mission capability. Difficulties arise due to payload constraints that limit the available sensor suite which is often assumed to include a single monocular camera, inertial measurement unit (IMU), and GPS receiver. It is desired, however, to provide mission capability in urban environments where GPS measurements are unreliable and often unavailable. Therefore, several vision-only technologies are currently being investigated including vision-based state estimation and vision-based scene reconstructions. The goal of this research is to extend and build upon such computer vision technologies to develop path planning strategies for vision-based optimal mapping of urban environments.

Several issues arise when mapping an unknown environment with a MAV. First, vehicle state estimates incur significant drift over time, therefore, environment measurements cannot simply be concatenated to produce a spatially coherent map. Additionally, static landmarks that are uniquely identifiable from multiple vantage points must be defined to generate a map from an onboard vision sensor. Lastly, online generation of dynamically feasible trajectories requires an efficient motion planning algorithm to compute control commands in real-time.

Scene Reconstruction

Environmental mapping is achieved by inferring three-dimensional information from two-dimensional images gathered by the onboard camera. Three-dimensional feature points, defined as points of interest in the environment, are calculated by a wellknown Structure from Motion (SFM) algorithm. Geometric primitives are fit to the cloud of three-dimensional feature points to create a reduced set of environmental landmarks (planes, prisms, etc.) that are visible and distinguishable from multiple vantage points.

Incorporating the geometric primitives into a single spatial map by concatenating sensor measurements would produce a map affected by drift incurred in the state estimation process. Therefore, Simultaneous Localization and Mapping (SLAM) is employed to correct for drift in state estimates by including static landmark state information into the vehicle state estimation process. The result is inertial vehicle state estimates significantly less affected by drift and a spatially coherent map of the environment.

Path Planning

Path planning is accomplished using the Rapidly-Exploring Random Tree (RRT) paradigm. Motion planning with RRTs involves random sampling of the vehicles' configuration space within the available workspace. For aircraft the random samples represent trim conditions which are connected by dynamically feasible trajectories to produce a tree structure. The sampling procedure is designed to explore the space with a sparse set of candidate trajectories from which a near optimal solution can be selected without relying on an exhaustive search for the optimal solution.

For mapping unknown environments a tree is expanded within the vehicle sensors' field of view from which a solution is extracted. The suboptimal trajectory is selected from the tree based on mapping criteria (coverage, information gain, etc.). As the vehicle navigates along the selected trajectory sensor information is gathered and used to define the next region within which a tree is expanded.