Autonomous Robot Vehicles

A wheeled mobile robot is here modelled as a planar rigid body that rides on an arbitrary number of wheels. The relationship between the rigid body motion of the robot and the steering and drive rates of wheels is developed. In particular, conditions are obtained that guarantee that rolling without skidding or sliding can occur. Explicit differential equations are derived to describe the rigid body motions that arise in such ideal rolling trajectories. The simplest wheel configuration that permits access of arbitrary rigid-body motions is determined. Then the question of slippage due to misalignment of the wheels is investigated by minimization of a nonsmooth convex dis­sipation functional that is derived from Coulomb’s Law of friction. It is shown that this minimization principle is equivalent to the construction of quasi-static motions. Examples are presented to illustrate the models.

We have introduced a methodology for the kinematic modeling of wheeled mobile robots 1–2. In this paper, we apply our methodology to Uranus3, an omnidirectional wheeled mobile robot which is being developed in the Robotics Institute of Carnegie Mellon University. We assign coordinate systems to specify the transformation matrices and write the kinematic equations-of-motion. We illustrate the actuated inverse and sensed forward solutions; i.e., the calculation of actuator velocities from robot velocities and robot velocities from sensed wheel velocities. We apply the actuated inverse and sensed forward solutions to the kinematic control of Uranus by: calculating in real-time the robot position from shaft encoder readings (i.e., dead reckoning); formulating an algorithm to detect wheel slippage; and developing an algorithm for feedback control.

An automatically guided vehicle, traveling without fixed guide ways, has been developed. In this paper, the construction of the vehicle, the control algorithm, and its general performance are described.

This paper describes a control system for an autonomous robot cart designed to operate in well-structured environments such as offices and factories. The onboard navigation system comprises a reference-state generator, an error-feedback controller, plus cart location sensing using odometry. There is a convenient separation between the path guidance and control logic. Under normal operating conditions, the controller ensures that the errors between the measured and reference states are small. These errors only exceed set limits if the cart is malfunctioning. Major hardware failures can be detected in this way and failsafe procedures invoked. Results on the control system performance derived from a computer simulation of the cart and its operating environment, and from an experimental cart, indicate that it can provide reliable, accurate, and safe operation of autonomous robot carts.

Symmetry can simplify the control of dynamic legged systems. In this paper, the symmetries studied describe motion of the body and legs in terms of even and odd functions of time. A single set of equations describes symmetric running for systems with any number of legs and for a wide range of gaits. Techniques based on symmetry have been used in laboratory experiments to control machines that run on one, two, and four legs. In addition to simplifying the control of legged machines, symmetry may help us to understand legged locomotion in animals. Data from a cat trotting and galloping on a treadmill and from a human running on a track conform reasonably well to the predicted symmetries.

Two cost functions of paths for smoothness are defined; Path curvature and the derivative of path curvature. Through these definitions, two classes of simple paths are obtained; the set of circular arcs and the set of cubic spirals. A cubic spiral is a curve whose tangent direction is described by a cubic function of path distance s. These sets of simple paths are used for solving path planning problems of symmetric posture (position and orientation) pairs. For a non-symmetric posture pair, we use two simple paths as a solution. In order to find those paths, we use the fact that the locus of split postures is a circle or a straight line. A posture q is said to be a split posture of a pair (p₁,p₂) of postures, if p₁ and q are symmetric and so are q and p₂. The resultant solutions are smoother than those obtained by one of the authors using clothoid curves. This algorithm has been successfully implemented on the autonomous mobile robot Yamabico-11 at UCSB.

We maintain that the key to intelligent fusion of disparate sensory information is to provide an effective model of sensor capabilities. A sensor model is an abstraction of the actual sensing process. It describes the information a sensor is able to provide, how this information is limited by the environment, how it can be enhanced by information obtained from other sensors, and how it may be improved by active use of the physical sensing device. The importance of having a model of sensor performance is that capabilities can be estimated a priori and, thus, sensor strategies developed in line with information requirements.

