Autonomous vehicle navigation system and method

[0002] The invention pertains to a self-contained navigation system that can be used by self-propelled, fully automatic vehicles. As such, it is not intended as a complete solution but as a critical component of a larger system. The disclosed invention allows automated machines to do such simple, repetitive tasks as lawn mowing, snow removal, excavation, surveying, sentry duty and mine sweeping. The vehicle must be trained to execute the intended task, but can operate unattended thereafter.

[0003] Autonomous mobile devices have been fashioned with a variety of techniques. All must solve the problem of traversing a terrain efficiently and accurately.

[0004] Many devices are specifically adapted for highly conditioned environments, e.g. building corridors, and assume, say, that the device is moving on a flat level surface, that the work area is bounded walls, or other such cues. Devising autonomous vehicles that work outdoors in a natural environment is more challenging.

[0005] Several categories of autonomous vehicles rely on conditioning the environment in the target area of the device with navigational cues.

[0006] An early outdoors model (U.S. Pat. No. 4,133,404, Griffin, 1979) is an autonomous lawn mowing device which utilizes optical sensors to detect the cut/uncut lawn boundary, and uses this boundary as a navigation tool. Beyond the obvious limitation that the cut/uncut boundary must be well defined, this device requires that the boundary of the lawn to be cut manually previous to each use. A refinement of this method (U.S. Pat. No. 5,007,234, Shurman, 1991) which, however, has the same limitations, is to detect the cut/uncut boarder via the resistance of the lawn to cutting (motor speed). There is also a slow-moving solar-powered version (U.S. Pat. No. 5,444,965, Colens, 1995) which requires the mower to be continuously present in the yard to be mowed. These devices are application specific, in other words, the navigational cue is derived from the purpose of the vehicle.

[0007] A more general-purpose method of environment conditioned guidance (U.S. Pat. No. 4,777,785, Rafaels, 1988) depends on having a fixed array of transmitters or beacons pre-positioned in the target area. The number of required transmitters was reduced to three (U.S. Pat. No. 5,974,347, Nelson, 1999) in a version in which the vehicle followed a programmed path of position points. Maintenance of the system is a problem whether the transmitters are left in place between device operations, or are reinstalled prior to each use.

[0008] Another common method of environment conditioned guidance is (U.S. Pat. No. 5,163,273, Wojtkowski, 1992) to have the vehicle follow a buried wire. This method entails a large capital cost and yields little flexibility. A version (U.S. Pat. No. 4919,224) with only a guide wire around the boundary of the operational area has less installation cost, but at the expense of efficiency of traversal. Buried metal objects have also been used by Noonan et al. (U.S. Pat. No. 4919,224) as positioning and turn guides.

[0009] All these methods involve installation of permanent structures. In general, if the environment is not to be conditioned, then devising an autonomous vehicle that functions outdoors in a natural environment represents another level of complexity, since the area of operation is fundamentally three dimensional. Specifically, the motion space of the vehicle is two dimensional, being confined by gravity to the earth's surface, while the navigation space is three dimensional, with an additional two dimensional orientation space.

[0010] A device which depends only on the motion space is possible, but prone to error. Chen (U.S. Pat. No. 4,694,639, 1987) offers a simple autonomous lawn mower with no external apparatus and no sensors. The mower follows a learning track made on paper tape. Since no provision is made for error correction, this version requires exact propositioning and even then would be restricted to a very small area of operation.

[0011] The autonomous vehicle in a non-conditioned environment must have the ability to

[0012] 1. determine its current position

[0013] 2. determine its desired position

[0014] 3. determine how to move during the next movement segment to effect the desired change.

[0015] Several modern systems, for instance Gudat et al. (U.S. Pat. No. 5,838,562, 1998), use a Global Positioning System for navigation. However, even the best Global Positioning System is only accurate to about 5 meters. Good enough to know where you are to within a city block, but not good enough to avoid obstacles or repeat a path with any accuracy.

[0016] Another expensive and complicated solution is to use computer vision, for example (U.S. Pat. No. 5,155,684 Burke, 1992). Vision based systems have trouble with atmospheric conditions. What might appear as a sharp point of light on a cold night is a fuzzy patch of light on a hazy summer afternoon. The haze caused by humidity can make resolving landmarks with any accuracy very difficult.

