In this paper we propose an efficient preconditioned conjugate gradients (PCG) approach to solving large-scale SLAM problems. While direct methods, popular in the literature, exhibit quadratic convergence and can be quite efficient for sparse problems, they typically require a lot of storage and efficient elimination orderings to be found. In contrast, iterative optimization methods only require access to the gradient and have a small memory footprint, but can suffer from poor convergence. Our new method, subgraph preconditioning, is obtained by re-interpreting the method of conjugate gradients in terms of the graphical model representation of the SLAM problem. The main idea is to combine the advantages of direct and iterative methods, by identifying a sub-problem that can be easily solved using direct methods, and solving for the remaining part using PCG. The easy sub-problems correspond to a spanning tree, a planar subgraph, or any other substructure that can be efficiently solved. As such, our approach provides new insights into the performance of state of the art iterative SLAM methods based on re-parameterized stochastic gradient descent. The efficiency of our new algorithm is illustrated on large datasets, both simulated and real.

We believe that machine learning can be used to help diabetics and care providers manage diabetes by predicting the effect that behaviors have on blood glucose. This when coupled with telemedicine could help care providers provide better individualized therapy more frequently. Currently, diabetics might get 15 minutes of interaction with a health expert during a checkup, and in that amount of time the physician must quickly evaluate the patient's health to offer therapy advice. The Intelligent Diabetes Assistant (IDA) addresses this problem by remotely collecting data, instantaneously sharing that data with a physician, and automatically processing the data to reveal important patterns. The system makes data collection more efficient for the patient, and it will make data analysis more efficient for the care team. We have conducted a two week longitudinal study tracking the lifestyle, nutrition, and blood glucose readings of 10 diabetics using IDA.

Accomplishing simultaneous localization and mapping (SLAM) in very large city environments is a great challenge because of theoretical and practical issues on computational complexity, dynamic environment, representation and data association. In this paper, we describe practical algorithms for dealing with the representation issues. Feature-based, grid-based and direct methods are integrated into the framework of the hierarchical object based representation. The sampling and correlation based range image matching algorithm is developed to tackle the problem arising from uncertain, sparse and featureless data in outdoor environments. Experimental results of a 800 meter /spl times/ 600 meter neighborhood demonstrate the feasibility of city-sized SLAM.

The simultaneous localization and mapping (SLAM) with detection and tracking of moving objects (DATMO) problem is not only to solve the SLAM problem in dynamic environments but also to detect and track these dynamic objects. In this paper, we derive the Bayesian formula of the SLAM with DATMO problem, which provides a solid basis for understanding and solving this problem. In addition, we provide a practical algorithm for performing DATMO from a moving platform equipped with range sensors. The probabilistic approach to solve the whole problem has been implemented with the Navlab11 vehicle. More than 100 miles of experiments in crowded urban areas indicated that SLAM with DATMO is indeed feasible.

Both simultaneous localization and mapping (SLAM) and detection and tracking of moving objects (DTMO) play key roles in robotics and automation. For certain constrained environments, SLAM and DTMO are becoming solved problems, but for robots working outdoors and at high speeds, SLAM and DTMO are still incomplete. In earlier works, SLAM and DTMO are treated as two separate problems. In fact, they can be complementary to one another. In this paper, we present a new method to integrate SLAM and DTMO to solve both problems simultaneously for both indoor and outdoor applications. The results of experiments carried out with CMU Navlab8 and Navlab11 vehicles with the maximum speed of 45 mph in crowded urban and suburban areas verify the described work.

A method is presented to recover 3D scene structure and camera motion from multiple images without the need for correspondence information. The problem is framed as finding the maximum likelihood structure and motion given only the 2D measurements, integrating over all possible assignments of 3D features to 2D measurements. This goal is achieved by means of an algorithm which iteratively refines a probability distribution over the set of all correspondence assignments. At each iteration a new structure from motion problem is solved, using as input a set of 'virtual measurements' derived from this probability distribution. The distribution needed can be efficiently obtained by Markov Chain Monte Carlo sampling. The approach is cast within the framework of Expectation-Maximization, which guarantees convergence to a local maximizer of the likelihood. The algorithm works well in practice, as will be demonstrated using results on several real image sequences.