A motion controller for the autonomous mobile vehicle commands the robot’s drive mechanism to keep the robot near its desired path at all times. In order for the controller to behave properly, the controller must know the robot’s position at any given time. The controller uses the information provided by the optical encoders attached to the wheels to determine vehicle position. This paper analyzes the effect of measurement errors, wheel slippage, and noise on the accuracy of the estimated vehicle position obtained in this manner. Specifically, the location estimator and its uncertainty covariance matrix are derived.

Inertial Navigation Systems have found universal application both militarily and commercially. They are self-contained, nonradiating, nonjammable, and sufficiently accurate to meet the requirements of users in a most satisfactory manner. An overview of inertial navigation is provided, followed by several sections detailing a specific, but different mechanization approach. A Ring Laser Gyro (RLG) based navigation system design is reviewed with special emphasis directed at requirements for navigation accuracy and alignment time. Along with discussions of the RLG unit, an introduction to a novel accelerometer approach, the Vibration Beam Accelerometer (VBA), is provided. A gimballed, self-contained High Accuracy Inertial Navigation System, denoted HAINS, represents one approach toward achieving navigation capability of 0.2 nmi / h and an rms velocity of 1.5 ft / s per axis while retaining the form and fit and affordability of standard inertial tactical flight navigators. The Stellar-Inertial Navigation section illustrates the bounding of position and verticality errors thus achieving exceptional accuracies. Two gyroscopic approaches, presently in development are finally discussed, The Fiber Optic Gyroscope (FOG) and Magnetic Resonance Gyroscopes (MRG’s) are of interest for navigation because of their potential for low cost and excellent reliability.

Despite the advantage of high average power output, traditional continuous transmission FM (CTFM) sonars suffer from two major defects: separate transmit and receive transducers are required, and the demodulated signal is unavailable for a proportion of the sweep period. The paper shows how, by using a dual-demodulation system, the demodulated signal can be made continuous, resulting in the complete elimination of the blind time and in a range resolution as good as two wavelengths of the mean frequency. Experimental results using a CTFM air sonar justify both these claims.

A simple, low cost, infra-red rangefinder has been developed for investigation of autonomous robot cart navigation in factories and similar environments. A 2mW 0.82μ LED source (not a laser) is 100% amplitude modulated at 5MHz and used to form a collimated 1″ diameter transmit beam that is unconditionally eye-safe. Returning scattered radiation is focussed by a 4″ diameter coaxial Fresnel lens onto a p-i-n silicon photodiode. Range is determined from the phase shift between the 5MHz modulation on the transmitted and received signals. Use of a rotating mirror provides 360° polar coordinate coverage of both distance and reflectance out to ∿20 ft. around the vehicle. Both radial and angular resolution correspond to ∿1 inch at a ranging distance of 5 ft., with an overall bandwidth of ∿lKHz. The ranging resolution at 20 ft. is ∿2.5 inches, which is close to the theoretical limit possible for the radiated power, bandwidth, optics and receiver employed. The system is capable of reading wall bar codes “on the fly” and is in addition capable of simultaneously ranging and acting as a wideband optical communication receiver. Total parts cost for the optical transmitter, Fresnel lens, receiver and all the electronics is <$200. The remaining major parts, consisting of the rotating mirror, ring mounting, motor and incremental encoder, cost <$500.

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.

A derivation of the principal algorithms and an analysis of the performance of the two most important passive location systems for stationary transmitters, hyperbolic location systems and direction- finding location systems, are presented. The concentration ellipse, the circular error probability, and the geometric dilution of precision are defined and related to the location-system and received-signal characteristics. Doppler and other passive location systems are briefly discussed.

In this paper, we describe a representation for spatial information, called the stochastic map, and associated procedures for building it, reading information from it, and revising it incrementally as new information is obtained. The map contains the estimates of relationships among objects in the map, and their uncertainties, given all the available information. The procedures provide a general solution to the problem of estimating uncertain relative spatial relationships. The estimates are probabilistic in nature, an advance over the previous, very conservative, worst-case approaches to the problem. Finally, the procedures are developed in the context of state-estimation and filtering theory, which provides a solid basis for numerous extensions.