[0017] The invention uses three onboard sensor groups for navigation. The first of these sensors measures the distance traveled by the vehicle along its forward axis. The second and third sensor groups detect the earth's magnetic and gravitational fields. Because the orientation sensors make use of naturally occurring phenomena, this invention does not require externally placed emitters or buried objects, or environmental conditioning of any kind. The invention is also an improvement on vision based systems because the relatively rugged and inexpensive sensor configuration is sufficient for training and normal operation of the vehicle. Once the sensor information is collected, the on-board computer needs only a few simple, linear mathematical operations to know the vehicle's precise location in three dimensions at all times. Training the vehicle is no more difficult than mowing a lawn. The invention is more flexible than designs that use artificial landmarks and is considerably less complicated and more reliable than vision based systems.

[0018] The invention is a means of navigation that allows a vehicle to autonomously repeat the path taught to it. The essential components are: a set of three sensors, a computer and a drive system. The vehicle must be trained to recognize the target path by an operator. After being trained, the vehicle can autonomously direct itself over the same path.

[0019] Mechanically, the invention has two independent driving wheels that are controlled by the computer. For balance and distance measurement, at least one non-driving wheel is needed. This wheel is attached to the chassis with a caster to give it two planes of freedom. The measurement of the rotation of this passive wheel is the basis for an exact measurement of the distance traveled by the vehicle. The driving wheels are subject to slipping and can't be use for this purpose. The exact configuration of wheels is unimportant as long as the platform is stable and the vehicle can turn effectively. The independent driving wheels effect forward, backward and rotational locomotion. The passive wheel has a set of two optical shaft encoders attached to it. An absolute shaft encoder measures the angle of the axis of the passive wheel with respect to the chassis. An incremental shaft encoder is mounted on the chassis and connected to the non-driving wheel's axis using a flexible shaft. An exact measurement of the distance traveled by the vehicle with respect to the ground is made by knowing the angle of the caster and the rotation of this wheel.

[0020] A three axis magnetometer measures the direction and magnitude of the Earth's magnetic field. That is, three magnetometers are positioned at orthogonal angles to provide a three dimensional vector that gives the direction of the naturally occurring field. It's not necessary that the sensors give the exactly direction to the magnetic North Pole. The important requirement is that the directional vector is constant and repeatable with respect to the Earth. This obviates the need for any special calibration.

[0021] A three axis accelerometer measures the direction and magnitude of the force of gravity. It is constructed from a set of three accelerometers positioned at orthogonal angles. Like the magnetometers, the important aspect of this sensor is that it gives a repeatable vector that is constant with respect to Earth. An unwanted side-effect of accelerometers for this application is that they also measure any inertial change in the vehicle. However, using the information from the optical shaft encoders attached to the vehicle's wheels, the effects of inertial changes can be cancelled from the sensor yielding a constant gravitational vector.

[0022] The autonomous vehicle is trained by an operator who directs the motion either by actuators mounted directly on the device or by using a remote control. This can be over any arbitrary terrain. For the algorithm to work, the vehicle must have a common starting point for both training and unattended operation. This marker can be as simple as a visual indicator on the ground or an iron bar buried in the ground that the vehicle detects with the magnetometers. During the training pass, the vehicle collects the sensory information at regular sampling intervals and stores this data in a sensor log. The sensor log contains: the distance traveled since the last sample, the three components of the magnetic vector and the three components of the gravitational vector. This stored information is sufficient to construct a three dimensional map of the subject terrain using relatively simple linear math formulas.

[0023] During unattended operation of the vehicle, the same formulas are used with the current sensor data to calculate the current location. The difference between the internal map and the current location generates an error signal. This signal is used to direct the proportion and direction of the power delivered to the driving wheels, keeping the vehicle on the predetermined path.

[0024] FIG. 1 is a block diagram that shows the major system components of the invention and the flow of information starting with the sensors and ending in a velocity signal to the motor drives.

[0025] FIG. 2 is a drawing that demonstrates the minimum mechanical requirements of the invention. This drawing is represents one possible configuration of a system using the disclosed invention. Others are possible if they meet the minimum requirements.

[0026] FIG. 3A is a side view of an embodiment of a passive wheel encoder design for the invention used to sense the distance traveled.

