In this paper, we propose a resource-efficient approach to provide an autonomous UAV with an on-board perception method to detect safe, hazard-free landing sites during flights over complex 3D terrain. We aggregate 3D measurements acquired from a sequence of monocular images by a Structure-from-Motion approach into a local, robot-centric, multi-resolution elevation map of the overflown terrain, which fuses depth measurements according to their lateral surface resolution (pixel-footprint) in a probabilistic framework based on the concept of dynamic Level of Detail. Map aggregation only requires depth maps and the associated poses, which are obtained from an on-board Visual Odometry algorithm. An efficient landing site detection method then exploits the features of the underlying multi-resolution map to detect safe landing sites based on slope, roughness, and quality of the reconstructed terrain surface. The evaluation of the performance of the mapping and landing site detection modules are analyzed independently and jointly in simulated and real-world experiments in order to establish the efficacy of the proposed approach.

Thermal cameras can enable autonomous flight at night without GPS. However, image-based navigation in the thermal infrared spectrum has been researched significantly less than in the visible spectrum. In this paper, we demonstrate closed-loop controlled outdoor flights at night on a quadrotor. Our state estimator can tightly couple inertial data with either thermal images at nighttime, or visual images at daytime. It is integrated in an autonomy framework for motion planning and control, which runs in real time on a standard embedded computer. We analyze thermal-inertial odometry performance extensively from sunset to sunrise, for various thermal non-uniformity levels, and compare it to visual-inertial odometry at daytime.

Robust autonomous flight without GPS is key to many emerging drone applications, such as delivery, search and rescue, and warehouse inspection. These and other applications require accurate trajectory tracking through cluttered static environments, where GPS can be unreliable, while high-speed, agile, flight can increase efficiency. We describe the hardware and software of a quadrotor system that meets these requirements with onboard processing: a custom 300 mm wide quadrotor that uses two wide-field-of-view cameras for visual-inertial motion tracking and relocalization to a prior map. Collision-free trajectories are planned offline and tracked online with a custom tracking controller. This controller includes compensation for drag and variability in propeller performance, enabling accurate trajectory tracking, even at high speeds where aerodynamic effects are significant. We describe a system identification approach that identifies quadrotor-specific parameters via maximum likelihood estimation from flight data. Results from flight experiments are presented, which 1) validate the system identification method, 2) show that our controller with aerodynamic compensation reduces tracking error by more than 50% in both horizontal flights at up to 8.5 m/s and vertical flights at up to 3.1 m/s compared to the state-of-the-art, and 3) demonstrate our system tracking complex, aggressive, trajectories.

Use of low-cost depth sensors, such as a stereo camera setup with illuminators, is of particular interest for numerous applications ranging from robotics and transportation to mixed and augmented reality. The ability to quantify noise is crucial for these applications, e.g., when the sensor is used for map generation or to develop a sensor scheduling policy in a multi-sensor setup. Range error models provide uncertainty estimates and help weigh the data correctly in instances where range measurements are taken from different vantage points or with different sensors. Such a model is derived in this work. We show that the range error for stereo systems with integrated illuminators is cubic and validate the proposed model experimentally with an off-the-shelf structured light stereo system. The experiments confirm the validity of the model and simplify the application of this type of sensor in robotics.

Recently, there have been numerous advances in the development of payload and power constrained lightweight Micro Aerial Vehicles (MAVs). As these robots aspire for highspeed autonomous flights in complex dynamic environments, robust scene understanding at long-range becomes critical. The problem is heavily characterized by either the limitations imposed by sensor capabilities for geometry-based methods, or the need for large-amounts of manually annotated training data required by data-driven methods. This motivates the need to build systems that have the capability to alleviate these problems by exploiting the complimentary strengths of both geometry and data-driven methods. In this paper, we take a step in this direction and propose a generic framework for adaptive scene segmentation using self-supervised online learning. We present this in the context of vision-based autonomous MAV flight, and demonstrate the efficacy of our proposed system through extensive experiments on benchmark datasets and realworld field tests.

3-D perception of scenes with specular surfaces is still challenging for robotics applications in urban areas, for both active and passive range sensors; there is a need for improved solutions that work without artificial illumination over a wide range of distances. The advent of cameras with microgrid polarization filter arrays, which allow acquiring four orientations of linearly polarized images simultaneously, has potential to make the use of polarization information in 3-D perception more practical. It is well-known that polarization can provide information about the orientation of specular surfaces; however, prior work with polarization for 3-D perception has had several limitations. We present the first unified formulation of depth perception with stereo and polarization by extending previous energy minimization formulations to include surface orientation constraints computed from the polarization channels. We apply an existing quadratic pseudo-boolean optimization (QPBO) method to approximate the optimal depth map. We use synthetic and real indoor/outdoor images to demonstrate that the new method achieves better results than prior methods, with fewer assumptions and limitations.

The literature in computer vision is rich of works where different types of activities -- single actions, two persons interactions or ego-centric activities, to name a few -- have been analyzed. However, traditional methods treat such types of activities separately, while in real settings detecting and recognizing different types of activities simultaneously is necessary. We first design a new unified descriptor, called Relation History Image (RHI), which can be extracted from all the activity types we are interested in. We then formulate an optimization procedure to detect and recognize activities of different types. We assess our approach on a new dataset recorded from a robot-centric perspective as well as on publicly available datasets, and evaluate its quality compared to multiple baselines.

We present a task-oriented grasp model, that encodes grasps that are configurationally compatible with a given task. For instance, if the task is to pour liquid from a container, the model encodes grasps that leave the opening of the container unobstructed. The model consists of two independent agents: First, a geometric grasp model that computes, from a depth image, a distribution of 6D grasp poses for which the shape of the gripper matches the shape of the underlying surface. The model relies on a dictionary of geometric object parts annotated with workable gripper poses and preshape parameters. It is learned from experience via kinesthetic teaching. The second agent is a CNN-based semantic model that identifies grasp-suitable regions in a depth image: regions where a grasp will not impede the execution of the task. The semantic model allows us to encode relationships such as “grasp from the handle.” A key element of this work is to use a deep network to integrate contextual task cues, and defer the structured-output problem of gripper pose computation to an explicit (learned) geometric model. Jointly, these two models generate grasps that are mechanically fit, and that grip on the object in a way that enables the intended task.

