Integrated vehicle positioning and navigation system, apparatus and method

The present invention relates to positioning systems, and more particularly to a positioning system and method for determining the terrestrial position of an autonomous vehicle at or near the surface of the earth.

Various national governments, including the United States of America (USA), are currently developing a terrestrial positioning system, commonly referred to as the Global Positioning System (GPS). In a GPS, a number of satellites are placed in orbit around the planet Earth. The GPS satellites are designed to transmit electromagnetic signals. From these electromagnetic signals, the absolute terrestrial position (position with respect to the center of the earth) can be absolutely determined by any receiver at or near the surface of the earth.

The US government has called their GPS "NAVSTAR". The NAVSTAR GPS is declared operational by the US Government in 1993. In addition, the Government of the Union of Soviet Socialist Republics (USSR) is developing a GPS known as "GLONASS", which is essentially similar to the NAVSTAR GPS.

The NAVSTAR GPS is designed to have four orbiting GPS satellites in each of six separate orbits. A total of 24 GPS satellites will be in orbit at any given time with 21 GPS satellites in operation and three GPS satellites serving as replacements. The three GPS satellite orbits will have mutually perpendicular planes relative to the earth. The GPS satellite orbits will be neither polar or equatorial. In addition, the GPS satellites will run around the Earth once every 12 hours.

Using the NAVSTAR GPS, the relative position of orbiting GPS satellites with respect to any earth receiver can be determined from the electromagnetic signals. The relative position is generally referred to as a "pseudorange". In addition, the relative position of two methods can be calculated.

One method is to measure the propagation time delays between the transmission and reception of the propagating electromagnetic signals. In the NAVSTAR GPS, the electromagnetic signals are continuously encoded with the time at which the signals are sent from the GPS satellites. It is clear that one can record the recording time and subtract the coded transmission time to derive time delays. From the calculated time delays and from knowing the speed at which electromagnetic waves travel through the atmosphere, pseudoranges can be accurately deduced. Pseudoranges calculated using the foregoing method are referred to as "true" pseudoranges in the context of this document.

Another method takes into account satellite position data encoded in the electromagnetic signals emitted by the orbiting satellites. Almanac data relating to the satellite position data of the NAVSTAR GPS is publicly available. Reference to this almanac data with respect to the signals encoded in the electromagnetic signals permits accurate derivation of the pseudoranges. Pseudoranges calculated using the foregoing method are referred to as "estimated" pseudoranges in the context of this document.

However, with reference to the previous method of deriving estimated pseudoranges, it should be noted that the satellite position data on the GPS satellite is updated to that hour only once per hour. As a result, the accuracy of the estimated pseudorange decreases with time after every hour until the next hour when a newly estimated pseudorange is calculated using the updated satellite position data.

Further, while knowing the relative position of at least three of the orbiting GPS satellites, the absolute terrestrial position (ie, length, width, and altitude with respect to the center of the earth) can be calculated by any earthcatcher via simple geometric theories involving triangulation techniques. The accuracy of terrestrial position estimation depends in part on the number of orbiting GPS satellites that are being received or received. The use of more GPS satellites in the computation can increase the accuracy of terrestrial position estimation.

Conventionally, four GPS satellites are sampled to determine each terrestrial position estimate because of errors contributed by circuit clock differences between the earth receiver and the various GPS satellites. Clock differences can be several milliseconds. If the earthmovie's clock were synchronized with that of the GPS satellites, then only three GPS satellites would need to be recorded to accurately detect the earthmoving location.

In NAVSTAR GPS, electromagnetic signals are transmitted continuously from all GPS satellites on a single carrier frequency. However, each of the GPS satellites has a different modulation scheme, allowing discrimination of the signals. In the NAVSTAR GPS, the carrier frequency is modulated using a pseudo random signal which is unique to each GPS satellite. Consequently, the orbiting GPS satellites can be identified on the NAVSTAR GPS as the carrier frequencies are demodulated.

Furthermore, the NAVSTAR GPS provides two modes of operation for modulating the carrier wave using pseudorandom number (PRN) signals. In an operating state referred to as coarse / capture mode (C / A), the PRN signal is a gold code sequence with a clock rate of 1.023 MHz. The gold code sequence is a well-known conventional pseudorandom sequence in the art. A chip is an individual pulse of the pseudo-random code. The chip rate of a pseudorandom code sequence is the rate at which the chips are generated in the sequence. Thus, the chip rate is equal to the code repetition rate divided by the number of terms in the code. Accordingly, with respect to the coarse / seek operation state of the NAVSTAR GPS, there are 1023 chips in each gold code sequence, and the sequence is repeated every millisecond. The use of the 1,023 MHz gold code sequence from four orbiting GPS satellites allows the terrestrial position of a terrestrial receiver to be determined with an approximate accuracy of within 60 to 300 meters.

The second modulation mode in the NAVSTAR GPS is generally referred to as the "precise" or "protected" (P) mode of operation. In the protected operating state, the pseudo-random code has a chip rate of 10.23 MHz. In addition, the protected mode sequences are extremely long so that the sequences do not repeat more than once every 267 days. As a result, the terrestrial position of any terrestrial receiver can be determined within an approximate accuracy of 16 to 30 meters.

However, the sequences are classified under protected operating conditions and are not made publicly available by the United States Government. In other words, the protected operating condition is only for the use of earthcounters authorized by the United States Government.

In order for the earthmoving receivers to distinguish the various C / A signals from the other circulating GPS signals, Earthcopper's usually have a variety of different gold code sources to produce localized gold code sequences. Each locally derived gold code sequence corresponds to each unique gold code sequence of each of the GPS satellites.

The locally derived gold code sequences and the transmitted gold code sequences are cross-correlated with each other over gold code sequence intervals of one millisecond. The phase of the locally derived gold code sequences varies on a chip-by-chip basis and then within a chip until the maximum cross-correlation function is obtained. Since the cross relationship or Cross correlation for two gold code sequences having a length of 1023 bits, about 16 times as large as the cross correlation function of any of the other combinations of gold code sequences, it is relatively easy to lock the locally derived gold code sequence to the same gold code sequence as that of one the GPS satellite has been transmitted.

The gold code sequences of at least four of the GPS satellites in the field of view of an earth receiver are thus separated using a single channel which responds sequentially to each of the locally derived gold code sequences, or alternatively by using parallel channels which simultaneously respond to the different gold code sequences. After four locally derived gold code sequences have been locked in phase with the gold code sequences received from four GPS satellites in the field of view of a terrestrial receiver, the relative position of the terrestrial receiver can be determined to an accuracy of approximately 60 to 300 meters.

The foregoing approximate accuracy of the NAVSTAR GPS is affected by (1) the number of GPS satellites transmitting signals to which the earth receiver effectively responds, (2) the variable amplitudes of the received signals, and (3) the magnitude of the cross correlation peaks between the received signals from the different GPS satellites.

Since multiple PRN or pseudo-random number signals are received simultaneously at the earth receiver, there is a common time interval in which some of the codes may conflict. In other words, the codes cause a deterioration of the arrival time measurements of each received pseudo-random number because of the cross-correlations between received conflicting signals.

The time of arrival measurement for each PRN signal is made by determining the time of a peak amplitude of a cross-correlation between the gold code sequence of the received PRN signal and the locally derived PRN signal. When a locally derived PRN signal is superimposed over a received PRN signal, thereby increasing the average time of its cross-correlation, the average noise contribution decreases. However, because cross-correlation errors between the received PRN signals are periodic, increasing the average time also results in enlargements of both the error signal and the cross-correlation value between the received pseudo-random numbers. Consequently, errors in the arrival time of the PRN signals are not reduced by the cross-correlation.