When trying to recover 3D structure from a set of images, the most difficult problem is establishing the correspondence between the measurements. Most existing approaches assume that features can be tracked across frames, whereas methods that exploit rigidity constraints to facilitate matching do so only under restricted cam(cid:173) era motion. In this paper we propose a Bayesian approach that avoids the brittleness associated with singling out one "best" cor(cid:173) respondence, and instead consider the distribution over all possible correspondences. We treat both a fully Bayesian approach that yields a posterior distribution, and a MAP approach that makes use of EM to maximize this posterior. We show how Markov chain Monte Carlo methods can be used to implement these techniques in practice, and present experimental results on real data.

Pedestrian detection is essential to avoid dangerous traffic situations. We present a fast and robust algorithm for detecting pedestrians in a cluttered scene from a pair of moving cameras. This is achieved through stereo-based segmentation and neural network-based recognition. The algorithm includes three steps. First, we segment the image into sub-image object candidates using disparities discontinuity. Second, we merge and split the sub-image object candidates into sub-images that satisfy pedestrian size and shape constraints. Third, we use intensity gradients of the candidate sub-images as input to a trained neural network for pedestrian recognition. The experiments on a large number of urban street scenes demonstrate that the proposed algorithm: (1) can detect pedestrians in various poses, shapes, sizes, clothing, and occlusion status; (2) runs in real-time; and (3) is robust to illumination and background changes.

Presents a trinocular stereo algorithm that we have developed as part of an obstacle detection system that detects small obstacles at long range on the highway. We describe the stages of the stereo algorithm itself and the reasons behind the design decisions that were made. This is followed by a description of the obstacle detection system that we have built. Finally, we show results from our system for a variety of different obstacles.

This paper presents a multibaseline stereo technique specially suited to detecting obstacles. A method is described for weakly calibrating a set of multibaseline stereo cameras with high accuracy. This method is then used to tailor the stereo search space to the special case where the world in front of the cameras consists mainly of nearly horizontal planar surfaces (the ground), where we are interested in deviations from those planar surfaces (obstacles). The resulting disparity maps are presented and compared to the output of a traditional stereo algorithm.

In this paper, we present a car tracking system which provides quantitative and qualitative motion estimates of the tracked car simultaneously from a moving observer. First, we construct three motion models (constant velocity, constant acceleration, and turning) to describe the qualitative motion of a moving car. Then the models are incorporated into the Extended Kalman Filters to perform quantitative tracking. Finally, we develop an Extended Interacting Multiple Model (EIMM) algorithm to manage the switching between models and to output both qualitative and quantitative motion estimates of the tracked car. Accurate motion modeling and efficient model management result in a high performance tracking system. The experimental results on simulated and real data demonstrate that our tracking system is reliable and robust, and runs in real-time. The multiple motion representations make the system useful in various autonomous driving tasks. 1 Introduction Vehicle tracking is an important a...

This paper discusses how we integrated our 3D car tracking approach with the lane following module RALPH on the Navlab autonomous vehicles, obtaining a hybrid vision system that tracks both the road and cars better than those two systems in isolation. The tracking system brings precise and crisp measurements of the car in the image, and performs image stabilization. However, because it does not know, about the yaw or lateral offset of the ego-vehicle, its curvature estimate can be misguided. RALPH takes a more global image processing approach and can provide this missing information, as well as a good estimate of curvature, so that the combined curvature estimate is superior to both taken in isolation. The additional information provided by RALPH also improves tracking performance, and allows us to estimate properties of the tracked car that were previously unobservable, in particular its in-lane displacement. Better car tracking, and a better idea of where the road is, gives us a substantial foundation on which to base other capabilities needed to realize fully autonomous vehicles.

We present an approach to tracking planar surface patches over time. In addition to tracking a patch with full six degrees of freedom, the algorithm also produces a super-resolved estimate of the texture present on the patch. This texture estimate is kept as an explicit model texture image which is refined over time. We then use it to infer the 3D motion of the patch from the image sequence. The main idea behind the approach is to use a technique from computer graphics, known as texture mapping, as the measurement model in an extended Kalman filter. We also calculate the partial derivative of this image formation process with respect to the 3D pose of the patch, which functions as the measurement Jacobian. The super-resolved estimate of the texture is obtained using the standard extended Kalman filter measurement update, with one essential approximation that makes this computationally feasible. The resulting equations are remarkably simple, yet lead to estimates that are properly super-resolved. In addition to developing the theory behind the approach, we also demonstrate both the tracking and the super-resolution aspect of the algorithm on real image sequences.