Sensing the 3D environment of a moving robot is essential for collision avoidance. Most 3D sensors produce dense depth maps, which are subject to imperfections due to various environmental factors. Temporal fusion of depth maps is crucial to overcome those. Temporal fusion is traditionally done in 3D space with voxel data structures, but it can be approached by temporal fusion in image space, with potential benefits in reduced memory and computational cost for applications like reactive collision avoidance for micro air vehicles. In this paper, we present an efficient Gaussian Mixture Models based depth map fusion approach, introducing an online update scheme for dense representations. The environment is modeled from an ego-centric point of view, where each pixel is represented by a mixture of Gaussian inverse-depth models. Consecutive frames are related to each other by transformations obtained from visual odometry. This approach achieves better accuracy than alternative image space depth map fusion techniques at lower computational cost.

Fusing data from multiple sensors on-board a mobile platform can significantly augment its state estimation abilities and enable autonomous traversals of different domains by adapting to changing signal availabilities. However, due to the need for accurate calibration and initialization of the sensor ensemble as well as coping with erroneous measurements that are acquired at different rates with various delays, multi-sensor fusion still remains a challenge. In this paper, we introduce a novel multi-sensor fusion approach for agile aerial vehicles that allows for measurement validation and seamless switching between sensors based on statistical signal quality analysis. Moreover, it is capable of self-initialization of its extrinsic sensor states. These initialized states are maintained in the framework such that the system can continuously self-calibrate. We implement this framework on-board a small aerial vehicle and demonstrate the effectiveness of the above capabilities on real data. As an example, we fuse GPS data, ultra-wideband (UWB) range measurements, visual pose estimates, and IMU data. Our experiments demonstrate that our system is able to seamlessly filter and switch between different sensors modalities during run time.

In this paper, we present a new feature representation for first-person videos. In first-person video understanding (e.g., activity recognition), it is very important to capture both entire scene dynamics (i.e., egomotion) and salient local motion observed in videos. We describe a representation framework based on time series pooling, which is designed to ab] short-term/long-term changes in feature descriptor elements. The idea is to keep track of how descriptor values are changing over time and summarize them to represent motion in the activity video. The framework is general, handling any types of per-frame feature descriptors including conventional motion descriptors like histogram of optical flows (HOF) as well as appearance descriptors from more recent convolutional neural networks (CNN). We experimentally confirm that our approach clearly outperforms previous feature representations including bag-of-visual-words and improved Fisher vector (IFV) when using identical underlying feature descriptors. We also confirm that our feature representation has superior performance to existing state-of-the-art features like local spatio-temporal features and Improved Trajectory Features (originally developed for 3rd-person videos) when handling first-person videos. Multiple first-person activity datasets were tested under various settings to confirm these findings.

In this paper, we present a core technology to enable robot recognition of human activities during human-robot interactions. In particular, we propose a methodology for early recognition of activities from robot-centric videos (i.e., first-person videos) obtained from a robot's viewpoint during its interaction with humans. Early recognition, which is also known as activity prediction, is an ability to infer an ongoing activity at its early stage. We present an algorithm to recognize human activities targeting the camera from streaming videos, enabling the robot to predict intended activities of the interacting person as early as possible and take fast reactions to such activities (e.g., avoiding harmful events targeting itself before they actually occur). We introduce the novel concept of 'onset' that efficiently summarizes pre-activity observations, and design a recognition approach to consider event history in addition to visual features from first-person videos. We propose to represent an onset using a cascade histogram of time series gradients, and we describe a novel algorithmic setup to take advantage of such onset for early recognition of activities. The experimental results clearly illustrate that the proposed concept of onset enables better/earlier recognition of human activities from first-person videos collected with a robot.

In this paper, we present a novel approach in combining visual and inertial measurements in non-static environments for first order characterization of the metric motion of non-static objects in the scene. Our approach leverages online estimated ego motion states and uses a novel inertial-optical flow (IOF) measurement analysis to identify moving objects and to characterize them in their angular and linear velocities. The novelty of our algorithm lies in the identification and segmentation of consistent optical flow outliers in the so-called kinematic space. These consistent outliers in combination with the IOF information for ego-motion estimation yield a first order estimation of the moving object in full 3D and in metric units. The approach is highly efficient as it only requires matched features in two consecutive images. We evaluate and demonstrate our algorithm in simulations and in real world tests.

Sub pixel interpolation of stereo disparity is essential to achieve adequate range resolution for many applications, especially in autonomous navigation. Sub pixel interpolation is plagued by systematic biases caused by pixel-locking, foreshortening, and scaling phenomena. Prior work on this problem has produced partial solutions or solutions that are undesirably slow for real-time applications. We describe a new algorithm ? Stereovision Bias Removal by Autocorrelation (SBRA) ? to correct these biases. SBRA addresses all three of these causes of bias, achieving 0.02 pixel RMS disparity error in synthetic stereo image data and a significant error reduction on real stereo images for which no ground truth is available. SBRA is simple and fast, increasing the runtime of a sum square difference (SSD) stereo matching algorithm by about 10%.

In this paper, we describe a novel method using only optical flow from a single camera and inertial information to quickly initialize, deploy, and autonomously stabilize an inherently unstable aerial vehicle. Our approach requires a minimal number of tracked features in only two consecutive frames and inertial readings eliminating the need of long feature tracks or local maps and rendering it inherently failsafe. We show theoretically, in simulation, and in real experiments that we can reliably estimate and control the vehicle velocity, full attitude, and metric distance to the scene while self-calibrating inertial intrinsics and sensor extrinsics. In fact, the fast initialization, self-calibration, and inherent fail-safe property leads to the first visual-inertial throw-and-go capable system.

We address obstacle avoidance for outdoor flight of micro air vehicles. The highly textured nature of outdoor scenes enables camera-based perception, which will scale to very small size, weight, and power with very wide, two-axis field of regard. In this paper, we use forward-looking stereo cameras for obstacle detection and a downward-looking camera as an input to state estimation. For obstacle representation, we use image space with the stereo disparity map itself. We show that a C-space-like obstacle expansion can be done with this representation and that collision checking can be done by projecting candidate 3-D trajectories into image space and performing a z-buffer-like operation with the disparity map. This approach is very efficient in memory and computing time. We do motion planning and trajectory generation with an adaptation of a closed-loop RRT planner to quadrotor dynamics and full 3D search. We validate the performance of the system with Monte Carlo simulations in virtual worlds and flight tests of a real quadrotor through a grove of trees. The approach is designed to support scalability to high speed flight and has numerous possible generalizations to use other polar or hybrid polar/Cartesian representations and to fuse data from additional sensors, such as peripheral optical flow or radar.