Before we delve into the details of the text, it would be useful to see where we are going on a conceptual basis. Therefore, the rest of this chapter will provide an overview of the optimal linear estimator, the Kalman filter. This will be conducted at a very elementary level but will provide insights into the underlying concepts. As we progress through this overview, contemplate the ideas being presented: try to conceive of graphic images to portray the concepts involved (such as time propagation of density functions), and to generate a logical structure for the component pieces that are brought together to solve the estimation problem. If this basic conceptual framework makes sense to you, then you will better understand the need for the details to be developed later in the text. Should the idea of where we are going ever become blurred by the development of detail, refer back to this overview to regain sight of the overall objectives.

In this paper we describe our current ideas related to the problem of building and updating 3-D representation of the environment of a mobile robot that uses passive Vision as its main sensory modality. Our basic tenet is that we want to represent both geometry and uncertainty. We first motivate our approach by defining the problems we are trying to solve and give some simple didactic examples. We then present the tool that we think is extremely well-adapted to solving most of these problems: the extended Kalman filter (EKF). We discuss the notions of minimal geometric representations for 3-D lines, planes, and rigid motions. We show how the EKF and the representations can be combined to provide solutions for some of the problems listed at the beginning of the paper, and give a number of experimental results on real data.

This paper describes the position estimation system for an autonomous robot vehicle called Blanche, which is designed for use in structured office or factory environments. Blanche is intended to be low cost, depending on only two sensors, an optical rangefinder and odometry. Briefly, the position estimation system consists of odometry supplemented with a fast, robust matching algorithm which determines the congruence between the range data and a 2D map of its environment. This is used to correct any errors existing in the odometry estimate. The integration of odometry with fast, robust matching allows for accurate estimates of the robot’s position and accurate estimates of the robot’s position allow for fast, robust matching. That is, the system is self sustaining.

A sonar-based mapping and navigation system developed for an autonomous mobile robot operating in unknown and unstructured environments is described. The system uses sonar range data to build a multileveled description of the robot’s surroundings. Sonar readings are interpreted using probability profiles to determine empty and occupied areas. Range measurements from multiple points of view are integrated into a sensor-level sonar map, using a robust method that combines the sensor information in such a way as to cope with uncertainties and errors in the data. The resulting two-dimensional maps are used for path planning and navigation. From these sonar maps, multiple representations are developed for various kinds of problem-solving activities. Several dimensions of representation are defined: the abstraction axis, the geographical axis, and the resolution axis. The sonar mapping procedures have been implemented as part of an autonomous mobile robot navigation system called Dolphin. The major modules of this system are described and related to the various mapping representations used. Results from actual runs are presented, and further research is mentioned. The system is also situated within the wider context of developing an advanced software architecture for autonomous mobile robots.

CD ROM is an ideal storage medium for digital maps. Data volumes are very large, and random access is required for many applications. Etak has developed a digital map database which is used in conjunction with a vehicle navigation system. This database can be licensed for use in other applications. With CD ROM storage, the variety and depth of such applications is expected to expand dramatically.

This paper presents algorithms for computing constraints on the position of an object due to the presence of other objects. This problem arises in applications that require choosing how to arrange or how to move objects without collisions. The approach presented here is based on characterizing the position and orientation of an object as a single point in a configuration space, in which each coordinate represents a degree of freedom in the position or orientation of the object. The configurations forbidden to this object, due to the presence of other objects, can then be characterized as regions in the configuration space, called configuration space obstacles. The paper presents algorithms for computing these configuration space obstacles when the objects are polygons or polyhedra.

We are interested in Voronoi diagrams as a tool in robot path planning, where the search for a path in an r-dimensional space may be simplified to a search on an (r-1)-dimensional Voronoi diagram. We define a Voronoi diagram V based on a measure of distance which is not a true metric. This formulation has lower algebraic complexity than the usual definition, which is a considerable advantage in motion-planning problems with many degrees of freedom. In its simplest form, the measure of distance between a point and a polytope is the maximum of the distances of the point from the half-spaces which pass through faces of the polytope. More generally, the measure is defined in configuration spaces which represent rotation. The Voronoi diagram defined using this distance measure is no longer a strong deformation retract of free space, but it has the following useful property: any path through free space which starts and ends on the diagram can be continuously deformed so that it lies entirely on the diagram. Thus it is still complete for motion planning, but it has lower algebraic complexity than a diagram based on the Euclidean metric.