In addition to the GPS, it is known in the conventional art to use inertial systems in navigation systems to obtain a position estimate of the vehicles. Such an inertial reference unit (IRU) receives specific force measurements from accelerometers in a reference coordinate frame stabilized by gyroscopes or gyroscopes. An inertial reference unit may be of several types, such as lasers, mechanics or fiber optics. In an unsupported navigation system using an inertial reference unit, the specific force (corrected for the effects of Earth's gravity) as measured by an accelerometer is integrated into a mathematical navigation equation to produce the speed and position of the vehicle.

The instrument measurements of the inertial reference unit may be set in a rectangular coordinate frame other than the reference navigation frame, depending on the platform device. The most commonly used reference navigation frame for navigating near the surface of the earth is the local level frame (latitude-longitude-vertical position). Several gimbal platform devices exist in the previous reference navigation frame.

In a gimbal-mounted north-facing local level reference unit, the gyroscopes and accelerometers are mounted on a platform that is rotated to keep the platform level and azimuth north-facing. The platform is the reference level. In contrast, in a gimballed azimuth-traveling local level inertial reference unit, the platform is maintained at the level, but not twisted about the vertical axis.

Furthermore, in a slimmed down or strap-down inertial reference unit, the gyroscopes and accelerometers are mounted directly on the vehicle body. They measure the linear and angular motion of the vehicle relative to the inertial space. The movement is expressed in vehicle coordinates. Therefore, in a strap-down inertial reference unit, it is necessary to first calculate the height of the vehicle to the reference navigation frame. Then the calculated height is used to transform the acceleration measurements into the reference frame. After the acceleration measurement data of a strap-down inertial reference unit in the reference frame has been extrapolated, the solution to the aforementioned navigation equations is identical for both the gimbal-mounted inertial reference unit and the strap-down inertial reference unit.

In the strap-down inertial reference unit, the height calculations required to resolve the acceleration measurements are performed at a high rate. The calculations suffer from numerical errors because of limited computer bit size and throughput availability. These calculation errors depend on the frequency response of the sensor loop, the data rate and the resolution and size of the sensor output at the time of recording.

However, considerable benefits accrue from the use of the strap-down inertial reference unit instead of the gimbal-mounted inertial reference unit. The strap-down inertial reference units are cheaper. In addition, the strap-down inertial reference units are generally smaller in physical size. Thus, the potential for achieving size and cost savings on the inertial reference units may make the strap-down inertial reference units attractive for both military and commercial applications.

The performance of navigation systems using inertial reference units is limited primarily by errors contributed by the various proportionate sensors within the inertial reference units. Gyroscopes show a drift or a deviation. Accelerometers have inherent biases. Other errors are contributed by inaccurate scaling factors and inaccurate inertial reference unit alignment angles. Typically, the previous errors cause inaccuracies in the estimates of vehicle positions, speed, and altitude that accumulate over time as a vehicle mission progresses. To a certain extent, the errors depend on the dynamic actions of the user.

When a very accurate navigation system is required for a vehicle, high-precision gyroscopes and accelerometers can be used to meet this need. However, such high-precision equipment adds to the complexity and cost of the vehicle.

EP-A-0181012 discloses a vehicle position estimation system combining GPS and inertial navigation systems. IEEE Position Location and Navigation Symposium, 4.-7. November 1986 discloses an inertial navigation system in comparison with the GPS.

DE-A-3310111 discloses a navigation system with drift compensation. US-A-3630079 discloses a navigation system using multiple sensors and error correction.

US-A-4786164 discloses a cylindrical scan obstacle detection sensing system.

According to the present invention, a scanning system is provided to detect obstacles in a path of a vehicle, the system being mounted on the vehicle and comprising:

Means for generating an energy beam;

Means for sensing the energy beam over a desired range of angles relative to the vehicle in the cycles; and

Means for detecting reflected energy;

marked by

Means for storing information during each of the sampling cycles associated with the reflected, detected energy; and

Means for calculating the distance over which the reflected detected energy has traveled by processing the associated information stored during each of the sampling cycles; and

Means for generating an energy beam during a portion of the sampling cycle so that only a fraction of the total field of view is scanned, minimizing the total amount of data transmitted.

The present invention also provides a scanning method for detecting obstacles in a path of a vehicle using a scanner mounted on the vehicle, the method comprising the steps of:

Generation of an energy beam;

Guiding the energy beam over a desired range of angles relative to the vehicle in cycles;

Measuring distances between the vehicle and objects in the path of the vehicle, comprising the steps of:

Detecting reflected energy; and

characterized by the following steps:

Storing information associated with the reflected detected energy during each of the sampling cycles;

Calculating the distance over which the reflected detected energy has traveled by processing the associated information stored during each of the sampling cycles; and

Generating an energy beam during a portion of the scan cycle so that only a fraction of the total field of view is scanned, minimizing the total amount of data transmitted.

Other features and advantages of the present invention will become apparent to those skilled in the art upon examination of the following drawings and detailed description.

It is intended that any additional features and advantages be included herein.

The present invention as defined in the claims will be better understood with reference to the text and to the following drawings.

Fig. 1 illustrates a block diagram of the preferred embodiment of the present invention;

Fig. 1A is a block diagram 100A of the operating GPS satellites in the NAVSTAR GPS;

Fig. 2 illustrates four simultaneous navigation equations that consider four GPS satellites of the NAVSTAR GPS;

Fig. 3 is a block diagram of a typical stand-alone work site;

4 is a block diagram of relationships between a navigator, VPS and vehicle controls of the present invention;

Fig. 5 is a block diagram illustrating the elements in an autonomous control system;

Fig. 6 is a block diagram of the operation of a GPS;

Fig. 7 is a block diagram of a GPS processing system of the preferred embodiment;

Fig. 8 is a flowchart of the GPS processing system of Fig. 7;

Fig. 9 is a block diagram of a Motion Positioning System (MPS) including an odometer 902 and an inertial reference unit (IRU) 904;

Fig. 10 is a block diagram of the VPS (Vehicle Positioning System);

Fig. 11 is a block diagram of the VPS architecture of Fig. 10;

Fig. 12 is a diagram of vehicle route definitions;

Fig. 13 is a diagram showing the re-planning of a path;

Fig. 14 is a diagram showing how to calculate an error vector including a curvature;

Fig. 15 is a diagram showing how to calculate an error vector including a curvature including the vehicle path;

Fig. 16 is a context diagram of the navigator of the present invention;

Fig. 17 is a context diagram of a path trace structure;

Figs. 18A-18D are data flow summaries of the navigator 406;

Fig. 19A is an illustration of a vehicle-mounted scanner 404;

Fig. 19B is an illustration of an autonomous vehicle which is related to. an obstacle scans or feels;

Fig. 20 is a diagram of selected scanning lines in a laser scanning system;

Fig. 21 is a diagram of an autonomous vehicle which avoids obstacles;

Fig. 22 is an illustration of an obstacle;

Fig. 23 is a block diagram of a laser scanner system used for obstacle detection;

Fig. 24 is a block diagram 4300 of a control system for an autonomous mining vehicle;

Fig. 25 is a state diagram showing the transitions between the operating states of the control system of Fig. 24;

Fig. 26 is a communication diagram showing the tasks of a navigator.

(1) "Absolute position" in relation to this document refers to a position with respect to the center of the earth. In general, it will be an absolute position relative to a vehicle or base station, both on and near the surface of the earth. First, second and third position estimates are all absolute positions.

(2) "Actual Pseudorange" means an approximation to the distance between (1) a reference point and (2) a source of a terrestrial positioning system. In this document, the actual pseudoranges usually refer to an approximation of the distance between (1) an Earth receiver and (2) GPS satellites and / or pseudolites. Actual pseudoranges are approximated by first measuring the propagation time delays between the transmission and reception of the electromagnetic signals coming out of the GPS satellites and / or pseudolites. Actual pseudoranges can be easily calculated by multiplying the calculated time delays by the speed of light, or by 2.9979245898 x 10 & sup8; m / s.

(3) "Antiselective availability" refers to a method / technique / process for detecting and compensating corrupted GPS data in the coarse / seek (C / A) modulation mode.

(4) "Autonomous" is used in this document in the traditional sense. It indicates the operation, which is either completely automatic or essentially automatic or without significant involvement of a human being in operation. In general, an autonomous vehicle means an unmanned vehicle in service or a vehicle in service without a human driver or passenger. However, an autonomous vehicle may be automatically driven or otherwise operated and may also have one (more) human (human) passenger (s).

(5) "Base correlation derivative" means a spatial derivative derived according to the flowchart 1700A of Fig. 17A.

(6) "Basic correlation derivation technique" means a method / process for calculating the base correlation derivatives.

(7) "Estimated Base Position" or "BEP" refers to the relative position of the base station with respect to a vehicle. The estimated base position is used in the base correlation derivation technique.

(8) "Known base position" or "BKP" is the absolute position of the base station (used as a reference point) which is known. The known base position may itself be an estimate derived from any precise positioning system. It is assumed that the known base position is a more accurate estimate of the base station's absolute position than any other position estimate.

(9) "Base Position Estimate" means the estimation of the absolute position of the base station as derived from the GPS processing system within the host processing system. The base position estimate is substantially similar to the first position estimate derived from the GPS processing system in the vehicle. The base position estimate is calculated in the base residual derivative technique.

(10) "Base residual derivative" means a spatial derivative which is the effective difference of the base station's known base position (BKP) and the base station position estimate calculated by the host processing system.

(11) "Basic residual derivative technique" refers to a method for deriving base residual derivatives.

(12) "bias" refers to a difference between two measurements, usually position estimates (spatial derivatives) or clock rates (clock bias). Since it is known that one measurement is usually more accurate than the other, the derivative is often referred to as an "error".

(13) "clock derivative" means the difference of the clock times between (1) the transmission circuit of the GPS satellites and / or GPS pseudolites and (2) the reception circuit of a terrestrial receiver. Using a clock derivative in the computation of a spatial derivative, the clock derivative is multiplied by the speed of light or 2.988 x 10 $ meters per second. Consequently, the clock derivation is converted to units of length.

(14) "Constellation" refers to a group consisting of GPS satellites and / or pseudolites whose signals are used to derive an absolute position estimate of the point at or near the surface of the earth. See below "optimal constellation".

(15) "Constellation effect method" means a technique or process whereby an optimal constellation of GPS satellites is selected from a larger group of GPS satellites in the field of view of a vehicle.

(16) "Data radio" refers to a transmitter, receiver, transceiver or any combination thereof for the transmission of data at radio frequencies (RF = radio frequencies).

(17) "Earth recipient" refers to any device or device or any part thereof that receives and processes signals from a GPS and / or pseudolite. Earth recipients may be located at or near the surface of the earth. In addition, earthquake recipients may take the form of a vehicle or a base station, for example.

(18) "Estimated Pseudorange" refers to the approximation of the distance between (1) a reference point and (2) a source of a terrestrial positioning system. In this document, the actual pseudoranges usually refer to an approximation of the distance between (1) an Earth receiver and (2) GPS satellites and / or pseudolites. Estimated pseudoranges are calculated from GPS data encoded in the electromagnetic signals transmitted by the GPS satellites and / or the pseudolites. Almanac equations for calculating estimated pseudoranges from the GPS data of the NAVSTAR GPS are publicly available.

(19) "First Position Estimate" or "FPE" or "FPE (i)" refers to an estimated absolute position of any vehicle output in some form from the GPS. The first position estimate and the second position estimate are independently derived in the present invention. Subsequently, these estimates are combined and filtered to derive a third position estimate. Consequently, the accuracy of the first position estimate affects the accuracy of the third position estimate.

(20) "GLONASS-GPS" refers to the GPS which has been constructed by the USSR and is currently used by it.

(21) "Global Positioning System" or "GPS" is a type of terrestrial positioning system. In a GPS, a number of satellites are placed in orbit around the planet Earth. The GPS satellites are designed to transmit electromagnetic signals. From these electromagnetic signals, the absolute terrestrial position (position with respect to the center of the earth) can be ultimately determined by any receiver at or near the earth's surface. The US government has called their GPS "NAVSTAR". The USSR government has called their GPS "GLONASS".

(22) "GPS data" means all data encoded on signals transmitted by GPS satellites of a GPS. For example, GPS data includes ephemeris data and time data.

(23) "GPS processing system" refers to a system for receiving signals from a terrestrial positioning system and for deriving first position estimates of vehicles from the recorded signals. The GPS processing system may receive electromagnetic signals from the GPS satellites of a GPS and / or pseudolites.

(24) "host processing system" refers to a computer system operating at the base station for carrying out methods and techniques that improve the accuracy of the vehicle position estimates. Data derived from these methods and techniques are transmitted to vehicles so that the vehicles can use the data when calculating first, second and third position estimates. The architecture / hardware (components) of the host processing system are substantially similar to the architecture / hardware of the vehicle positioning system.

(25) "Inertial Reference Unit" or "IRU" refers to a system, usually onboard a vehicle, to assist in the derivation of a second position estimate of the vehicle. An inertia reference unit receives specific force measurements from accelerometers in a reference coordinate frame stabilized by gyroscopes or gyroscope means. An inertial reference unit may be of a laser type or of a mechanical type. In an unsupported navigation system using an inertial reference unit, the specific force (corrected for the effects of earth gravity) as measured by the accelerometer is integrated into a mathematical navigation equation to generate the vehicle position and speed. The inertial reference unit may be part of the movement position determination system.

(26) "Kalman filter" is used in the conventional sense. This refers to a software program for filtering out noise or errors in the data. A GPS Kalman filter is used to filter out noise or errors in the GPS processing system to improve the accuracy of the first position estimates. It is also a VPS or Vehicle Positioning Kalman filters are used to filter out the noise in the vehicle position determination system to improve the accuracy of the second position estimates.

(27) "Motion Positioning System" or "MPS" (MPS) means a system having at least one inertia reference unit and a vehicle odometer. The travel position determination system derives the second position estimate from any vehicle at or near the earth's surface. Moreover, a moving position determination system need not be present at the base station because of its stationary nature.

(28) "Optimal constellation" means a satellite constellation in which the relative positions of the GPS satellites in space require superior triangulation capabilities to derive the most accurate estimate of a point on or near the surface of the earth.

(29) "Initial derivative" means a spatial derivative calculated by subtracting both estimated pseudoranges and clock derivatives (in units of length) from the actual pseudoranges. Clock derivatives are converted into units of length by passing them at the speed of light or with 2.9979245898 x 10 & sup8; Meters per second multiplied.

(30) "Original derivation technique" is a method of calculating the original derivatives.

(31) "NAVSTAR-GPS" means the GPS that has been designed by the US Government and is currently used by the US Government.

(32) "Navigation system" refers to any systems and / or methods for guiding a vehicle on or near the surface of the earth. The navigation systems can be on board a vehicle. The vehicle positioning system of the present invention can provide the vehicle's navigation system with a very accurate third position estimate of the vehicle so that the navigation system can thereby precisely guide the vehicle.

(33) "Parabolic derivative" is a spatial derivative calculated by constructing parabolic models for the actual pseudoranges of each observed GPS satellite and extrapolating values ​​from the parabolic models. The parabolic derivatives are the actual pseudoranges minus the value extrapolated from the constructed parabolic models and minus the clock derivatives (in units of length by multiplying by the speed of light).

(34) "Parabolic Derivative Technique" is a method of calculating parabolic derivatives of each of the GPS satellites that are used.

(35) "Preferred Embodiment" refers to the best way to set up the present invention. The preferred embodiment is only exemplary. The present invention should not be interpreted as being limited to the preferred embodiment.

(36) "Pseudolite" refers to a radiation system or transmission system at or near the surface of the Earth for the emulation of a GPS satellite. Electromagnetic signals, similar to GPS satellites, are transmitted by land-based pseudolites. One or more pseudolites may be used to emulate GPS satellites to improve the calculation of the first position estimates.

(37) "Pseudolite data" means all data encoded in signals picked up by the pseudolites. The pseudolite data is similar in many ways to the GPS data and has similar information.

(38) "Pseudorange" means the distance between a source of a terrestrial positioning system and a point on or near the surface of the earth. The sources may be GPS satellites and / or pseudolites. The terrestrial positioning system may be a GPS used with pseudolites, if any. Furthermore, the point on or near the surface of the earth may be the base station and / or vehicles.

(39) "Satellite position prediction" is a method of determining the future positions of the GPS satellites. The method allows the premature selection of optimal constellations.

(40) "Second Position Estimation" or "SPE" (SPE) refers to an estimated absolute position of any vehicle output in some form by the MPS. The second position estimates have at least one position information from an inertial reference unit. The second position estimate may include position information from a vehicle odometer located on a vehicle.

(41) "Spatial derivative" refers to a derivative that refers to approximations of positions in a two-dimensional or three-dimensional space. Spatial derivatives are used to offset a position estimate to improve the accuracy of the position estimate. Spatial derivatives may be calculated by a number of different methods of the present invention. Included in these methods are, for example, an original derivation technique 1500, a parabolic derivation technique 1600, a base residue derivation technique 1700, and a base correlation derivation technique 1700A.

(42) "System" is used for the purpose of signifying a device, a method or a combination of both a device and a method. In addition, it could include programs, hardware or components or a combination of hardware and programs.

(43) "Positioning system" means any system with sources that emit signals that can be used by a receiver of the signals to estimate the relative distance between the sources and the receiver. The signals may, for example, be in the form of electromagnetic waves, percussion waves and / or sound waves.

(44) "Terrestrial positioning system" means any positioning system that can be used to ultimately estimate the terrestrial position of an Earth receiver. The signals may, for example, be in the form of electromagnetic waves, percussion waves and / or sound waves. In the preferred embodiment, the terrestrial positioning system is the NAVSTAR GPS.

(45) "Third position estimate" or "TPE" (TPE) refers to an estimated absolute position of any vehicle issued in any form by the vehicle positioning system. The third position estimates are more accurate position estimates of the vehicle positions compared to the first and second position estimates. The third position is derived from the first and second position estimates by the VPS processing system.

(46) "Vehicle" means any carrier for transporting physical things. Vehicles may take the form of mining trucks, construction trucks, farm tractors, automobiles, ships, boats, railways, balloons, rockets or airplanes. In the preferred embodiment, a 785 PFF road truck is used by Caterpillar Inc.

(47) "Vehicle Positioning System" or "VPS" (VPS) refers to the system that derives position estimates from any vehicle. The position estimates from the vehicle positioning system are extremely accurate and can be used by a navigation system on any vehicle to accurately guide the vehicle. Position estimates are referred to by the vehicle positioning system as third position estimates.

(48) "VPS processing system" means the processing system of the vehicle positioning system or the VPS. The VPS processing system derives third position estimates from the first and second position estimates. The architecture is shown in FIGS. 10 and 11.

(49) "Weighted combination" refers to a special software program that processes data. The input data is assigned a predetermined weighting factor based on the estimated accuracy of the data and the technique used to collect the data. For example, the first position estimate of the GPS signal 716 is weighted more heavily than the second position estimate of the inertial reference unit signal 910 because the former is inherently more accurate. Furthermore, the speed measured by the inertial reference unit may be weighted more heavily than the speed measured by the GPS processing system because the former is more accurate. The speed measured by the GPS processing system, not used at all, could however be used in other constructions.

(50) "Weighted Path History Technique" is a method or process for increasing the accuracy of the first position estimates output from the GPS processing system. The technique uses earlier first position estimates to derive a vehicle path model to test the validity of the future first position estimates. The application of the weighted path history technique results in a reduction in wandering of the first position estimates and improved immunity to incorrect position calculations.

FIG. 1 illustrates a high-level block diagram 100 of an exemplary position determination system. To provide for the accurate autonomous operation of a vehicle 102 at or near the earth's surface, the example includes both a vehicle positioning system (VPS) 1000 and a navigation system 1022. Both of these systems include apparatus, methods, and techniques that, when integrated together, provide for highly accurate control of unmanned vehicles.

The task of guiding the autonomous vehicle 102 along a prescribed path requires inter alia an accurate estimate of the current vehicle position relative to a reference point. Once the current position is known, the vehicle 102 may be instructed to proceed to its next destination.

Using the VPS 1000, position estimates of the vehicle 102 can be determined with extreme accuracy. The VPS 1000 receives GPS data from GPS satellites 104 from a GPS, such as the NAVSTAR GPS or the GLONASS GPS.

The NAVSTAR GPS can be used. Fig. 1A illustrates the NAVSTAR GPS. GPS satellites 130-168 travel around the earth 172 into six orbitals 174-184.

With reference to FIG. 1, the VPS 1000 may also receive pseudolite data from pseudolite (s) 105. The term "pseudolite" in the context of this document means a radiation emitting device on or near the surface of the earth to emulate a GPS satellite.

From the GPS data and / or the pseudolite data, the VPS 1000 derives accurate estimates of the position of the vehicle 102. The GPS data and / or the pseudolite data is significantly enhanced over numerous inventive techniques and methods to improve the accuracy of the vehicle position estimate.

In particular, the VPS 1000 is a positioning system based on the use of GPS data from the NAVSTAR GPS 104 and a motion positioning system 900. The motion positioning system 900 includes an inertial reference unit (IRU) 904 and or a vehicle odometer 902. The IRU 904 includes one or more laser gyroscopes 106 and one or more accelerometers 108 that may be used to generate position, velocity, roll, altitude, and yaw data. The vehicle odometer 902 generates data about the distance traveled by the vehicle 102.

A first position estimate of the vehicle 102 is derived by the GPS processing system 700 from the GPS data received from the GPS satellites 104 and from the pseudolite data received from the dummy list (s) 105. To increase the accuracy of the first position estimate, a number of methods may be used. In addition, a second position estimate is derived by the MPS communication processor 906 of the travel position system 900 having the IRU 904 and / or the vehicle odometer 902.

As shown by the respective arrows 112 and 114, the first position estimate and the second position estimate are then combined and filtered by a VPS processing system 116. The result, as shown by an output arrow 118, is a more accurate third position estimate.

The navigation system 1022 receives the third position estimate from the VPS 1000. The navigation system 1022 uses the precise third position estimate to accurately navigate the vehicle 102. A primary purpose of the navigation system 1022 is to guide the vehicle 102 between points along a predetermined or dynamically generated path.

The navigation system 1022 is located in the vehicle 102 itself. In other words, it is essentially an "on-board" system. In addition, the navigation system 1022 may be designed to be retrofitted in the vehicle 102.

So that the navigation system 1022 can route the vehicle 102 to follow preset or dynamically generated paths, various models or conceptual representations are created and used. For example, lines and curves may be used to establish vehicle paths between object points. Mathematical B-splines or clothoid curves may be used to model the actual path where the vehicle 102 must navigate.

The use of the above modeling techniques provides for improved data communications, storage and handling of the vehicle 102. The techniques further allow for simplification of monitoring tasks by providing a hierarchy of control and communication. The higher a control level in the hierarchical control scheme, the simpler the task and the more compact the commands.

The navigation system 1022 further provides control of the vehicle's mechanical systems, such as brakes, steering, and engine and transmission, to perform the necessary physical actions required to move, stop, and steer the vehicle 102 ,

The navigation system 1022 also checks the actual position of the vehicle 102 against the desired position to correct the vehicle control according to the desired position. The navigation system 1022 may run multi-state models to improve that verification capability. The navigation system 1022 also checks for errors or failures in the system itself and in vehicle components. If errors or failures are detected or can be determined, the navigation system 1022 can ensure a fail-safe shutdown, or by bringing the vehicle 102 to a complete stop.

The navigation system 1022 further provides various operating conditions for controlling the vehicle 102. These include: (1) a fully autonomous mode where the navigation of the vehicle 102 is automatically handled by the navigation system 1022; (2) a telephoto or remote control mode where a remote human operator (not shown) controls the direction and movement, etc. the vehicle 102 can control; and (3) a manual mode in which a human operator sitting in the vehicle 102 can take control of the vehicle 102 and manually drive it.

In autonomous mode, obstacle detection is critical because if the vehicle 102 is not under control, it could cause large property damage and severe injury to living beings. The navigation system 1022 can efficiently detect obstacles. Stones, animals, humans, trees or other obstacles may unexpectedly enter the path of the vehicle 102. The navigation system 1022 is capable of detecting these obstacles, either by stopping or by drawing a path around the obstacle and returning the vehicle 102 to its original path if the route is considered safe.

Accurate tracking of the desired route is another function of the navigation system 1022. The operation and architecture of the navigation system 1022 has been designed for real-time tracking of the vehicle paths at speed up to about 30 miles per hour (mph).

The example may include a host processing system 186 in a base station 188. The host processing system 186 performs functions for both the VPS 1000 and the navigation system 1022.

With respect to the VPS 1000, the host processing system 186 receives GPS data and / or pseudolite data as shown by respective arrows 190 and 192. In effect, the host processing system 186, as well as the base station 188, may function as a known reference point to improve the accuracy of the vehicle position estimates, as discussed in detail below.

The following discussion with respect to the VPS 1000 will refer in particular to FIGS. 7-10. Figure 10 shows the architecture / hardware of the VPS 1000. The VPS 1000 is a high precision position determination system for a moving or stationary vehicle 102 at or near the surface of the earth.

It is recalled that the VPS 1000 has the GPS processing system 700 and the MPS 900 shown in the respective FIGS. 7 and 9. Further, it should be remembered that the MPS 900 includes the IRU 904 and the vehicle odometer 902, both of which are shown in FIG. In effect, these systems have been improved and integrated to create a highly effective positioning system.

Referring to FIG. 7, the GPS processing system 700 includes an antenna 702 connected to a GPS receiver 706. When the GPS satellites 104 in the field of view of the antenna 702 have multiple GPS satellites 200-206, as shown in FIGS. 2 and 3, the GPS receiver 706 reads all of its GPS data along with any pseudolite data from any (any) Pseudolit (s) 105 in the field of view of the antenna 702. The GPS receiver 706 is responsible for calculating the first position estimate of the vehicle 102 from the GPS data and / or the pseudolite data.

In order to increase the accuracy of the first position determination method, the satellite position prediction method 1800 is implemented by a GPS processor 710 of the GPS processing system 700. The satellite position prediction method 1800 predicts the position of any GPS satellite at the current time or for any future time.

Using the satellite position information, the GPS processing system 700 may determine the optimal GPS satellite constellation for detection using a constellation effect method 1300. The constellation effect method 1300 is also implemented by the GPS processor 710. According to the constellation effect method 1300, a best constellation is selected from the data sources comprising the GPS satellites 200-206 and pseudolit (s) 105.

The GPS processor 710 computes a first position estimate of the vehicle 102 based on the best constellation and on geometry / triangulation methods. The accuracy of the first position estimate depends in part on the number of GPS satellites used in the calculation. Any additional GPS satellite used can increase the accuracy of the first position estimate. After the calculation, the first position estimate of the vehicle 102 is transmitted to a VPS main processor 1002 of FIG.

Referring to FIG. 9, the IRU 904 includes laser gyroscopes and accelerometers that generate position, velocity, roll, pitch, and grade data. The IRU 904 combines this information into a second position estimate of the vehicle 102. The odometer 902 may be implemented to measure the distance traveled by the vehicle 102. The data from the IRU 904 and the odometer 902 are also transmitted via the MPS communications processor 906 to the VPS main processor 1002, as shown in FIG.

The VPS main processor 1002 combines the second position estimate from the MPS 900 (the IRU 904 and perhaps the odometer 902) with the first position estimate from the GPS processing system 700 to produce a more accurate third position estimate.

The VPS 1000 further implements a method for eliminating erroneous or incorrect third position estimates that may cause "vehicle drifting". This method is called weighted path history methods. In essence, the path history of the vehicle 102 is used to statistically determine the accuracy of future estimates of the position of the vehicle 102.

With reference to FIGS. 1 and 3, a base station 188 provides a near geographic reference point for the VPS 1000. The base station 188 includes a host processing system 186. The host processing system 186 has a similar architecture and performs the same functions as the GPS processing system 700. However, the host processing system 186 performs additional functions to increase the accuracy of the first position estimates.

The satellite position prediction method 1800 is implemented by the host processing system 186, in addition to the GPS processing system 700 discussed above. Accordingly, the host processing system 186 will detect the same GPS satellite constellation being observed by the vehicle 102 have the same GPS satellite in a larger constellation.

Calculations are then performed on the GPS data and / or the pseudolite data to derive leads (biases), including spatial derivatives and clock derivatives. To calculate spatial derivatives, the host processing system 186 implements a number of methods.

The GPS processing system 700 uses the vehicle position data from a terrestrial positioning system to derive the first position estimate of the vehicle 102. The terrestrial positioning system includes the NAVSTAR GPS currently being developed by the US government and / or terrestrial pseudolites.

As shown in Figure 1A, 24 hand-made GPS electronic satellites 132-170 are currently provided in six orbits 174-184 for the NAVSTAR GPS. They are planned for use in 1993. As currently anticipated, the GPS satellites 132-170 will orbit the earth 172 at a height of approximately 14,000 miles and orbit the globe twice a day. Using the C mode or C operating state of the NAVSTAR GPS, as will be discussed below, it will be possible to determine terrestrial positions within 15 meters, in any weather, at any time and in most areas of the earth 172.

At the time of submission of this document, six experimental and seven operational GPS satellites in orbit around Earth 172 are known. Further, it is known that several manufacturers are currently designing and manufacturing GPS receivers, such as the GPS receiver 706 of FIG. 7. As more and more GPS satellites are launched or are operational and in use, the time periods in which three or more of the experimental GPS satellites are available each day for position tracking increase.

Moreover, the location of the experimental GPS satellites (and all others once in use) is very predictable. The relative position or "pseudorange" of these GPS satellites with respect to the GPS receiver 706 on the vehicle 102 may be determined by two methods from the electromagnetic signals.

One method is to measure the propagation time delays between transmission and reception of the outgoing electromagnetic signals. In the NAVSTAR GPS, the electromagnetic signals are continuously encoded with the time at which the signals are transmitted from the GPS satellites. It is needless to say that one can make a record of the reception time and subtract the coded transmission time to derive the time delays. From the calculated time delays and from knowing the speed at which the electromagnetic waves travel through the atmosphere, pseudoranges can be accurately deduced. Pseudoranges calculated using the foregoing method will be referred to as "actual" pseudoranges in the context of this document.

Another method involves satellite position data encoded in the electromagnetic signals transmitted by the orbiting GPS satellites. Almanac or directory data related to the GPS satellite position data of the NAVSTAR GPS is publicly available. A reference of this directory data with respect to data encoded in the electromagnetic signals allows an accurate derivation of pseudoranges or Pseudoranges, if the location of the receiver is known. Pseudoranges calculated using the foregoing method will be referred to as "estimated" pseudoranges in the context of this document.

However, it should be noted that with reference to the foregoing method of deriving estimated pseudoranges, the satellite position data is updated with the GPS satellite only once every hour at the full hour. Thus, an estimated pseudorange decreases in accuracy over time, after each hour to the next full hour, where a new estimated pseudorange is calculated using the updated satellite position data.

Referring again to Figure 1A of the drawings, the configuration of the fully operational NAVSTAR GPS is schematically illustrated. Each of the 24 GPS satellites 132-170 transmits electromagnetic signals that may be used to determine the absolute terrestrial position of the vehicle 102 (ie, length, width and altitude with respect to the center of the earth 172).

In particular, by notifying the relative position of at least three of the orbiting GPS satellites 132-170, the absolute terrestrial position of the vehicle 102 may be calculated via a simple geometric theory involving triangulation techniques. The accuracy of the terrestrial position estimate depends, in part, on the number of orbiting GPS satellites 132-170 being sampled by the vehicle 102. Sampling or Receiving more GPS satellites 132-170 in the calculation increases the accuracy of the terrestrial position estimate. Conventionally, four GPS satellites instead of three are sampled to determine each terrestrial position estimate because of errors caused by circuit clock differences between the circuit of the vehicle 102 and the vehicle various GPS satellites 132-170 will be contributed.

In NAVSTAR GPS, electromagnetic signals are transmitted continuously from all GPS satellites 132-170, at a single carrier frequency. However, each of the GPS satellites 132-170 has a different modulation scheme, thereby allowing differentiation of the electromagnetic signals. In the NAVSTAR GPS, the carrier frequency is modulated using a pseudorandom binary code signal (data bit stream), which is unique to each GPS satellite. The pseudo-random binary code signal is used to two-phase modulate the carrier frequency or to carry out a two-phase modulation. Consequently, the orbiting GPS satellites in the NAVSTAR GPS can be identified as the carrier frequencies are demodulated.

Moreover, the NAVSTAR GPS provides two modulation modes of the carrier wave, using a pseudorandom number (PRN). In a mode referred to as a "coarse / acquisition" (C / A) or "coarse / capture" mode, the PRN signal is a gold code sequence with a 1.023 MHz chip rate , The gold code sequence is a well known conventional pseudorandom sequence in the art. A chip is an individual pulse of the pseudo-random code. The chip rate of a pseudorandom code sequence is the rate at which the chips are generated in the sequence. Thus, the chip rate is equal to the code-recovery rate divided by the number of terms in the code. Accordingly, with respect to the coarse / acquisition or Rough / capture mode of the NAVSTAR-GPS 1023 chips in each gold code sequence and the sequence is repeated once every millisecond. The use of the 1.023 MHz gold code sequence from four orbiting GPS satellites allows the terrestrial position of the vehicle 102 to be determined with an approximate accuracy of within 60 to 300 meters.

The second modulation mode in the NAVSTAR GPS is generally referred to as the "precise" or "protected" (P) mode. In P-mode, the pseudorandom code has a chip rate of 10.23 MHz. Moreover, the P-mode sequences are extremely long, so that the sequences do not repeat more than once every 267 days. As a result, the terrestrial position of the vehicle 102 can be determined within an approximate accuracy of 16 to 30 meters.

However, the P-mode sequences are classified and are not publicly available by the United States Government. In other words, the P-mode is only for the use of earth-receivers authorized by the United States Government.

FIG. 2 illustrates navigation equations 212 taking into account four GPS satellites 200-206 of the NAVSTAR GPS. The four GPS satellites 200, 202, 204 and 206 have respective pseudoranges R0, R2, R4 and R6 and have the current constellation of the GPS satellites 132-170 recognized by the vehicle 102.

The navigation equations 212 comprise the clock bias Cb between the GPS satellites 200-206 and the vehicle 102. The navigation equations 212 are used to calculate the length and width of the vehicle 102 using the pseudoranges R0, R2, R4 and R6.

As shown in description block 208, each of the GPS satellites 200, 202, 204, and 206 transmits GPS data having timing data (GPS time) and ephemeris data. Using the navigation equations 212, which are well known in the conventional art, and the previous timing data, the pseudoranges R0, R2, R4, and R6 can be determined (called actual pseudoranges) by the GPS processing system 700. Moreover, the previous ephemeris data and almanac data on the earth 172, the pseudoranges R0, R2, R4 and R6 can be estimated (called estimated pseudoranges) by the GPS processing system.

Referring to Figure 6, a representative GPS constellation is shown in operation. Four GPS satellites 200, 202, 204 and 206 transmit GPS data. Both the vehicle 102 and the base station 188 receive these signals from each of the GPS satellites 200, 202, 204 and 206 on their respective GPS antennas 312 and 316. Both the C / A code and the carrier frequency are applied to the GPS Receive antennas 312 and 316 for processing.

In addition to the four GPS satellites shown in FIG. 6, there are the pseudolites 105. The pseudolit (s) 105 may be strategically located around the perimeter of any mine pit, and the GPS coordinates may be determined. Satellites 200, 202, 204 and 206, as shown in FIG. 6, emulate or emulate. This arrangement can be extremely useful in situations such as a mine pit, a cavity or the like, in which mine or Mining vehicles from the field of view of one or more of the GPS satellites 200, 202, 204 and 206 are due to topographical features such as high mine-pit walls. The ground based pseudolit (s) 105 provide additional range signals and thus may improve the availability and accuracy of the position capability of the present invention.

The pseudolit (s) 105 is (are) synchronized with the GPS satellites 200, 202, 204 and 206 and has a signal structure which, although different, is compatible with the GPS satellites 200, 202, 204, and 206 is compatible. In addition, the distance (range) between the vehicle 102 and the pseudolit (s) 105 is calculated, similar to the distance between the vehicle 102 and one of the GPS satellites 200, 202, 204, and 206. With pseudolite (s) 105, the range error has no ionospheric errors or errors due to selective availability. However, other errors such as tropospheric, pseudolite clock errors, and multipath errors must be considered.

In mine operation in a deep pit surface, the field of vision of the vehicle 102 in the mine may be limited by the mine walls. Thus, an adequate number of GPS satellites may not be within the GPS processing system 700 to properly derive a first position estimate. In such a case, one or more pseudolites 105 may serve as secondary sources. The pseudolite (s) can be placed at the edge of the mine or anywhere else. The pseudolit 105 (s) 105 may be used by the vehicle 102 in conjunction with any of the visible GPS satellites to obtain accurate first position estimates.

It is also contemplated that other forms of secondary sources may be implemented to assist the GPS satellite or to completely eliminate the need to receive GPS data from the GPS satellites. In addition, a laser scanning technique may be used to provide local area data to the vehicle 102 from a second reference source.

The communication channel 618 represents the communication link between the base station 188 and the vehicle 102. The communication channel 618 has an electromagnetic link set up by data radios 620 and 622, which are transceivers. The communication channel 618 is used to transfer data between the base station 188 and the vehicle 102. It is contemplated that other forms of communication media may be used.

For example, a laser scanning technique may be used to provide information from the base station 188 to the vehicle 102.

The data radios 620 and 622 are located in the base station 188 and in the vehicle 102, respectively. The radios 620 and 622 are responsible for the data exchange between the base station 188 and the vehicle 102. The exchanged data type will be discussed further below.

A radio transceiver suitable as the data radios 620 and 622 is commercially available from Dataradio Ltd., Montreal, Canada, under model number DR-4800BZ.

Referring to Fig. 7, a GPS processing system 700 is shown. The GPS processing system 700 of the vehicle 102 includes a GPS antenna 702. The GPS antenna 702 receives the radio spectrum of electromagnetic radiation. However, the exemplary system also contemplates receiving any signal through which GPS satellites 132-170 could encode data. The GPS antenna 702 is the commercially available model number CA3224 antenna from Chu Associates Inc., Littleton, Massachusetts.

The GPS antenna 702 is coupled to a preamplifier 704 so that the signals received at the GPS antenna 702 may be transmitted to the preamplifier 704. The term "coupling" in the context of this document means any system and method for establishing communication. The coupling of systems and methods, for example, electronic, optical and / or noise or Sound techniques, as well as others not explicitly described here. The clutch is generally electronic and corresponds to any one of many industry standard electronic interfaces.

The preamplifier 704 amplifies and converts the GPS data received from the GPS antenna 702 so that the GPS data can be processed or decoded. The exemplary system contemplates any method by which the received signals can be amplified. Preamplifier 704 is the commercially available Model Number 5300 preamplifier GPS RF / IF from Stanford Telecommunications Inc. (STel), Santa Clara, California. The preamplifier 704 is coupled to a GPS receiver 706. The GPS receiver 706 processes the GPS data sent from the GPS satellites 200, 202, 204 and 206 in the field of view of the GPS antenna 702. The GPS receiver 706 computes the actual pseudoranges for each of the GPS satellites 200, 202, 204, and 206. Actual pseudoranges are defined in this document as an estimate of the pseudoranges R0, R2, R4, and R6, which is derived from the time delay between the transmission of the electromagnetic signals from the GPS satellite and the reception of the electromagnetic signals by the GPS processing system 700. In addition, GPS receiver 706 may process in parallel all of the actual pseudoranges for GPS satellites 200, 202, 204, and 206.

The GPS receiver 706 generates this data when four or more GPS satellites are visible. Using the differential correction techniques described herein, the GPS processing system 700 may calculate (in the GPS processor 710) the first position estimate, with an accuracy of approximately 25 meters, if an optimal constellation of four GPS satellites 200, 202, 204 and 206 is in view. When an optimal constellation of five GPS satellites (not shown) is in view, the GPS processing system 700 may calculate the first position estimate with an accuracy of approximately 15 meters. An "optimal" constellation is one wherein the relative positions of the GPS satellites in space require higher triangulation capability, with triangulation technology being well known in the art.

The GPS receiver 706 outputs actual pseudoranges and the number of GPS satellites 132-170 that are currently being sampled or received. In cases where the number of seen or For example, if received GPS satellites 132-170 are less than four for a series of first position estimates, in the preferred embodiment, the VPS weight combination device 1204 does not use the first position estimates received from the GPS processing system 700 (particularly from the GPS processor 710) the calculation of the third position estimate.

The GPS receiver 706 includes a model number 5305-NSI receiver, commercially available from Stanford Telecommunications Inc. However, any receiver capable of delivering actual pseudoranges and the number of sampled or received GPS satellites may be used.

The GPS receiver is coupled 706 to a GPS communications processor 708. The communication processor 708 is the commercially available 68000 microprocessor from Motorola Inc., Schaumburg, Illinois, USA. Any processor alone or in combination with the GPS receiver 706 for performing the same purpose as described below may be used.

The GPS communication processor 708 is further connected to a GPS processor 710 and a GPS console 1712. The GPS communication processor 708 coordinates the data exchange between these three devices. In particular, the GPS communications processor 708 receives pseudorange data from the GPS receiver 706, which forwards them to the GPS processor 710. The pseudorange data includes, for example, the actual pseudoranges computed by the GPS receiver 706, the number of GPS satellites 200, 202, 204 and 206 currently seen by the GPS receiver 706, and other GPS data. required by the GPS processor 710 to calculate the estimated pseudoranges for each of the GPS satellites 200, 202, 204, and 206. The GPS intercommunication or GPS communication processor 708 also transmits status information concerning GPS receiver 706 and GPS processor 710 to GPS console 1712.

The GPS communications processor 708 transmits the above information to the GPS processor 710. The GPS processor 710 includes the 68020 microprocessor commercially available from Motorola Inc. FIG. 8 is a low-level flowchart 800 illustrating the operation of the software in the GPS processor 710.

The GPS processor 710 uses a number of algorithms and methods to process the data it receives, including, for example, a GPS Kalman filter 802, shown in FIG. Kalman filter 802 is well known in the art.

The GPS Kalman Filter 802 is a module in the software of the GPS Processor 710.

In part, it is the function of the Kalman filter 802 to filter out noise associated with the pseudorange data.

The GPS processor 710 then calculates the estimated pseudoranges, the first position estimate, and the vehicle speed (from the Doppler shift) using the above current state and any derivatives including the clock derivatives and the spatial derivatives , However, the GPS processor 710 stores the calculated speed data when the C / A code is used instead of the carrier frequency by the GPS receiver 706 to derive the vehicle speed. The reason for dropping the vehicle speed is that experimental results have shown that it is not adequately accurate when derived from the C / A code.

Vehicle speeds derived from the carrier frequency (Doppler shift) are much more accurate than the speeds derived from the C / A code. The first estimated position (and vehicle speed when derived from the carrier frequency) is encoded in the GPS signal 716 and sent to the VPS main processor 1002 shown in FIG.

As previously discussed, the GPS processor 710 analyzes both the carrier frequency and the C / A code. Unlike data demodulated by the C / A code, data from the carrier frequency may be retrieved by the GPS receiver 706 at approximately 50 Hz (not approximately 2 Hz, as is the case for demodulating a C / A code). A codes is). This increased speed allows the present invention to produce more accurate position and velocity determinations with less error.