This paper discusses the problem of recognizing interaction-level human activities from a first-person viewpoint. The goal is to enable an observer (e.g., a robot or a wearable camera) to understand 'what activity others are performing to it' from continuous video inputs. These include friendly interactions such as 'a person hugging the observer' as well as hostile interactions like 'punching the observer' or 'throwing objects to the observer', whose videos involve a large amount of camera ego-motion caused by physical interactions. The paper investigates multi-channel kernels to integrate global and local motion information, and presents a new activity learning/recognition methodology that explicitly considers temporal structures displayed in first-person activity videos. In our experiments, we not only show classification results with segmented videos, but also confirm that our new approach is able to detect activities from continuous videos reliably.

This paper describes the stereo vision near-field terrain mapping system used by the Legged Squad Support System (LS3) quadruped vehicle to automatically adjust its gait in complex natural terrain. The mapping system achieves high robustness with a combination of stereo model-based outlier rejection and spatial and temporal filtering, enabled by a unique hybrid 2D/3D data structure. Classification of sparse structures allows the vehicle to traverse through vegetation. Inference of negative obstacles allows the vehicle to avoid steep drop-offs. A custom designed near-infrared illumination system enables operation at night. The mapping system has been tested extensively with controlled experiments and 72km of field testing in a wide variety of terrains and conditions.

In this paper, we describe a novel approach in fusing optical flow with inertial cues (3D acceleration and 3D angular velocities) in order to navigate a Micro Aerial Vehicle (MAV) drift free in 4DoF and metric velocity. Our approach only requires two consecutive images with a minimum of three feature matches. It does not require any (point) map nor any type of feature history. Thus it is an inherently failsafe approach that is immune to map and feature-track failures. With these minimal requirements we show in real experiments that the system is able to navigate drift free in all angles including yaw, in one metric position axis, and in 3D metric velocity. Furthermore, it is a power-on-and-go system able to online self-calibrate the inertial biases, the visual scale and the full 6DoF extrinsic transformation parameters between camera and IMU.

This paper presents a model based approach to autonomous dexterous manipulation, developed as part of the DARPA Autonomous Robotic Manipulation (ARM) program. The developed autonomy system uses robot, object, and environment models to identify and localize objects, and well as plan and execute required manipulation tasks. Deliberate interaction with objects and the environment increases system knowledge about the combined robot and environmental state, enabling high precision tasks such as key insertion to be performed in a consistent framework. This approach has been demonstrated across a wide range of manipulation tasks, and in independent DARPA testing archived the most successfully completed tasks with the fastest average task execution of any evaluated team.

We present a real-time system that enables a highly capable dynamic quadruped robot to maintain an accurate 6-DOF pose estimate (better than 0.5m over every 50m traveled) over long distances traversed through complex, dynamic outdoor terrain, during day and night, in the presence of camera occlusion and saturation, and occasional large external disturbances, such as slips or falls. The system fuses a stereo-camera sensor, inertial measurement units (IMU), and leg odometry with an Extended Kalman Filter (EKF) to ensure robust, low-latency performance. Extensive experimental results obtained from multiple field tests are presented to illustrate the performance and robustness of the system over hours of continuous runs over hundreds of meters of distance traveled in a wide variety of terrains and conditions.

Stereo vision is useful for a variety of robotics tasks, such as navigation and obstacle avoidance. However, recovery of valid range data from stereo depends on accurate calibration of the extrinsic parameters of the stereo rig, i.e., the 6-DOF transform between the left and right cameras. Stereo self calibration is possible, but, without additional information, the absolute scale of the stereo baseline cannot be determined. In this paper, we formulate stereo extrinsic parameter calibration as a batch maximum likelihood estimation problem, and use GPS measurements to establish the scale of both the scene and the stereo baseline. Our approach is similar to photogrammetric bundle adjustment, and closely related to many structure from motion algorithms. We present results from simulation experiments using a range of GPS accuracy levels; these accuracies are achievable by varying grades of commercially-available receivers. We then validate the algorithm using stereo and GPS data acquired from a moving vehicle. Our results indicate that the approach is promising.

Robust water detection is a critical perception requirement for unmanned ground vehicle (UGV) autonomous navigation. This is particularly true in wide-open areas where water can collect in naturally occurring terrain depressions during periods of heavy precipitation and form large water bodies. One of the properties of water useful for detecting it is that its surface acts as a horizontal mirror at large incidence angles. Water bodies can be indirectly detected by detecting reflections of the sky below the horizon in color imagery. The Jet Propulsion Laboratory (JPL) has implemented a water detector based on sky reflections that geometrically locates the pixel in the sky that is reflecting on a candidate water pixel on the ground and predicts if the ground pixel is water based on color similarity and local terrain features. This software detects water bodies in wide-open areas on cross-country terrain at mid- to far-range using imagery acquired from a forward-looking stereo pair of color cameras mounted on a terrestrial UGV. In three test sequences approaching a pond under a clear, overcast, and cloudy sky, the true positive detection rate was 100% when the UGV was beyond 7 meters of the water's leading edge and the largest false positive detection rate was 0.58%. The sky reflection based water detector has been integrated on an experimental unmanned vehicle and field tested at Ft. Indiantown Gap, PA, USA.

A Feature and Pose Constrained Extended Kalman Filter (FPC-EKF) is developed for highly dynamic computationally constrained micro aerial vehicles. Vehicle localization is achieved using only a low performance inertial measurement unit and a single camera. The FPC-EKF framework augments the vehicle's state with both previous vehicle poses and critical environmental features, including vertical edges. This filter framework efficiently incorporates measurements from hundreds of opportunistic visual features to constrain the motion estimate, while allowing navigating and sustained tracking with respect to a few persistent features. In addition, vertical features in the environment are opportunistically used to provide global attitude references. Accurate pose estimation is demonstrated on a sequence including fast traversing, where visual features enter and exit the fleld-of-view quickly, as well as hover and ingress maneuvers where drift free navigation is achieved with respect to the environment.

Robust water detection is a critical perception requirement for unmanned ground vehicle (UGV) autonomous navigation. This is particularly true in wide open areas where water can collect in naturally occurring terrain depressions during periods of heavy precipitation and form large water bodies (such as ponds). At far range, reflections of the sky provide a strong cue for water. But at close range, the color coming out of a water body dominates sky reflections and the water cue from sky reflections is of marginal use. We model this behavior by using water body intensity data from multiple frames of RGB imagery to estimate the total reflection coefficient contribution from surface reflections and the combination of all other factors. We then describe an algorithm that uses one of the color cameras in a forward-looking, UGV-mounted stereo-vision perception system to detect water bodies in wide open areas. This detector exploits the knowledge that the change in saturation-to-brightness ratio across a water body from the leading to trailing edge is uniform and distinct from other terrain types. In test sequences approaching a pond under clear, overcast, and cloudy sky conditions, the true positive and false negative water detection rates were (95.76%, 96.71%, 98.77%) and (0.45%, 0.60%, 0.62%), respectively. This software has been integrated on an experimental unmanned vehicle and field tested at Ft. Indiantown Gap, PA, USA.

