Research at the Robotics Lab

Nonholonomic Motion Planning for Robots

Generally nonholonomic constraints arise from the presence of one or more rolling contacts between rigid bodies, or from the nature of controls that it is possible to apply to the system in question, or from conservation laws (usually angular momentum conservation). Such motion planning problems are considerably more difficult than motion planning problems in the presence of only position constraints, and arise, for instance, in planning problems involving: 1) mobile robots navigating in a cluttered environment; 2) multifingered robot hands rolling on the surface of grasped objects; 3) space robots that are unanchored; and 4) hopping robots. There are many applications that have benefited from this research, including automated parking cars and trucks, motion planning for airport luggage carriers, and construction animation; grasping and regrasping by multifingered hands for assembly operations; and path planning for construction robots in space.

Millirobots for Minimally Invasive Surgery

Centimeter-size and smaller teleoperators are needed for surgical and other types of manipulation. For example, current minimally-invasive surgical tools are a poor substitute for the degrees of freedom and perception capability of the human hand. We are developing miniature grippers with force and tactile feedback capability that are designed to improve surgical capabilities.

Computational Vision

The goal of computational vision is to start with one or more video sequences of a scene and extract spatial information adequate to guide manipulation and navigation, as well as to recognize objects in the scene. A principal result of the work at Berkeley has been the development of a framework for vision based on an initial stage of convolving the image with a bank of spatiotemporal linear filters tuned to various orientations and scales. This multichannel filtering has been shown to be an excellent substrate for early vision tasks such as texture, stereopsis, and motion analysis.

Also see the UCB Vision Group

Assembly and Materials Handling - RISC Robotics

The goal of this project is to develop a robotic assembly/materials handling system for small mechanical parts. In this work we are exploring a RISC paradigm that uses simple actuators and sensors, and that achieves flexibility through intelligence embedded in the control software. Use of new, simple sensing technologies, such as optical beam sensing, allows very accurate part recognition and localization in milliseconds. Other low-bandwidth sensing methods, like tactile and force sensing, are being explored. A key to the project is the integration of many diverse, large software packages and provision for a uniform user interface.

Adaptation and Learning in Biological and Artificial Systems

One of the amazing successes of biological systems is their ability to coordinate many degrees of freedom and sensing. They do so using a sophisticated hierarchy of sensory-motor neural networks which have different time scales of operation consistent with their hierarchical organization. In addition these sensory motor networks "learn by doing" and adapt to their environment. In addition they have built in mechanisms to preserve the safety of the organism and gracefully degrade its performance when there are untoward disturbances. In this project we are interested in building control theoretic and robotically inspired models for adaptation and learning in biological systems. This is used in turn to inspire mechanisms for learning and adaptation in complex hierarchically, organized intelligent control systems.

Air Traffic Mangement Systems

In a new project with NASA Ames Research Center and Honeywell Systems Research Center, we are studying the design of new architectures for air traffic management. The problem here is to improve the utlization of congested airports by allowing for "free flight" in the region around airports and to effectively sequence the rapid landing and take off of aircraft. The technical problems involve coordination between the auto-pilots on board aircraft and both local and regional air traffic control. The techniques involved are a combination of non-linear control and hybrid control . Our architecture is heavily motivated by the automated highway architectures of PATH .

A partial list of other projects (which will hopefully be more complete as time goes on) is shown below. If you are a member of the lab and have research that you want to list, please contact Eric Paulos.

Index of Other Research By Topic

Grasping

Motion Planning With Nonholonomic Velocity Constraints

Vision Group

Other

Solution of Systems of Polynomial Equations and Applications to Robotics and Vision

I.Z. Emiris and J.F. Canny

Several problems in robot kinematics, computer vision, modeling, mechanical design as well as drug fabrication involve systems of nonlinear polynomial equations that are sparse. Sparsity here means that the Mixed Volume of the system, which provides an upper bound on the number of isolated zeros, is almost tight and significantly smaller than the classical Bezout bound. Existing methods, such as Grobner bases, homotopies and the classical multivariant resultant, fail to take advantage of this kind of sparsity. However, for certain problems where sparsity was exploited ad hoc , resultants have been shown to provide the most efficient way for eliminating variables as well as for computing the zeros of the given system.

We have proposed the first general and efficient algorithm for constructing the sparse resultant of a system of polynomials and have designed an algorithm that produces a more compact formula for this resultant; the second method produces an optimal formula for several classes of polynomial systems. Moreover, we have proven that, by means of the sparse resultant, finding the roots of a polynomial system reduces to an eigenvector problem.