Figure 8 illustrates other functions of the GPS processor 710. However, the present invention contemplates any method by which GPS data can be processed to determine pseudoranges. As shown in a flowchart block 816, a console function controls the operation of the GPS console 2. The console function regulates the operation of the GPS Kalman filter 802 by providing an operator interface into the filter.

The VPS communication function 818 controls the outputs of the GPS Kalman filter 802 which are routed to the VPS 1000. In the flowchart block 806, it is shown that the GPS Kalman filter 802 requests and decodes data from the GPS receiver 706, which data is passed through an IPROTO function 804, as shown in a flowchart block 806.

As shown, the IPROTO function 804 resides in the GPS communications processor 708 and performs tasks associated with the GPS communications processor 708. IPROTO function 804 is Model No. XVME-081, which is commercially available from Xycom Inc.

The GPS console 712 is well known in the art. Many types of devices are commercially available that provide the desired function. One such device is commercially available from Digital Equipment Corporation, Maynard, Massachusetts, under model no. VT220. The GPS console 712 maps processor activity data pertaining to the GPS communications processor 708 and the GPS processor 710.

The GPS processor 710 is coupled to a GPS console 722 and a GPS communication interface processor 720. The GPS console 722 is well known in the art. Many types of devices are commercially available that provide the desired console function. One such device is commercially available from Digital Equipment Corporation, Maynard, Massachusetts, under model no. VT220. The GPS console 722 provides the operator interface or operator interface from which the GPS processor 710 can be activated and monitored.