We study the problem of localizing a balloon in the atmosphere of Saturn's moon Titan by registering onboard imagery with orbital imagery. This is critical for both autonomous navigation purposes and acquisition and sampling of scientifically interesting sites. Because of Titan's atmospheric opacity, we require the ability to match combinations of visible, infrared (IR) and synthetic aperture radar (SAR) images. For both localization and direct use as a multi-modal data product for science analysis, match results must be sub-pixel accurate. We demonstrate the feasibility of matching orbital SAR data to visible and IR imagery and outline a framework for using this data as a navigation product. We demonstrate a technique to compensate for local distortions to enable accurate data registration in spite of differences in sensor return and imaging geometry. Finally, we show match results using both terrestrial imagery and the limited amount of available Titan data acquired by the Cassini orbiter and Huygens probe.

In this paper, we present the vision-aided inertial navigation (VISINAV) algorithm that enables precision planetary landing. The vision front-end of the VISINAV system extracts 2-D-to-3-D correspondences between descent images and a surface map (mapped landmarks), as well as 2-D-to-2-D feature tracks through a sequence of descent images (opportunistic features). An extended Kalman filter (EKF) tightly integrates both types of visual feature observations with measurements from an inertial measurement unit. The filter computes accurate estimates of the lander's terrain-relative position, attitude, and velocity, in a resource-adaptive and hence real-time capable fashion. In addition to the technical analysis of the algorithm, the paper presents validation results from a sounding-rocket test flight, showing estimation errors of only 0.16 m/s for velocity and 6.4 m for position at touchdown. These results vastly improve current state of the art for terminal descent navigation without visual updates, and meet the requirements of future planetary exploration missions.

This paper describes a method for learning the terrain classification of long-range appearance data from short- range, stereo-based geometry, along with a map representation for utilizing this data to improve autonomous off-road navigation. The continuous, online learning method allows the system to constantly adapt to changing terrain and environmental conditions, while the polar-perspective map representation allows the system to effectively plan with stereo data at long ranges. Various evaluations of the long-range classification and improvements in system performance are described, including results from an independent third-party testing team.

Visual odometry can augment or replace wheel odometry when navigating in high slip terrain which is quite important for autonomous navigation on Mars. We present a computationally efficient and robust visual odometry algorithm developed for the Mars Science Laboratory mission. This algorithm is a significant improvement over the algorithm developed for the Mars Exploration Rover Mission because it is at least four time more computationally efficient and it tracks significantly more features. The core of the algorithm is an integrated motion estimation and stereo feature tracking loop that allows for feature recovery while guiding feature correlation search to minimize computation. Results on thousands of terrestrial and Martian stereo pairs show that the algorithm can operate with no initial motion estimate while still obtaining subpixel attitude estimation performance.

We introduce a new method for stereo visual SLAM (simultaneous localization and mapping) that works in unstructured, outdoor environments. Unlike other grid-based SLAM algorithms, which use occupancy grid maps, our algorithm uses a new mapping technique that maintains a posterior distribution over the height variance in each cell. This idea was motivated by our experience with outdoor navigation tasks, which has shown height variance to be a useful measure of traversability. To obtain a joint posterior over poses and maps, we use a Rao-Blackwellized particle filter: the pose distribution is estimated using a particle filter, and each particle has its own map that is obtained through exact filtering conditioned on the particle's pose. Visual odometry provides good proposal distributions for the particle pose. In the analytical (exact) filter for the map, we update the sufficient statistics of a gamma distribution over the precision (inverse variance) of heights in each grid cell. We verify the algorithm's accuracy on two outdoor courses by comparing with ground truth data obtained using electronic surveying equipment. In addition, we solve for the optimal transformation from the SLAM map to georeferenced coordinates, based on a noisy GPS signal. We derive an online version of this alignment process, which can be used to maintain a running estimate of the robot's global position that is much more accurate than the GPS readings.

Unmanned planetary landers to date have landed blind, without the benefit of onboard landing hazard detection and avoidance systems. This constrains landing sites to very benign terrain and limits the scientific goals of missions. We review sensor options for landing hazard detection, then identify an approach based on stereo vision and shadow analysis that appears to address the broadest set of missions with the lowest cost. We describe algorithms for slope estimation and rock detection with this approach, develop models of their performance, and validate those models experimentally. Instantiating our model of rock detection reliability for Mars predicts that this approach would reduce the probability of failed landing by at least a factor of 4 compared to blind landing. Conversely, for the safety level desired for the 2009 Mars lander, this approach would increase the fraction of the planet that is accessible for landing from about 1/3 to nearly 100%.

We propose a method for learning using a set of feature representations which retrieve different amounts of information at different costs. The goal is to create a more efficient terrain classification algorithm which can be used in real-time, onboard an autonomous vehicle. Instead of building a monolithic classifier with uniformly complex representation for each class, the main idea here is to actively consider the labels or misclassification cost while constructing the classifier. For example, some terrain classes might be easily separable from the rest, so very simple representation will be sufficient to learn and detect these classes. This is taken advantage of during learning, so the algorithm automatically builds a variable-length visual representation which varies according to the complexity of the classification task. This enables fast recognition of different terrain types during testing. We also show how to select a set of feature representations so that the desired terrain classification task is accomplished with high accuracy and is at the same time efficient. The proposed approach achieves a good trade-off between recognition performance and speedup on data collected by an autonomous robot.

We address the problem of learning terrain traversability properties from visual input, using automatic mechanical supervision collected from sensors onboard an autonomous vehicle. We present a novel probabilistic framework in which the visual information and the mechanical supervision interact to learn particular terrain types and their properties. The proposed method is applied to learning of rover slippage from visual information in a completely automatic fashion. Our experiments show that using mechanical measurements as automatic supervision significantly improves the visual-based classification alone and approaches the results of learning with manual supervision. This work will enable the rover to drive safely on slopes, learning autonomously about different terrains and their slip characteristics.