We have implemented both algorithms and are currently examining their performance on specific applications such as the Stewart platform forward kinematics and the motion from point-matches problem. Of independent interest is our program that computes the Mixed Volume of a system of $n$ nonlinear polynomials in n variables. We have applied this program to derive the first upper bounds on the number of zeros for several instances of the cyclic n-th root problem. Moreover, in using continuation methods for solving very large systems, the Mixed Volume computation can be used to define the initial system for a sparse homotopy.

Postscript version of above with citations (1 page postscript)

Papers

Extended Goursat Normal Forms with Applications to Nonholonomic Motion Planning

L. Bushnell, D. Tilbury, and S. Sastry

The theme of this paper is the generalization of Goursat normal forms for Pfaffian systems with co-dimension greater than two. There are necessary and sufficient conditions for the existence of coordinates that transform a Pfaffian system with co-dimension greater than two into an extended Goursat normal form, which is the dual of the multiple-chain, single-generator chained form mentioned in our earlier work. In this paper, we concentrate on how to find such coordinate transformations for multi-steering, multi-trailer mobile robot systems so that we can use available steering and stabilization algorithms for nonholonomic motion planning. We present a methodology for constructing a coordinate transformation and apply it to the example of a five-axle, two-steering mobile robot.

Paper (12 Pages PostScript)

Steering Three-Input Chained Form Nonholonomic Systems: The Fire Truck Example

L. G. Bushnell, D. M. Tilbury and S. S. Sastry

In this paper, we steer wheeled nonholonomic systems that can be represented in a so-called chained form. Necessary and sufficient conditions for converting a multiple-input system with nonholonomic velocity constraints into a multiple-chain, single-generator chained form via state feedback and coordinate transformation are presented along with the sinusoidal and polynomial control algorithms to steer such systems. Our example is the three-input nonholonomic system of a fire truck, or tiller truck. In this three-axle system, the control inputs are the steering velocities of both the first and third axles and the driving velocity of the first axle. Simulation results are given for parallel parking, left-hand turns, right-hand turns, and changing lanes. Comparison is made to the same vehicle without tiller steering.

Paper (24 Pages PostScript)

An Obstacle Avoidance Algorithm for a Car Pulling Trailers with Kingpin Hitching

A. Sahai and M. Secor and L. Bushnell

We present a new method for planning motion around obstacles for a mobile robot system configured as a car pulling many trailers with non-standard kingpin hitching. In our method, we need only plan for the front car and the trailers will follow without hitting obstacles. We assume there are no back-ups in the trajectory. By setting the distance between an axle and its neighboring kingpin to be the same for all axles, by showing exponential convergence of the distance between the path followed by a trailer and the path followed by the car, and by showing there exists a bound on this distance, we propose an obstacle avoidance algorithm for a multi-trailer system using any existing path planner for the front car only. Examples are given for a car pulling a single trailer and three trailers.

Paper (25 Pages PostScript)

Fast Object Recognition by Selectively Examining Hypotheses

Clark F. Olson

Object recognition systems for the problem of recognizing three-dimensional objects from intensity icons have been plagued by low speed. Hypothetical poses can be determined from a small number of model features appearing in the image. The number of correct matches between these small sets of model and image features (and thus correct hypotheses) is combinatorial in the number of image features. Since only one of these correct hypotheses needs to be found to recognize the object, an exhaustive examination of all hypothetical matches is not necessary. I am studying techniques to obtain fast object recognition through the selective examination of the possible hypotheses.

Papers:

Fast Alignment Using Probabilistic Indexing
Paper (? Pages PostScript)
IEEE Conference on Computer Vision and Pattern Recognition, 1993
Clark F. Olson

Probabilistic Indexing: A New Method of Indexing 3D Model Data from 2D Image Data
Paper (? Pages PostScript)
Proceedings of the Second CAD-Based Vision Workshop, 1994
Clark F. Olson

Time and Space Efficient Pose Clustering
Paper (? Pages PostScript)
IEEE Conference on Computer Vision and Pattern Recognition, 1994
Clark F. Olson

Efficient Numerical Programs for the Solution of Nonlinear Optimal Control Problems

Adam Lowell Schwartz

Advisor: Elijah Polak

General optimal control problems for nonlinear dynamical systems do not have analytical solutions. Instead, they require numerical solution by a computer. Furthermore, both the constraints and the control are typically functions rather than finite dimensional vectors. Because of this, a discretization strategy must be employed to solve a sequence of finite-dimensional problems which approximate the original problem. These finite-dimensional problems must satisfy certain consistency condition to ensure convergence to the optimal control. Beyond this, there is a great deal of flexibility in choosing both the discretization strategy and the nonlinear programming methods used to solve the approximate problems. Intelligent utilization of this flexibility is important because the approximate problems result in difficult large-scale optimization problems.