The GPS communication interface processor 720 is essentially an I / O or input / output board. It is coupled to a data radio 714 and a GPS data collection device 718. The GPS communication interface processor 720 coordinates the communication between the GPS processor 710 and both the data radio 714 and the GPS data collection device 718. The communication interface processor 720 in the exemplary system is model no. MVME331, which is commercially available from Motorola Inc. USA.

The data radio 714 establishes a communication link between the GPS processor 710 at the vehicle 102 (through the GPS communication interface processor 720) and a similar data radio 714 located at the base station 188 (see FIG. 6). The data radio 714 communicates synchronously at 9600 baud using RF (Radio Frequency) frequencies. The data radio 714 at the base station 188 provides periodic updates of the amount of spatial derivative and clock derivative for each satellite to the data radio 714 at the vehicle 102 at a rate of 2 Hz (twice per second). Spatial and clock derivatives calculated by base station 188 will be discussed further below.

The GPS data collection device 718 may be any of numerous conventional electronic processing and storage devices, such as a desktop computer. Any personal computer (PC) manufactured by International Business Machines Corporation (IBM) of Boca Raton, Florida, USA can be implemented.

The MPS (motion positioning system) 900 is illustrated in FIG. The MPS 900 derives the second position estimate of the vehicle 102. Usually, this second position estimate is combined with the first position estimate and filtered to thereby derive a more accurate third position estimate. However, it is envisaged that in some examples, the second position estimate exclusively or can be used extraordinarily as a third position estimate if the first position estimate is considered completely inaccurate.