[0027] FIG. 3B shows more detail of the passive wheel encoder of FIG. 3A from the front.

[0028] FIG. 4 shows the robot coordinate system of the invention and how it relates to the world coordinate system.

[0029] FIG. 5 depicts a vehicle using the invention and its basis set (coordinate system) and how the magnetic field and gravitational vectors appear to the vehicle.

[0030] FIG. 6 shows how the magnetic field generated by the North Pole is projected onto and is measured by the sensors of the invention.

[0031] FIG. 7 shows how the gravitational field is projected onto and is measured by the sensors of the invention.

[0032] FIG. 8 shows graphically how the components of the Basis Change Matrix used in the invention are derived.

[0033] FIG. 9 is a depiction of a virtual terrain used to generate the sensor log for the invention.

[0034] FIG. 10 is a reconstructed wire-frame representation of the virtual field stored in the sensor log for the invention.

[0035] FIG. 2 demonstrates the essential mechanical components of the vehicle. The chassis 13 provides the platform on which the driving wheels 12, the motors 10, the passive wheel 9, the computer and sensors 6, the power source 11 and the passive wheel's encoders 7 are mounted. Flexible shaft 8 allows the rotation of the passive wheel to turn an encoder mounted on the chassis.

[0036] The distance traveled by the vehicle can be measured any number of ways. One solution is demonstrated figures FIG. 3A and FIG. 3B. In this design, a flexible steel tube 14 is attached to the axle of a wheel 15 which is attached to the chassis 1 using a caster 2 mount. As the wheel turns, the flexible steel tube 14 turns an incremental shaft encoder 4 mounted above the gear assembly 3. The incremental shaft encoder 4 keeps a highly accurate measurement of the rotation of the wheel 15. Since the wheel can swivel on the caster 2, its rotation doesn't always translate into forward motion of the vehicle. In order to use the information in from the incremental shaft encoder 4, the angle of the wheel with respect to the vehicle body must be known. Sensing this requires an absolute shaft encoder 6 attached using a gear assembly 3 mounted on the caster 2. The value from the absolute shaft encoder 5 is proportional to the angle that the wheel 15 makes with respect to the chassis 1. This value can be multiplied by a constant, k, to yield the angle in radians. If the distance traveled by the wheel is Δx, and the angle of the wheel is Φ, then the distance, Δd, traveled by the chassis along the forward axis is:

[0037] Δd=Δx×cos(k×Φ).

[0038] In the following discussion, a coordinate system is an ordered triple of three linearly independent vectors, called basis vectors. In FIG. 4 we see the two coordinate systems which are relevant to the invention. The world coordinate system (FIG. 4A), consists of three unit vectors, N 22, E 20 and G 21, nominally indicating North, East, and the direction of the Earth's center, respectively. The second coordinate system (FIG. 4B), is the vehicle coordinate system, also consisting of three vectors. The unit vector, F 18, points in the forward direction of the chassis 19. The unit vector, R 16, points to the right of vector F 18 and unit vector, D 17, points straight down from the chassis 19. The world coordinate system is fixed, while the vehicle coordinate system changes from moment to moment as the vehicle travels through the world. Mathematically, the most important concept behind this invention is its ability to relate the subjective vehicle coordinate system to an objective world coordinate system. Two non-collinear vectors—which are fixed with respect to the world coordinate system—are needed for this translation.

[0039] The first vector is provided by the Earth's magnetic field, which has a direction and magnitude. The second is the Earth's gravitational field which also has a direction and magnitude. Both fields are easily measured by conventional transducers. FIG. 5 shows how the earth's magnetic and gravitational field vectors, C 23 and G 24 respectively, are seen in the context of the vehicle. All input vectors are normalized when they are read from the sensors so the magnitude of the vector is irrelevant to navigation; only the direction is important. A limitation that is worth noting as an illustration is that the invention will not work at the North or South Poles where the magnetic and gravitational fields are collinear.

[0040] Three magnetometers are mounted at right angles to each other to measure the scalar components of the magnetic field on the vehicle's coordinate system. Each of the sensors measures the projection of the field along the axis on which it is mounted. FIG. 6 shows how the magnetic vector 23 is decomposed into a forward vector 27, a right vector 26 and a downward vector 25 by the sensors.