Our research addresses these issues. Additionally, we are designing a CAD system utilizing our theory to implement a library of optimal control routines enabling quick construction of experimental algorithms. Another feature of the CAD system will be a graphical user interface which will allow monitoring of useful information and modification of internal parameters to improve the optimization efficiency. Currently, our software solves smooth optimal control problems with control bounds and terminal constraints. Two papers are being prepared for publication.

Feasibility Study of Fully Autonomous Vehicles Using Dynamic Belief Networks

Stuart Russell

Previous research into autonomous vehicles has concentrated on low-level sensing and control, and has achieved a reasonable degree of success in providing basic driving capabilities (following a lane, keeping a safe distance, tracking other vehicles). At the same time, technology for real-time Bayesian decision-making under uncertainty has developed to the point where it is reasonable to consider the integration of high-level and low-level systems. Our objective is to evaluate the applicability and potential impact of real-time decision-making technology to the problem of guiding a vehicle in unrestricted traffic in both urban and freeway settings, including the development and demonstration of prototypes in simulation. Ideally, one should be able to board such a vehicle, state a destination, and leave the rest to the vehicle. Although it is a difficult technical problem, autonomous operation in unrestricted traffic has the potential to provide a feasible, ``non-invasive'' migration path towards high-throughput automated traffic with no modification of existing infrastructure. It can also provide ``on-demand'', low-overhead bus, taxi and rental-car operation, an efficient local feeder system for mass transit, and greater transportation access for a wide segment of the population. By developing robust, rigorous techniques for real-time sensing and decision-making under uncertainty using a complex and flexible model, we will contribute to the development of accurate driver-behavior simulators, situation surveillance methods, probabilistic data fusion and sensor failure detection and recovery, and more robust control mechanisms.

Papers: No publications have appeared.

Application of Signal Processing techniques to Computer Vision problems

Roberto Manduchi
Research Fellow from the University of Padova, Italy

My current projects include (1) improving the accuracy of differential-based optical flow algorithms and (2) analysis of the low-level stages of typical differential-based optical flow algorithms. I am examining the latter in order to improve the overall accuracy by exploiting the information provided by both fields within a frame for interlaced scanning systems and by using adapted differentiators.

References:

R. Manduchi, "Improving the Accuracy of Differential--Based Optical Flow Systems" Technical Report UCB//CSD-93-776, University of California at Berkeley, 1993

R. Manduchi, "Motion-Based Segmentation for Layered Image Models with Tracking and Occlusion Reasoning" Are we really able to segment an image just using motion information?

Optimal Grasps Planning

Carlo Ferrari

The problem of planning optimal grasps is addressed. Two general optimality criteria, that consider the total finger force and the maximum finger force have been introduced and studied. Moreover their formalization, using various metrics on a space of generalized forces, have been detailed. The geometric interpretation of the two criteria leads to an efficient planning algorithm. An example of its use in a robotic environment equipped with two-jaw and three-jaw grippers is under development.

References:

Ferrari C., Canny J., "Optimal Grasps Planning", Proc. 1992 IEEE Int. Conf. on Robotics and Automation, Nice (Francia), May 1992.

Car Tracking for Automated Highways

Dieter Koller, Joseph Weber and Jitendra Malik

We address the problem of occlusion in tracking multiple 3D objects in a known environment. For that purpose we employ a contour tracker based on intensity and motion boundaries. The motion of a contour enclosing the image of a vehicle is assumed to be well describable by an affine motion model with a translation and a change in scale. Contours are represented by closed cubic splines the position and motion of which are estimated along the image sequence In order to employ linear Kalman Filters we decompose the estimation process in two filters: one for estimating the affine motion parameters and one for estimating the shape of the contours of the vehicles. Occlusion detection is performed by intersecting the depth ordered regions associated to the objects. The intersection part is then excluded in the motion and shape estimation. Occlusion reasoning also improves the shape estimation in case of adjacent objects where shape estimates can be corrupted by image data of other objects. In this way we obtain robust motion estimates and trajectories for vehicles even in the case of occlusions, as we show in some experiments with real world traffic scenes. For a picture and more information press here.

References:

Dieter Koller and Joseph Weber and Jitendra Malik, "Robust Multiple Car Tracking with Occlusion Reasoning" ECCV, Stockholm, May 1994.

Machine Vision Based Vehicle Guidance: Lateral and Longitudinal Control

Dieter Koller, Quang-Tuan Luong, Joseph Weber and Jitendra Malik