For the MPS 900, the exemplary system provides for the combination of the 902 and IRU 904 odometer. However, the IRU 904 could be used without the odometer 902. The odometer and the IRU 904 are coupled to an MPS communications processor 906 to thereby provide the MPS 900. IRUs and gauges are well known in the art and are commercially available from Honeywell Inc., Minneapolis, Minnesota, under Model No. HG1050-SRO1 or from Caterpillar Inc., Peoria, Illinois, under part no. 7T6337.

The IRU 904 features ring laser gyroscopes and accelerometers of known design. The IRU 904 is a replica of the system used by the Boeing 767 aircraft to determine the aircraft position except that the IRU 904 has been modified to accommodate the low dynamics (e.g., speed). To account for the vehicle 102 relative to those of a 767 aircraft.

The IRU 904 can output the vehicle position at 5 Hz, the speed at 10 Hz, the pitch at 50 Hz, the altitude at 50 Hz and the pitch data at 50 Hz. Moreover, the vehicle odometer 902 may output the distance traveled by the vehicle 102 at 20 Hz.

The laser gyroscopes of the IRU 904 must first be given an estimate of the length, width and height of the vehicle 102 in order for them to function properly. Using this data as a baseline position estimate, the gyroscopes then use a predetermined calibration in conjunction with forces associated with the rotation of the earth 172 to determine an estimate of the current position of the vehicle 102.

This information is then combined by the IRU 904 with the data acquired by the accelerometers of the IRU 904 to produce a more accurate second position estimate of the actual vehicle position. The second position estimate from the IRU 904 and the data from the vehicle odometer 902 are transmitted to the MPS communications processor 906 as shown by respective arrows 910 and 908 of FIG. Arrow 114 of FIG. 1 includes arrows 908 and 910.

In experiments, it has been determined that the IRU 904 may provide erroneous estimates of the second position of the vehicle 102 due to imprecise assembled parts. In particular, it has been observed in the exemplary system that the direct output of the IRU 904 has drifted counterclockwise from the north direction during operation. The drift depends on the direction in which the vehicle 102 and consequently the IRU 904 are running.

Moreover, the drift can be defined by an IRU deviation equation. The IRU deviation equation can be derived similarly to the construction of the path equations described with respect to the weighted path history technique or similar to the construction of the parabolic equations described with respect to the parabolic derivation technique. After it has been derived, the IRU drift or IRU deviation equation can be used to extrapolate more accurate second position estimates.

Communications processor 1002 includes the commercially available Motorola Inc. 68000 microprocessor. The communication processor 1002 coordinates the data exchange between the MPS 900 and the VPS 1000. Any processor having a similar function as described herein may be used.

Referring to Figure 10, the architecture of the VPS 1000 (VPS = Vehicle Positioning System) is depicted. 11 shows in detail a diagram of the VPS 1000 connected to the GPS processing system 700 and the MPS 900.