Free space is represented as a union of (possibly overlapping) generalized cones. An algorithm is presented which efficiently finds good collision-free paths for convex polygonal bodies through space littered with obstacle polygons. The paths are good in the sense that the distance of closest approach to an obstacle over the path is usually far from minimal over the class of topologically equivalent collision-free paths. The algorithm is based on characterizing the volume swept by a body as it is translated and rotated as a generalized cone, and determining under what conditions one generalized cone is a subset of another.

We study the computational complexity of the art gallery problem originally posed by Klee, and its variations. Specifically, the problem of determining the minimum number of vertex guards that can see an n-wall simply connected art gallery is shown to be NP-hard. The proof can be modified to show that the problems of determining the minimum number of edge guards and the minimum number of point guards in a simply connected polygonal region are also NP-hard. As a byproduct, the problem of decomposing a simple polygon into a minimum number of star-shaped polygons such that their union is the original polygon is also shown to be NP-hard.

The need for intelligent interaction of a robot with its environment frequently requires sensing of the environment. Further, the need for rapid execution requires that the interaction between sensing and action take place using as little sensory data as possible, while still being reliable. Previous work has developed a technique for rapidly determining the feasible poses of an object from sparse, noisy, occluded sensory data. Techniques for acquiring position and surface orientation data about points on the surfaces of objects are examined with the intent of selecting sensory points that will force a unique interpretation of the pose of the object with as few data points as possible. Under some simple assumptions about the sensing geometry, we derive a technique for predicting optimal sensing positions. The technique has been implemented and tested. To fully specify the algorithm, estimates of the error in estimating the position and orientation of the object are needed. Analytic expressions for such errors in the case of one particular approach to object recognition are derived.

We investigate the complexity of determining the shape and presentation (i.e. position with orientation) of convex polytopes in multi-dimensional Euclidean space using a variety of probe models.

We present an automatic system for planning the (translational and rotational) collision-free motion of a convex polygonal body B in two-dimensional space bounded by a collection of polygonal obstacles. The system consists of a (combinatorial, non-heuristic) motion planning algorithm, based on sophisticated algorithmic and combinatorial techniques in computational geometry, and is implemented on a Cartesian robot system equipped with a 2-D vision system. Our algorithm runs in the worst-case in time O(kn λ₆(kn) log kn), where k is the number of sides of B, n is the total number of obstacle edges, and λ₆(r) is the (nearly-linear) maximum length of an (r,6) Davenport Schinzel sequence. Our implemented system provides an “intelligent” robot that, using its attached vision system, can acquire a geometric description of the robot and its polygonal environment, and then, given a high-level motion command from the user, can plan a collision-free path (if one exists), and then go ahead and execute that motion.

The problem of path planning for an automaton moving in a two-dimensional scene filled with unknown obstacles is considered. The automaton is presented as a point; obstacles can be of an arbitrary shape, with continuous boundaries and of finite size; no restriction on the size of the scene is imposed. The information available to the automaton is limited to its own current coordinates and those of the target position. Also, when the automaton hits an obstacle, this fact is detected by the automaton’s “tactile sensor.” This information is shown to be sufficient for reaching the target or concluding in finite time that the target cannot be reached. A worst-case lower bound on the length of paths generated by any algorithm operating within the framework of the accepted model is developed; the bound is expressed in terms of the perimeters of the obstacles met by the automaton in the scene. Algorithms that guarantee reaching the target (if the target is reachable), and tests for target reachability are presented. The efficiency of the algorithms is studied, and worst-case upper bounds on the length of generated paths are produced.

The use of autonomous vehicles for moving materials between workstations is an important consideration in the overall design of a flexible automated factory. An algorithm for computing a collision-free motion for a vehicle with limited steering range is presented and its running time is analyzed. When given m “lanes” on which the vehicle is allowed to move in a polygonal environment of complexity n the algorithm produces a motion with the minimum number of turns between two query placements of the vehicle in time O(m2) after O(m2(n2 + logm)) preprocessing. A restricted version of the algorithm has been implemented.