In this paper we predict the amount of slip an exploration rover would experience using stereo imagery by learning from previous examples of traversing similar terrain. To do that, the information of terrain appearance and geometry regarding some location is correlated to the slip measured by the rover while this location is being traversed. This relationship is learned from previous experience, so slip can be predicted later at a distance from visual information only. The advantages of the approach are: 1) learning from examples allows the system to adapt to unknown terrains rather than using fixed heuristics or predefined rules; 2) the feedback about the observed slip is received from the vehicle's own sensors which can fully automate the process; 3) learning slip from previous experience can replace complex mechanical modeling of vehicle or terrain, which is time consuming and not necessarily feasible. Predicting slip is motivated by the need to assess the risk of getting trapped before entering a particular terrain. For example, a planning algorithm can utilize slip information by taking into consideration that a slippery terrain is costly or hazardous to traverse. A generic nonlinear regression framework is proposed in which the terrain type is determined from appearance and then a nonlinear model of slip is learned for a particular terrain type. In this paper we focus only on the latter problem and provide slip learning and prediction results for terrain types, such as soil, sand, gravel, and asphalt. The slip prediction error achieved is about 15% which is comparable to the measurement errors for slip itself

For real-time stereo vision systems, the standard method for estimating sub-pixel stereo disparity given an initial integer disparity map involves fitting parabolas to a matching cost function aggregated over rectangular windows. This results in a phenomenon known as pixel-locking, which produces artificially-peaked histograms of sub-pixel disparity. These peaks correspond to the introduction of erroneous ripples or waves in the 3D reconstruction of truly flat surfaces. Since stereo vision is a common input modality for autonomous vehicles, these inaccuracies can pose a problem for safe, reliable navigation. This paper proposes a new method for sub-pixel stereo disparity estimation, based on ideas from Lucas-Kanade tracking and optical flow, which substantially reduces the pixel-locking effect. In addition, it has the ability to correct much larger initial disparity errors than previous approaches and is more general as it applies not only to the ground plane. We demonstrate the method on synthetic imagery as well as real stereo data from an autonomous outdoor vehicle

During the Mars Exploration Rover (MER) landings, the descent image motion estimation system (DIMES) was used for horizontal velocity estimation. The DIMES algorithm combined measurements from a descent camera, a radar altimeter, and an inertial measurement unit. To deal with large changes in scale and orientation between descent images, the algorithm used altitude and attitude measurements to rectify images to a level ground plane. Feature selection and tracking were employed in the rectified images to compute the horizontal motion between images. Differences of consecutive motion estimates were then compared to inertial measurements to verify correct feature tracking. DIMES combined sensor data from multiple sources in a novel way to create a low-cost, robust, and computationally efficient velocity estimation solution, and DIMES was the first use of computer vision to control a spacecraft during planetary landing. This paper presents the detailed implementation of the DIMES algorithm and the results from the two landings on Mars.

Future robotic space missions will employ a precision soft-landing capability that will enable exploration of previously inaccessible sites that have strong scientific significance. To enable this capability, a fully autonomous onboard system that identifies and avoids hazardous features such as steep slopes and large rocks is required. Such a system will also provide greater functionality in unstructured terrain to unmanned aerial vehicles. This paper describes an algorithm for landing hazard avoidance based on images from a single moving camera. The core of the algorithm is an efficient application of structure from motion to generate a dense elevation map of the landing area. Hazards are then detected in this map and a safe landing site is selected. The algorithm has been implemented on an autonomous helicopter testbed and demonstrated four times resulting in the first autonomous landing of an unmanned helicopter in unknown and hazardous terrain.

A system that enables continuous slip compensation for a Mars rover has been designed, implemented, and field-tested. This system is composed of several components that allow the rover to accurately and continuously follow a designated path, compensate for slippage, and reach intended goals in high-slip environments. These components include: visual odometry, vehicle kinematics, a Kalman filter pose estimator, and a slip compensation/path follower. Visual odometry tracks distinctive scene features in stereo imagery to estimate rover motion between successively acquired stereo image pairs. The vehicle kinematics for a rocker-bogie suspension system estimates motion by measuring wheel rates, and rocker, bogie, and steering angles. The Kalman filter merges data from an inertial measurement unit (IMU) and visual odometry. This merged estimate is then compared to the kinematic estimate to determine how much slippage has occurred, taking into account estimate uncertainties. If slippage has occurred then a slip vector is calculated by differencing the current Kalman filter estimate from the kinematic estimate. This slip vector is then used to determine the necessary wheel velocities and steering angles to compensate for slip and follow the desired path.

NASA's Mars Exploration Rovers (MER) was designed to traverse in Viking Lander-I style terrains: mostly flat, with many small non-obstacle rocks and occasional obstacles. During actual operations in such terrains, onboard position estimates derived solely from the onboard inertial measurement unit and wheel encoder-based odometry achieved well within the design goal of at most 10% error. However, MER vehicles were also driven along slippery slopes tilted as high as 31 degrees. In such conditions an additional capability was employed to maintain a sufficiently accurate onboard position estimate: visual odometry. The MER visual odometry system comprises onboard software for comparing stereo pairs taken by the pointable mast-mounted 45 degree FOV navigation cameras (NAV-CAMs). The system computes an update to the 6-DOF rover pose (x, y, z, roll, pitch, yaw) by tracking the motion of autonomously-selected "interesting" terrain features between two pairs of stereo images, in both 2D pixel and 3D world coordinates. A maximum likelihood estimator is applied to the computed 3D offsets to produce a final, corrected estimate of vehicle motion between the two pairs. In this paper we describe the visual odometry algorithm used on the Mars Exploration Rovers, and summarize its results from the first year of operations on Mars.

Dynamic scene perception is very important for autonomous vehicles operating around other moving vehicles and humans. Most work on real-time camera based object tracking from moving platforms has used sparse features or assumed flat scene structures. We have recently extended a real-time, dense stereo system to include real-time, dense optical flow, enabling more comprehensive dynamic scene analysis. We describe algorithms to robustly estimate 6-DOF robot egomotion in the presence of moving objects using dense flow and dense stereo. We then use dense stereo and egomotion estimates to identify other moving objects while the robot itself is moving. We present results showing accurate egomotion estimation and detection of moving people and vehicles under general 6-DOF motion of the robot and independently moving objects. The system runs at 18.3 Hz on a 1.4 GHz Pentium M laptop, computing 160/spl times/120 disparity maps and optical flow fields, egomotion, and moving object segmentation. We believe this is a significant step toward general unconstrained dynamic scene analysis for mobile robots, as well as for improved position estimation where GPS is unavailable.