The GPS processing system 700 and the MPS 900 are independently coupled to the VPS main processor 1002. The independent clutch is an important novel feature of the present invention. Since they are independent, the failure of one of the systems will not cause the other to go out of service. Thus, if the GPS processing system 700 is not operating, data may still be collected and processed by the MPS 900, and thus also by the VPS 1000. GPS processing system 700 and MPS 900 transmit signals 716, 908, 910 to VPS main processor 1002 as shown. These signals include position, velocity, time, altitude, pitch, roll, yaw, and distance data (see FIGS. 7 and 9 and the associated discussions).

The VPS main processor 1002 is coupled to the VPS I / O processor 1004. The VPS main processor 1002 transmits a signal 1008 to a VPS I / O processor 1004 as shown. Signal 1008 includes the third position estimate. The third position estimate is derived from the GPS, IRU, and odometer data, as noted above, and more particularly the first and second position estimates of the vehicle 102.

The exemplary system contemplates any system and method by which the signals indicated by arrows 716, 908, and 910 may be received by the VPS main processor 1002 of the GPS processing system 700 and the MPS system 900 the VPS main processor 1002 can be supplied. The VPS main processor 1002 is the 68020 microprocessor commercially available from Motorola Inc., USA.

The VPS I / O processor 1004 is coupled to a VPS communications interface processor 1020. The communications interface processor 1020 is the MVME331 processor commercially available from Motorola, Inc., USA. Any processor that performs the same purpose as described below may be used.

The VPS communications interface processor 1020 is coupled to three different devices: (1) a VPS console 1012, (2) a data collector 1014, and (3) the navigation system 1022. The VPS communications interface processor 1020 routes the data, including the data third position estimation included in the output 1016 to the above three devices at a rate of 20 Hz.

The VPS console 1012 is well known in the art and is available from Digital Equipment Corporation, Minneapolis, Minn., Under model no. VT220 available. This VPS console 1012 is used to map the actual state of the VPS I / O processor 1004.

The VPS data collection device 1014 may be any of numerous commercially available electronic processing and storage devices, such as a desktop PC. Any MacIntosh PC available from Apple Computer, Cupertino, California can be successfully used to accomplish this purpose.

The navigation system 1022 has the features associated with the navigation of the vehicle 102. The VPS 1000 transmits the third position estimate to the navigation system 1022 so that the navigation system 1022 can accurately and safely route the autonomous vehicle 102.

Referring to FIG. 7, host processing system 186 at base station 188 includes GPS processing system 700 of FIG. The purposes of the host processing system 186 at the base station 188 are as follows: (1) monitoring the operation of the vehicle 102, (2) providing a known terrestrial reference point from which spatial derivatives can be generated, and (3) providing; , Supplying any other information to the vehicle 102, if necessary, via the high-speed data communication channel 618.

The base station 188 will be located near the vehicle 102, preferably within 20 miles. The close geographic relationship will provide effective radio communication between the base station 188 and the vehicle 102 over the communication channel 618. It will also provide an accurate reference point for comparing the satellite transmissions received by the vehicle 102 with those received by the base station 188.

A near geographical reference point is needed to compute proper spatial derivatives. Spatial and clock derivatives are effectively the general mode noise that inherently exists in the NAVSTAR GPS and the GPS processing system 700. Once computed at the base station 188, the spatial or Room and clock leads are then sent to the vehicle 102 using data radius 714, as shown in FIG. The spatial derivatives are calculated using various methods, which are discussed further below.

The host processing system 186 further coordinates at the base station 188 the autonomous activities of the vehicle 102 and provides an interface for the VPS 1000 with the human monitors.

The exemplary system improves the accuracy of the position estimates of the vehicle 102 via a number of differential correction techniques. These differential derivative techniques are used to improve the first, second and third position estimates.

Several of these differential correction techniques are designed to directly remove errors (noise or interference) in the calculation of pseudoranges R0, R2, R4, and R6 (both actual and estimated pseudoranges). The removal of these errors results in a more precise first position estimate output from the GPS processing system 700 to the VPS 1000, and ultimately results in a more precise third position estimate output from the VPS 1000 to the navigation system 1022.

The host processing system 186 is responsible at the base station 188 for performing these differential techniques and for providing the results to the vehicle 102. It will be understood that the host processing system 186 includes the GPS processing system 700 as well as the vehicle 102 has. The term "differential" is used because the base station 188 and the vehicle 102 use an independent but substantially identical GPS processing system 700. Further, since the base station 188 is stationary and its absolute position is known, it serves as a reference point from which to measure electronic errors (noise or interference) and other phenomenon-causing errors.

The exemplary system includes a method by which the future positions of the GPS satellites 132-170 with respect to a known absolute position of the base station 188 and / or the vehicle 102 can be predicted. The future locations are based on estimated pseudoranges computed by the GPS processor 710 in the host processing system 188 and / or the vehicle positioning system 1000. In addition, the calculations may be performed at the base station 188 and / or in the vehicle 102 and, if necessary, transmitted somewhere.

By predicting the future locations of the GPS satellites 132-170, optimal satellite constellations for the vehicle 102 can be fairly predicted. Thus, the exemplary system may provide a prediction of availability or non-availability from the satellites in a systematic manner. It allows further future planning regarding. operation, service and maintenance of the vehicle 102.

When considering the establishment of an autonomous navigation system, there are certain basic questions that any autonomous system must be able to answer in order to successfully navigate from point A to point B. The first question is "Where are we (the vehicle) now?". The first question is answered by the Positioning System as discussed in section III above.

The next or second question is "Where are we going and how are we going to get there?". This second question falls within the scope of the navigation system part, which is discussed in this section (VI).

Another (third) question, actually a refinement of the second, is "How do we actually physically move the vehicle, for example, what actuators (steering, speed, brake, etc.) are involved to get there?". This is the area of ​​the vehicle control subsystem of the navigation system, which is also discussed below.

As implicitly discussed above, the autonomous navigation of, for example, a mining vehicle can provide certain significant advantages over conventional navigation. Among them is an increased productivity of a 24-hour operation of the vehicle around the clock. The problems presented by hazardous work environments or work environments where visibility is poor are particularly well suited for solution by an autonomous system.

For example, there are some mining areas where visibility is so poor that working for 200 days of the year is not possible. There are other areas that are dangerous to human life because they are contaminated by industrial or nuclear pollution. An area may be so remote or devastated that if it were required that people work there, it would impose severe restrictions or be impractical. The application could foreseeably include off-ground operations, such as mining on the moon, provided that the necessary GPS satellites are placed in orbit of the moon.

In a typical application, as shown in Fig. 3, there are three basic areas of operation relating to the navigation of a mining vehicle on a mining site: the loading site, the delivery segment and the unloading site. At the point of loading, a delivery vehicle can be loaded with ore in a variety of ways, such as man-operated shovels controlled either directly or remotely, or by autonomous shovels. The delivery vehicle must then travel over an area called delivery segment, which may be only a few hundred meters or several kilometers. At the end of the delivery segment is the unloading point, where the ore is unloaded from the delivery vehicle, for example, to be crushed or otherwise processed. In the exemplary system, autonomous positioning and navigation may be used to control the delivery vehicle along the delivery segment. Autonomously navigated tank vehicles and maintenance vehicles are also considered.

Referring to FIGS. 4 and 5, the autonomous mining truck (AMT) navigation system includes various systems, devices, and / or functions. The subsystem of the vehicle positioning system 1000 of the entire autonomous mining truck system, as discussed above, outputs position data indicating where the vehicle is located having, for example, north and longitude and east and latitude positions, respectively.

With reference to FIGS. 4 and 5, position data output from the vehicle position determination system is taken by a navigator 406. The navigator determines where the vehicle wants to go (from the route data) and how it gets there, and in turn outputs data composed of steering and speed commands to a vehicle control function block 408 to move the vehicle.

The vehicle control block then issues commands at a low level to the various systems of the vehicle 102, such as the governor, the brakes, and the transmission. When the vehicle is moving to its destination, the vehicle controls block, and the vehicle positioning system receives feedback information from the vehicle indicating, for example, any fault conditions in the vehicle systems, the current speed, and so forth.

The navigation must also have an obstacle handling capability (detection and avoidance) to cope with the unexpected. A scanner system 404 detects obstacles in the projected track of the vehicle, as well as obstacles that may approach from the sides, and informs the navigator about it.

It may then be necessary for the navigator to decide if action is required to pass the obstacle. If an action is required, the navigator decides how to avoid the obstacle. And after the obstacle has been avoided or bypassed, the navigator decides how to get the vehicle back on a path to its destination.

With reference to Fig. 16, which will be referred to as a context diagram, and with reference to Figs. 18A-18D, definitions of the communications shown as circles with numbers therein are described below:

502nd Host commands and requests:

Commands given by the host to the vehicle manager. These commands could be of various kinds: initiation / termination;

Supply parameters;

emergency action; and

instructions

The requirements ask about the condition of different parts of the navigator.

504th Responses to the host:

These are answers to the questions asked by the host.

432nd Position data:

This is a flow of information provided by the vehicle positioning system (VPS).

416th Range data:

These are area data from the line laser scanner. 432. VPS control:

These are commands given to the vehicle positioning system to turn it on, shut down, and switch between operating states.

416th Scanner Control:

These are commands that are sent to the laser scanner to initiate movement and adjust the following speed profile.

420th Steering and speed commands:

These are commands issued to the vehicle to control steering and speed. These commands are issued at a rate of 2 to 5 Hertz.

Referring to FIG. 5, as described above, both the vehicle positioning system and the navigator are located on the vehicle and communicate with the base station 188 to receive high-level GPS position information and instructions from a host processing system 186, as discussed below. The system obtains GPS position information from the GPS satellites 200-206 at the base station and on-board the vehicle so that a common operating state error can be removed and the accuracy improved. Alternatively, parts of the vehicle positioning system and the navigator may be located at the base station.

The host at the base station may instruct the navigator, for example, to travel from point A to point B, and may direct one of a set of fixed routes to use. The host also handles other typical scheduling and scheduling activities, such as the coordination of vehicles and equipment, to maximize efficiency, avoid collisions, schedule maintenance, detect fault conditions, and so on. The host also has an operational interface for a human manager.

It has been found that it is desirable to place the host at the base station and navigate the vehicle to avoid a bottleneck in communication and consequent degradation in performance and responsiveness. Because the host sends commands at a relatively high level and simplified data to the navigator, it requires relatively little communication bandwidth. However, in situations where broadband communication is available, this can not be a factor.

Another factor in determining the specific location of elements of the system is the sensitivity of autonomous navigation over time. The navigation system must continuously check its absolute and relative position to avoid unacceptable inaccuracies in tracking a route. The required frequency of checking the attitude increases with the speed of the vehicle, and the communication speed can become a limiting factor even at a relatively moderate vehicle speed.

However, in applications where maximum vehicle speed is not a primary consideration and / or where a high degree of tracking accuracy of the road is not critical, this communication factor may be unimportant. For example, with a relatively fast ride over large expanses of open, flat land on a relatively straight path, it may not be necessary to check the position on the trip as often as would be necessary while navigating a journey along a winding mountain road.

Conceptually, the navigation aspects of the present invention may be arbitrarily divided into the following main functions:

Route planning / path generation;

Path tracking; and

Obstacle treatment.

The navigation of an automatic vehicle conceptually consists of two sub-problems, the path generation and the path tracking, which are solved separately.

Path generation utilizes intermediate goals from a high level scheduling device to generate a detailed path which the vehicle 102 is to follow. There is a certain trade-off between simplifying the presentation of such levels and the ease with which they can be performed. For example, it is a simple scheme to decompose a path into straight lines and circular curves. However, such paths can not be accurately tracked in a straightforward manner because of curvature irregularities at transition points of segments requiring sudden accelerations.

