Integrated vehicle positioning and navigation system, apparatus and method

Background of the invention

1. Field of the invention

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.

Second Related Technology

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.

In the NAVSTAR GPS, it is envisioned that there are 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 replacement GPS satellites. 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 acquired 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 of the GPS satellites with each unique gold code sequence.

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-to-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 gimballed north-facing local 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 to 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-33 10 111 discloses a navigation system with drift or deviation compensation. US-A-3630079 discloses a navigation system using multiple sensors and error correction.

EP-A-221643 discloses a visual navigation system for a free-running mobile robot in which the robot has a plurality of beacons mounted to identify its location for fixed overhead vision cameras. The system provides a hierarchical control system. IEEE General of Robotics and Automation, Vol. 4, No. 3, June 1988 discloses a hierarchical control device for an unmanned robot having a task related controller.

According to the present invention, there is provided a multi-task navigation system 406 (multi-concurrent task navigation system) for an autonomous land-based vehicle 102, comprising:

(1) main task means 5316 for coordinating communications between the tasks having means for carrying out high-level decision making;

(2) monitoring vehicle status task means 5308 for reading a communication port 5326 into the vehicle 102 having means for notifying vehicle operating state changes, and means for notifying the state of communication from the system to the vehicle to the main task means 5316 and the further means for writing a vehicle state message to a vehicle have global memory structure 5400;

(3) scanner task means 5310 for providing data from an obstacle detection system 40 to the main task means 5316;

(4) instructions 5320 for fetching instruction tasks for interfacing the system 406 with a host (computer) 4020 having means for receiving, and means for decoding messages from the host 402, and means for transmitting a received and decoded message to other task means;

(5) means 5318 for providing a message to the host for interfacing the system 406 with the host 402 having means for forming messages and transmitting means for transferring messages from the system to the host;

(6) VS position task means 5322 for interfacing a vehicle position determination system 1000 with the system 406 having means for reading an output from the vehicle position determination system 1000; further, checksum means for checking the output for correctness;

Writing means for transmitting the checked output to the global memory structure 5400, and error indicating means for sending a message to the main task means 5316 whenever a position error occurs;

(7) VS attitude task means 5324 for monitoring vehicle position while the vehicle 102 is pulling a track having means for maintaining a plurality of orientations in an alignment buffer 5410 of the global memory structure 5400; and

(8) tracking device task 5306 for calculating the steering and speed corrections for the vehicle 102 having means for reading position information from the position buffer 5412 of the global memory structure 5400, further means for reading alignment information from the alignment buffer 5410 of the global memory structure 5400 and means for Sending the steering and speed corrections to the vehicle 102 to control the vehicle heading.

The present invention also provides a method for operating a multi-task navigation system 406 for an autonomous land-based vehicle 102, comprising the steps of:

(9) coordinating 5316 the communications between the tasks;

(10) performing 5316 high-level decision making;

(11) reading 5308 a communication port 5326 into the vehicle 102;

(12) message 5308 of vehicle operating state changes to a main task 5316;

(13) report 5308 a state of communication from the system to the vehicle to a main task 5316;

(14) writing 5308 a vehicle state message into a global memory structure 5400;

(15) provide 5310 of data from an obstacle detection system 40 to the main task 5316;

(16) interfacing 5320 the system 406 with a host (computer) 402 by receiving and decoding messages from the host 402 and transmitting a recorded and decoded message to another task;

(17) interfacing 5318 system 406 with host 402 by forming messages and transmitting messages from system 406 to host 402;

(18) Interfacing 5322 a vehicle positioning system 1000 with the system 406 by reading an output from the vehicle positioning system 1000, checksum checking the output for correctness, writing the checked output to a position buffer 5412 in a global memory structure 5400, and displaying an error message by sending a message to the main task 5316, whenever a position error occurs;

(19) monitoring 5324 the vehicle position while the vehicle is pulling a lane by holding a plurality of alignments in an alignment buffer 5410 of the global memory structure 5400; and

(20) Calculation 5306 of steering and speed corrections for the vehicle 102 by reading position information from the position buffer 5412 of the global memory structure 5400, reading the alignment information from the alignment buffer 5410 of the global memory structure 5400, and calculating and sending the steering and speed corrections to it Vehicle 102 for controlling the vehicle course.

The autonomous vehicles may be stationary or mobile. In addition, the autonomous vehicles may be at or near the surface of the earth. In other words, the present invention provides a very accurate and fast tracking of any terrestrial vehicle. It provides both devices and methods that allow for superior positioning capability and thus flexible autonomous navigation capability.

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.

In the drawings, the present invention as defined in the claims may be better understood with reference to the text and 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 the 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 an 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 diagram of an embodiment of the alignment ring buffer;

Fig. 12 is a block diagram of a travel tracking control architecture / hardware;

Fig. 13 is a diagram showing relevant alignments in a steering plan cycle;

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

Fig. 15 is a diagram showing how an error vector including a curvature is calculated with the included 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 to 18D are data flow summaries of the navigator 406;

19 is an illustration of a vehicle-mounted scanner 404 (scanner).

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

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

Fig. 22 is a high level speed control block diagram;

Fig. 23 is a high level block diagram of a service brake control circuit of the speed control;

Fig. 24 is a block diagram of a speed control control circuit of the preferred embodiment;

Fig. 25 is a block diagram of a steering control circuit;

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

Fig. 27 is a communication diagram showing a memory of a navigator shared by the navigator;

Fig. 28 is a flowchart relating to execution decisions;

Fig. 29 is a flowchart of the relationship / connection of execution flowcharts 5600A to 5600D of the respective Figs. 26A to 30D.

Figs. 23A to 29D are execution flowcharts 5600A-5600D respectively of the high-level execution flowchart;

Figs. 30A to 30R are respective flowcharts 5700A to 5700R respectively showing "action-on-blocks" of the execution flowcharts;

Fig. 31 is a high level flowchart of the relationship of the respective Figs. 31A to 31C; and

Figs. 31A to 31C are respective flowcharts 5800A to 5800C showing the "work on state block" in each of the execution flowcharts 5700A to 5700Q.