An outdoor environment presents to a robot objects that are drivable, such as tall grass and small bushes, and non-drivable, such as trees and rocks. Due to the difficulty of discriminating between these classes, traditionally a robot searches for paths free of any objects, drivable or not. Although this approach prevents collisions with objects misclassified as drivable, it also eliminates a large number of drivable paths and by doing so, it may eliminate the only path to a desired destination. We present a real time algorithm that detects foliage, using a range from a rotating ladar. Objects not classified as foliage are conservatively labeled as nondrivable obstacles. In contrast to related work that uses range statistics to classify the objects, we exploit the expected localities and continuities of an obstacle, in both space and time. Also, instead of attempting to find a single accurate discriminating factor for every ladar return, we hypothesize the class of some few returns and then spread the confidence (and classification) to other returns using the locality constraints. The Urbie robot is presently using this algorithm to discriminate drivable grass from obstacles during outdoor autonomous navigation tasks.

Detecting negative obstacles (ditches, potholes, and other depressions) is one of the most difficult problems in perception for autonomous, off-road navigation. Past work has largely relied on range imagery, because that is based on the geometry of the obstacle, is largely insensitive to illumination variables, and because there have not been other reliable alternatives. However, the visible aspect of negative obstacles shrinks rapidly with range, making them impossible to detect in time to avoid them at high speed. To relieve this problem, we show that the interiors of negative obstacles generally remain warmer than the surrounding terrain throughout the night, making thermal signature a stable property for night-time negative obstacle detection. Experimental results to date have achieved detection distances 45% greater by using thermal signature than by using range data alone. Thermal signature is the first known observable with potential to reveal a deep negative obstacle without actually seeing far into it. Modeling solar illumination has potential to extend the usefulness of thermal signature through daylight hours.

Dynamic scene perception is currently limited to detection of moving objects from a static platform or scenes with flat backgrounds. We discuss novel real-time methods to segment moving objects in the motion field formed by a moving camera/robotic platform with mostly translational motion. Our solution does not explicitly require any egomotion knowledge, thereby making the solution applicable to mobile outdoor robot problems where no IMU information is available. We address two problems in dynamic scene perception on the move, first using only 2D monocular grayscale images, and second where 3D range information from stereo is also available. Our solution involves real-time optical flow computations, followed by optical flow field preprocessing to highlight moving object boundaries. In the case where range data from stereo is computed, a 3D optical flow field is estimated by combining range information with 2D optical flow estimates, followed by a similar 3D flow field preprocessing step. A segmentation of the flow field using fast flood filling then identifies every moving object in the scene with a unique label. This novel algorithm is expected to be the critical first step in robust recognition of moving vehicles and people from mobile outdoor robots, and therefore offers a robust solution to the problem of dynamic scene perception in the presence of certain kinds of robot motion. It is envisioned that our algorithm will benefit robot scene perception in urban environments for scientific, commercial and defense applications. Results of our real-time algorithm on a mobile robot in a scene with a single moving vehicle are presented.

Tracked mobile robots in the 20 kg size class are under development for applications in urban reconnaissance. For efficient deployment, it is desirable for teams of robots to be able to automatically execute path following behaviors, with one or more followers tracking the path taken by a leader. The key challenges to enabling such a capability are (1) to develop sensor packages for such small robots that can accurately determine the path of the leader and (2) to develop path following algorithms for the subsequent robots. To date, we have integrated gyros, accelerometers, compass/inclinometers, odometry, and differential GPS into an effective sensing package. The paper describes the sensor package, sensor processing algorithm and path tracking algorithm we have developed for the leader/follower problem in small robots and shows the results of performance characterization of the system. We also document pragmatic lessons learned about design, construction, and electromagnetic interference issues particular to the performance of state sensors on small robots.

Small, tracked mobile robots designed for general urban mobility have been developed for the purpose of reconnaissance and/or search and rescue missions in buildings and cities. Autonomous stair climbing is a significant capability required for many of these missions. In this paper we present the design and implementation of a new set of estimation and control algorithms that increase the speed and effectiveness of stair climbing. We have developed: (1) a Kalman filter that fuses visual/laser data with inertial measurements and provides attitude estimates of improved accuracy at a high rate; and (2) a physics based controller that minimizes the heading error and maximizes the effective velocity of the vehicle during stair climbing. Experimental results using a tracked vehicle validate the improved performance of this control and estimation scheme over previous approaches.

We discuss techniques to predict the dynamic vehicle response to various natural obstacles. This method can then be used to adjust the vehicle dynamics to optimize performance (e.g. speed) while ensuring that the vehicle is not damaged. This capability opens up a new area of obstacle negotiation for UGVs, where the vehicle moves over certain obstacles, rather than avoiding them, thereby resulting in more effective achievement of objectives. Robust obstacle negotiation and vehicle dynamics prediction requires several key technologies that are discussed in this paper. We detect and segment (label) obstacles using a novel 3D obstacle algorithm. The material of each labelled obstacle (rock, vegetation, etc) is then determined using a texture or color classification scheme. Terrain load-bearing surface models are then constructed using vertical springs to model the compressibility and traversability of each obstacle in front of the vehicle. The terrain model is then combined with the vehicle suspension model to yield an estimate of the maximum safe velocity, and predict the vehicle dynamics as the vehicle follows a path. This end-to-end obstacle negotiation system is envisioned to be useful in optimized path planning and vehicle navigation in terrain conditions cluttered with vegetation, bushes, rocks, etc. Results on natural terrain with various natural materials are presented.

In the exploration of the other planets of our solar system, images taken during a lander's descent to the surface of a planet provide a critical link between orbital images and surface images. The descent images not only allow us to locate the landing site in a global coordinate frame, but also provide progressively higher-resolution maps for mission planning. The paper addresses the generation of depth maps from the descent images. Our approach has two steps: motion refinement and depth recovery. During motion refinement, we use an initial motion estimate in order to avoid the intrinsic ambiguity in descending motions. The objective of the motion refinement step is to adjust the motion parameters such that the epipolar constraints are valid between adjacent frames. The depth recovery step correlates adjacent frames to match pixels for triangulation. Due to the descending motion, the conventional rectification process is replaced by a set of anti-aliasing image warpings corresponding to a set of virtual parallel planes. We demonstrate experimental results on synthetic and real descent images.

Robust navigation for mobile robots over long distances requires an accurate method for tracking the robot position in the environment. Techniques for position estimation by determining the camera ego-motion from monocular or stereo sequences have been previously described. However, long-distance navigation requires a very high level of robustness and a very low rate of error growth. In this paper, we describe a methodology for long-distance rover navigation that meets these goals using robust estimation. We show that a system based on only camera ego-motion estimates will accumulate errors with super-linear growth in the distance travelled, owing to increasing orientation errors. When an absolute orientation sensor is incorporated, the error growth can be reduced to a linear function of the distance travelled. We tested these techniques using both extensive simulation and hundreds of real rover images and achieved a low, linear rate of error growth.