We present a novel method for obstacle detection for automated highway environments. Laser range scanners have frequently been used for obstacle detection for mobile robots. Although most laser scanners provide intensity information in addition to range, laser intensity has been ignored by most researchers. We show that laser intensity, on its own, is sufficient (and better) for detecting obstacles at long ranges in mild terrain such as an automated highway.

We present a Kalman filter based approach to perform model-based motion estimation and tracking. Unlike previous approaches, the tracking process is not formulated as an SSD minimization problem, but is developed by using texture mapping as the measurement model in an extended Kalman filter. During tracking, a super-resolved estimate of the texture present on the object or in the scene is obtained. A key result is the notion of Jacobian images, which can be viewed as a generalization of traditional gradient images, and represent the crucial computation in the tracking process. The approach is illustrated with three sample applications: full 3D tracking of planar surface patches, a projective surface tracker for uncalibrated camera scenarios, and a fast, Kalman filtered version of mosaicking with detection of independently moving objects.

This paper describes a series of quantitative studies of a user interface for robot vehicle teleoperation. Supervised telerobotics using incremental polyhedral Earth geometry (STRIPE) is a teleoperation system for a robot vehicle that allows a human operator to accurately control the remote vehicle across very low bandwidth communication links, and communication links with large delays. In STRIPE, a single image from a camera mounted on the vehicle is transmitted to the operator workstation. The operator uses a mouse to pick a series of "waypoints" in the image that define a path that the vehicle should follow. These 2D waypoints are then transmitted back to the vehicle, where they are used to compute the appropriate steering commands while the next image is being transmitted. STRIPE requires no advance knowledge of the terrain to be traversed. This paper describes a series of tests of the STRIPE system. Conditions tested include different graphical interfaces, bandwidths, lenses, and rates of image compression.

Our long term goal is to integrate the position-based navigation with visual road following in order to build a more robust and reliable road navigation system. In this paper, we describe the first part of the project: constructing a navigation system that can build maps of highways and landmarks, and use those feature for position-based navigation. Speed and yaw rate gyro sensors are used for vehicle motion detection, and a millimeter wave radar system is used for landmark detection. To achieve position estimation and error correction, we use an extended Kalman filter. First, a map is built without previous knowledge of landmarks while human drives the vehicle. Then, at the stage of autonomous navigation, the previously produced map is used for position estimation. The experimental results show that a map produced by the proposed method can be used for later navigation, and that vehicle position is estimated accurately.

A major issue in building a prototype automated highway system (AHS) is whether the system needs dedicated lanes, occupied only by computer-controlled cars that communicate and cooperate with each other; or whether the automated vehicles can be provided with enough sensing and intelligence that they can safely operate on regular highways, intermixed with manually-driven vehicles. A major portion of the CMU research effort in AHS is focused on determining the technical feasibility of operation in mixed traffic. This paper outlines the issues of mixed traffic vs. dedicated lanes, then describes CMU efforts in building complete demonstration systems, vehicle sensors, obstacle sensors, car tracking software, reasoning for tactical driving, and deployment scenarios.

We have designed an architecture that allows a gait planner to effectively control primitive walking behaviors. The behaviors ensure safe and efficient walking, even without planning; the addition of planning improves performance in rough terrain by allowing the robot to anticipate changes in its gait. We have implemented our approach and demonstrated it on a real robot, Dante II, and on a simulated hexapod with more complex kinematics. With the hexapod we can produce a variety of gaits and stably switch among them. We have attained performance improvement by using narrowly focused planning to guide behavior.

ELVIS (Eigenvectors for Land Vehicle Image System) is a road-following system designed to drive the CMU Navlabs. It is based on ALVINN, the neural network road-following system built by Dean Pomerleau at CMU. ELVIS is an attempt to more fully understand ALVINN and to determine whether it is possible to design a system that can rival ALVINN using the same input and output, but without using a neural network. Like ALVINN, ELVIS observes the road through a video camera and observes human steering response through encoders mounted on the steering column. After a few minutes of observing the human trainer, ELVIS can take control. ELVIS learns the eigenvectors of the image and steering training set via principal component analysis. These eigenvectors roughly correspond to the primary features of the image set and their correlations to steering. Road-following is then performed by projecting new images onto the previously calculated eigenspace. ELVIS architecture and experiments are discussed as well as implications for eigenvector-based systems and how they compare with neural network-based systems.