Following path generation, the path trace takes as an input the detailed path created and controls the vehicle 102 to follow the path as precisely as possible. It is not enough simply to follow a list of guidance commands previously established, as failing to accurately achieve the required steering movements will result in steady state steady state transients. The errors accumulate over time. Global position feedback 432 may be used to compensate for less than ideal actuators. Methods have been devised which deviate from the traditional vehicle control schemes in which a time history of the position (a trajectory) is provided in the schedule set for the vehicle 102.

These methods are suitably referred to as "path tracking" in that the steering motion is decoupled from time, ie steering motions are directly related to the geometric nature of the fixed path, making the speed of the vehicle 102 an independent parameter.

With reference to FIG. 3, an autonomous vehicle 102 may be required to traverse a delivery segment 320 to an unloading point 322 and, after having unloaded its load, to drive over another delivery segment to a shop floor 324 under the instruction of Host processing system 186. Host processing system 186 determines the destinations of vehicle 102, which is called "cycle planning." The determination of which routes should be taken to get to a desired destination must be achieved by "route planning".

"Route planning" is the determination of which path segments to take to get to a desired destination. In general, a route may be considered as an abstraction or representation of a set of points between two defined high level layers. As one can say to a human driver "Take Route 95 south from Lobster, Maine to Miami, Florida," and the driver will translate the instruction into a sequence of operations (starting vehicle 102, releasing the brake , engaging the gearbox, accelerating to the commanded speed limit, steering the steering wheel, driving around obstacles 4002, etc. may include), the autonomous navigation system of the present invention operates in a similar manner. A "route" is a sequence of contiguous "segments" between the beginning and the end of a journey.

An autonomous vehicle 102 may begin at any position in the sequence and travel the route in either direction. A "segment" is the "path" between "nodes". A "node" is an "alignment" on a path that requires a decision. Examples of nodes are load locations 3318, unload locations 322, and interfaces 326.

There are different types of segments. For example, there are linear and circular segments. The linear segments (lines) are defined by two nodes. Circular segments (arcs) are defined by three nodes.

"Postures" are used, for example, to model parts of a route, paths and nodes. Layers may consist of a position, a direction, a curvature, a maximum speed, and other information for a given point on the path.

A "path" is a succession of successive layers.

A segment is therefore a sequence of successive layers between nodes. All segments have an associated speed which determines the maximum speed at which the vehicle 102 can travel over that segment. The Navigator 406 may command slower speeds to meet other requirements, if necessary.

Determining which layers are required to define a path segment by analytical methods, experimental methods, or a combination of both is called "path planning." To complete the discussion, a sequence of contiguous routes, as mentioned above, is referred to as a "cycle" and the work objectives of a vehicle 102 determine its "cycle".

Therefore, to define a route, one must first define the nodes and segments. Next, the nodes and segments must be instructed. Finally, the routes must be defined by specifying where in the commanded set a route should begin and in which direction the commanded set is to be overrun (see Figure 12, which illustrates these concepts of the present invention).

The aforementioned method of defining routes has been developed for memory efficiency. It is also a convenient way to define many routes to a specific set of nodes and segments.

In one example from the real world, an image of a terrain may be provided where there are many intersecting roads 326. A route programmer would define nodes at the intersections and segments to define the roads between the intersections. The routes would therefore be determined by roads and intersections. However, there will be many ways to get from point A to point B (many routes) with a fixed set of intersections and roads.

The path tracking method uses the route curvature to steer the vehicle. The route definition methods that use lines and arcs do not provide continuous curvature. Clothoid curves are another way to define routes.

Another method for defining routes developed by the inventors fits B-splines into the route data. B-splines provide a continuous curvature and therefore improve tracking performance. In addition, since B-splines are free of curves, a route can be defined by a simple B-spline curve. Using free-form curves, a more robust (semi-automatic) method is used to fit routes to data collected by driving from the vehicle over the routes.

Referring to FIGS. 4 and 12, in operation, host processing system 186 from base station 188 instructs an identified vehicle 102 to take route N from the current location. The navigator 406 acts to generate a path by translating "Route 1" into a series of segments, each having a "commanded" or associated maximum speed limit, which together form a generated path to which the vehicle is assigned should try to follow. By setting routes and instructing the autonomous vehicle 102 with high-level commands in this manner, enormous demands on data and inefficiencies in giving directions are avoided.

The navigator 406 stores the routes as a linked list of path segments instead of the set of sequences of sentences of the individual points. These segments are also abstractions of the set of points between defined locations or nodes.

A LINKER then takes the given path segments and creates a linked list of control points, allowing flexibility and efficient arrangement. Path segments are shared by different routes, as shown in FIG. 12.

The path segments are stored in a memory called TARGA 5302 as a set of arcs, lines and layers. For example, an analytical generator function generates paths using these arcs, lines and layers. In another example, B-splines (curves) are used as a mathematical representation of a route, as mentioned above. In another example, "clothoid curves" are used in creating path segments.

Data is first collected and stored by the vehicle positioning system 1000 to generate routes for a terrain 300 while a human travels the vehicle 102 over the road system of the work site 300. Nodes and segments are then fitted to the stored, trailing data and organized into routes for the aforementioned method.

An application on an Apollo computer workstation (now Hewlett-Packard, Palo Alto, California) (not shown graphical display system) has been developed to graphically fit route data to the stored wandered data and further define routes (ie, speeds, sequences, a Starting point, a transverse direction). Any graphics workstation or graphic computer equivalent to the Apollo could be used.

Once the routes for a terrain are defined, the route data is written to a permanent storage device. The storage device used may be a blister storage cartridge 5302 with an associated read / write device. The bubble memory device 5302 is durable and holds the data when the power supply is disconnected. The Apollo application can write data to a cartridge 5302 and read data from a 5302 cartridge.

As explained above, routes can be predefined or they can be created dynamically.

In mining applications, terrain 300 is generally monitored and roads are pre-planned, carefully designed and built. The routes used by the navigation system may then be obtained either from a manually generated computer database (specially created to be used by the navigation system), or alternatively, a vehicle may be physically driven over the actual routes on the site to learn the routes as described above. In the learning process, various journeys can be made over a given route. Then, the changes in the data (for example, due to the driver shaking) are grouped together and a smoothed best fit is developed.

The tracking method of the present invention requires some information about the route being tracked. The information is contained in a package called "Location" 3314. A single layer 3314 may include a location (latitude and longitude coordinates), orientation, and curvature data for a particular location on the route. Therefore, a way to generate location data from the route description is required.

Among the navigator tasks (discussed below) is a task that reads out the route information and generates locations at intervals along the route (for example, at one meter intervals) used by the tracking method. In an exemplary system, each tier requires 36 bytes of storage, yielding approximately 36K of storage for every kilometer of the route. To reduce memory requirements, the navigator buffers the location data.

The task generating the plies reads out the current position of the vehicle 102, finds the next point on the route to the current position, then generates a fixed number of plies in front of the vehicle 102. The number of plies generated depends on the maximum Stop distance (braking distance) of the vehicle 102.

That is, there should always be enough layers in the buffer 3000 to guide the vehicle 102 to a stopping point.

In the route definition B-spline approach, the need for a location buffer is eliminated because the tracking method can directly generate location information from the B-spline curve.

Path tracking is a critical aspect of vehicle navigation in the exemplary system. The technique of the present invention utilizes position-based navigation (rather than sight-based navigation used in conventional navigation systems) to ensure that the correct path 3312 of the autonomous vehicle is tracked. The present invention is also novel in that it provides separate control of the steering angle 3316 and the vehicle speed 3318.

FIG. 17 graphically illustrates a path tracking system 3102.

For an autonomous vehicle 102 according to the present invention for tracking fixed paths, it is necessary to generate reference inputs to the vehicle servo controllers. Thus, path tracking may be considered a problem in obtaining a reference steering angle and a reference speed for the next time interval to return to the reference path before the presently-deviated position.

Generally speaking, the path trace determines the commands of the autonomous vehicle (speed, steering angle) required to follow a given path. For a given pre-determined steering angle, driven wheel speed values ​​and error components, the steering command and drive inputs are calculated.

The obstacle treatment provides at least three major functions: detecting obstacles 4002, avoiding obstacles 4002, and returning to path 3312. The function of returning to the path is similar to path creation and tracking as described above.

In addition to path tracking (tracking), successful navigation of vehicle 102 requires that vehicle 102 be able to detect obstacles 4002 in its path, thus allowing the vehicle to stop or otherwise avoid such an obstacle before a collision occurs.

In one embodiment of the present invention, an infrared laser scanner 404 is used with a single line (see Fig. 19) in a configuration where the scan is horizontal (not shown). The scan line 3810 does not touch the ground, so any inequalities in the area data may be associated with the objects 4002 in the environment.

Since a reference path 3312 is available and the vehicle position relative to the reference path is known, only the area data and a region boundary of the threat path reference path 3312 4002 are processed. The objects outside this region or boundary zone are ignored. The width of the boundary zone (not shown) is equal to the vehicle width plus a certain selected safety buffer to compensate for tracking and positioning errors. This method is limited in its usefulness and is referred to as "free space check".

In the simplest case of the present invention, the laser 404 may be used in a single line scan mode with subsequent range measurements made at regular angular intervals as the laser sweeps across the field of view. Again, for simplicity, these samples may begin at regular time intervals. The term "free space check" has been used to describe this method. In this version of the present invention, the method has been limited to the processing of only two-dimensional data.

This type of obstacle detection method is limited to checking to see if the path 3312 is free using a single line scan mode with subsequent range measurements performed at regular angular intervals when the scanner 404 over the field of view. It does not exclude any procedures for setting up or Check the existence of any obstacle 4002, nor does it create a path around it if the path is not clear. This type of method is not considered to be a particularly useful obstacle detection method except in highly controlled environments such as on a factory floor.

A second embodiment of obstacle detection of the present invention uses a multi-line scanner 3804 (see FIG. 19) whose scan 3810 contacts the ground a certain distance ahead of the vehicle 102. Since the scan line touches the ground, unevenness of the area data may no longer be associated with threatening objects 4002. For example, profiles of natural objects, such as hills and sloping or arched roads, may cause unevenness in the area data. This technique of the present invention can distinguish unevenness in the area data between threatening objects 4002 and natural objects (not shown).

In this embodiment of the present invention, a filtering scheme is used to reduce the amount of data processed, and it is independent of the scanner configuration used. The edges of the boundary zone are found by transmitting the area data in an image plane representation 3900 (see FIG. 20) where each area value is located by a line number 3908 and a column number 3910 (a matrix representation).

The processing load is minimized by selecting a relatively small number of scan lines available in a range image representation 3900. The scan lines are selected by the vehicle speed and are concentrated at and above the vehicle stop distance. The selected scan lines of successive data frames may overlap.

In this method, when the vehicle 102 is moving rapidly, the selected scan lines 3906 are far ahead of the vehicle (near the top of the area image representation 3900). In contrast, when the vehicle is traveling slowly, the selective scan lines 3906 are closer to the vehicle (near the bottom of the area image representation 3900).

Each scan line consists of many pixels of data. Each pixel has two associated parameters. First, the actual value of the pixel is the range value returned by the scanner 3804. Second, the location of the pixel on the scan line gives an indication of the angle relative to the vehicle centerline at which the area value was recorded. This corresponds to a cylindrical coordinate frame description (R, theta, Z).