(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 in the preferred embodiment of the present invention.

(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 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 108 m / s.

(3) "Antiselective availability" refers to a method / technique for detecting and compensating corrupt 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 determined in the basic correlation derivation technique of Part II.F.2.d. used this font.

(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. Base position estimation is described in the basic residue derivation technique in Part II.F.2.c. this font calculates.

(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 calculated at the speed of light or at 2.998 x 10 8 ohms. Meters per second multiplied. 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, ground recipients may, for example, take the form of a vehicle or a base station.

(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 the system of the present invention for receiving signals from a terrestrial positioning system and for deriving first position estimates of vehicles from the recorded signals. In the preferred embodiment, the GPS processing system receives 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. In the preferred embodiment, the architecture / hardware (components) of the host processing system is 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. In the preferred embodiment, the inertial reference unit is part of the motion positioning 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. In the preferred embodiment, 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 filter is 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. In the preferred embodiment, the move 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 requires 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, which 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. In the preferred embodiment, 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. In the preferred embodiment, electromagnetic signals, similar to those from the GPS satellites, are transmitted from land-based pseudolites. One or more pseudolites can 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. In the preferred embodiment, 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. In these methods, for example, an original derivation technique 1500 (part II.F.2.a), a parabolic derivation technique 1600 (part II.F.2.b), a base residual derivation technique 1700 (part II.F.2.c), and a base correlation derivation technique 1700A (part II.F.2.d) included.

(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 of the present invention for deriving 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. In the preferred embodiment, position estimates from the vehicle positioning system are referred to 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, in the preferred embodiment, the first position estimate of the GPS signal 716 is weighted heavier 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, since the former is more accurate. In the preferred embodiment, the speed measured by the GPS processing system is not used at all, but could 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.

II. General Overview

FIG. 1 illustrates a high-level block diagram 100 of the preferred embodiment of the present invention. To provide for the accurate autonomous operation of a vehicle 102 at or near the earth's surface, the present invention 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.

A. Vehicle Positioning System (VPS)

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 of the present invention, 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.

In the preferred embodiment, the NAVSTAR GPS is used. Fig. 1A illustrates the NAVSTAR GPS. GPS satellites 130-168 travel around 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 of the present invention to improve the accuracy of the vehicle position estimate.

In particular, the VPS 1000 of the preferred embodiment is a positioning system based on the use or inclusion of GPS data from the NAVSTAR GPS 104 and a motion positioning system 900. In the preferred embodiment, the motion positioning system 900 includes a 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. In order to increase the accuracy of the first position estimate, the present invention implements a number of methods, which are discussed in detail below. 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.

B. Navigation system

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.

In the preferred embodiment, 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 re-fitted to 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. These mathematical curves will be discussed in detail later in this document.

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 shutdown by 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).

C. Base Station

The present invention may include a host processing system 186 in a base station 188. The host processing system 186 performs functions for both the VPS 100 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 host processing system 186 implements a number of methods for improving the accuracy of the vehicle position estimates. The satellite position prediction method 1800 (part II.G.) discussed above is also implemented by the host processing system 186. The host processing system 186 will recognize the same satellite constellation observed by the vehicle 102.

Calculations are performed on the GPS data and / or the pseudolite data to derive deflections (biases). The term "bias" in the context of this document refers to a difference between two measurements, usually position estimates (spatial derivative) or clock rates (clock derivative). Because one measurement is usually known to be more accurate than the other, the derivation or often referred to the bias as an "error".

To calculate spatial derivatives, the host processing system 186 implements a number of methods. Among these methods, for example, there are provided an original derivation technique 1500 (part II.F.2.a.), a parabolic derivation technique 1600 (part II.F.2.b.), a base residual derivation technique 1700 (part II.F. .2.c.), And a base correlation derivation technique 1700A (Part II.F.2.d.).

The foregoing differential correction techniques compensate for data errors. In other words, the biases computed in the host processing system 186 indicate data errors. As shown by an arrow 194, the leads are transferred to the GPS processing system 700 of the vehicle 102. The GPS processing system 700 uses these biases to eliminate errors in the vehicle position estimates.

The host processing system 186 further provides functions related to the navigation system 1022 of the present invention. The host processing system 186 serves as the highest control level of the navigation system 1022, as indicated by an arrow 196. It handles the scheduling and scheduling of the vehicle 102 with exactly the same results as a human dispatcher would achieve. As a result, the host processing system 186 may thereby determine the duty cycle of the vehicle 102.

The host processing system 186 commands the vehicle 102 to proceed from a current position to a future position via a predetermined route so that the vehicle 102 can perform its work objectives. The host processing system 186 may specify the vehicle routes by name, rather than by listing each point along the route, as is conventionally the case. Accordingly, the on-board navigation system 1022 of the vehicle looks up the designated vehicle route and transmits the named vehicle route into sets of nodes and segments along said vehicle route.

III. Vehicle positioning system

A. Overview

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

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 by the present invention to produce a highly effective position determination 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 one ( any) pseudolit (s) 105 in the field of view of the antenna 702. In the preferred embodiment, 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 in the preferred embodiment. 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 706 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. In the preferred embodiment, 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 700 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.

As shown by an arrow 194, the spatial derivatives and timing derivatives are transmitted to the GPS processing system 700 of the vehicle 102. The GPS processing system 700 uses these derivatives to eliminate errors in the vehicle position estimates.

B. GPS processing system

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. In the preferred embodiment, the terrestrial positioning system comprises the NAVSTAR GPS currently being developed by the US government and / or terrestrial pseudolites.

1. NAVSTAR GPS

As shown in Figure 1A, 24 handcrafted GPS electronic satellites 132-170 are currently provided in six orbitals 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. It is also 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 due to 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.

In addition, the NAVSTAR GPS provides two modulation modes of the carrier wave, using a pseudorandom number (PRN). In a mode referred to as "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 pseudorandom 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 1023 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 pseudo-random 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 consequence, the terrestrial position of the vehicle 102 can also 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.

In order for the earthmoving receivers to distinguish the various C / A signals from the various orbiting GPS satellites, 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 from 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 or Cross correlation for two gold code sequences having a length of 1023 bits is about 16 times 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 into the same gold code sequence or hang up, which was transmitted by one of the GPS satellites.

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

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

Referring to FIG. 7, the GPS processing system 700 processes the GPS data from the GPS satellites 132-170 and the pseudolite data from any pseudolite (s) 105. In addition, the GPS receiver 706 decodes the C / Cs. A signals from the various GPS satellites 132-170.

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.

Second business

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. In the preferred embodiment, both the C / A code and the carrier frequency are on receive the GPS antennas 312 and 316 for processing.

In addition to the four GPS satellites shown in FIG. 6, there are the pseudolites 105. The pseudolit 105 may be strategically located around the circumference of any mine pit, and the GPS may Satellites 200, 202, 204, and 206, as shown in FIG. 6, 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 pseudolite (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 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. Moreover, the distance (range) between the vehicle 102 and the pseudolite (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 in the present invention. 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. In the preferred embodiment, 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 data exchange between the base station 188 and the vehicle 102. The exchanged data type will be discussed further below.

A radio transceiver, which functions suitably as the data radios 620 and 622 in the preferred embodiment, is commercially available from Dataradio Ltd., Montreal, Canada, under model number DR-4800BZ.

Referring to Figure 7, the preferred embodiment of a GPS processing system 700 is shown. The GPS processing system 700 of the vehicle 102 includes a GPS antenna 702. In the preferred embodiment, the GPS antenna 702 receives the radio spectrum of electromagnetic radiation. However, the present invention also contemplates receiving any signal through which GPS satellites 132-170 could encode data. In the preferred embodiment, 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. In the preferred embodiment, a clutch is generally electronic and corresponds to any of numerous 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 present invention contemplates any method by which the received signals can be amplified. In the preferred embodiment, the preamplifier 704 is the commercial or commercially available model number 5300 preamplifiers, GPS Rf / IF series 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 calculates 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. Moreover, in the preferred embodiment, the GPS receiver 706 may process in parallel all of the actual pseudoranges for the GPS satellites 200, 202, 204, and 206.

In the preferred embodiment of the present invention, the GPS receiver 706 generates this data when four or more GPS satellites are visible.

The GPS processing system 700 (in the GPS processor 710) may calculate the first position estimate, with an accuracy of approximately 25 meters, when 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 of the preferred embodiment 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 well known in the art.

In the preferred embodiment, 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 (specifically, the GPS processor 710) the calculation of the third position estimate.

In the preferred embodiment, 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.

Because of the receiver type used in the preferred embodiment, the GPS receiver 706 is coupled to a GPS communications processor 708. In the preferred embodiment, 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 communication processor 708 transmits the above information to the GPS processor 710. In the preferred embodiment, the GPS processor 710 includes the 68020 microprocessor commercially available from Motorola Inc. FIG. 8 is a low level flow chart 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. The Kalman filter 802 is well known in the conventional art. In the preferred embodiment, the GPS Kalman filter 802 is a module in the software of the GPS processor 710.

For the best mode of the present invention, the threshold of the GPS Kalman filter 802 does not vary continuously or at very small separate intervals. Rather, the intervals are larger discrete intervals and therefore less accurate than a continuously varying filter. However, the GPS Kalman filter 802 of the present invention is easy to implement or provide less costly and requires less computation time than with a continuously varying filter. However, it should be understood that the use of a continuously varying filter is possible and that it is intended to be included herein.

For operation, the GPS Kalman filter 802 must be given an initial value at system startup. From the initial value and the GPS data collected by the GPS receiver 706, the GPS Kalman filter 802 extrapolates an on-going state (having the first position estimate and vehicle speed for north, east, and elevation). The GPS Kalman filter 802 operates in a cyclic manner. In other words, it is assumed that the extrapolated running or Actual state is the initial value for the next iteration. It is combined / filtered with new GPS data (an update) to derive a new current state.

The manner in which the GPS data is used depends on a previously stored file called control file 820. The control file 820 will determine: (1) the noise threshold, (2) the response speed, (3) the initial states of vehicle position and velocity, (4) the amount of deviation before a reset or Resetting of the GPS Kalman filter 802 occurs, (5) the number of allowed bad measurements, and / or (6) the time that is distributed between measurements.

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 explanation for storing 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. In the preferred embodiment, the first estimated position (and vehicle speed as 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.

FIG. 8 illustrates other functions of the GPS processor 710 in the preferred embodiment. 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 or 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. In the preferred embodiment, IPROTO function 804 is Model No. XVME-081, which is commercially available from Xycom Inc.

As shown in a flowchart block 810, the data transmitted over the communication channel 618 enters the IPROTO function 804. Many of these data are ultimately destined for the GPS Kalman filter 802. The communication manager function shown at flowchart block 808 coordinates the incoming data from the IPROTO function. The communication manager function 808 also coordinates the data received from an ICC function shown in a flowchart block 812. The ICC function 812 exchanges data with the data radio 714 (via the GPS Intercommunication processors 720) and with the GPS data collection device 718 as shown.

The GPS console 712 is well known in the art. Many types of devices are commercially available that provide the desired function. Such a device is commercially available from Digital Equipment Corporation, Maynard, Massachusetts, under the 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. Such a device is commercially available from Digital Equipment Corporation, Maynard, Massachusetts, under the 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 preferred embodiment is model no. MVME331, which is commercially available from Motorola Inc. USA.

The data radio 714 directs 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). In the preferred embodiment, 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.

C. Movement Positioning System (MPS)

The MPS 900 (MPS = motion positioning system) of the preferred embodiment 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 preferred embodiment provides for the combination of the odometer 902 and the IRU 904. However, the IRU 904 could be used without the odometer 902. The odometer and 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-SR01 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 used in the preferred embodiment 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 compensate for the low dynamics and / or speed , take into account dynamic effects (e.g., speed) exhibited by 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, in the preferred embodiment, 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 preferred embodiment that the direct output of the IRU 904 has drifted counterclockwise from the north direction during operation. The drift or Deviation depends on the direction in which the vehicle 102 and consequently the IRU 904 is running.

Moreover, the drift can be defined by an IRU deviation equation. The IRU deviation equation may 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 used to extrapolate more accurate second position estimate.

In the preferred embodiment, communication 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.

D. Vehicle Positioning System (VPS)

Referring to Figure 10, the preferred embodiment of the architecture of the VPS 1000 (VPS = Vehicle Positioning System) is depicted.

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 present invention moves any system and method by which the signals indicated by arrows 716, 908, and 910 can 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.

In the preferred embodiment, 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 third position estimate 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, Minnesota, 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 used successfully 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.

E. Base Station

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.

In the preferred embodiment, 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.

In the preferred embodiment of the present invention, the host processing system 186 at the base station 188 further coordinates the autonomous activities of the vehicle 102 and provides an interface for the VPS 1000 with the human monitors.

F. Satellite-based accuracy enhancements

The present invention improves the accuracy of the position estimates of the vehicle 102 over 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.

In the preferred embodiment, the host processing system 186 at the base station 188 is responsible for performing these differential techniques and delivering the results to the vehicle 102. It will be understood that the host processing system 186 also includes the GPS processing system 700 as the vehicle 102 has. The term "differential" is used because the base station 188 and 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.

IV. Navigation system

A. Overview

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 position determination system part of the present invention as discussed in Section II 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 domain of the navigation system part of the present invention, which is discussed in this section (III).

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 of the present invention could foreseeably include off-ground operations, for example, mining on the moon, provided that the necessary GPS satellites are placed in orbit of the moon.

In a typical application of the present invention, as shown in Fig. 3, there are three basic work areas with respect 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 present invention, autonomous position determination 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 types:

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.

432nd VPS control:

These are commands that have been given to the vehicle positioning system to turn it on or shut down and toggle 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, in the preferred embodiment of the present invention, 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. In an alternative embodiment of the present invention, portions 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 for the present invention, this may not be a factor.

Another factor in determining the particular location of elements of the system of the present invention 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 it would take to navigate while traveling 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 function of the present invention will be discussed below.

B. route planning / path generation

1. introduction

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

Path generation uses intermediate goals from a level planning device to generate a detailed path that the vehicle 102 should 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 inputs 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 developed for the present invention which deviate from the traditional vehicle control scheme in which a time history of the position (a trajectory) is provided in the schedule set for the vehicle 102.

These methods are suitably called "path tracking" in that the steering movement is decoupled from time; that is, steering motions are directly related to the geometric nature of the fixed path, which makes 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 4406, the insertion of the gear 4610, the acceleration to the commanded speed limit, the steering of the steering wheel 4910, the avoidance of obstacles 4002, etc. may include), the autonomous navigation system of the present invention operates in a similar manner. As used in the system of the present invention, a "route" is a sequence of contiguous "segments" between the beginning and 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.

The determination of which layers are required to define a path segment by analytical methods, experimental methods or a combination of both is called "path planning" according to the present invention. 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 22, which illustrates these concepts of the present invention).

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

In an actual world example of the present invention, 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 of the present invention (discussed below) 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. By using free-form curves, a more robust (semi-automatic) method of fitting routes to data collected by driving from the vehicle over the routes is used by the present invention.

Referring to FIG. 4, 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 of data and inefficiencies in giving instructions are avoided in the present invention.

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.

Second Route generation and storage

a. introduction

In one embodiment of the present invention, 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 drive data and organized into routes for the aforementioned method.

An application on an Apollo computer workstation (now Hewlett-Packard, Palo Alto, California) (not shown graphic display system) has been developed to graphically fit route data to the stored trailing 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. In one embodiment of the present invention, the storage device used is a blister storage cartridge 5302 having 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 may be predefined in the present invention, or they may be generated 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.

b. route definition

In one embodiment of the present invention, the following method is used for route definition.

1. Define nodes and segments that make up the routes. Put the node and segment data in an array called "route data arrangement". Each record in the array contains the following information:

1. Type of part (ie node, linear segment, circular segment and end-of-route marker)

Second If it is a node part, define the longitude and latitude coordinates of the node.

Otherwise, if it is a linear segment part, define the velocity along the segment.

Otherwise, if it is a circular segment, define the latitude and longitude coordinates of the center, the radius, the direction in which the circle passes (ie, clockwise or counterclockwise), and the velocity along the segment)

Otherwise, if it is a mark of the end of the route, there is no further information.

Second Connect the node and segment data to each other in sequences. The sequences are simply an array of indices in the route data arrangement. Each sequence must begin with a mark of the end of the route followed by a node, then the rest of the sequence will alternate between segments and nodes until the sequence is terminated by another mark of the end of the route. An example sequence would be 1, 6, 3, 4, 7, 9, 10, 23, 78, 1 where the integers are indices in the route data array.

Third Finally, define a route by setting an index in the order of succession, and defining whether to run indexically through the sequence in the positive or negative direction. Place the index and index direction in an array called the "route description arrangement" (the routepec arrangement). A part of the route description arrangement may look like this:

6.1 this description defines a route that starts at node 6 and is indexed in the positive direction.

78, -1 This description defines a route that starts at node 78 and is indexed in the negative direction.

A user simply tells the vehicle which part in the route description arrangement to use as a route.

4th The aforementioned data is stored in the storage device in the order in which they were defined in steps 1 to 3.

C. Navigator route usage

The following describes how navigator 406 uses the defined routes from the above method of the present invention.

When the navigator 406 is turned on, it reads the route information from the storage device 5302 and stores it in the random access memory (RAM) in the syntax already shown.

Next, the operator sets a route to follow the vehicle 102. Again, the route is simply an index to the route description arrangement.

When the navigator 406 decides that all systems are ready for automatic operation, it sends a message to the VPS_Location task 5324 to cause it to operate.

The VPS_Lage task 5324 then determines the position along the route that is closest to the current position 2812 of the vehicle 102. The search for the next position 284 on the route proceeds as follows:

1. A pointer is set to the first segment in the route.

Second The vertical distance from the vehicle position to the segment is determined.

Third The pointer is moved to the next segment in the route.

4th The vertical distance from the vehicle position to the next segment is determined.

5th Repeat steps 3 and 4 until the end-of-route marker 2218 has been reached.

6th Determining the distance from the vehicle position to the endpoints 2218 of the route.

7th Set a counter to the route segment which had the closest distance and store the coordinates of the next distance.

The VPS_Lage task 5324 then uses the description of the route (lines, arcs, and velocities) to create a location at one meter intervals. Task 5324 creates a predefined distance of plies plus a safety margin and places the plies in a buffer 3000. To create a ply one meter from a given ply, VPS_lay task 5324 uses the following procedure:

1. Determining the type of segment from which the given position was generated.

Second Apply the proper formula for the type of segment to determine the change in length and width per meter of segment length.

Third Adding the change in length and width per meter to the last given location.

4th If the created location is beyond the end of the current segment, set a pointer to the next segment and repeat steps 2 and 3, otherwise return to the created location.

The VPS_Layer task 5324 then informs the executive 5316 that it is ready to be tracked.

When the autonomous vehicle 102 moves along the position in the buffer 3000, the security frame 3006 is cleared.

If the security frame is below a specified size, the VPS_lay task 5324 creates another security frame 3006 of layers and attaches it to the current buffer 3000. The VPS_Lage task 5324 clears the location buffer 3000 by monitoring the current position 2812 of the vehicle 102 and moving a pointer 3002 into the buffer 3000 to the next location. The position buffer 3000 is constructed as a ring, which is passed through in a clockwise direction (see FIG. 30, storage buffer). That is, layers are arranged in the ring so that the direction of vehicle movement corresponds to passing the bearing-in buffer 3000 clockwise. Therefore, as the vehicle 102 moves, the pointer 3002 will be moved to the next location in the buffer 3000 in a clockwise direction. When the pointer 3002 is moved clockwise, the memory in the ring is vacant (counterclockwise from the pointer) to be overwritten.

Step 7 (in the search routine above) is in action until the end-of-route marker 2218 is reset, at which time the VPS_Layer task 5324 stops generating a location, and the executive 5316 is informed that the end of the Route was reached.

As mentioned above, a path is like a series or sequence of contiguous "layers". The location includes the speed and longitudinal angle that need to be tracked. A ply may have the width, length, orientation, curvature (1 / radius of curvature), maximum speed, and distance to the next location information.

Third location production

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 according to the present invention 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 one embodiment of the present invention, each layer requires 36 bytes of memory, yielding approximately 36K of memory 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.

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

C. path tracking

1. introduction

Path tracking is a critical aspect of vehicle navigation in accordance with the present invention. 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 the path tracking system 3102 of the present invention.

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 predetermined steering angle, driven wheel speed values, and error components, the steering command and drive inputs are calculated in the present invention.

Second considerations

a. global position feedback

The path to follow is defined in Cartesian coordinates. If the control scheme consists of only one servo controller to reference steering commands, vehicle position and registration errors accumulate. The position and alignment result from the integration of the entire history of the steering and the driving processes. Thus, it is necessary to feed back vehicle position 3304 and alignment 3318 in Cartesian space.

Consequently, reference inputs to the servo controllers are generated in real time based on position feedback 3114 (as shown in FIG. 17).

b. separate steering and driving control

The steering and driving reference inputs are calculated from the given path or vehicle speed in the present invention. This allows for easy path tracking integration with other modules of the present invention, such as collision avoidance.

Third embodiments

a. Tracking Control Structure (FIG. 12)

One of the challenges of autonomy of vehicles is to determine the steering inputs that are required to track a set path. For conventionally steered vehicles, in the present invention, the desired path and speed along the path can be tracked separately, reducing the problem to steering control. (A path for this meeting is a geometric curve that is independent of time, as opposed to a career that is a time history or time sequence of positions.)

Steering angles are planned from the desired path 3312 and sensed vehicle positions. These angles are directed to the vehicle via a steering control device 3104.

The functional block diagram in Fig. 12 shows a tracking control structure according to the present invention.

In kinematic steering schemes, errors in position, orientation, and curvature are reduced based on the geometry of the errors, without consideration of actuator saturation, performance, friction, or mass expressions. Adjustment values, such as the look ahead distance and path curvature selection, are selected through empirical trials and simulations to achieve good performance.

In a manually driven vehicle, the look ahead distance is the distance 3310 in front of a vehicle that a driver sees while driving. The lookahead distance in the present invention is the distance by which the errors in position, orientation, and curvature are scheduled to zero. This varies with the speed of the conventional or autonomous vehicle.

Varying the anticipation distance varies the extent to which steering adjustments must be made to effect a change in the course. The anticipation distance is discussed in more detail in a following section.

However, real vehicles deviate from kinematic idealization, and their tax response deviates accordingly. As the vehicle speed, the mass and the path conditions deviate, the actual vehicle response differs even further from a kinematic idealization. Therefore, kinematic idealization is generally valid only at low velocities with constant states.

An embodiment of the present invention uses a model that has considerations of stiffness, mass and slip angle. The control problem is formulated as a linear quadratic optimal tracking problem where errors in position, orientation, and curvature are minimized based on the vehicle control model.

The optimal path and controls are calculated from the desired path 3312 and the currently sensed vehicle position using the current errors as initial states for the optimal control problem. A few calculated steering angles along the initial part of the optimum path are used as references for the low level steering control device for the next sensing time interval.

This predictive optimal routing design has the advantage of guaranteeing stability and optimal performance with respect to the given performance index. The optimal foresight control method of the present invention is central to the steering planning of an autonomous vehicle.

Referring again to Fig. 12, the inner loop 3116 of the steering controller 3104 is executed on the order of 10 milliseconds while the outer loop 3114 is closed at the rate of 0.25 to 0.5 seconds.

The following procedure is used to close the loop-on position. After sensing the current position Pa, k) 3210, the location is expected at the end of the current time interval (Pa, k + 1) 3216.

Then, the desired alignment at the end of the next time interval (Pd, k + 2) 3218 is calculated at a reference steering angle between (Pa, k + 1) 3216 and (Pd, k + 2) 3218 which are determined.

As mentioned above, these vehicle and path techniques of the present invention significantly decouple the steering control from the speed control of the vehicle.

b. quintic procedure

Shown in the navigator task diagram, Fig. 26, which will be discussed in more detail below, is a functional block called tracker 5306. Tracker 5306 operates to establish a smooth path to the desired or correct path. In an embodiment of the present invention as mentioned above, a quintic method is used. This provides a fifth-order curve in the error space for the steering commands.

The parameter L3310 (look ahead distance) may be set to modify the vehicle's response, and the value L3310 may be selected based on trial and error. This scheme has provided good results at speeds up to about 28 km / h at the time the disclosure of this application was prepared.

The method used by the tracking device of the present invention is as follows:

(1) estimating the next position either by averaging or evaluating the states of the position;

(2) Compensation of delays using any of the estimation methods

(3) dynamic look-ahead changes at different speeds - the coefficients of the quintic method: look ahead distance.

c. Latency and slow system response

An additional path tracking embodiment of the present invention employs various compensation techniques to improve vehicle responsiveness. This is used in conjunction with the quintic polynomial method to realize improved tracking performance.

Some vehicle response characteristics include latency of the vehicle control commands, slow system response, and dynamic vehicle characteristics that have vehicle ground interaction (VGI) (slip angle and understeer / oversteer).

The latency of the vehicle commands has been compensated in one embodiment of the present invention by modifying the vehicle control components to reduce time delays and by using a method that requires control commands far enough to compensate for existing delays.

The reduction in the time delay between when the vehicle position is sensed and when the command is issued reduces prediction errors, which reduction is required to plan steering angles, and results in better tracking performance.

A speed-varying look ahead distance also improves tracking performance compared to the constant look ahead distance.

A tracking method outputs steering and speed commands via a serial connection to a vehicle control system. The vehicle control system is a multi-tasking system or multi-processor concurrent task system that relies on an input loop for inter-task communication.

This mailbox queue consists of two types of series, a high-performance series and an abundance series. During high data rates from the tracking task, the high-performance arrays overflow into the overflow queue, degrading the performance of the inter-task communication. This can result in total latencies between the tracking task and the actual steering actuator commands, which are on the order of seconds.

The dynamic behaviors of the steering can be modeled as a first order lag system. It takes a period equivalent to a first order delay response time constant to reach approximately 63% of the desired final value. As will be clear, for slow systems with large time constants, the response time can be considerable.

In order to solve the latency and response problems, the hardware or components may be adjusted so that they may be used in close conjunction with the tracking method to control the vehicle steering, and a new control scheme may be considered to provide a better control easy time delay and a bad response to compensate.

For example, the components may be set to lie in the same backplane as the processor executing the tracking process and directly controlling the vehicle steering system. This serves to eliminate delays due to the serial connection and serialization.

To compensate for the remaining delays (delays due to the processing time of the tracking process and the communication between the tasks within the tracking system), a method according to the present invention is used which sends speed and steering commands in advance to counteract any delays. The process can be carried out as follows:

Feeling the current position Pist

(Initialization: Pist = P [0] = P [1] = ... = P [d_index + 1])

Calculation of the error between the predicted and the sensed position:

Pe = Pist - P (0) for i = 0, d_index

P [i] = P [i + 1) + Pe

Calculation of the position on the path according to the position of the beginning of the time interval: Calling Pon (P [d_index], Pon)

Calling the initial state: error (0) = P [d_index] - Pon

Calculation of a quintic polynomial curve or fifth order polynomial curve in the error space [1]

Prediction of a position at the end of the planning time interval;

Calling despos (Pon, ds, P + d_index + 1)

P [d + index + 1] + = error (ds)

For example, to compensate for a system having time delays on the order of two scheduling intervals (on the order of 250 ms), the variable d index is set to 2.0.

The tracking performance improves as the compensation index (d_index) is increased to match the delays inherent in the system.

The tracking performance has been improved according to the present invention by examining and understanding the dynamic behaviors of the vehicle and the control system and by designing compensation methods on the premise of these insights.

Weaker performance of the tracking method is due to the latency of vehicle control commands, slow system response, and dynamic vehicle characteristics. It is possible to counteract any of these effects.

The latency of vehicle commands, a dominant effect, can be successfully compensated by modifying the vehicle control components (hardware) and by using a method that requires control commands far enough to compensate for the delays. The reduction of the time delay between the vehicle position is sensed, and when the error is issued, this reduces the prediction errors. This is necessary to plan steering angles and results in better tracking performance.

Varying the look ahead distance with speed also improves tracking performance compared to using a constant look ahead distance.

Generally speaking, path tracking is the function of staying on the course. In the path tracing in the present invention as discussed above, some of the items considered are errors in distance, orientation and curvature, delays in the system, processing delays and delays in vehicle response to actuators, etc. include the dynamic lookahead distance, weighted path history, and extrapolation.

D. Obstacle treatment

1. introduction

The obstacle treatment provides at least three major functions before 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".

E. Vehicle control systems

1. introduction

Referring to Fig. 20, 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). These are again described below.

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 Motorola 68000 16-bit series. Each of these microprocessors talks to and hears about the other bus 4314.

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

Second Vehicle manager (operating states)

As mentioned above, the vehicle manager 4302 receives commands from a remote control panel 410 and the navigator 406. It then decides in which operating state "A, M, T or R" (for autonomous, manual, tele or ready) the vehicle 102 will be should.

a. Ready mode (ready)

Reference is now made to FIG. 21, which shows the states (operating conditions) and how the vehicle 102 changes between states. The Navigator 406 can not set the operating state by itself. It should be noted that the vehicle 102, for example, can not switch directly from telephoto to automatic. In this case, it must first run through the Ready mode (ready) 4404.

The ready mode 4404 causes the vehicle 102 to stop in a known state. This is because it would be difficult to make a smooth transition from, for example, the automatic operating state 4408 to the tele-operating state 4406 while the vehicle 102 is moving. The telephoto panel operating lever 4502, 4504 should be in exactly the right position when the control is switched.

When going from the teleprocess state 4406 to the automatic operating state 4408, there is the consideration that the navigator 406 must initialize. For example, he must determine where he is with respect to a route before taking control, which takes some limited time during which the vehicle 102 could otherwise break out in an uncontrolled manner.

b. Tele mode

The telecontrol mode 4406, also referred to as telephoto, remote, or radio control mode, provides a way to control the vehicle 102 from a remote location while maintaining the vehicle 102 in view.

Workshop personnel, for example, would use the teleprocess state 4406 to move the vehicle 102 in the yard, for example. Advantageously, this operating condition would also have to be used by a shovel or loader operator to maneuver the vehicle into a loading or unloading position and move the vehicle to a location where autonomous operating condition 4408 would resume control.

In telephoto state 4406, each vehicle 102 at an autonomous workstation 300 would have its own unique identification code selected on a radio control panel 410 to ensure communications only with the correct vehicle and control thereof. The vehicle 102 would only respond to the teleprocess commands 4318 when its unique identification code is transmitted. Any conflict between operating conditions, such as between manual operating state 4402 and teleprocess state 4406, would be resolved for obvious safety considerations in case of doubt for manual operating state 4402.

The navigator 406 keeps track of where the vehicle 102 is while operating in the telephoto state 4406, even though the vehicle may be maneuvered in the teleprocess state far from a known route.

c. manual operating state

The manual mode 4402 may be required when the vehicle 102 is maneuvered in very tight environments, such as a repair shop, depot, etc., or when a control subsystem needs to be removed for repair or maintenance.

This control mode can be set up to be invoked whenever a human operator activates any of the manual controls. The simple act of stepping on the brakes 4708, moving the shift lever from some predetermined position for autonomous operation or, for example, grasping the steering wheel 4910 would immediately signal to the control system that the manual control mode 4402 is desired, and the system would immediately open go to the manual operating state.

While in the manual mode, the autonomous system would continuously monitor vehicle motion and maintain an updated vehicle position record so that if and when an autonomous mode 4408 is desired, a faster and more efficient transition could be made.

Again, if autonomous operating state 4408 is desired, the human operator would then act in an affirmative manner to turn on autonomous operating state 4408 by physically moving a switch or lever to the autonomous control mode, for example. A time delay would preferably be set up such that the human operator would have the option of leaving the vehicle 102, if desired. At the end of the time delay, the system would then go through various warning levels, such as lights, horn or the like, indicating that the autonomous takeover of the vehicle 102 is imminent.

d. autonomous operating state

In the autonomous operating state 4408, the ready operating state 4404 (ready) is entered. In the autonomous operating state 4408, the vehicle 102 is under the control of the autonomous navigation system.

In this mode, the vehicle control system receives messages from the navigator 406, as discussed above, by the vehicle manager 4302. The vehicle manager 4302 is basically, as discussed, the communication and command hub for the remainder of the controllers.

The vehicle manager 4302 and the other functional control blocks are all also in communication with the shutdown circuits 4312. The shutdown circuits 4312 will be discussed in greater detail below.

Third speed control

The speed control subsystem 4302 may be organized to include a speed command analysis device, closed loop 4800 for the engine 4614, transmission and brakes 4700, 5000, a real time simulation model of the speed control system, and a monitor 4310 linked to an independent vehicle shutdown system 4312. It is designed to be arranged parallel to the production system in the vehicle 102.

The speed control functional block 4304 performs three basic functions. It controls the governor of the engine 4614. It controls the brake system 4606. And it controls the transmission 4610 via the production transmission control block 4616.

The production transmission control block 4616 interfaces with the speed control block 4304 in a parallel retrofit of the autonomous system in the production system, as shown in FIG. Production Gear Control Block 4616 is a microprocessor-based system that primarily monitors speed and gear shifting accordingly.

Autonomous system speed control block 4304 feeds transmission control block 4616 at the maximum desired gear. For example, if the vehicle 102 is to travel at 15 mph, the largest gear could be the third gear. The production gearbox control block 4616 will control all the necessary circuits to properly access this gear.

The monitor 4626 (FIG. 22) controls the amount of fuel delivered to the engine 4616. Thus, it controls the engine speed. The autonomous system may be retrofitted in parallel with the production monitoring control system in a manner similar to that described above with respect to the transmission system.

The brake system is shown in FIG. The autonomous system can also be retrofitted in the production brake system.

The following discusses the vehicle systems shown in FIGS. 22, 23, 24, and 25. These systems relate to the systems of the 4600 vehicle powertrain and the 4900 steering system.

Referring to FIG. 22, a monitor 4626 controls the engine speed 4222, which in turn controls the vehicle speed 4624. The engine power is transmitted to the drive wheels through the drive train 4600, which consists of the following:

Torque Converter 4612

Gearbox 4610

Final drive 4608

Braking system 4606

Wheels 4604.

The function of these systems is well known in the art.

Various key systems have been modified in accordance with the present invention to effect autonomous control. The main systems were the speed control (engine speed, transmission, vehicle speed and brakes) and steering systems. Each key system is designed with a manual override capability as a safety measure. In all cases, manual control has priority so that when the vehicle is autonomous and an operator takes control of one of the vehicle functions, control is automatically returned to the operator.

The system also provides an emergency override button (not shown) (also referred to as a "panic button") that shuts off all electronically controlled systems when activated and returns the vehicle 102 to manual control 4402.

The system also provides for sensing the pneumatic pressure that is a key part of the operation of some of the key systems. If this pressure falls below a certain preset threshold, it is assumed that there is a problem and the vehicle control system shifts to the manual control 4402 and the vehicle 102 is stopped.

Fig. 24 depicts the system used to control engine speed. This system uses electronically controlled valves 4808 and 4812 to control the pneumatic pressure in parallel with a pedal 4806, which can be manually operated to override the electronic control of the engine speed 4622. The pressure sensor 4802 and the engine speed sensor 4622 provide the necessary feedback for the electronic speed control system 4304.

It is also necessary to control the vehicle speed a transmission control 4616. The basic control system is readily available for the particular vehicle used for this purpose.

In addition to controlling engine speed 4622 as means for controlling vehicle speed, it is also necessary to control vehicle service brakes 4606. This system is shown in FIG. 23 and is necessary to effect the normal stopping or slowing down of the vehicle 102. This system employs electronically controlled pneumatic valves 4712 and 4716 in parallel with a manually operated brake pedal 4708 and / or a retarder. Delay lever 4710 for controlling the braking force. These two manual inputs can override or override the electronic control system when actuated. The pressure sensor 4702 and the vehicle speed sensor 4624 provide the necessary feedback for controlling the braking force.

Control of the vehicle steering is also required for the vehicle to operate autonomously. The system performing this function is shown in FIG. The system consists of a Rexroth 4912 Proportional Hydraulic Valve which can be electronically actuated to provide flow to the hydraulic cylinders 4914 and 4916 mounted on the vehicle steering link. The system also includes a manually operable manual metering unit or HMU 4918 which is in parallel with the electronically controlled system. The manual system may override the electronic system as a safety measure, if necessary. Also, the system provides a switch 4920 on the manual metering unit to detect when the manual steering wheel 4910 is deviating from the center position. If not centered, the autonomous system assumes that the system is being manually operated 4402 and disables the autonomous control of the vehicle 102.

The electronic control of the vehicle parking brake or vehicle parking brake is also provided as an additional security feature.

4th steering control

Referring again to Fig. 20, the steering control function block 4306 is responsible for controlling the steering angle of the vehicle wheels. It sends commands to a valve 4912 to control the steering angle and picks up information from a resolver (not shown) mounted on the drawbar system so that it knows what the actual wheel angle is.

The steering angle can be controlled with an accuracy on the order of one-half degree, and the resolver is accurate to a slightly smaller magnitude, on the order of one eighth of a degree.

At some point in the useful life of the vehicle 102, the resolver may deviate from the setting. When this happens, the vehicle will not be able to track the path 3312 properly.

However, the navigator 406 constantly monitors the vehicle 102 to determine how far the vehicle 102 is from the desired path 3312. (The vehicle 102 is always to some extent removed from the desired path 3812 and the system is constantly correcting.) If the vehicle 102 is away from the desired path 3312 by more than a certain distance, for example, several meters, the navigator 406 stops the vehicle as a safety precaution.

The steering control system 4306 also always checks to ensure that the resolver is accurate and that the received steering commands 420 have not been disturbed by noise (or noise) or other sources of error. A steering simulation model can also be set up as an additional review of the system.

The autonomous steering system 4900 may be configured to be set up in parallel with a manual steering system and may be retrofitted to the vehicle 102 in a manner similar to the cruise control system.

As shown in Fig. 25, the existing or manual production steering system has a manual steering wheel 4910 which rotates a manual metering unit or HMU 4918. The manual metering unit 4918 controls a valve 4912 which controls the flow of hydraulic fluid to the steering cylinders 4914, 4916, which in turn rotate the wheels (not shown).

A switch 4920 on the manual metering unit 4918 detects the position of the steering wheel 4910 out of center as a change indication for manually controlling the steering. An operator who is traveling in the cab can only turn the steering wheel 4910 to turn off the autonomous steering controller 4408.

Under the autonomous steering control 4408, the manual steering wheel 4910 remains centered in the cab, regardless of the position in which the autonomous steering control has rotated the wheels r. There is no mechanical connection between the steering wheel 4910 and the wheels themselves.

Of course, a vehicle 102 may be manufactured on the vehicle without any manual steering system, if desired. To manually drive the vehicle, the telephoto or remote control 410 could be used, or some type of telephoto or remote could be plugged into the side of the vehicle 102 to control it without a radio link 4506 in, for example, tight environments. A seat may be provided for an operator in such situations.

Some discussion of the developed steering model may facilitate a better understanding of the present invention.

a. steering model

The basis for the steering planning device is a three-cycle steering model shown in FIG. 5.1. This model allows the calculation of the required steering angle regardless of the speed of the vehicle.

Φ = tan -1 LC path

To use this model, the desired path 3312 must contain the curvature of the path to be followed. The curvature is the reciprocal of the instantaneous radius of curvature at the point of the curve.

f (s) / p: position curve

f '(s) / p: tangent to the curve or orientations

f "(s) / p: curvature at this point

This is also equivalent to the second path derivation at this point.

In general, and as shown in FIG. 14, it is required that the path 3812 be continuous in position when a layer 3314 as the quadruple or quadruple of the parameter position 3320, orientation 3318 and curvature 3316 (x, y, 0, c) is desired is. In addition, the extent to which the steering movements are likely to keep the vehicle 102 on the desired path 3312 is related to the linearity of the path's sharpness, since a linear curvature along a path means a linear steering velocity as one moves along the path.

Certain spline curves guarantee positional continuity. However, these spline curves do not guarantee linear curvature gradients along the curves. Clothoid curves 2602 have the "good" property that their curvature varies linearly with the distance along the curve. Paths composed of (a) arcs and straight lines or (b) clothoid segments have been developed.

A path that has unevenness in curvature will result in greater steady state tracking errors. This is especially the case where the actuators are slow.

The path representation must contain sufficient information to calculate the steering angle 3112 (see FIG. 12) needed to travel the desired path 3312, ie, it must consist of at least the position, orientation, curvature, and velocity. A position on the desired path 3312 has been defined as posture 3314, and the structure of the posture in the present invention is given as follows:

c. Location definition

Length: desired length coordinate

Width: desired latitude coordinate

Orientation: desired alignment

Curvature: desired curvature

Speed: desired driving speed

Distance: desired distance between the current situation and the previous situation.

d. location information

The position information 3322 is obtained from the VPS 1000 and is, for example, 71 data bits. The structure of the information used to trace the desired path 3312 is a subset of the 71-bit VPS output and is given by the VPS short definition shown below.

e. VPS short definition

Time: GPS time

Length: WGS84_Length

Width: WHGS84_width

Orientation: Compass direction in which the vehicle is moving

Curvature: calculated by another variable

N_speed: longitudinal speed

E_speed: width speed

Swing rate: rate of change of registration

G_speed: driving speed, distance traveled

f. steering method

The steering planning device calculates the steering angle needed to follow the desired path. If the vehicle 102 was on the desired path 3312, the steering angle is as follows:

On the path Φ steering = f (Csoll) = tat-1 LC

When the vehicle 102 is away from the desired path 3312, the steering angle is:

From the path Φ steering = f (Csoll + Cerror)

The method of the present invention used to calculate C error is a quintic method. The quint is a fifth-order polynomial in a error space that defines a smooth path back to the desired path 3312. The degree of the polynomial is defined by the required data, ie C errors and the known end constraints. Polynomial in the error space:

At S = 0:

Error (0) Position = Current Target Position minus Current Actual Positioning System

Error '(0) Alignment = Current Target Alignment minus Current Actual Alignment

Error "(0) curvature = current desired curvature minus current actual curvature

For S = L (L = expected distance):

Error (L) Position = 0

Error (L) alignment = 0

Error (L) curvature = 0

The coefficients of the polynomial error (s) are functions of L, the distance at which the errors go to zero.

Error (0) = a & sub0;

Error '(0) = a & sub1;

Error "(0) = 2a & sub2;

Error (L) = a 0 + a 1 L + a 2 L 2 + a 3 L 3 + a 4 L 4 + a 5 L 5 + a.

Error '(L) = a 1 + 2a 2 L ++ 3a 3 L 2 + 4 a 4 L 3 + 5 a 5 L 4.

Error "(L) = 2a 2 + 6a 3 L + 12a 4 L 2 + 20a 5 L 3

These five equations are used symbolically for the coefficients a 0, a 1,. solved. Then each coefficient can simply be determined for a reasonable set of limit states.

Once the coefficients of the polynomial have been obtained, the error (s) may be evaluated for some picked_s (which corresponds to a distance along the desired path of s = 0 and is currently defined as:

Recorded = travel speed · planning interval

to get the correction expression:

C Error = Error "(Recorded) Curvature

To calculate the new steering angle:

Φ steering = tan &¹ [(Csoll + C error @ auf recorded) L]

This calculation is performed at each scheduling interval, which is currently 0.25 seconds (dt_plan).

5th Monitoring / auxiliary function

Referring to Fig. 20, the monitor / utility function blocks 4308 and 4310 do certain different functions that are not performed by the other blocks of the vehicle control system. For example, starting or shutting off the 4616 engine, sounding the horn, raising or lowering the charging cradle, turning the parking brake on or off, turning the lights on or off are some of their functions.

The monitor block 4310 also checks the instructions sent from or sent to the other function blocks on the bus 4314 to see if they are valid. If an error is detected, it will notify the shutdown circuit block 4312 and the system will shut down as discussed below.

6th Security system (shutdown, shutdown)

a. introduction

The safety system, which includes the shutdown circuits 4312 (see FIG. 20), acts to stop the vehicle 102 in detecting a plurality of fault conditions in which the parking brake is being adjusted. This has the consequence that the vehicle 102 comes to a safe stop in the shortest possible distance.

Since the parking brake is designed to be normally "on" or "on", the electronic circuits act to release them, ie if the electronic control system (s) fails, the power 5216 becomes the actuators 5006 turned off, so that there is no power to actuate valves, and the parking brake returns to its normal position, which is called "set".

Whenever various erroneous commands are received, or whenever the speed and / or steering simulation models deviate from the vehicle sensor outputs 4622 and 4624 beyond an acceptable tolerance, these are examples of conditions that could result in system shutdown , The shutdown system 4312 is an independent subsystem separate from the other autonomous control subsystems (see FIG. 20).

b. Shutdown control

One feature of the design of the vehicle control system 4312 is that all functional blocks can detect errors in the outputs of the others on the serial bus 4314. Thus, if one of them senses that another is not functioning properly, it may send a signal to shutdown circuits 4312 to shut down the system.

For example, the speed and steering blocks each look at their received commands (received via the vehicle manager 4302 to make sure they are valid.) They also ensure that what they should do, ie, what to command, within If not, they will act to shut down the system.

The safety system may also monitor oil, hydraulic and pneumatic pressures, and temperatures, for example, ensuring that they are sufficient to safely operate and control the vehicle.

The safety system includes manual override switches having a panic stop 5208, switches on the brake pedal 5202 and steering wheel 5206.

7th bus architecture

The bus 4314 connecting the functional units 4302, 4304, 4306, 4308, and 4310 of the vehicle control system is a common serial data bus that is set up in a ring structure using a data packet collision detection scheme.

F. Functional Descriptions / Procedures

1. navigator

The following is a description of the navigator 406 shown in Fig. 26 titled "task chart". Each of the diagrammed tasks is discussed below.

a. Main (executive)

In the middle of FIG. 26, a task is labeled "executive" 5316. This task 5316 coordinates the communications between the tasks and for high-level decision making for the navigator 406. One of the major decisions made by task 5316 is when tracker 5306 is to be turned on (off) based on messages received from the other tasks in the system.

b. Monitoring vehicle condition

This task 5308 is shown at the top and right of the main 5316. It acts to read out the vehicle port 5326 and report the operating state changes of the vehicle and the state of navigator and vehicle communication to the "main task" 5316 via the execute queue 5328. In addition, the state of the vehicle 102 is written to a global memory structure 5400 (see FIG. 27).

c. Scanner / scanner

The scanner task 5310, which provides communication to the "main task" 5316 of the data from the obstacle detection system 404, is shown in the lower right hand corner of the task diagram of FIG.

d. Console and console decomposition

The console 5312 and the console divider 5314 are shown just below the "main task" 5316 in the task diagram of FIG. These tasks were developed as a debugging tool during the development of the system. They show and manipulate the states of the navigator 406 according to the user input from a terminal 5302. The console decomposition task 5314 is also used to set the tracking parameters.

e. Get instructions

This task 5320 is shown in the upper left corner of the task chart of FIG. It is part of the host navigator interface 5330. Messages from the host processing system 186 are captured and decoded from this task 5320. Then, depending on the message, the message is either delivered to the "main task" 5316 or to another task. This other task would then formulate a corresponding response from the navigator 406 to the host processing system 186.

f. Message to host

This task 5318, shown just above and to the left of the "main task" 5316, formulates messages from the navigator 406 to the host processing system 186 and communicates them to the host processing system 186.

G. VPS position

This task 5322 is shown on the left side of the task diagram of FIG. The VPS_Position task 5322 reads the output (20 Hertz) from the vehicle positioning system 1000. The data is checked for correctness (for example, by a "checksum"), and if correct, is output to a global memory structure 5400 , the position buffer (VPS_position queue) 5332. The task sends a message to the "main task" 5316 whenever a position error occurs.

H. VPS location

This task 5324 is shown in the lower left corner of the task chart. If the vehicle is tracking, this task will hold the location buffer (VPS_Lage_Schlange) 5334. The task (5324) monitors the vehicle position and retains approximately 50 locations from the current vehicle position in the direction of travel in the location buffer (3000).

i. Tracker

Task 5306 reads the current position 5332 and the location buffers 5334 in the upper right corner of the task diagram of FIG. 26. Based on the information read out, task 5306 calculates the steering and speed corrections 420. It sends them to the vehicle 102, causing the vehicle Course of the vehicle is controlled.

j. Navigator (shared) global storage

As mentioned above with reference to navigator tasks 5300, navigator 406 has a global memory structure 5400 that reads and writes various tasks. This memory structure 5400 is illustrated in FIG. 27.

Referring to Fig. 27, the tasks are depicted as ellipses with the specific tasks written therein. The memory 5400 is depicted in the middle portion of Fig. 27 as a stack of boxes. The unprotected memory is depicted as a single box in the stack of boxes. A semaphore protected memory is depicted as a box within a box in the memory.

An arrow points in the direction of the data transfer between the tasks and the memories. Therefore, a write from the memory to a task is shown as a line with an arrow pointing to the memory in question from the task. Likewise, a read from the memory by a task is shown by a line with an arrow pointing to the task in question from memory. Where a two-way data transfer occurs between the task and the memory, a line with an arrow is shown at both ends.

k. Main (exec) -Flußdiagramme

FIGS. 28 and 29A-29D are flowcharts of the navigator main or executive tasks 5316.

With reference to Figure 28, this is a diagram of the general structure of the main or executive task flow. The following describes various flowcharts associated with navigator executive tasks 5316.

Referring to Fig. 28, which is an executive flow chart, these five blocks show: block 5502, which is the start block; block 5504, which is the navigator initialization; block 5506, which is the wait for execution queue block, block 5506, which is the executive decision block; and block 5510, which is the effect-on-state block.

The flow chart of Fig. 28 describes how the executive task 5316 performs its functions starting from turning on (power on) the navigator 406. At power-up, the executive task 5316 (or executive) starts at the start block 5502 and proceeds immediately advancing to initialize the navigator 5504, with the executive 5316 setting the navigator 406 to a known initial state. The executive then proceeds to the queue execution queue 5506 and waits for a message from a number of sources to arrive in its message queue 5328. For example, a typical message could be a request for information from the host processing system 186.

Upon receiving a message in the execution queue 5328, the executive 5316 proceeds to the executive decision block 5508. In this block, the executive 5316 sets a series of state flags in a known manner. These flags place the navigator 406 in a known state corresponding to the received message.

Once the state flags have been properly set, the executive 5316 then advances to the active-on state 5510, where the necessary effect is performed, in accordance with the received instruction.

With reference to Figs. 29A-29D, these show the flow of the "executive decision block" 5508 of the general structure diagram of Fig. 9.

The various responses which the Executive Task 5316 can initiate will now be discussed in more detail. There is a known set of messages expected within the execution queue 5328. These messages are shown in detail in Figs. 29A-29D. Fig. 29A diagrammatically illustrates the organization of Figs. 29A-29D. Figures 29A-29D describe in detail the procedure that the executive 5316 uses to address different messages.

With reference to Figure 29A, the effect of the executive 5316 on particular messages will be described. Upon receiving a message on the execution queue 5328, the program flow leaves block 5506 and proceeds to block 5602, where the executive 5316 determines whether the message is "new route instruction". If the message is "new_route_instruction", then executive 5316 proceeds forward to the "new_route" instruction block 5604. Once an action has been successfully completed specifically for the new_out_out instruction, then the executive 5316 then advances to the active-on-state block 5510. Once the action has been completed, the executive 5316 returns to the control room Execution queue block 5506 to await another message. If the initial message is not "new_route_instruction" at block 5602, then executive 5316 proceeds to block 5606 to determine if the message is "instruction_to_change_out".

Responses to messages such as "command_for_change", "vehicle_response", "no_vehicle_response", and "vehicle_check_error_error" follow a similar procedure to that described for the message "new_ride_instruction". However, the actions performed in the action on "..." blocks 5604-5620 are different for the other possible messages. The different types of valid messages and a brief description of each are as follows:

New_route_instruction: Set the number of routes to follow the vehicle.

Instruction_to_change_gang: Assign a maximum possible gear for which the vehicle can drive over a specific part of the route.

Vehicle Response: The vehicle is responding to commands properly, set navigator health flags to Healthy.

No_Vehicle Response: The vehicle does not respond to commands, stop vehicle.

Vehicle Checksum Error: The vehicle does not receive / feel data correctly, stop vehicle.

Tele, Manual, Done or Auto: set the operating condition of the vehicle in the proper order.

VPS_Time overflow: The vehicle positioning system does not send any data, stop the vehicle.

VPS_Checksum Error: Vehicle Positioning System (VPS) sends distorted data, stop vehicle.

VPS_location_ready: ready to create path layers.

VPS_Position finished: Vehicle positioning system data is available.

VPS_Position_Assignment: Initializes the vehicle positioning system, do not move the vehicle.

End of the route: The vehicle is approaching the end of the current route, informing the host processing system.

Scanning_ready: The scanning system is ready to search for objects in the path.

Scanning_all_free: No objects have been detected in the vehicle path, continue normally.

Sampling_obstruction: An object has been detected on the vehicle path, stop the vehicle.

Pursuiter_outside_course: The vehicle does not follow the desired path within the tolerance, vehicle stop.

Tracker_route_end: Tracker has reached the end of the path, stop vehicle.

Tracker_stopped: Notifying the navigator that the tracking task has stopped the vehicle.

The answers to the messages "Tele", "Manual", "Auto" and "Done" are somewhat different because these messages are related and need to be executed in special order. This has been described above. The program flow for these messages is shown in Figs. 29A and 29B with reference to block 5622-5630.

The response to subsequent message possibilities is depicted by blocks 5632-5678 in Figs. 29B-29D. These responses are similar to those described for the "new_route_instruction" message.

If the received message is not one of the expected messages, or if the message is skewed, then executive 5316 is directed to block 5680, where the host processing system 186 is notified of the problem. The executive 5316 then returns to the execution queue 5506 to respond to the next message in the queue.

Figures 30A-30R show the special procedures that the executive 5316 uses to respond to a particular message. For example, Fig. 30A shows in detail how the executive 5316 responds to a "new_route_instruction" message. Once this message arrives in the execution queue 5328, then the executive 5316 then proceeds to a flowchart block 5702 to determine what the message is: in this case, "instruction_for_new_route". If the message is "new_route_instruction", then the executive 5316 then proceeds to a flowchart block 5705 to respond to the message. Otherwise, it proceeds to a flowchart block 5704 to determine if it is valid (one of the other possible messages) or invalid.

Given that the message is a "new_route_instruction", then the executive 5316 follows the process described in Figure 30A to address the message. This process is depicted by blocks 5706-5714. In this procedure (and in response to other instructions), the executive 5316 checks the states of the different tasks within the navigator 406 and responds to those states in a known predetermined manner.

The effect of this response is to set a series of state flags that will cause subsequent responses from other tasks in the navigator 406 when the executive 5316 reaches the active-on state 5510. The actual procedures established in block 5510 are shown in FIG.

The replies of executive 5316 to other valid messages are similar to those described for the "new_route_instruction". The effect of each response to instructions first changes a set of flags, which in turn affects the state of the navigator 406. The special flags set depend on the specific instruction. The navigator 406 responds to the changes of these flags when the executive 5316 moves to the active-on state block 5510.

FIGS. 31A-31C illustrate the flow of the "act-on-state block" 5510.

The "action-on-state block" 5510 is shown in Figs. 31A-31C. FIG. 31 shows the relationship of FIGS. 31A-31C, wherein each of these three figures depicts part of the active-on-state block 5510.

Once the executive task 5316 has set the corresponding flags in response to a particular execution message, the executive 5316 then proceeds to send messages to the appropriate tasks or devices that need to be notified of changes in the navigator 406 system as a result of the execution message.

For example, if executive task 5316 exits executive decisions 5508 and enters work-in-action block 5510 first, it checks to see that the state is set to provide the vehicle for the autonomous operating state (For example, vehicle positioning system is finished, vehicle is communicating properly, a proper route has been instructed, and the vehicle is ready for automatic operation). See block 5802. If one or more of these conditions is not met, then the executive returns to wait for another valid message. If all of these conditions are met, then the executive 5316 checks to see that the path generator 5804 is operating. If so, then the executive 5316 then proceeds to start the other systems required for autonomous operation.

If the path generation system is not operating, then executive task 5316 sends the message "VPS_location_dependent" to the VPS location queue 5334 to start the path generator. The executive task will then return to the wait for execution queue 5506 to wait for another instruction to ensure proper operation of the vehicle 102.