Several methods for computing observer motion from monocular and stereo image sequences have been proposed. However, accurate positioning over long distances requires a higher level of robustness than previously achieved. This paper describes several mechanisms for improving robustness in the context of a maximum-likelihood stereo ego-motion method. We demonstrate that even a robust system will accumulate super-linear error in the distance traveled due to increasing orientation errors. However, when an absolute orientation sensor is incorporated, the growth is reduced to linear in the distance traveled, grows much more slowly in practice. Our experiments, including a trial with 210 stereo pairs, indicate that these techniques can achieve errors below 1% of the distance traveled. This method has been implemented to run on-board a prototype Mars rover.

One goal of the "Demo III" unmanned ground vehicle program is to enable autonomous nighttime navigation at speeds of up to 10 m.p.h. To perform obstacle detection at night with stereo vision will require night vision cameras that produce adequate image quality for the driving speeds, vehicle dynamics, obstacle sizes, and scene conditions that will be encountered. This paper analyzes the suitability of four classes of night vision cameras (3-5 /spl mu/m cooled FLIR, 8-12 /spl mu/m cooled FLIR, 8-12 /spl mu/m uncooled FLIR, and image intensifiers) for night stereo vision, using criteria based on stereo night matching quality, image signal to noise ratio, motion blur, and synchronization capability. We find that only cooled FLIRs will enable stereo vision performance that meets the goals of the Demo III program for nighttime autonomous mobility.

The Tactical Mobile Robot (TMR) program calls for autonomous mobility in an urban environment. Among all man-made structures which pose as barriers for a mobile robot stairs are the most obvious and ubiquitous structure an autonomous urban robot needs to be able to handle. The Urban II chassis by IS Robotics provides a mechanically simple and elegant way to enable the stair-climbing capability. This paper addresses the issue of using computer vision techniques to control the vehicle automatically when climbing stairs. The algorithm is based in detecting stair edges from a monocular sequence. It is shown that the position and orientation of the stair edges can be used to compute the 3D orientation and position of the vehicle relative to the stairs. Robust examination of those parameters is the key to reliable performance. A combination of techniques such as medium filtering, histogram peak finding, outlier rejection and weighted average are shown to be effective in practice. At the end, we briefly explain our work-in-progress in automatic corner-turning in climbing multiple flights of stairs.

Much prior work in mobile robot path planning has been based on assumptions that are unrealistic for exploration of planetary terrains. Based on the first author's experience with the Mars Pathfinder mission, this paper reviews issues that are critical for successful autonomous navigation of planetary rovers. No currently proposed methodology accurately addresses all of these issues. We report on an extension of the recently proposed "TangentBug" algorithm. The implementation of this extended algorithm on the Rocky 7 Mars Rover prototype at the Jet Propulsion Laboratory is described and experimental results are presented. In addition, limitations encountered by the Sojourner rover in actual Martian terrain suggest that terrain traversability is a key issue for future interplanetary rover autonomous planning algorithms.

This paper describes maximum likelihood estimation techniques for performing rover localization in natural terrain by matching range maps. An occupancy map of the local terrain is first generated using stereo vision. The position of the rover with respect to a previously generated occupancy map is then computed by comparing the maps using a probabilistic formulation of image matching techniques. Our motivation for this work is the desire for greater autonomy in Mars rovers. These techniques have been applied to data obtained from the Sojourner Mars rover and run on-board the Rocky 7 Mars rover prototype.

We present a stereoscopic mapping system for use in post-nuclear accident operations by the Pioneer robot. First we discuss a radiation shielded sensor array designed to tolerate extended cumulative dose using 4/spl times/ shielding. Next, we outline procedures to ensure timely, accurate range estimation using trinocular stereo. Finally, we review the implementation of a system for the integration of range information into a 3-D, textured, metrically accurate surface mesh.

Correlation-based real-time stereo systems have been proven to be effective in applications such as robot navigation, elevation map building etc. This paper provides an in-depth analysis of the major error sources for such a real-time stereo system in the contest of cross-country navigation of an autonomous vehicle. Three major types of errors: foreshortening error, misalignment error and systematic error are identified. The combined disparity errors can easily exceed three-tenths of a pixel, which translates to significant range errors. Upon understanding these error sources, we demonstrate different approaches to either correct them or model their magnitudes without excessive additional computations. By correcting those errors, we show that the precision of the stereo algorithm can be improved by 50%.