One idea to increase traffic capacity is the platooning concept, i.e. organize the traffic in tightly spaced platoons. Automobiles in such a platoon will be controlled by computers supported by advanced sensor, actuators, and communication to other computers. The current approach is using magnetic sensors sensing magnets in the road for lateral control and doppler radar for obstacle detection and longitudinal control. We are investigating the possibility of supporting these non-visual sensors using visual sensors and suggest an integrated approach. Visual sensing becomes very important during a lane change or while merging into an already established platoon. For pictures and more information press here.

References:

D. Koller, Q.-T. Luong, J. Malik. Technical report UCB/CSD-94-804, May 1994.

On Goursat Normal Forms, Prolongations, and Control Systems

D. Tilbury and S. Sastry

In this paper, we present the method of exterior differential systems for analyzing nonlinear systems. We present conditions for converting Pfaffian systems into Goursat normal form, and for converting control systems into Brunovsky form. All of the existing results on feedback linearization for control systems can be restated in the language of Pfaffian systems. Our conditions for linearizing control systems using dynamic extension are closer to necessity than those which currently exist in the literature.

(28 pages postscript)

A Multi-Steering Trailer System: Conversion into Chained Form using Dynamic Feedback

D. Tilbury, O. Sordalen, L. Bushnell, and S. Sastry

In this paper, we examine in detail the kinematic model of an autonomous mobile robot system consisting of a chain of steerable cars and passive trailers, connected together with rigid bars. We define the state space and kinematic equations of the system, modeling the pair of wheels on each axle as able to roll but not slip. We then investigate how this system of kinematic equations may be converted into a multi-input chained form. The advantages of the chained form are that many methods are available for the open-loop steering of such systems as well as for point-stabilization.

In order to convert the system to this multi-input chained form, we use dynamic state feedback. We draw some motivation from the very simple example of a kinematic unicycle and the relationships of the angular velocities therein, and we show how the dynamic state feedback that we use corresponds to adding, in front of the steerable cars, a chain of virtual axles which diverges from the original chain of trailers.

We briefly discuss how some of the methods which have been proposed for steering and stabilizing two-input chained form systems can be generalized to multi-chained systems. For concreteness, we also present two different example systems: a fire truck (three axles) and a five-axle, two-steering system. Simulation results for a parallel-parking maneuver for the five-axle system are included in the form of margin movies.

(33 pages postscript)

Trajectory Generation for the N-Trailer Problem using Goursat Normal Form

D. Tilbury, R. Murray, S. Sastry

In this paper, we develop the machinery of exterior differential forms, more particularly the Goursat normal form for a Pfaffian system, for solving nonholonomic motion planning problems, \ie planning problems with non-integrable velocity constraints. We apply this technique to solving the problem of steering a mobile robot with n trailers. We present an algorithm for finding a family of transformations which will display the given system of rolling constraints on the wheels of the robot with n trailers in the Goursat canonical form. Two of these transformations are studied in detail. The Goursat normal form for exterior differential systems is dual to the so-called chained form for vector fields that we have studied in our earlier work. Consequently, we are able to give the state feedback law and change of coordinates to convert the N-trailer system into chained form. Three methods for steering chained form systems using sinusoids, piecewise constants and polynomials as inputs are presented.

The motion planning strategy is therefore to first convert the N-trailer system into chained form, steer the corresponding chained form system, then transform the resulting trajectory back into the original coordinates. Simulations and frames of movie animations of the N-trailer system for parallel parking and backing into a loading dock using this strategy are also included.

(52 pages postscript)

Short conference version of paper (7 pages postscript)

Steering a Three-Input Nonholonomic System Using Multirate Controls

D. Tilbury and A. Chelouah

In this paper we examine a multi-rate control scheme for nonholonomic path planning using constant control inputs over different time periods. For chained systems, an exact point-to-point trajectory is generated. Simulation results are presented for a three-input system, and comparisons are made with a sinusoidal method for path planning.

(4 pages postscript)

Stabilization of Trajectories for Systems with Nonholonomic Constraints

G. Walsh, D. Tilbury, S. Sastry, R. Murray, and J-P. Laumond

A new technique for stabilizing nonholonomic systems to trajectories is presented. It is well known that such systems cannot be stabilized to a point using smooth static state feedback. In this paper we suggest the use of control laws for stabilizing a system about a trajectory, instead of a point. Given a nonlinear system and a desired (nominal) feasible trajectory, the paper gives an explicit control law which will locally exponentially stabilize the system to the desired trajectory. The theory is applied to several examples, including a car-like robot.

(17 pages postscript)

UCB Robotics Lab / Eric Paulos / 6 Oct 1994