[0041] The gravitational field is measured the same way by a different set of sensors. FIG. 7 shows how the forward 30, right 28 and downward 29 components of the gravitational vector 24 are measured by the vehicle. These sensors will also measure the inertial changes in the vehicle. The optical shaft encoders 4, 5 on the passive rear wheel 15 can accurately measure the change in acceleration of the vehicle. These inertial forces can be subtracted from the gravitational forces yielding a constant vector to the center of the Earth.

[0042] The translation from the sensor information on the vehicle to an absolute world values is accomplished by constructing a Basis Change Matrix. Conceptually, this matrix is a World Coordinate System described in terms of the Vehicle Coordinate System. The first step is to select a world vector as the starting point. FIG. 8 shows how a vector, CN 32, that points to magnetic north and is at a right angle to the gravitational vector is found using The Gram-Schmidt Process:

[0043] CN=C−(C·G)G.

[0044] This vector is converted to a unit vector N 31 pointing north: $N=\frac{\mathrm{CN}}{\sqrt{\left(\mathrm{CN}·\mathrm{CN}\right)}}.$

[0045] The third matrix component needed to describe the world coordinate system is a simple cross-product of the gravity and north vectors:

[0046] E=G×N.

[0047] This vector points, nominally, in the eastern direction and is orthogonal to both the gravity and north 31 vectors. The basis change matrix is formed easily from these values: $M=\left[\begin{array}{ccc}[& N& ]\\ [& E& ]\\ [& G& ]\end{array}\right]=\left[\left[\begin{array}{c}\\ F\\ \end{array}\right]\left[\begin{array}{c}\\ R\\ \end{array}\right]\left[\begin{array}{c}\\ D\\ \end{array}\right]\right].$

[0048] This matrix is constructed from values retrieved from the vehicle's sensors. It is used to translate the vehicle's forward motion, Δd, into world coordinates. The rows of matrix M represent the vectors of the World Coordinate System in terms of the vehicle's coordinate system. The columns represent each of the vehicles basis vectors: the first column represents the forward axis, the second column is the right axis and the last column is the down axis. To calculate the change in three dimensions, ΔX, of the vehicle's position, multiply the distance traveled along the forward axis, Δd, by the first column of matrix M:

[0049] ΔX=F×Δd.

[0050] For example, suppose the vehicle is traveling to the north-east straight up an incline of 45 degrees, and, for simplicity, that the compass vector points due north. The vehicle will measure the gravity vector, G, as [−0.7, 0.0, 0.7] and the magnetic field vector, C, as [0.5, −0.7, 0.5]. The orthogonal unit vector to the north, N, is computed as [0.5, −0.,7, 0.5]. The eastern facing unit vector, E, is the cross-product of G and N: [0.5, 0.7, 0.5]. For this example, we'd like to know the change in three dimensions after the vehicle has traveled 2 feet. The basis change matrix will be: $M=\left[\begin{array}{ccc}0.5& -0.7& 0.5\\ 0.5& 0.7& 0.5\\ -0.7& 0.0& 0.7\end{array}\right].$

[0051] from which we find F=[0.5, 0.5, −0.7]. Multiplying by the distance traveled, Δd=2 feet, the change in position is calculated to be [1.0, 1.0, −1.4] feet. A more complex test of the formulas is demonstrated in FIG. 9 and FIG. 10. In FIG. 9, a virtual three-dimensional playing field is constructed using a simple mathematical formula. In this virtual world, the sensor values that a real vehicle might register when traveling over the same terrain as shown in Table 1 have been simulated.

[0052] Table 1 above shows the components of the sensor log. The actual values were collected from the virtual sensors as a mathematically modeled vehicle traveled over the field shown in FIG. 9. Finally, FIG. 10 shows a wire-frame reconstruction of the data found in Table 1 when it is integrated using the formulas described above. The sensor values collected in the log are sufficient to map an arbitrary, three-dimensional space. When this stored map is compared against the sensor values at a later time, the difference in three dimensions can be calculated and the vehicle can correct its heading to follow the original path.

[0053] Although specific features of the invention are shown in some drawings and not others, this is for convenience only, as the features may be combined in manners apparent to those skilled in the art without departing from the following claims.

[0054] Other embodiments will occur to those skilled in the art and are within the scope of the claims.