Experiments had been conducted on Mars rover detection and localization using residue image processing and stereo vision. In NASA's Pathfinder mission, an unmanned lander had been landed on Mars and a microrover was released from the lander to perform scientific experiments. Rover localization is an important issue because, for navigation purpose the rover's position needs to be continuously updated. Three aspects of the problem have been studied: motion detection, residue image processing, and range estimation. The algorithms are described. Stereo-pairs of images taken at the Jet Propulsion's Laboratory's (JPL's) Mars Test Arena were used to test the algorithms. The results were presented along with analysis of range estimation accuracy.

A new laser-based optical sensor system that provides hazard detection for planetary rovers is presented. The sensor can support safe travel at speeds up to 12 cm/second for large (1 m) rovers in full sunlight on Earth or Mars. This is at least a 5 times improvement over the sensor aboard NASA's Mars Pathfinder rover. The system overcomes limitations in the older design that require image differencing to detect a laser stripe in full sun. The new system ensures the projected laser light is detectable in a single image, eliminating the requirement for additional difference images. The improvement is significant since any reduction in image gathering or processing time provides for faster rover motion. The savings are even more important in the case of a Mars rover since power and radiation-hardening requirements lead to severely constrained computational resources. The paper includes a thorough discussion of design details and tradeoffs for optical hazard sensing that will benefit future efforts in this area.

The development of the CMOS active pixel sensor (APS) has, for the first time, permitted large scale integration of supporting circuitry and smart camera-functions on the same chip as a high-performance image sensor. This paper reports on the demonstration of a new 128/spl times/128 CMOS APS with programmable multiresolution readout capability. By placing signal processing circuitry on the imaging focal plane, the image sensor can output data at varying resolutions which can decrease the computational load of downstream image processing. For instance, software intensive image pyramid reconstruction can be eliminated. The circuit uses a passive switched capacitor network to average arbitrarily large neighborhoods of pixels which can then be read out at any user-defined resolution by configuring a set of digital shift registers. The full resolution frame rate is 30 Hz with higher rates for all other image resolutions. The sensor achieved 80 dB of dynamic range while dissipating only 5 mW of power. Circuit error was less than -34 dB and introduced no objectionable fixed pattern noise or other artifacts into the image.

In 1996, NASA will launch the Mars Pathfinder spacecraft, which will carry an 11 kg rover to explore the immediate vicinity of the lander. To assess the capabilities of the rover, the authors have constructed a new microrover testbed consisting of the Rocky 3.2 vehicle and an indoor test arena containing Mars analog terrain and overhead cameras for automatic, real-time tracking of the true rover position and heading. In this paper, the authors present initial performance evaluation results obtained with this testbed. The authors first decompose rover navigation into four major functions: goal designation, rover localization, hazard detection, and path selection. The authors then describe the Mars Pathfinder approach to each function, present results to date of evaluating the performance of each function, and outline their approach to enhancing performance for future missions. The results show key limitations in the quality of rover localization, the speed of hazard detection, and the ability of behavior control algorithms for path selection to negotiate the rock frequencies likely to be encountered on Mars.

To visually determine the position and orientation of a mobile robot from a fixed location in its vicinity, the authors have employed a cylindrical target which has different colors in each of its four quadrants. By judicious selection of the colors, segmentation of imagery from the fixed location can determine the size and centroid of the cylinder, as well as the visible color quadrants. Both the cylinder size in monocular images, and the centroid disparity in stereo pairs, are shown to provide a measure of distance. The angle of the cylinder is determined by analyzing which color quadrants are visible and to what degree. Implementation and experimental testing of this technique shows that it provides accurate localization data to within one or two pixels of error.

Statistical modeling and evaluation of the performance of obstacle detection systems for unmanned ground vehicles (UGV's) is essential for the design, evaluation and comparison of sensor systems. In this report, we address this issue for imaging range sensors by dividing the evaluation problem into two levels: quality of the range data itself and quality of the obstacle detection algorithms applied to the range data. We review existing models of the quality of range data from stereo vision and AM-CW LADAR, then use these to derive a new model for the quality of a simple obstacle detection algorithm. This model predicts the probability of detecting obstacles and the probability of false alarms, as a function of the size and distance of the obstacle, the resolution of the sensor, and the level of noise in the range data. We evaluate these models experimentally using range data from stereo image pairs of a gravel road with known obstacles at several distances. The results show that the approach is a promising tool for predicting and evaluating the performance of obstacle detection with imaging range.>

Statistical modeling and evaluation of the performance of obstacle detection systems for unmanned ground vehicles (UGVs) is essential for the design, evaluation, and comparison of sensor systems. This issue is addressed for imaging range sensors by dividing the valuation problem into two levels, i.e., the quality of the range data itself and the quality of the obstacle detection algorithms applied to the range data. Existing models of the quality of range data from stereo vision and AM-CW laser range-finders (LADAR) are reviewed. These are used to derive a new model for the quality of a simple obstacle detection algorithm. This model predicts the probability of detecting obstacles and the probability of false alarms, as functions of the size and distance of the obstacle, the resolution of the sensor, and the level of noise in the range data. These models are evaluated experimentally using range data from stereo image pairs of a gravel road with known obstacles at several distances. The results show that the approach is a promising tool for predicting and evaluating the performance of obstacle detection with imaging range sensors.>

To design high-performance obstacle detection systems for semi-autonomous navigation, it will be necessary to characterize the performance of obstacle detection sensors in quantitative, statistical terms and to develop design methodologies that relate task requirements (e.g., vehicle speed) to sensor system parameters (e.g., image resolution). Steps to be taken to realize such a methodology are outlined. For the specific case of obstacle detection with passive stereo range imagery, the development of the statistical models needed for the methodology is begun, and experimental results for outdoor images of a gravel road, which test the models empirically, are presented. The experimental results show sample error distributions for estimates of disparity and range, illustrate systematic errors caused by partial occlusion, and demonstrate that effective obstacle detection is achievable.>

A program to develop planetary rover technology is underway at the Jet Propulsion Laboratory (JPL) under sponsorship of NASA. Developmental systems with the necessary sensing, computing, power, and mobility resources to demonstrate realistic forms of control for various missions have been developed, and initial testing has been completed. These testbed systems and the associated navigation techniques used are described. Particular emphasis is placed on three technologies: Computer-Aided Remote Driving (CARD), Semiautonomous Navigation (SAN), and behavior control. It is concluded that, through the development and evaluation of such technologies, research at JPL has expanded the set of viable planetary rover mission possibilities beyond the limits of remotely teleoperated systems such as Lunakhod. These are potentially applicable to exploration of all the solid planetary surfaces in the solar system, including Mars, Venus, and the moons of the gas giant planets.>

The authors introduce a novel pixel-based (iconic) algorithm that estimates depth and depth uncertainty at each pixel and incrementally refines these estimates over time. They describe the algorithm for translations parallel to the image plane and contrast its formulation and performance to that of a feature-based Kalman filtering algorithm. They compare the performance of the two approaches by analyzing their theoretical convergence rates, by conducting quantitative experiments with images of a flat poster, and by conducting qualitative experiments with images of a realistic outdoor scene model. The results show that the method is an effective way to extract depth from lateral camera translations and suggest that it will play an important role in low-level vision.>

The authors use occupancy grids to combine range information from sonar and one-dimensional stereo into a two-dimensional map of the vicinity of a robot. Each cell in the map contains a probabilistic estimate of whether it is empty or occupied by an object in the environment. These estimates are obtained from sensor models that describe the uncertainty in the range data. A Bayesian estimation scheme is applied to update the current map using successive range readings from each sensor. The occupancy grid representation is simple to manipulate, treats different sensors uniformly, and models uncertainty in the sensor data and in the robot position. It also provides a basis for motion planning and creation of more abstract object descriptions.>

In stereo navigation, a mobile robot estimates its position by tracking landmarks with on-board cameras. Previous systems for stereo navigation have suffered from poor accuracy, in part because they relied on scalar models of measurement error in triangulation. Using three-dimensional (3D) Gaussian distributions to model triangulation error is shown to lead to much better performance. How to compute the error model from image correspondences, estimate robot motion between frames, and update the global positions of the robot and the landmarks over time are discussed. Simulations show that, compared to scalar error models, the 3D Gaussian reduces the variance in robot position estimates and better distinguishes rotational from translational motion. A short indoor run with real images supported these conclusions and computed the final robot position to within two percent of distance and one degree of orientation. These results illustrate the importance of error modeling in stereo vision for this and other applications.

We describe a second generation system that drives a camera-equipped mobile robot through obstacle courses. The system, which evolved from earlier work by Moravec [6], incorporates a new path planner and has supported experiments with interest operators, motion estimation algorithms, search constraints, and speed-up methods. In this paper we concentrate on the effects of constraint and on speed improvement. We also indicate some of our plans for a follow-on system.