The use of artificial neural networks in the domain of autonomous driving has produced promising results. ALVINN has shown that a neural system can drive a vehicle reliably and safely on many different types of roads, ranging from paved paths to interstate highways. The next step in the evolution of autonomous driving systems is to intelligently handle road junctions. In this paper the authors present an addition to the basic ALVINN driving system which makes autonomous detection of roads and traversal of simple intersections possible. The addition is based on geometrically modelling the world, accurately imaging interesting parts of the scene using this model, and monitoring ALVINN's response to the created image.

The authors' experience over the years with different architectures and planning systems for mobile robots has led them to a distributed approach where an arbiter receives votes for and against commands from each subsystem and decides upon the course of action which best satisfies the current goals and constraints of the system. Centralized arbitration of votes from distributed, independent decision-making processes provides coherent, rational, goal-directed behavior while preserving real-time responsiveness to its immediate physical environment. The Distributed Architecture for Mobile Navigation (DAMN) has been successfully used to integrate various independently developed subsystems, providing systems that perform road following, cross-country navigation, or teleoperation while avoiding obstacles and meeting mission objectives. Examples of implemented systems are given. Further research will seek to more rigorously define the behavior of the system.

SCARF, a color vision system that recognizes difficult roads and intersections, is presented. It has been integrated into several navigation systems that drive a robot vehicle, the Navlab, on a variety of roads in many different weather conditions. SCARF recognizes roads that have degraded surfaces and edges with no lane markings in difficult shadow conditions. It also recognizes intersections with or without predictions from the navigation system. This is the first system that detects intersections in images without a priori knowledge of the intersection shape and location. SCARF uses Bayesian classification to determine a road-surface likelihood for each pixel in a reduced color image. It then evaluates a number of road and intersection candidates by matching an ideal road-surface likelihood image with the results from the Bayesian classification. The best matching candidate is passed to a path-planning system that navigates the robot vehicle on the road or intersection. The SCARF system is described in detail, results on a variety of images are presented, and Navlab test runs using SCARF are discussed.>

collisions Is an Important task for any autonomous mobile system. Thls paper describes an apprvach uslng a sonar system that we Implemented for the autonomous land vehlcle Navlab. The general hardware configuration of the system ls shown, followed by a description of how the system buikb a local grid map of its envlronment. The Information collected In the map can then be used for a varkty of a plications in vehlcle navigation Uke colllslon avoidance, gaturn tracking and parking. A slmple algorithm was Implemented that can track a static feature such as a rail, wall or an array of parked cars and use this Information to drlve the vehlcle. Methods for Illterlng the raw data and generatlng the steerlng commands BIP discussed and the Implementation for collision avoidance and