Given the cylindrical description and the known scanner attitude with respect to the vehicle 102, the range values ​​may be converted into a Cartesian coordinate system (X, Y, Z). The result is a road profile description that may be used by a novel filtering scheme to determine if threatening objects 4002 are present in the vehicle path 3812, while ignoring effects due to natural hills and valleys on a typical road.

After the scanner data has been converted to Cartesian coordinates, the data is processed to determine which part of the scan is actually on the road 3312 and which part of the scan line is outside the vehicle path and therefore can safely be ignored. Given the vehicle position and the width of a boundary (equal to the vehicle width plus a certain safety margin), the coordinates of the boundary can be determined on each side of the vehicle path. The coordinates of the boundary can be compared with the coordinates of each pixel on the current scan line. The pixels that have coordinates outside the boundary are ignored.

The filter scheme builds an expectation of the road profile from previously sensed road profiles. This expectation is based on three parameters which are found to adequately describe typical paved roads. These three parameters are the following:

- Road curvature: The curvature of the road cross section (perpendicular to the road center line).

- Road slope: The "slope" of the road profile (perpendicular to the center line).

Road height: The height of the road centerline above a reference plane, which is described by the location of the four wheels of the vehicle 102.

Expected values ​​of road curvature and road grade are determined by performing a standard Kalman least squares filter technique on previously sensed scanner data. The Kalman filter basically holds some kind of running average of the two parameters based on the values ​​determined from the previous data.

The expected road height for a particular scan may be determined by one of two similar methods. One is to average the street height at each pixel within the current scan line to determine a characteristic height of the scan line in question.

The second method is to filter the road height using the standard Kalman filter, similar to the one used when estimating the curvature and slope.

These three parameters can be used to determine a second order equation describing the expected road profile. This expected profile is compared to the actual road profile. Any discrepancies between the two that exceed a pre-set threshold are likely to be threatening objects.

This scheme is feasible on the assumption that any detected objects 4002 are small compared to the width of the road. When using these averaging methods or least squares methods, the effects due to objects are negligible compared to natural road data.

This filter scheme also has a very simple edge detection method which associates the selected area data with a simple seven point weighting function.

An additional technique processes an entire area image representation 3900 from a multi-object scanner 3804. This procedure achieves three goals:

1. Do not recognize any obstacles 4002, if none exist,

Second Recognize obstacles 4002 when obstacles exist, and

Third Recognize the correct obstacles 4002 when obstacles exist.

The obstacle extraction is an obstacle detection by applying blob extraction. Stain extraction is well known in computer graphics art. Obstacles are found by clustering similar pixels into groups called blobs. The goal of obstacle extraction is to store and process obstacles as units rather than as individual pixels.

The obstacle extraction may be performed by preforming the following steps in the image plane 3901:

1. Project the vehicle path onto the image plane 3901,

Second Convert the area data into elevation data,

Third Adjust a curve to the height in the middle of the road (this represents the expected road height for each line),

4th Make the threshold of the actual road height over the altitude expectation, and

5th Extract the obstacles (indicated by differences in actual and expected road heights that exceed the threshold).

Once an obstacle 4002 has been detected in the path of the vehicle 102 (see FIG. 40), it must then avoid collision with the object. Certain assumptions are made regarding the obstacle avoidance problem:

1. The obstacle environment is populated with obstacles 4002, which may be represented by convex polygons or convex lines;

Second The navigation methods have access only to the local environment information in the form of a local map representing all visible end-faces of the obstacle from the position of the vehicle 102, which may be obtained from unprocessed laser range data or data processed by spot extraction ;

Third The vehicle 102 is a conventionally steered type having limitations on its speed and acceleration, and restrictions on the steering angle and the rate of change of the steering angle.

To cope with the problem of avoiding obstacles, this problem is split into two sub-problems.

First, the distinction as to whether any obstacles are in the way, and if so, to which side the vehicle should proceed. Then, the selection of a sub-goal 4006, which will lead the vehicle 102 around the obstacle 4002, resulting in a higher-level goal 4008, which is to return to the desired path.

Second, once a sub-goal 4006 is selected to make a steering decision that drives the vehicle 102 toward the sub-goal 4006 while steering around the obstacle 4002. A sub-target selection process and a steering decision process solve these two sub-problems.

The exemplary system includes a method as diagrammed in FIG. 21, whereby a secure path around a detected object 4002 is recorded and navigated so that the vehicle 102 will again reach the reference path after having received the object 4002 avoided.

Referring to FIGS. 19 and 23, the present invention also includes a laser scanner system 404. The scanner 404 is used to find obstacles 4002 (see FIG. 21) that incidentally accumulate in the path of the vehicle 102, as previously discussed.

Sources of such obstacles 4002 can be varied and numerous, depending on the particular work site. You may have fallen trees and branches, rocks, moving and parked vehicles, and people.

The scanner 404 gives the autonomous vehicle 102 the ability to detect and cope with the surrounding world, as circumstances require.

The major components of the laser scanner system 404 are shown in FIG.

A laser range finder 3804 uses an infrared ray 3810 to measure the distances between the range finder unit 3804 and the next object 4002. A short pulse is transmitted by the unit 3804, and the time taken for the beam 3810 to reflect and return from an object 4002 gives the distance.

The beam 3810 from the range finder 404 is reflected by a rotating mirror 4222, giving the range finder 404 a 360 ° view of the world. The mirror rotation is achieved by an engine 4206. The engine speed is controlled via port 4210, which communicates with a motor amplifier and controller 4220 through a conventional serial RS232C link 4224. The synchronization between the laser fire and the mirror angle position is performed with an encoder.

Distance data on a line 4226 from the laser range finder 404 is received by an interface circuit 4228 which differentially transfers the data to a buffer circuit 4214. Individual pieces of data are collected by the buffer circuit 4214 until the mirror 4222 makes a full turn. This record has a scan. When a scan is completed, the buffer circuit 4214 signals a processor 4212, whereupon data is transferred from the full scan to the processor 4212 for processing.

The interface circuit 4228 has three functions.

First, it acts as a security monitor. A situation could occur where the mirror 4222 would stop rotating, as in the case where the drive belt 4230 between the motor 4206 and the mirror 4222 breaks down. In this condition, the laser 4204 would continue to fire, and since the mirror 4222 is stationary, it would shine to a single point (dangerous to someone looking directly into the laser beam). However, the interface circuit 4228 senses when the angular velocity of the mirror 4222 falls below half a revolution per second and shuts off the laser 4204 when such a condition occurs.

The second function is to turn off the laser 4204 from firing for a portion of the scan area of ​​360 degrees. Typically, the laser scanner unit 404 will be mounted on the front of a vehicle 102, and the interesting field is in the 180 degree front of the vehicle. The vehicle itself will block the back of the scan area of ​​360 degrees. In this case, the circuit 4228 will prevent the laser 4204 from illuminating the vehicle, extending the life of the laser diode while taking data for the area in front of the vehicle. The turning on and off of the laser range finder 4204 is performed by two sensors (not shown) mounted near the mirror housing 4222. For test purposes or for applications where a scan of 360 degrees is desirable, the turn-off feature can be turned off by a DIP switch.

The third function of the circuit 4228 is to convert signals between a single ended and differential form, TTL signals from the laser unit 4204 are differentially transferred to the buffer circuit 4214, and the differentially transmitted signals from the buffer circuit 4214 are converted to TTL levels. This prevents noise interference along the cable 4226 connecting the two circuits.

The function of the buffer circuit 4214 is to synchronize the firing operations of the laser 404 with the angular position of the mirror 4222 to collect data for a complete scan and transmit the scan to the computer 4214 for processing.

The angular position of the mirror 4222 may be determined by signals sent from the encoder 4208. The buffer circuit 4214 uses two signals from the encoder 4208: the Z and A channels.

The Z channel is the encoder index (pointer); is set once per revolution of the encoder 4208 and is used to signal the beginning of the scan area.

The A channel is one line of the two-wire quadrature output of the 4208 encoder, giving pulses a thousand times per revolution of the encoder. This channel is used to trigger the laser illuminations.

An additional signal is needed to completely synchronize the scan field with the encoder signals. There is a 2: 1 gear ratio between the 4206 encoder / motor and the 4222 mirror. Two turns of the 4208 encoder rotate the 4222 mirror once. This is converted into 2 Z-channel pulses and 2000 A-channel pulses per revolution of the mirror 4222 and the inability to distinguish the beginning of the first half of the sample from the beginning of the second half.

To completely synchronize the scan field, the DB signal (DB = Deadband) generated by interface circuit 4228 is used. The DB signal, which is used to turn off the laser 4204 to fire in the back of the scan, allows the discrimination of the front and back halves of the scan. The Z signal and the DB signal together signal the beginning of the scan area.

The second task of the full scan data collection buffer circuit 4214 is achieved by the A channel of the encoder 4208. The 2000 pulses of the channel are divided by either 2, 4, 8, or 16, selected by DIP switches (not shown) on board 4228. This allows the number of data points per sample to be between 1000, 500, 250, and 125 is varied. The divided signal is used to trigger the laser range finder 4204 at appropriate angular intervals and store the resulting range data in memory 4214.

The sequence of events is as follows. W (write) is assigned to one clock cycle on a rising edge of the divided A signal. At this point, data from a previous T (laser trigger) is available and stored in memory 4214. T is assigned to the following clock cycle, which triggers the laser and inputs the resulting range data to the memory input bus 4226. This data is written on the next W pulse, repeating the cycle.

The ultimate task of the buffer circuit 4214 is to transmit the sample data to a computer 4212 for processing. Completed samples are signaled by the Z and DB signals (the beginning of a sample is also the end of a previous one). In a complete scan is an interrupt or Associated with the interrupt request line, and remains allocated until either the mirror 4222 has made half a turn, or the processor 4212 acknowledges the interrupt. In the first case, half the revolution of the mirror 4222 is signaled by a subsequent Z-pulse and indicates a timeout condition; the processor 4212 has failed to respond and the data is lost.

In the normal case the break is recognized. Upon receipt of the acknowledgment, STR (data strobe) is allocated and held until IBF (input buffer full) is received. During this time, data is placed on the data bus 4230 and can be read by the computer 4212. Data is valid on bus 4230 until IBF is allocated, at which time STR is no longer allocated and the data is removed from bus 4230. Once the processor 4212 detects the removal of STR, it removes IBF. This causes STR to be allocated for the next data parts, which repeats the cycle.

Sampling data is collected and stored in two memory banks 4214. This avoids problems with shared memory and synchronization between the sample memory and the sample transfer. Data for a new scan is stored in one bank while the previous scan is transferred from the other bank.

The buffer circuit 4214 takes the responsibility of the processor 4212 to synchronize the laser results with the mirror position and to collect individual pieces of data. It allows more efficient use of CPU time when capturing data in one-sample increments. The processor 4212 spends its time processing the data rather than collecting it.

Referring to Fig. 24, the vehicle controls consist of four functional blocks at a low level.

One is called "Vehicle Manager" 4302. A second is called "speed control" 4304. The third is called "steering control" 4306. The fourth is called "Monitor / Auxiliary Control" (shown as two separate blocks 4310 and 4308).

They are all connected by a high-speed serial data bus 4314. Bus 4314 is a data collision detecting packet forwarding system.

Each of these functional blocks has separate microprocessors, such as the 16-bit Motorola 68000 series.

Each of these microprocessors talks to the others over bus 4314 and hears about them.

While each functional block has a more or less specific function, the vehicle manager 4302 acts as a communications hub. It sends messages to the Navigator 406 via a 9600 baud serial R5-422 connection 4316 and also receives messages from them. He also listens to the remote control or "teletafel" 410 via an FM radio communication link 4318 and sends to it.