This paper presents a unique real-time obstacle avoidance approach for manipulators and mobile robots based on the artificial potential field concept. Collision avoidance, traditionally considered a high level planning problem, can be effectively distributed between different levels of control, allowing real-time robot operations in a complex environment. This method has been extended to moving obstacles by using a time-varying artificial potential field. We have applied this obstacle avoidance scheme to robot arm mechanisms and have used a new approach to the general problem of real-time manipulator control. We reformulated the manipulator control problem as direct control of manipulator motion in operational space—the space in which the task is originally described—rather than as control of the task’s corresponding joint space motion obtained only after geometric and kinematic transformation. Outside the obstacles’ regions of influence, we caused the end effector to move in a straight line with an upper speed limit. The artificial potential field approach has been extended to collision avoidance for all manipulator links. In addition, a joint space artificial potential field is used to satisfy the manipulator internal joint constraints. This method has been implemented in the COSMOS system for a PUMA 560 robot. Real-time collision avoidance demonstrations on moving obstacles have been performed by using visual sensing.

The Stanford Cart was a remotely controlled TV-equipped mobile robot. A computer program was written which drove the Cart through cluttered spaces, gaining its knowledge of the world entirely from images broadcast by an on-board TV system. The CMU Rover is a more capable, and nearly operational, robot being built to develop and extend the Stanford work and to explore new directions.The Cart used several kinds of stereopsis to locate objects around it in three dimensions and to deduce its own motion. It planned an obstacle-avoiding path to a desired destination on the basis of a model built with this information. The plan changed as the Cart perceived new obstacles on its journey.The system was reliable for short runs, but slow. The Cart moved 1 m every 10 to 15 min, in lurches. After rolling a meter it stopped, took some pictures, and thought about them for a long time. Then it planned a new path, executed a little of it, and paused again. It successfully drove the Cart through several 20-m courses (each taking about 5 h) complex enough to necessitate three or four avoiding swerves; it failed in other trials in revealing ways.The Rover system has been designed with maximum mechanical and control system flexibility to support a wide range of research in perception and control. It features an omnidirectional steering system, a dozen on-board processors for essential real-time tasks, and a large remote computer to be helped by a high-speed digitizing/data playback unit and a high-performance array processor. Distributed high-level control software similar in organization to the Hearsay II speech-understanding system and the beginnings of a vision library are being readied.By analogy with the evolution of natural intelligence, we believe that incrementally solving the control and perception problems of an autonomous mobile mechanism is one of the best ways of arriving at general artificial intelligence.

Research on mobile robots began in the late sixties with the Stanford Research Institute’s pioneering work. Two versions of SHAKEY, an autonomous mobile robot, were built in 1968 and 1971. The main purpose of this project was “to study processes for the realtime control of a robot system that interacts with a complex environment” 〈NIL 69〉. Indeed, mobile robots were and still are a very convenient and powerful support for research on artificial intelligence oriented robotics. They possess the capacity to provide a variety of problems at different levels of generality and difficulty in a large domain including perception, decision making, communication, etc., which all have to be considered within the scope of the specific constraints of robotics: on-line computing, cost considerations, operating ability, and reliability.

Some technical issues concerning a Mars rover launched in the 1990’s are discussed. Two particular modes of controlling the travelling of the vehicle are described. In one mode, most of the control is from Earth, by human operators viewing stereo pictures sent from the rover and designating short routes to follow. In the other mode, computer vision is used in order to make the rover more autonomous, but reliability is aided by the use of orbital imagery and approximate long routes sent from Earth. In the latter case, it is concluded that average travel rates of around 10 km/day are feasible.

A mobile robot architecture must include sensing, planning, and locomotion which are tied together by a model or map of the world based on sensor information, a priori knowledge and generic models. The architecture of a Stanford’s autonomous mobile robot is described including its distributed computing system, locomotion, and sensing. Additionally, some of the issues in the representation of a world model are explored. Sensor models are used to update the world model in a uniform manner, and uncertainty reduction is discussed