Ahstruct-Gait generation is the formulation and selection of a sequence of coordinated leg and body motions that propel a legged robot along a desired path. Approaches to gait generation can be classified into control, behavioral, rule-based, and constraintbased paradigms. We survey these models of gait generation and introduce the Ambler, a hexapod robot that can circulate its legs to produce unique gaits. Then we present kinematic, collision, terrain, support, and stability constraints available for gait generation, and discuss our progress using a constraint-based method to generate the Ambler's gait. I. INTRODUCTION In comparison to wheeled mechanisms, legged rnechnisms require complex design, move slowly, and are difficult to control. However, for locomotion over rough or discontinuous terrain, legged mech'anisms are potentially superior to wheeled mech,uiisms.[ 11 Legged mechanisms make discrete terrain contacts and avoid undesirable footholds while wheeled mechanisms have rollers in continuous contact with the ground. The posture of a wheeled mechanism is dependent upon the terrain, but a legged mechanism can isolate its body from tlie ten ani- ' achieving a more stable stunce' and allowing smooth level motion. Legged locomotion is theoretically more energy efficient because body propulsion does not expend as much energy in soil compaction and body motion can occur in a level plane decoupled from the effects of gravity. Legged mechanisms can actively position their center of gravity to maximize stability. Dead reckoning (estimating position by integrating motion over time) can be more accurate in a legged machine where feet make discrete contacts and do not slip or skid like a wheel. The complexity in the design of legged mechanisms can be achieved, a$ is demonstrated by the working systems examined in this paper. We believe that the slow, smooth motion of legged devices is advantageous in rough terrain where caution (and, sometimes, sensing) will limit the speed of wheeled and legged mechanisms alike. The significant drawback to legs has been the difficulty in control. For a slow-moving walker, this challenge is not in moving the individual legs, a$ this is directly analogous to well-unders tood manipulator control, but in the coordination of leg and body motions. The legged robot, either with a real-time controller, low-level planner, or as an artifact of its architecture, must generate a sequence of leg and body motions, a gait, that will propel it along some path. Gait yeneralion is the formulation and selection of a sequence of coordinated leg and body motions that propcl the robot along a desired path. In this paper we survey several approaches taken toward gait generation aid present some of and discuss our work on gait generation for the Ambler.

The problem of navigating a robot vehicle on unstructured roads that have no lane markings, may have degraded surfaces and edges, and may be partially obscured by strong shadows is addressed. These conditions cause many road following systems to fail. The authors have build a system, UNSCARF, which is based on pattern recognition techniques, for successfully navigating on a variety of unstructured roads. UNSCARF does not need a road location prediction to find the location of the road; therefore, UNSCARF can be used as a bootstrapping system. It uses a clustering technique to group pixels with similar colors and locations. It then matches models of road shape to locate the roads in the image. These methods are more robust in noisy conditions than other road interpretation techniques. UNSCARF has been integrated into a navigation system that has successfully driven a test vehicle in may types of weather conditions.>

Mobile robots must deal with unstructured environments in order to be general and useful. Current laboratory robots often use single approach to deal with unstructured environments: position sensing, environment sensing, planning, or mechanical design. Robust robots of the future will have to use combinations of all those approaches, and also handle the difficult problems of system integration. This article is an overview of the problems to be faced and of some of the more promising approaches being investigated.

The authors discuss the need for explicit models in the context of road following, showing how previously built road followers have suffered by not having such models. The approach will not only model appearance and shape information, but also include semantics. It is suggested that using an explicit model will make it easier to program and debut a road follower and will lead to efficient programs. The bulk of the processing can be done by simple operators that need not be concerned with special cases, whereas the costlier recovery procedures and switching between operators will occur infrequently. The authors introduce FERMI (Following Explicit Road Models Intelligently) and describe its construction and performance. FERMI includes explicit geometric models and multiple trackers, and it uses explicit models to select features to track and methods to track them.>

Geometric camera calibration is the process of determining a mapping between points in world coordinates and the corresponding image locations of the points. In previous methods, calibration typically involved the iterative solution to a system of nonlinear equations. A method is presented for performing camera calibration that provides a complete, accurate solution, using only linear systems of equations. By using two calibration planes, a line-of-sight vector is defined for each pixel in the image. The effective focal point of a camera can be obtained by solving the system that defines the intersection point of the line-of-sight vectors. Once the focal point has been determined, a complete camera model can be obtained with a straightforward least-squares procedure. This method of geometric camera calibration has the advantages of being accurate, efficient, and practical for a wide variety of applications.>

A method is presented for combining two previously proposed algorithms for path-planning and dynamic steering control into a computationally feasible scheme for real-time feedback control of autonomous vehicles in uncertain environments. In the proposed approach to vehicle guidance and control, Path Relaxation is used to compute critical points along a globally desirable path using a priori information and sensor data. Generalized potential fields are then used for local feedback control to drive the vehicle along a collision-free path using the critical points as subgoals. Simulation results are presented to demonstrate the control scheme.

This paper describes sensor fusion in the context of an autonomous mobile robot. The requirements of a complex mission, real-world operation, and real-time control dictate many facets of the system architecture. The hardware architecture must include both general-purpose and special-purpose computers, and multiple sensors of various modalities (vision, range, etc.). The software architecture must allow modular development of a parallel system that supports many perceptual modalities and navigation planning tasks, but at the same time enforces global consistency regarding position and orientation of the vehicle and sensors. We are building such a system at CMU, called the NAVLAB system, based on a commercial truck with computer controls and studded with cameras and other sensors. This paper describes the software architecture of the NAVLAB, consisting of two parts: a "whiteboard" system called CODGER that is similar to a blackboard but supports parallelism in the knowledge source modules, and an organized collection of perceptual and navigational modules tied together by the CODGER system. In general, the system philosophy is to provide as much top-down guidance as possible, and to exploit sensor modality differences to produce complementary rather than competing perceptual processes in the system. In this way, the limitations of each sensor modality are compensated for as much as possible by other sensors or by higher level knowledge. The NAVLAB is being produced as part of the DARPA Strategic Computing Initiative, in conjunction with the Autonomous Land Vehicle project.

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.