DE69033979T2

DE69033979T2 - Integriertes Fahrzeugpositionier- und -navigationssystem, dessen Vorrichtung und Verfahren

Info

Publication number: DE69033979T2
Application number: DE69033979T
Authority: DE
Inventors: Walter J Bradbury; House Broadgate; Dana A Christensen; Richard G Clow; Lonnie J Devier; Douglas W Friedrich; Adam J Gudat; Carl A Kemner; Karl W Kleimenhagen; Craig L Koehrsen; Christos T Kyrtsos; Norman K Lay; Joel L Peterson; Prithvi N Rao; Larry E Schmidt; James W Sennott; Gary K Shaffer; Wenfan Shi; Dong Hun Shin; Sanjiv J Singh
Original assignee: Caterpillar Inc
Current assignee: Caterpillar Inc
Priority date: 1989-12-11
Filing date: 1990-12-10
Publication date: 2003-01-23
Anticipated expiration: 2010-12-11
Also published as: EP0936516A3; EP0936519B1; EP0936518A2; JP3321115B2; EP0936518B1; JP2000029519A; DE69033831D1; DE69034047T2; DE69026274D1; EP0936520A2; DE69026274T2; EP0936521A3; EP0679974A3; EP0507845B1; EP0679974A2; EP0936517A3; EP0936518A3; AU642638B2; DE69033753T2; DE69034068D1

Description

Hintergrund der Erfindung

1. Gebiet der Erfindung

Die vorliegende Erfindung bezieht sich auf Positionsbestimmungssysteme und insbesondere auf ein Positionsbestimmungssystem und ein Verfahren zur Bestimmung der terrestrischen Position eines autonomen Fahrzeuges auf oder nahe der Erdoberfläche.

2. Verwandte Technik

Verschiedene nationale Regierungen, einschließlich der Vereinigten Staaten von Amerika (USA) entwickeln gegenwärtig ein terrestrisches Positionsbestimmungssystem, auf das im allgemeinen als globales Positionsbestimmungssystem (GPS) Bezug genommen wird. Bei einem GPS wird eine Anzahl von Satelliten in einer Umlaufbahn um den Planeten Erde angeordnet. Die GPS-Satelliten sind ausgelegt, um elektromagnetische Signale zu senden. Aus diesen elektromagnetischen Signalen kann die absolute terrestrische Position (Position mit Bezug auf den Erdmittelpunkt) von irgendeinem Empfänger auf oder nahe der Erdoberfläche absolut bestimmt werden.
Die US-Regierung hat ihr GPS "NAVSTAR" genannt. Das NAVSTAR-GPS wird von der US-Regierung 1993 als betriebsbereit erklärt. Darüber hinaus entwickelt die Regierung der Union der sozialistischen Sowjetrepubliken (USSR) ein GPS, welches als "GLONASS" bekannt ist, welches im wesentlichen dem NAVSTAR-GPS ähnlich ist.
Beim NAVSTAR-GPS ist vorgesehen, daß vier umlaufende GPS- Satelliten in jeder von sechs getrennten Umlaufbahnen existieren. Eine Gesamtzahl von 24 GPS-Satelliten wird in der Umlaufbahn sein, und zwar zu jedem gegebenen Zeitpunkt mit 21 GPS-Satelliten im Betrieb und drei GPS- Satelliten, die als Ersatz dienen. Die drei GPS-Satellitenumlaufbahnen werden gegenseitig senkrechte Ebenen relativ zur Erde haben. Die GPS-Satellitenumlaufbahnen werden weder Polarumlaufbahnen noch Äquatorialumlaufbahnen sein. Darüber hinaus werden die GPS-Satelliten einmal alle 12 Stunden um die Erde laufen.
Unter Verwendung des NAVSTAR-GPS kann die Relativposition von umlaufenden GPS-Satelliten mit Bezug auf irgendeinen Erdempfänger aus den elektromagnetischen Signalen bestimmt werden. Die Relativposition wird im allgemeinen als "Pseudobereich" bezeichnet. Darüber hinaus kann die Relativposition von zwei Verfahren berechnet werden.
Ein Verfahren ist es, die Fortpflanzungszeitverzögerungen zwischen der Aussendung und dem Empfang der sich fortpflanzenden elektromagnetischen Signale zu messen. In dem NAVSTAR-GPS werden die elektromagnetischen Signale kontinuierlich mit der Zeit codiert, mit der die Signale von den GPS-Satelliten ausgesandt werden. Es ist klar, daß man die Aufnahmezeit aufzeichnen kann und die codierte Sendezeit davon abziehen kann, um Zeitverzögerungen abzuleiten. Aus den berechneten Zeitverzögerungen und daraus, daß man die Geschwindigkeit kennt, mit der elektromagnetische Wellen durch die Atmosphäre laufen, können Pseudobereiche genau abgeleitet werden. Pseudobereiche, die unter Verwendung des vorangegangenen Verfahrens berechnet wurden, werden im Zusammenhang mit dieser Schrift als "tatsächliche" Pseudobereiche bezeichnet.
Ein weiteres Verfahren berücksichtigt Satellitenpositionsdaten, die in den elektromagnetischen Signalen codiert sind, die von den umlaufenden Satelliten ausgesandt werden. Almanachdaten bezüglich der Satellitenpositionsdaten des NAVSTAR-GPS sind öffentlich verfügbar. Eine Bezugnahme auf diese Almanachdaten bezüglich der in den elektromagnetischen Signalen codierten Signale gestattet eine genaue Ableitung der Pseudobereiche. Pseudobereiche, die unter Verwendung des vorangegangenen Verfahrens berechnet werden, werden im Zusammenhang mit diesem Dokument als "abgeschätzte" Pseudobereiche bezeichnet.
Jedoch mit Bezug auf das vorherige Verfahren des Ableitens von abgeschätzten Pseudobereichen sei bemerkt, daß die Satellitenpositionsdaten beim GPS-Satelliten nur einmal pro Stunde auf diese Stunde aktualisiert werden. Folglich nimmt die Genauigkeit des abgeschätzten Pseudobereiches mit der Zeit nach jeder vollen Stunde bis zur nächsten Stunde ab, wenn ein neu abgeschätzter Pseudobereich unter Verwendung der aktualisierten Satellitenpositionsdaten berechnet wird.
Während man weiter die Relativposition von mindestens drei der umlaufenden GPS-Satelliten kennt, kann die absolute terrestrische Position (d. h. Länge, Breite und Höhe mit Bezug auf den Erdmittelpunkt) von irgendeinem Erdempfänger über einfache geometrische Theorien berechnet werden, die Triangulationsverfahren einschließen. Die Genauigkeit der terrestrischen Positionsabschätzung hängt teilweise von der Anzahl der umlaufenden GPS-Satelliten ab, die aufgenommen bzw. empfangen werden. Die Verwendung von mehr GPS-Satelliten bei der Berechnung kann die Genauigkeit der terrestrischen Positionsabschätzung steigern.
Herkömmlicherweise werden vier GPS-Satelliten gesampelt bzw. aufgenommen, um jede terrestrische Positionsabschätzung zu bestimmen, und zwar wegen Fehlern, die durch Schaltungstaktdifferenzen zwischen dem Erdempfänger und den verschiedenen GPS-Satelliten beigetragen werden. Taktdifferenzen können mehrere Millisekunden sein. Wenn die Uhr des Erdempfängers mit der der GPS-Satelliten synchronisiert wäre, dann müßten nur drei GPS-Satelliten aufgenommen werden, um die Lage des Erdempfängers genau festzustellen.
Bei dem NAVSTAR-GPS werden elektromagnetische Signale kontinuierlich von allen GPS-Satelliten auf einer einzigen Trägerfrequenz übertragen. Jedoch hat jeder der GPS- Satelliten ein anderes Modulationsschema, wodurch eine Unterscheidung der Signale gestattet wird. Beim NAVSTAR- GPS wird die Trägerfrequenz unter Verwendung eines Pseudozufallsignals moduliert, welches für jeden GPS-Satelliten einzigartig ist. Folglich können die umlaufenden GPS-Satelliten beim NAVSTAR-GPS identifiziert werden, wenn die Trägerfrequenzen demoduliert werden.
Weiterhin sieht das NAVSTAR-GPS zwei Betriebszustände zur Modulierung der Trägerwelle unter Verwendung von Pseudozufallszahl-(PRN-)Signalen vor. In einem Betriebszustand, der als "Grob/Aufnahme-Betriebszustand" (C/A-Betriebszustand, C/A = coarse/acquisition) ist das PRN-Signal eine Goldcodesequenz mit einer Chip- bzw. Taktrate von 1,023 MHz. Die Goldcodesequenz ist in der Technik eine wohlbekannte herkömmliche Pseudozufallssequenz. Ein Chip ist ein individueller Impuls des Pseudozufallscodes. Die Chiprate einer Pseudozufallscodesequenz ist die Rate, mit der die Chips in der Sequenz erzeugt werden. Folglich ist die Chiprate gleich der Codewiederholungsrate geteilt durch die Anzahl der Glieder im Code. Entsprechend existiert mit Bezug auf den Grob/Aufnahme- bzw. Grob/Suchbetriebszustand des NAVSTAR-GPS 1023 Chips in jeder Goldcodesequenz, und die Sequenz wird jede Millisekunde wiederholt. Die Verwendung der Goldcodesequenz mit 1,023 MHz von vier umlaufenden GPS-Satelliten, ermöglicht, daß die terrestrische Position eines Erdempfängers mit einer angenäherten Genauigkeit von innerhalb 60 bis 300 Metern bestimmt wird.
Der zweite Modulationsbetriebszustand im NAVSTAR-GPS wird im allgemeinen als der "präzise" oder "geschützte" (P-) Betriebszustand bezeichnet. Im geschützten Betriebszustand hat der Pseudozufallscode eine Chiprate von 10,23 MHz. Darüber hinaus sind die Sequenzen im geschützten Betriebszustand extrem lang, so daß die Sequenzen sich nicht öfter als einmal alle 267 Tage wiederholen. Als eine Folge kann die terrestrische Position von irgendeinem Erdempfänger auf innerhalb einer ungefähren Genauigkeit von 16 bis 30 Metern bestimmt werden.
Jedoch sind die Sequenzen im geschützten Betriebszustand klassifiziert und werden von der Regierung der Vereinigten Staaten nicht öffentlich verfügbar gemacht. In anderen Worten ist der geschützte Betriebszustand nur zur Anwendung von Erdempfängern vorgesehen, die von der Regierung der Vereinigten Staaten autorisiert sind.
Damit die Erdempfänger die verschiedenen C/A-Signale von den anderen umlaufenden GPS-Signalen unterscheiden, weisen die Erdempfänger gewöhnlicherweise eine Vielzahl von unterschiedlichen Goldcodequellen auf, um lokal Goldcodesequenzen zu erzeugen. Jede lokal abgeleitete Goldcodesequenz entspricht jeder einzigartigen Goldcodesequenz jedem der GPS-Satelliten.
Die lokal abgeleiteten Goldcodesequenzen und die übertragenen Goldcodesequenzen werden miteinander in Querbeziehung bzw. Kreuzkorrelation gebracht und zwar über Goldcodesequenzintervalle von einer Millisekunde. Die Phase der lokal abgeleiteten Goldcodesequenzen variiert auf einer Basis von Chip zu Chip und dann innerhalb eines Chips, bis die maximale Querbeziehungsfunktion bzw. Kreuzkorrelationsfunktion erhalten wird. Da die Querbeziehung bzw. Kreuzkorrelation für zwei Goldcodesequenzen, die eine Länge von 1023 Bits hat, ungefähr 16 mal so groß ist, wie die Kreuzkorrelationsfunktion von irgendeiner der anderen Kombinationen der Goldcodesequenzen, ist es relativ einfach, die lokal abgeleitete Goldcodesequenz auf die gleiche Goldcodesequenz zu verriegeln, die von einem der GPS- Satelliten übertragen wurde.
Die Goldcodesequenzen von mindestens vier der GPS-Satelliten im Blickfeld eines Erdempfängers werden in dieser Weise unter Verwendung eines einzigen Kanals getrennt, der sequentiell auf jede der lokal abgeleiteten Goldcodesequenzen anspricht, oder alternativ durch Verwendung von parallelen Kanälen, die simultan auf die unterschiedlichen Goldcodesequenzen ansprechen. Nachdem vier lokal abgeleitete Goldcodesequenzen in einer Phase mit den Goldcodesequenzen verriegelt worden sind, die von vier GPS-Satelliten im Sichtfeld eines Erdempfängers empfangen wurden, kann die Relativposition des Erdempfängers mit einer Genauigkeit von ungefähr 60 bis 300 Metern bestimmt werden.
Die vorangegangene ungefähre Genauigkeit des NAVSTAR-GPS wird beeinflußt durch (1) die Anzahl der GPS-Satelliten, die Signale übertragen, auf die der Erdempfänger effektiv anspricht, (2) die variablen Amplituden der empfangenen Signale und (3) die Größe der Kreuzkorrelationsspitzen zwischen den empfangenen Signalen von den unterschiedlichen GPS-Satelliten.
Da mehrere PRN- bzw. Pseudozufallszahlsignale simultan beim Erdempfänger empfangen werden, existiert ein gemeinsames Zeitintervall, in dem einige der Codes in Konflikt kommen können. In anderen Worten bewirken die Codes eine Verschlechterung der Messungen der Ankunftszeit von jeder empfangenen Pseudozufallszahl, und zwar wegen den Kreuzkorrelationen zwischen empfangenen miteinander in Konflikt stehenden Signalen.
Die Ankunftszeitmessung für jedes PRN-Signal wird durch Bestimmung der Zeit einer Spitzenamplitude einer Kreuzkorrelation zwischen der Goldcodesequenz des empfangenen PRN-Signals und dem lokal abgeleiteten PRN-Signal vorgenommen. Wenn ein lokal abgeleitetes PRN-Signal über ein empfangenes PRN-Signal überlagert wird, wodurch die Durchschnittszeit ihrer Kreuzkorrelation vergrößert wird, sinkt der durchschnittliche Rauschbeitrag. Da jedoch Kreuzkorrelationsfehler zwischen den empfangenen PRN- Signalen periodisch sind, hat eine Vergrößerung der Durchschnittszeit genauso Vergrößerungen von sowohl dem Fehlersignal als auch dem Kreuzkorrelationswert zwischen den empfangenen Pseudozufallszahlen zur Folge. Folglich werden Fehler bezüglich der Ankunftszeit der PRN-Signale nicht durch die Kreuzkorrelation reduziert.
Zusätzlich zum GPS ist in der herkömmlichen Technik bekannt, Trägheitssysteme bei Navigationssystemen zu verwenden, um eine Positionsabschätzung der Fahrzeuge zu erhalten. Eine solche Trägheitsreferenzeinheit (IRU = inertial reference unit) erhält spezielle Kraftmessungen von Beschleunigungsmessern in einem Referenzkoordinatenrahmen, der von Gyroskopen oder Gyrovorrichtungen stabilisiert wird. Eine Trägheitsreferenzeinheit kann von mehreren Bauarten sein, wie beispielsweise Laser, Mechanik oder Faseroptik. In einem nicht unterstützten Navigationssystem unter Verwendung einer Trägheitsreferenzeinheit wird die spezifische Kraft (korrigiert bezüglich der Effekte der Erdschwerkraft) wie von einem Beschleunigungsmesser gemessen, in eine mathematische Navigationsgleichung integriert, um die Geschwindigkeit und die Position des Fahrzeugs zu erzeugen.
Die Instrumentenmessungen der Trägheitsreferenzeinheit können in einem anderen rechteckigen Koordinatenrahmen als dem Referenznavigationsrahmen festgelegt werden, und zwar abhängig von der Plattformeinrichtung. Der am meisten verwendete Referenznavigationsrahmen für die Navigation nahe der Erdoberfläche ist der Lokalniveaurahmen (Breite-Länge-Vertikalposition). Mehrere Kardanplattformeinrichtungen existieren bei dem vorangegangenen Referenznavigationsrahmen.
Bei einer kardanartig aufgehängten die Nordrichtung suchenden Lokalniveauträgheitsreferenzeinheit werden die Gyroskope und Beschleunigungsmesser auf einer Plattform montiert, die verdreht wird, um das Plattformniveau und den Azimuth auf nordweisend zu halten. Die Plattform ist die Referenzebene. Im Gegensatz dazu wird bei einer kardanartig aufgehängten im Azimuth wandernden Lokalniveauträgheitsreferenzeinheit die Plattform auf dem Niveau gehalten, wird jedoch nicht um die Vertikalachse verdreht.
Weiterhin werden bei einer abgespeckten bzw. Strap-Down- Trägheitsreferenzeinheit die Gyroskope und Beschleunigungsmesser direkt auf dem Fahrzeugkörper montiert. Sie messen die Linear- und Winkelbewegung des Fahrzeugs relativ zum Trägheitsraum. Die Bewegung wird in Fahrzeugkoordinaten ausgedrückt. Daher ist es bei einer Strap-Down- Trägheitsreferenzeinheit nötig, zuerst die Höhe des Fahrzeugs zum Bezugsnavigationsrahmen zu berechnen. Dann wird die berechnete Höhe verwendet, um die Beschleunigungsmessungen in den Referenzrahmen zu transformieren. Nachdem die Beschleunigungsmessdaten einer Strap-Down-Trägheitsreferenzeinheit in dem Referenzrahmen extrapoliert worden sind, ist die Lösung der zuvor erwähnten Navigationsgleichungen identisch sowohl bei der kardanartig aufgehängten Trägheitsreferenzeinheit als auch bei der Strap-Down- Trägheitsreferenzeinheit.
Bei der Strap-Down-Trägheitsreferenzeinheit werden die Höhenberechnungen, die erforderlich sind, um die Beschleunigungsmessungen aufzulösen, mit einer hohen Rate ausgeführt. Die Berechnungen leiden unter numerischen Fehlern und zwar wegen der begrenzten Computerbitgröße und Durchgangsverfügbarkeit. Diese Berechnungsfehler hängen von dem Frequenzansprechen der Sensorschleife, von der Datenrate und der Auflösung und der Größe der Sensorausgangsgröße bei der Aufnahmezeit ab.
Jedoch erwachsen beträchtliche Vorteile aus der Verwendung der Strap-Down-Trägheitsreferenzeinheit anstelle der kardanartig aufgehängten Trägheitsreferenzeinheit. Die Strap-Down-Trägheitsreferenzeinheiten sind billiger. Darüber hinaus sind die Strap-Down-Trägheitsreferenzeinheiten im allgemeinen bezüglich der physikalischen Größe kleiner. Somit kann das Potential zur Verwirklichung von Größen- und Kosteneinsparungen bei den Trägheitsreferenzeinheiten die Strap-Down-Trägheitsreferenzeinheiten sowohl für militärische als auch für kommerzielle Anwendungen attraktiv machen.
Die Leistung von Navigationssystemen, die Trägheitsreferenzeinheiten verwenden, ist in erster Linie durch Fehler begrenzt, die von den verschiedenen anteiligen Sensoren innerhalb der Trägheitsreferenzeinheiten beigetragen werden. Gyroskope zeigen einen Drift bzw. eine Abweichung. Beschleunigungsmesser haben innewohnende Vorspannungen. Weitere Fehler werden von ungenauen Skalierungsfaktoren und ungenauen Trägheitsreferenzeinheitsausrichtungswinkeln beigetragen. Typischerweise bewirken die vorhergehenden Fehler Ungenauigkeiten bei den Abschätzungen der Fahrzeugpositionen, der Geschwindigkeit und der Höhe, die sich mit der Zeit ansammeln, wenn eine Fahrzeugmission voranschreitet. In gewissem Ausmaß hängen die Fehler von den dynamischen Vorgängen des Anwenders ab.
Wenn ein sehr genaues Navigationssystem für ein Fahrzeug erforderlich ist, können hochpräzise Gyroskope und Beschleunigungsmesser verwendet werden, um diese Notwendigkeit zu erfüllen. Jedoch steigern solche hochpräzisen Ausrüstungsgegenstände die Komplexität und die Kosten des Fahrzeugs.
EP-A-0181012 offenbart ein Fahrzeugpositionsabschätzungssystem, welches GPS- und Trägheitsnavigationssysteme kombiniert. IEEE Position Location und Navigation Symposium, 4.-7. November 1986 offenbart ein Trägheitsnavigationssystem im Vergleich mit dem GPS.
DE-A-33 10 111 offenbart ein Navigationssystem mit Drift- bzw. Abweichungskompensation. US-A-3630079 offenbart ein Navigationssystem, welches mehrere Sensoren und die Fehlerkorrektur verwendet.
WO-A-8707056 offenbart ein System zur Vermeidung von Hindernissen im Pfad eines Fahrzeugs.
Gemäß der vorliegenden Erfindung ist ein System für das Navigieren eines Fahrzeugs entlang einer Route vorgesehen, das folgendes aufweist:
Mittel für das Speichern von Routendaten, die eine vorbestimmte Route repräsentieren;
Mittel für das Speichern von Pfaddaten für eine jede vorbestimmte Route;
Mittel für das Auswählen einer vorbestimmten Route, der das Fahrzeug folgt;
Mittel für das Herausziehen von Routendaten, die eine ausgewählte vorbestimmte Route repräsentieren;
Mittel für das Herausziehen von Pfaddaten für die herausgezogenen Routendaten;
Mittel für das Erzeugen eines Pfades aus den herausgezogenen Pfaddaten;
Mittel für das Assoziieren von Fahrzeugbefehlen mit einem erzeugten Pfad;
Mittel für das Ausführen der zugeordneten Fahrzeugbefehle, die bewirken, dass das Fahrzeug einem erzeugten Pfad zu folgen versucht;
Mittel für das periodische Berechnen von Fehlern beim Folgen eines erzeugten Pfades;
Mittel, und zwar ansprechend auf die berechneten Fehler, für das Angleichen bzw. Einstellen der Ausführung der zugeordneten Fahrzeugbefehle für das Reduzieren der berechneten Fehler, so dass das Fahrzeug einem erzeugten Pfad mit einem hohen Genauigkeitsgrad folgt;
Mittel für das Detektieren von Hindernissen in der Fortbewegungsrichtung des Fahrzeugs;
Mittel für das Vermeiden einer Kollision mit den Hindernissen, die wiederum Mittel aufweisen für das Anhalten des Fahrzeugs zum Verhindern einer Kollision mit den Hindernissen und Mittel für das Erzeugen eines Pfades um die Hindernisse herum;
wodurch ein autonomes bzw. selbständiges System für das sichere und effiziente Navigieren eines Fahrzeugs entlang einer Route realisiert wird; dadurch gekennzeichnet, dass die Mittel für das Erzeugen eines Pfades einen Pfad von aneinander hängenden Anordnungen bzw. Lagen erzeugt mit Änderungsraten für die Krümmung abhängig von den Lenkeinschränkungen des Fahrzeugs.
Die vorliegende Erfindung sieht auch ein Verfahren für das Navigieren eines Fahrzeugs entlang einer Route vor, das die folgenden Schritte aufweist:
Speichern von Routendaten, die eine vorbestimmte Route repräsentieren;
Auswählen einer vorbestimmten Route, der das Fahrzeug folgt;
Herausziehen der Routendaten, die eine ausgewählte vorbestimmte Route repräsentieren;
Herausziehen von Pfaddaten für die herausgezogenen Routendaten;
Erzeugen eines Pfades aus den herausgezogenen Pfaddaten; Assoziieren von Fahrzeugbefehlen mit einem erzeugten Pfad;
Ausführen der zugeordneten Fahrzeugbefehle, die bewirken, dass das Fahrzeug einem erzeugten Pfad zu folgen versucht;
Periodisches Berechnen von Fehlern beim Folgen eines erzeugten Pfades;
Angleichen bzw. Einstellen, und zwar ansprechend auf die berechneten Fehler, der Ausführung der zugeordneten Fahrzeugbefehle zum Reduzieren der berechneten Fehler, so dass das Fahrzeug einem erzeugten Pfad mit einem hohen Genauigkeitsgrad folgt;
Detektieren einer Kollision mit den Hindernissen durch Stoppen des Fahrzeugs, um eine Kollision mit den Hindernissen zu verhindern, Erzeugen eines Pfades um die Hindernisse herum oder Durchführen von beidem; wodurch ein autonomes Verfahren für ein sicheres und effizientes Navigieren eines Fahrzeugs entlang einer Route realisiert wird; gekennzeichnet dadurch, dass der erzeugte Pfad ein Pfad von aneinander gehängten Anordnungen bzw. Lagen mit einer Änderungsrate der Krümmung abhängig von den Lenkeinschränkungen des Fahrzeugs ist.
Die vorliegende Erfindung kann verwendet werden, um irgendeinem Navigationssystem für autonome Fahrzeuge zu helfen. Die autonomen Fahrzeuge können stationär oder beweglich sein. Darüber hinaus können die autonomen Fahrzeuge auf oder nahe der Erdoberfläche sein. Anders gesagt sieht die vorliegende Erfindung eine sehr genaue und schnelle Verfolgung von irgendeinem terrestrischen Fahrzeug vor. Sie sieht sowohl Vorrichtungen als auch Verfahren vor, die eine überlegene Positionierungs- bzw. Positionsbestimmungsfähigkeit und folglich eine flexible autonome Navigationsfähigkeit gestatten.
Weitere Merkmale und Vorteile der vorliegenden Erfindung werden dem Fachmann in der Technik bei der Untersuchung der folgenden Zeichnungen und der detaillierten Beschreibung offensichtlich werden. Es wird beabsichtigt, daß irgendwelche zusätzlichen Merkmale und Vorteile hier miteingeschlossen seien.
Die vorliegende Erfindung, wie in den Ansprüchen definiert, kann besser mit Bezug auf den Text und die folgenden Zeichnungen verstanden werden.
Fig. 1 veranschaulicht ein Blockdiagramm des bevorzugten Ausführungsbeispiels der vorliegenden Erfindung;
Fig. 1A ist ein Blockdiagramm 100A der in Betrieb befindlichen GPS-Satelliten beim NAVSTAR-GPS;
Fig. 2 veranschaulicht vier gleichzeitige Navigationsgleichungen, die vier GPS-Satelliten des NAVSTAR-GPS betrachten bzw. behandeln;
Fig. 3 ist ein Blockdiagramm einer typischen autonomen Arbeitsstelle bzw. Baustelle;
Fig. 4 ist ein Blockdiagramm der Beziehungen zwischen einem Navigator, einer VPS- bzw. Fahrzeugpositionsbestimmungssystem-Architektur und Fahrzeugsteuerungen der vorliegenden Erfindung;
Fig. 5 ist ein Blockdiagramm, welches die Elemente in einem autonomen Steuersystem veranschaulicht;
Fig. 6 ist ein Blockdiagramm des Betriebs eines GPS;
Fig. 7 ist ein Blockdiagramm eines GPS-Verarbeitungssystems des bevorzugten Ausführungsbeispiels;
Fig. 8 ist ein Flußdiagramm des GPS-Verarbeitungssystems der Fig. 7;
Fig. 9 ist ein Blockdiagramm eines MPS(Bewegungspositionssystems) und zwar einschließlich eines Odometers bzw. Wegmessers 902 und einer Trägheitsreferenzeinheit (IRU = inertial reference unit) 904;
Fig. 10 ist ein Blockdiagramm des VPS (Fahrzeugpositionsbestimmungssystems)
Fig. 11 ist ein Blockdiagramm der VPS-Architektur der Fig. 10;
Fig. 12 ist ein Diagramm von Fahrzeugroutendefinitionen;
Fig. 13 ist eine diagrammartige Darstellung, wie Lagen und assoziierte Kreise aus Objektivpunkten erhalten werden;
Fig. 14 ist ein Diagramm, wie das Vorzeichen eines ersten Clothoid-Segments bestimmt wird;
Fig. 15 ist ein Diagramm, wie das Vorzeichen eines letzten Clothoid-Segments bestimmt wird;
Fig. 16 ist eine grafische Darstellung einer Clothoid- Kurve;
Fig. 17 ist ein Flussdiagramm eines numerischen Verfahrens zur Berechnung von angenäherten Fresnel- Integralen;
Fig. 18 ist ein Diagramm, das die erneute Planung eines Pfades zeigt;
Fig. 19 ist eine Kurvendarstellung von B-Spline-Kurven von zweiter, dritter und vierter Ordnung;
Fig. 20 ist eine Abbildung eines Ausführungsbeispiels des Lageringpuffers;
Fig. 21 ist ein Diagramm, welches zeigt, wie ein Fehlervektor, der eine Krümmung einschließt, berechnet wird;
Fig. 22 ist ein Kontextdiagramm des Navigators der vorliegenden Erfindung;
Fig. 23 ist ein Kontextdiagramm einer Pfadverfolgungsstruktur;
Fig. 24A-24D sind Datenflusszusammenfassungen des Navigators 406;
Fig. 25A ist eine Darstellung eines auf einem Fahrzeug montierten Scanners bzw. einer Abtastvorrichtung 404;
Fig. 25B ist eine Darstellung eines autonomen Fahrzeuges, das bezügl. eines Hindernisses scannt, bzw. tastet;
Fig. 26 ist ein Diagramm eines autonomen Fahrzeugs, das Hindernisse vermeidet;

I. Definitionen

(1) "Absolute Position" bezieht sich im Zusammenhang mit diesem Dokument auf eine Position bezüglich dem Erdmittelpunkt. Im allgemeinen wird eine absolute Position in Bezug zu einem Fahrzeug oder einer Basisstation sein, sowohl auf als auch nahe der Erdoberfläche. Erste, zweite und dritte Positionsabschätzungen sind alle absolute Positionen.
(2) "Tatsächlicher Pseudobereich" bedeutet eine Annäherung an die Distanz zwischen (1) einem Bezugspunkt und (2) einer Quelle eines terrestrischen Positionsbestimmungssystems. In diesem Dokument beziehen sich die tatsächlichen Pseudobereiche gewöhnlicherweise auf eine Annäherung der Distanz zwischen (1) einem Erdempfänger und (2) GPS-Satelliten und/oder Pseudoliten. Tatsächliche Pseudobereiche werden angenähert, indem man zuerst die Fortpflanzungszeitverzögerungen zwischen der Übertragung und dem Empfang der elektromagnetischen Signale mißt, die aus den GPS-Satelliten und/oder Pseudoliten herauskommen. Tatsächliche Pseudobereiche können leicht berechnet werden durch Multiplizieren der berechneten Zeitverzögerungen mit der Lichtgeschwindigkeit oder mit 2,9979245898 · 108 m/s.
(3) "Antiselektive Verfügbarkeit" bezieht sich auf ein Verfahren/eine Technik/einen Prozeß zum Detektieren und Kompensieren von korrupten bzw. zerstörten GPS-Daten im Grob/Such-(C/A-)Modulationsbetriebszustand.
(4) "Autonom" wird in diesem Dokument im herkömmlichen Sinne verwendet. Es zeigt den Betrieb an, der entweder vollständig automatisch oder im wesentlichen automatisch oder ohne beträchtliches Einbeziehen eines Menschen im Betrieb ist. Im allgemeinen bedeutet ein autonomes Fahrzeug ein nicht bemanntes Fahrzeug im Betrieb oder ein Fahrzeug im Betrieb ohne einen menschlichen Fahrer oder Beifahrer. Jedoch kann ein autonomes Fahrzeug automatisch gefahren werden oder in anderer Weise betrieben werden und kann genauso einen (mehrere) menschlichen (menschliche) Passagier (e) haben.
(5) "Basiskorrelationsableitung" bedeutet eine räumliche Ableitung.
(6) "Basiskorrelationsableitungstechnik" meint ein Verfahren/Prozeß zur Berechnung der Basiskorrelationsableitungen.
(7) "Abgeschätzte Basisposition" oder "BEP" bezieht sich auf die relative Position der Basisstation mit Bezug auf ein Fahrzeug. Die abgeschätzte Basisposition wird in der Basiskorrelationsableitungstechnik verwendet.
(8) "Bekannte Basisposition" oder "BKP" ist die absolute Position der Basisstation (verwendet als Referenzpunkt) die bekannt ist. Die bekannte Basisposition kann selbst eine Abschätzung sein, die von irgendeinem genauen Positionsbestimmungssystem abgeleitet wird. Es wird angenommen, daß die bekannte Basisposition eine genauere Abschätzung der absoluten Position der Basisstation als irgendeine andere Positionsabschätzung ist.
(9) "Basispositionsabschätzung" bedeutet die Abschätzung der absoluten Position der Basisstation, wie sie von dem GPS-Verarbeitungssystem innerhalb des Host-Verarbeitungssystems abgeleitet wurde. Die Basispositionsabschätzung ist im wesentlichen ähnlich wie die erste Positionsabschätzung, die von dem GPS-Verarbeitungssystem in dem Fahrzeug abgeleitet wurde. Die Basispositionsabschätzung wird in der Basisresiduenableitungstechnik berechnet.
(10) "Basisresiduenableitung" bedeutet eine räumliche Ableitung, die die effektive Differenz der bekannten Basisposition (BKP) der Basisstation und der Positionsabschätzung der Basisstation ist, die von dem Host-Verarbeitungssystem berechnet wird.
(11) "Basisresiduenableitungstechnik" bezieht sich auf ein Verfahren zur Ableitung von Basisresiduenableitungen.
(12) "Ableitung" ("Bias") bezieht sich auf eine Differenz zwischen zwei Messungen, gewöhnlicherweise Positionsabschätzungen (räumliche Ableitungen) oder Clock- bzw. Takt-Raten (Clock-Ableitung bzw. Clock-Bias). Da bekannt ist, daß eine Messung gewöhnlicherweise genauer ist als die andere, wird die Ableitung oft als "Fehler" bezeichnet.
(13) "Taktableitung" (Clock-Ableitung) bedeutet die Differenz der Taktzeiten zwischen (1) der Übertragungsschaltung der GPS-Satelliten und/oder GPS-Pseudoliten und (2) der Aufnahmeschaltung eines Erdempfängers. Wenn man eine Taktableitung in der Berechnung einer räumlichen Ableitung verwendet, wird die Taktableitung mit der Lichtgeschwindigkeit oder mit 2,998 · 10$ Metern pro Sekunde multipliziert. Folglich wird die Taktableitung in Längeneinheiten umgewandelt.
(14) "Konstellation" bezieht sich auf eine Gruppe, die aus GPS-Satelliten und/oder Pseudoliten besteht, deren Signale verwendet werden, um eine absolute Positionsabschätzung des Punktes auf oder nahe der Erdoberfläche abzuleiten. Siehe unten "optimale Konstellation".
(15) "Konstellationseffektverfahren" meint eine Technik oder einen Prozeß, wodurch eine optimale Konstellation von GPS-Satelliten aus einer größeren Gruppe von GPS- Satelliten im Sichtfeld eines Fahrzeuges ausgewählt wird.
(16) "Datenfunk" bezieht sich auf einen Sender, Empfänger, Sender/Empfänger oder irgendeine Kombination davon zur Übertragung von Daten bei Funkfrequenzen (RF = Radiofrequenzen).
(17) "Erdempfänger" bezieht sich auf irgendeine Einrichtung oder Vorrichtung oder irgendeinen Teil davon, der Signale von einem GPS und/oder Pseudoliten empfängt und verarbeitet. Erdempfänger können auf oder nahe der Erdoberfläche gelegen sein. Darüber hinaus können Erdempfänger beispielsweise die Form eines Fahrzeuges oder einer Basisstation annehmen.
(18) "Abgeschätzter Pseudobereich" bezieht sich auf die Annäherung der Distanz zwischen (1) einem Referenzpunkt und (2) einer Quelle eines terrestrischen Positionsbestimmungssystems. In dieser Schrift beziehen sich die aktuellen Pseudobereiche gewöhnlicherweise auf eine Annäherung der Distanz zwischen (1) einem Erdempfänger und (2) GPS-Satelliten und/oder Pseudoliten. Abgeschätzte Pseudobereiche werden aus GPS-Daten berechnet, die in den elektromagnetischen Signalen kodiert sind, die von den GPS-Satelliten und/oder den Pseudoliten übertragen werden. Almanachgleichungen zur Berechnung von abgeschätzten Pseudobereichen aus den GPS-Daten des NAVSTAR-GPS sind öffentlich verfügbar.
(19) "Erste Positionsabschätzung" oder "FPE" oder "FPE (i)" (FPE = first position estimate) bezieht sich auf eine abgeschätzte absolute Position von irgendeinem Fahrzeug, die in irgendeiner Form aus dem GPS ausgegeben wird. Die erste Positionsabschätzung und die zweite Positionsabschätzung werden unabhängig abgeleitet. Darauf folgend werden diese Abschätzungen kombiniert und gefiltert, um eine dritte Positionsabschätzung abzuleiten. Folglich beeinflußt die Genauigkeit der ersten Positionsabschätzung die Genauigkeit der dritten Positionsabschätzung.
(20) "GLONASS-GPS" bezieht sich auf das GPS, welches von der USSR konstruiert worden ist und gegenwärtig von ihr eingesetzt wird.
(21) "Globales Positionsbestimmungssystem" oder "GPS" ist eine Art eines terrestrischen Positionsbestimmungssystems. Bei einem GPS wird eine Anzahl von Satelliten in einer Umlaufbahn um den Planeten Erde angeordnet. Die GPS-Satelliten sind ausgelegt, um elektromagnetische Signale zu senden. Aus diesen elektromagnetischen Signalen kann die absolute terrestrische Position (Position mit Bezug auf den Erdmittelpunkt) von irgendeinem Empfänger auf oder nahe der Erdoberfläche ultimativ bestimmt werden. Die US-Regierung hat ihr GPS "NAVSTAR" genannt. Die Regierung der USSR hat ihr GPS "GLONASS" genannt.
(22) "GPS-Daten" bedeutet alle Daten, die auf Signalen codiert wurden, die von GPS-Satelliten eines GPS übertragen wurden. GPS-Daten weisen beispielsweise Ephemeridendaten und Zeitdaten auf.
(23) "GPS-Verarbeitungssystem" bezieht sich auf ein System zur Aufnahme von Signalen von einem terrestrischen Positionsbestimmungssystem und zur Ableitung von ersten Positionsabschätzungen von Fahrzeugen aus den aufgenommenen Signalen. Das GPS-Verarbeitungssystem empfängt elektromagnetische Signale von den GPS-Satelliten eines GPS und/oder von Pseudoliten.
(24) "Host-Verarbeitungssystem" bezieht sich auf ein Computersystem, das an der Basisstation zur Ausführung von Verfahren und Techniken arbeitet, die die Genauigkeit der Positionsabschätzungen der Fahrzeuge verbessern. Daten, die aus diesen Verfahren und Techniken abgeleitet werden, werden zu Fahrzeugen übertragen, so daß die Fahrzeuge die Daten verwenden können, wenn sie erste, zweite und dritte Positionsabschätzungen berechnen. Die Architektur/Hardware (Komponenten) des Host-Verarbeitungssystems sind im wesentlichen ähnlich der Architektur/Hardware des Fahrzeugpositionsbestimmungssystems.
(25) "Trägheitsreferenzeinheit" oder "IRU" (IRU = inertial reference unit) bezieht sich auf ein System, gewöhnlicherweise an Bord eines Fahrzeuges, um der Ableitung einer zweiten Positionsabschätzung des Fahrzeuges beizuhelfen. Eine Trägheitsreferenzeinheit erhält spezifische Kraftmessungen von Beschleunigungsmessern in einem Referenzkoordinatenrahmen, der von Gyroskopen oder Gyroskopmitteln stabilisiert wird. Eine Trägheitsreferenzeinheit kann von einer Laserbauart oder von einer mechanischen Bauart sein. Tn einem nicht unterstützten Navigationssystem, welches eine Trägheitsreferenzeinheit verwendet, wird die spezifische Kraft (korrigiert bezüglich der Effekte der Erdschwerkraft) wie von dem Beschleunigungsmesser gemessen, in eine mathematische Navigationsgleichung integriert, um die Fahrzeugposition und -geschwindigkeit zu erzeugen. Die Trägheitsreferenzeinheit ist ein Teil des Bewegungspositionsbestimmungssystems.
(26) "Kalmanfilter" wird im herkömmlichen Sinne verwendet. Dies bezieht sich auf ein Softwareprogramm zum herausfiltern von Rauschen oder Fehlern in den Daten. Ein GPS-Kalman-Filter wird verwendet, um Rauschen oder Fehler im GPS-Verarbeitungssystem herauszufiltern, um die Genauigkeit der ersten Positionsabschätzungen zu verbessern. Es wird auch ein VPS- bzw. Fahrzeugpositionsbestimmungs- Kalman-Filter verwendet, um das Rauschen in dem Fahrzeugspositionsbestimmungssystem herauszufiltern, um die Genauigkeit der zweiten Positionsabschätzungen zu verbessern.
(27) "Bewegungspositionsbestimmungssystem" oder "MPS" (MPS = motion positioning system) bedeutet ein System, welches zumindest eine Trägheitsreferenzeinheit und einen Fahrzeugwegmesser aufweist. Das Bewegungspositionsbestimmungssystem leitet die zweite Positionsabschätzung von irgendeinem Fahrzeug auf oder nahe der Erdoberfläche ab. Darüber hinaus muß ein Bewegungspositionsbestimmungssystem nicht an der Basisstation vorhanden sein, und zwar aufgrund ihrer stationären Natur.
(28) "Optimale Konstellation" bedeutet eine Satellitenkonstellation, bei der die Relativpositionen der GPS- Satelliten im Raum überlegene Triangulationsfähigkeiten erfordert, um die genaueste Abschätzung eines Punktes auf oder nahe der Erdoberfläche abzuleiten.
(29) "Ursprüngliche Ableitung" bedeutet eine räumliche Ableitung, berechnet durch Subtrahieren von sowohl abgeschätzten Pseudobereichen als auch Taktableitungen (in Längeneinheiten) von den tatsächlichen Pseudobereichen. Taktableitungen werden in Längeneinheiten umgewandelt, indem man sie mit der Lichtgeschwindigkeit oder mit 2,9979245898 10a Metern pro Sekunde multipliziert.
(30) "Technik der ursprünglichen Ableitung" ist ein Verfahren zur Berechnung der ursprünglichen Ableitungen.
(31) "NAVSTAR-GPS" bedeutet das GPS, welches von der US- Regierung konstruiert worden ist und gegenwärtig von dieser eingesetzt wird.
(32) "Navigationssystem" bezieht sich auf irgendwelche Systeme und/oder Verfahren zum Leiten eines Fahrzeuges auf oder nahe der Erdoberfläche. Die Navigationssysteme können an Bord eines Fahrzeugs sein. Das Fahrzeugpositionsbestimmungssystem der vorliegenden Erfindung kann das Navigationssystem des Fahrzeugs mit einer sehr genauen dritten Positionsabschätzung des Fahrzeugs versorgen, so daß das Navigationssystem dadurch präzise das Fahrzeug führen kann.
(33) "Parabolische Ableitung" ist eine räumliche Ableitung, die durch den Aufbau von parabolischen Modellen für die tatsächlichen Pseudobereiche von jedem beobachteten GPS-Satelliten berechnet wird, und durch Extrapolieren von Werten aus den parabolischen Modellen. Die parabolischen Ableitungen sind die tatsächlichen Pseudobereiche abzüglich dem Wert, der aus den konstruierten parabolischen Modellen extrapoliert wurde, und abzüglich den Taktableitungen (in Längeneinheiten durch Multiplizieren mit der Lichtgeschwindigkeit).
(34) "Parabolische Ableitungstechnik" ist ein Verfahren zur Berechnung von parabolischen Ableitungen von jedem der GPS-Satelliten, die verwendet werden.
(35) "Bevorzugtes Ausführungsbeispiel" bezieht sich auf den besten Weg zur Einrichtung der vorliegenden Erfindung. Das bevorzugte Ausführungsbeispiel ist nur beispielhaft. Die vorliegende Erfindung sollte nicht so interpretiert werden, daß sie auf das bevorzugte Ausführungsbeispiel eingeschränkt ist.
(36) "Pseudolit" bezieht sich auf ein Strahlungssystem oder Sendesystem auf oder nahe der Erdoberfläche zur Emulation eines GPS-Satelliten. Elektromagnetische Signale werden, ähnlich jenen von den GPS-Satelliten, von landbasierten Pseudoliten übertragen. Einer oder mehrere Pseudoliten können verwendet werden, um GPS-Satelliten zu emulieren, um die Berechnung der ersten Positionsabschätzungen zu verbessern.
(37) "Pseudolitendaten" bedeutet alle Daten, die in Signalen kodiert sind, die von den Pseudoliten aufgenommen wurden. Die Pseudolitendaten ähneln den GPS-Daten in vieler Hinsicht und weisen ähnliche Informationen auf.
(38) "Pseudobereich" meint die Distanz zwischen einer Quelle eines terrestrischen Positionsbestimmungssystems und einem Punkt auf oder nahe der Erdoberfläche. Die Quellen können GPS-Satelliten und/oder Pseudoliten sein. Das terrestrische Positionsbestimmungssystem kann ein GPS sein, das mit Pseudoliten verwendet wird, falls vorhanden. Weiterhin kann der Punkt auf oder nahe der Erdoberfläche die Basisstation und/oder Fahrzeuge sein.
(39) "Satellitenpositionsvorhersage" ist ein Verfahren zur Bestimmung der zukünftigen Positionen der GPS-Satelliten. Das Verfahren gestattet die vorzeitige Auswahl von optimalen Konstellationen.
(40) "Zweite Positionsabschätzung" oder "SPE" (SPE = second position estimate) bezieht sich auf eine abgeschätzte absolute Position von irgendeinem Fahrzeug, die in irgendeiner Form vom Bewegungspositionsbestimmungssystem bzw. MPS ausgegeben wurde. Die zweiten Positionsabschätzungen weisen mindestens eine Positionsinformation von einer Trägheitsreferenzeinheit auf. Die zweite Positionsabschätzung könnte Positionsinformationen von einem Fahrzeugwegmesser aufweisen, der auf einem Fahrzeug gelegen ist.
(41) "Räumliche Ableitung" bezieht sich auf eine Ableitung, die sich auf Annäherungen der Positionen in einem zweidimensionalen oder dreidimensionalen Raum bezieht. Räumliche Ableitungen werden verwendet, um eine Positionsabschätzung zu versetzen (offset) um die Genauigkeit der Positionsabschätzung zu verbessern. Räumliche Ableitungen können durch eine Anzahl von unterschiedlichen Verfahren der vorliegenden Erfindung berechnet werden. Bei diesen Verfahren sind beispielsweise eine Originalableitungstechnik 1500, eine parabolische Ableitungstechnik 1600, eine Basisresiduenableitungstechnik 1700 und eine Basiskorrelationsableitungstechnik 1700A eingeschlossen.
(42) "System" wird für den Zweck verwendet, eine Vorrichtung, ein Verfahren oder eine Kombination von sowohl einer Vorrichtung als auch einem Verfahren zu bedeuten. Darüber hinaus könnte es Programme, Hardware bzw. Komponenten oder eine Kombination aus Hardware und Programmen aufweisen.
(43) "Positionsbestimmungssystem" bedeutet irgendein System mit Quellen, die Signale ausstrahlen, die von einem Empfänger der Signale verwendet werden können, um die relative Distanz zwischen den Quellen und dem Empfänger abzuschätzen. Die Signale können beispielsweise in Form von elektromagnetischen Wellen, Percussionswellen und/oder Schallwellen sein.
(44) "Terrestrisches Positionsbestimmungssystem" bedeutet irgendein Positionsbestimmungssystem, welches verwendet werden kann, um ultimativ die terrestrische Position eines Erdempfängers abzuschätzen. Die Signale können beispielsweise in Form von elektromagnetischen Wellen, Percussionswellen und/oder Schallwellen sein. Das terrestrische Positionsbestimmungssystem ist das NAVSTAR-GPS.
(45) "Dritte Positionsabschätzung" oder "TPE" (TPE = third position estimate) bezieht sich auf eine abgeschätzte absolute Position von irgendeinem Fahrzeug, die in irgendeiner Form vom Fahrzeugpositionsbestimmungssystem ausgegeben wurde. Die dritten Positionsabschätzungen sind genauere Positionsabschätzungen der Fahrzeugpositionen im Vergleich zu den ersten und zweiten Positionsabschätzungen. Die dritte Position wird von den ersten und zweiten Positionsabschätzungen durch das VPS-Verarbeitungssystem abgeleitet.
(46) "Fahrzeug" bedeutet irgendeinen Träger zum Transport von physischen Dingen. Fahrzeuge können die Form von Bergbaulastwägen, Baulastwägen, Farmtraktoren, Automobilen, Schiffen, Booten, Eisenbahnen, Ballons, Raketen oder Flugzeugen annehmen. Im bevorzugten Ausführungsbeispiel wird ein 785 PFF-Geländelastwagen von Caterpillar Inc. verwendet.
(47) "Fahrzeugpositionsbestimmungssystem" oder "VPS" (VPS = vehicle positioning system) bezieht sich auf das System, das Positionsabschätzungen von irgendeinem Fahrzeug ableitet. Die Positionsabschätzungen von dem Fahrzeugpositionsbestimmungssystem sind extrem genau und können von einem Navigationssystem auf irgendeinem Fahrzeug verwendet werden, um das genau Fahrzeug zu führen. Positionsabschätzungen werden von dem Fahrzeugpositionsbestimmungssystem als dritte Positionsabschätzungen bezeichnet.
(48) "VPS-Verarbeitungssystem" bedeutet das Verarbeitungssystem des Fahrzeugpositionsbestimmungssystems bzw. des VPS. Das VPS-Verarbeitungssystem leitet dritte Positionsabschätzungen von den ersten und zweiten Positionsabschätzungen ab. Die Architektur ist in den Fig. 10 und 11 abgebildet.
(49) "Gewichtete Kombination" bezieht sich auf ein spezielles Softwareprogramm, das Daten verarbeitet. Die eingegebenen Daten werden einem vorbestimmten Gewichtungsfaktor zugeordnet, und zwar basierend auf der abgeschätzten Genauigkeit der Daten und der Technik, die verwendet wird, um die Daten zu sammeln. Beispielsweise wird die erste Positionsabschätzung des GPS-Signals 716 schwerer gewichtet als die zweite Positionsabschätzung des Trägheitsreferenzeinheitssignals 910, da ersteres inhärent genauer ist. Weiterhin kann die Geschwindigkeit, die von der Trägheitsreferenzeinheit gemessen wurde, schwerer gewichtet werden, als die Geschwindigkeit, die von dem GPS- Verarbeitungssystem gemessen wird, da erstere genauer ist. Die Geschwindigkeit, die von dem GPS-Verarbeitungssystem gemessen wird, wird überhaupt nicht verwendet, könnte jedoch in anderen Aufbauten verwendet werden.
(50) "Technik der gewichteten Pfadhistorie" ist ein Verfahren oder ein Prozeß zur Steigerung der Genauigkeit der ersten Positionsabschätzungen, die aus dem GPS-Verarbeitungssystem ausgegeben werden. Die Technik verwendet frühere erste Positionsabschätzungen, um ein Fahrzeugpfadmodell abzuleiten, um die Gültigkeit der zukünftigen ersten Positionsabschätzungen zu testen. Die Anwendung der Technik der gewichteten Pfadhistorie hat eine Verringerung des Wanderns der ersten Positionsabschätzungen und eine verbesserte Immunität gegenüber falschen Positionsberechnungen zur Folge.

II. Allgemeiner Überblick

Fig. 1 veranschaulicht ein High-Level-Blockdiagramm 100 des beispielhaften Systems. Um den genauen autonomen Betrieb eines Fahrzeugs 102 auf oder nahe der Erdoberfläche vorzusehen, weist das beispielhafte System sowohl ein Fahrzeugpositionsbestimmungssystem (VPS = vehicle positioning system) 1000 als auch ein Navigationssystem 1022 auf. Diese beiden Systeme weisen eine Vorrichtung, Verfahren und Techniken auf, die, wenn sie zusammen integriert sind, eine hochgenaue Steuerung von unbemannten Fahrzeugen vorsehen.

A. Fahrzeugpositionsbestimmungssystem (VPS)

Die Aufgabe, das autonome Fahrzeug 102 entlang eines vorbeschriebenen Pfades zu führen, erfordert u. a. eine genaue Schätzung der augenblicklichen bzw. laufenden bzw. Ist-Fahrzeugposition, relativ zu einem Referenzpunkt. Sobald die laufende bzw. Ist-Position bekannt ist, kann das Fahrzeug 102 angewiesen werden, zu seiner nächsten Bestimmung voranzugehen bzw. zu fahren.
Unter Verwendung der VPS 1000 können Positionsabschätzungen des Fahrzeugs 102 mit extremer Genauigkeit bestimmt werden. Das VPS 1000 empfängt GPS-Daten von GPS- Satelliten 104 von einem GPS, wie beispielsweise dem NAV- STAR-GPS oder dem GLONASS GPS.
Das NAVSTAR-GPS wird verwendet. Fig. 1A veranschaulicht das NAVSTAR-GPS. GPS-Satelliten 130-168 laufen um die Erde 172 in sechs Orbitalen bzw. Umlaufbahnen 174-184.
Mit Bezug auf Fig. 1 kann das VPS 1000 auch Pseudolitendaten von Pseudolit(en) 105 empfangen. Der Ausdruck "Pseudolit" im Zusammenhang mit diesem Dokument bedeutet eine strahlungsaussendende bzw. strahlende Vorrichtung auf oder nahe der Erdoberfläche, um einen GPS-Satelliten zu emulieren bzw. nachzubilden.
Aus den GPS-Daten und/oder den Pseudolitendaten leitet das VPS 1000 genaue Schätzungen der Position des Fahrzeugs 102 ab. Die GPS-Daten und/oder die Pseudolitendaten werden signifikant über zahlreiche erfindungsgemäße Techniken und Verfahren des beispielhaften Systems verbessert bzw. verstärkt, um die Genauigkeit der Fahrzeugpositionsabschätzung zu verbessern.
Insbesondere ist das VPS 1000 ein Positionierungs- bzw. Positionsbestimmungssystem, basierend auf der Verwendung von GPS-Daten vom NAVSTAR-GPS 104 und von einem Bewegungspositionierungs- bzw. Bewegungspositionsbestimmungssystem 900. Das Bewegungspositionierungssystem 900 weist eine Trägheitsreferenzeinheit (IRU = inertial reference unit) 904 und/oder ein Fahrzeugodometer bzw. -wegmesser 902 auf. Die IRU 904 weist ein oder mehrere Lasergyroskope 106 und einen oder mehrere Beschleunigungsmesser 108 auf, die verwendet werden können, um die Position, die Geschwindigkeit, die Querneigung bzw. Rollneigung, die Höhe und die Gierungs- bzw. Neigungsdaten zu erzeugen. Der Fahrzeugswegmesser 902 erzeugt Daten über die vom Fahrzeug 102 gelaufene Distanz.
Eine erste Positionsabschätzung des Fahrzeugs 102 wird durch das GPS-Verarbeitungssystem 700 von den GPS-Daten abgeleitet, die von den GPS-Satelliten 104 und von den Pseudolitendaten empfangen werden, die von dem (den) Pseudolit(en) 105 empfangen werden. Um die Genauigkeit der ersten Positionsabschätzung zu verbessern, verwendet das beispielhafte System eine Anzahl von Verfahren, die unten besprochen werden. Zusätzlich wird eine zweite Positionsabschätzung durch den MPS-Kommunikationsprozessor 906 des Bewegungspositionssystems 900 abgeleitet, welches die IRU 904 und/oder den Fahrzeugswegmesser 902 aufweist. Wie durch die jeweiligen Pfeile 112 und 114 gezeigt, werden die erste Positionsabschätzung und die zweite Positionsabschätzung dann durch ein VPS-Verarbeitungssystem 116 kombiniert und gefiltert. Das Ergebnis, wie durch einen Ausgabepfeil 118 gezeigt, ist eine genauere dritte Positionsabschätzung.

B. Navigationssystem

Das Navigationssystem 1022 empfängt die dritte Positionsabschätzung vom VPS 1000. Das Navigationssystem 1022 verwendet die präzise dritte Positionsabschätzung, um das Fahrzeug 102 genau zu navigieren. Ein primärer Zweck des Navigationssystems 1022 ist es, das Fahrzeug 102 zwischen Punkten entlang eines vorbestimmten oder dynamisch erzeugten Pfades zu führen.
Das Navigationssystem 1022 ist im Fahrzeug 102 selbst gelegen. In anderen Worten ist es im wesentlichen ein "On- Board"- bzw. an Bord befindliches System. Darüberhinaus kann das Navigationssystem 1022 ausgelegt bzw. konstruiert sein, um in dem Fahrzeug 102 nachgerüstet zu werden.
So daß das Navigationssystem 1022 das Fahrzeug 102 führen kann, um voreingestellten oder dynamisch erzeugten Pfaden zu folgen, werden verschiedene Modelle oder konzeptionelle Darstellungen erzeugt und verwendet. Beispielsweise können Linien und Kurven bzw. Bögen verwendet werden, um Fahrzeugpfade zwischen Objektpunkten einzurichten. Mathematische B-Splines oder Clothoid-Kurven können verwendet werden, um den tatsächlichen Pfad bzw. Weg zu modellieren, wo das Fahrzeug 102 navigieren muß. Diese mathematischen Kurven werden später in dieser Schrift genau besprochen.
Die Verwendung der obigen Modelierungs- oder Darstellungstechniken sieht verbesserte Datenkommunikationen, - speicherung und -behandlung des Fahrzeugs 102 vor. Die Techniken gestatten weiter eine Vereinfachung der Überwachungsaufgaben durch das Vorsehen einer Hierarchie von Steuerung und Kommunikation. Je höher ein Steuerpegel im hierarchischen Steuerschema existiert, desto einfacher ist die Aufgabe und desto kompakter sind die Befehle.
Das Navigationssystem 1022 sieht weiterhin die Steuerung der mechanischen Systeme des Fahrzeugs vor, wie beispielsweise Bremsen, Lenkung und Motor und Getriebe, um die notwendigen physikalischen Vorgänge bzw. Handlungen vorzunehmen, die erforderlich sind, um das Fahrzeug 102 zu bewegen, zu stoppen und zu lenken.
Das Navigationssystem 1022 überprüft auch die tatsächliche bzw. Ist-Position des Fahrzeugs 102 gegen die gewünschte bzw. Soll-Position, um die Fahrzeugsteuerung gemäß der gewünschten Position zu korrigieren. Das Navigationssystem 1022 kann Mehrfach-Status-Modelle bzw. Mehrzustandsmodelle laufen lassen, um diese Überprüfungsfähigkeit zu verbessern. Das Navigationssystem 1022 überprüft auch Fehler oder Versagen im System selbst und in Fahrzeugkomponenten. Wenn Fehler oder Versagen detektiert bzw. ermittelt werden, kann das Navigationssystem 1022 für einen versagenssicheren Shutdown bzw. Systemabschluß sorgen, und zwar dadurch, daß es das Fahrzeug 102 zu einem vollständigen Stop bringt.
Das Navigationssystem 1022 sieht weiter verschiedene Betriebszustände zum Steuern des Fahrzeugs 102 vor. Diese weisen folgende auf: (1) Einen vollständig autonomen bzw. automatischen Modus, wo die Navigation des Fahrzeugs 102 automatisch durch das Navigationssystem 1022 behandelt wird; (2) einen Tele- oder Remote-Steuermodus, wo ein entfernter menschlicher (nicht gezeigter) Bediener die Richtung und Bewegung usw. des Fahrzeugs 102 steuern kann; und (3) einen manuellen Modus, bei dem ein menschlicher Bediener, der im Fahrzeug 102 sitzt, die Steuerung des Fahrzeugs 102 übernehmen kann und es manuell fahren kann.
Im autonomen Modus ist die Hindernisdetektion kritisch, da, wenn das Fahrzeug 102 nicht unter Kontrolle bzw. Steuerung ist, es großen Sachschaden und starke Verletzungen von Lebewesen erzeugen könnte. Das Navigationssystem 1022 kann effizient bzw. wirkungsvoll Hindernisse detektieren. Steine, Tiere, Menschen, Bäume oder andere Hindernisse können unerwartet in den Pfad bzw. Weg des Fahrzeugs 102 eintreten. Das Navigationssystem 1022 ist fähig, diese Hindernisse zu detektieren, und zwar entweder durch Stoppen oder durch das Ziehen bzw. Entwerfen eines Pfades um das Hindernis herum und durch Zurückbringen des Fahrzeugs 102 auf seinen Originalweg, wenn der Weg als sicher angesehen wird.
Eine genaue Verfolgung des gewünschten bzw. Soll-Wegs bzw. der Soll-Route ist eine weitere Funktion des Navigationssystems 1022. Das Funktionieren und die Architektur des Navigationssystems 1022 ist für eine Echtzeitverfolgung der Fahrzeugpfade ausgelegt bzw. konstruiert worden, und zwar bei Geschwindigkeit bis zu ungefähr 30 Meilen pro Stunde (mph).

C. Basisstation

Das beispielhafte System kann ein Host- bzw. Hauptverarbeitungssystem 186 in einer Basisstation 188 aufweisen. Das Host-Verarbeitungssystem 186 führt Funktionen für sowohl das VPS 1000 als auch für das Navigationssystem 1022 aus.
Mit Bezug auf das VPS 1000 empfängt das Host-Verarbeitungssystem 186 GPS-Daten und/oder Pseudolitendaten, wie durch die jeweiligen Pfeile 190 und 192 gezeigt. Im Endeffekt kann das Host-Verarbeitungssystem 186 genauso wie die Basisstation 188 als ein bekannter Referenzpunkt funktionieren, um die Genauigkeit der Fahrzeugpositionsabschätzungen zu verbessern, wie unten im Detail besprochen.
Das Host-Verarbeitungssystem 186 implementiert eine Anzahl von Verfahren zum Verbessern der Genauigkeit der Fahrzeugpositionsabschätzungen. Das Satellitenpositionsvorhersageverfahren 1800, welches oben besprochen wurde, wird auch durch das Host-Verarbeitungssystem 186 implementiert bzw. eingerichtet. Das Host-Verarbeitungssystem 186 wird die gleiche Satellitenkonstellation erkennen, die vom Fahrzeug 102 beobachtet wird.
Berechnungen werden an den GPS-Daten und/oder den Pseudolitendaten ausgeführt, um Auslenkungen bzw. Ableitungen (biases) abzuleiten. Der Ausdruck "Ableitung" ("bias") im Zusammenhang mit diesem Dokument bezieht sich auf eine Differenz bzw. einen Unterschied zwischen zwei Messungen, gewöhnlicherweise Positionsabschätzungen (räumliche Ableitung) oder Clock- bzw. Taktraten (Taktableitung). Weil eine Messung gewöhnlicherweise als genauer bekannt ist als die andere, wird auf die Ableitung bzw. den Bias oft als ein "Fehler" ("error") Bezug genommen.
Um räumliche Ableitungen zu berechnen, implementiert das Host-Verarbeitungssystem 186 eine Anzahl von Verfahren. Unter diesen Verfahren sind beispielsweise folgende vorgesehen: Eine originale Ableitungstechnik 1500, eine parabolische Ableitungstechnik 1600, eine Basisresiduen- Ableitungstechnik 1700, und eine Basiskorrelations- Ableitungstechnik 1700A.
Die vorangegangenen Differential- bzw. Differenzkorrekturtechniken kompensieren Datenfehler. In anderen Worten zeigen die Ableitungen bzw. Biases, die im Host- Verarbeitungssystem 186 berechnet werden, Datenfehler an. Wie durch einen Pfeil 194 gezeigt, werden die Ableitungen zum GPS-Verarbeitungssystem 700 des Fahrzeugs 102 übertragen. Das GPS-Verarbeitungssystem 700 verwendet diese Biases bzw. Ableitungen, um Fehler in den Fahrzeugpositionsabschätzungen zu eliminieren.
Das Host-Verarbeitungssystem 186 sieht weiter Funktionen vor, die sich auf das Navigationssystem 1022 des beispielhaften Systems beziehen. Das Host- Verarbeitungssystem 186 dient als das höchste Steuerniveau des Navigationssystems 1022, wie durch einen Pfeil 196 angezeigt. Es behandelt die Zeitplanung und - einteilung des Fahrzeugs 102 mit genau den gleichen Ergebnissen wie ein menschlicher Fahrdienstleiter bzw. Einteiler erreichen würde. Folglich kann das Host- Verarbeitungssystem 186 dadurch den Arbeitszyklus des Fahrzeugs 102 bestimmen.
Das Host-Verarbeitungssystem 186 befiehlt dem Fahrzeug 102, aus einer laufenden bzw. Ist-Position in eine zukünftige bzw. Soll-Position voranzuschreiten bzw. zu fahren, und zwar über eine festgelegte Route, so daß das Fahrzeug 102 seine Arbeitsziele durchführen kann. Das Host-Verarbeitungssystem 186 kann die Fahrzeugrouten durch den Namen festlegen, anstelle durch Auflisten eines jeden Punktes entlang der Route, wie es in herkömmlicher Weise der Fall ist. Dementsprechend schaut das an Bord gelegene Navigationssystem 1022 des Fahrzeugs die benannte Fahrzeugroute nach und überträgt die benannte Fahrzeugroute in Sätze von Knoten und Segmenten entlang der genannten Fahrzeugroute.

III. Fahrzeugpositionsbestimmungssystem

Die folgende Besprechung mit Bezug auf das VPS 1000 wird insbesondere Bezug auf die Fig. 7 bis 11 nehmen. Die Fig. 10 und 11 zeigen die Architektur/Hardware des VPS 1000. Das VPS 1000 ist ein hochgenaues Positionsbestimmungssystem, für ein sich bewegendes oder stationäres Fahrzeug 102 auf oder nahe der Erdoberfläche.
Es sei daran erinnert, daß das VPS 1000 das GPS-Verarbeitungssystem 700 und das MPS 900 aufweist, die in den jeweiligen Fig. 7 und 9 gezeigt sind. Weiter sei daran erinnert, daß das MPS 900 die IRU 904 und den Fahrzeugwegmesser 902 aufweist, die beide in Fig. 9 gezeigt sind. Im Endeffekt sind diese Systeme durch das beispielhafte System verbessert und integriert worden, um ein hocheffektives Positionsbestimmungssystem zu erzeugen.
Mit Bezug auf Fig. 7 weist das GPS-Verarbeitungssystem 700 eine Antenne 702 auf, die mit einem GPS-Empfänger 706 verbunden ist. Wenn die GPS-Satelliten 104 im Blickfeld der Antenne 702 mehrfache GPS-Satelliten 200-206 aufweisen, wie in den Fig. 2 und 3 gezeigt, liest der GPS- Empfänger 706 alle ihre GPS-Daten zusammen mit irgendwelchen Pseudolitendaten von irgendeinem (irgendwelchen) Pseudolit(en) 105 im Blickfeld der Antenne 702. Im bevorzugten Ausführungsbeispiel ist der GPS-Empfänger 706 für die Berechnung der ersten Positionsabschätzung des Fahrzeugs 102 aus den GPS-Daten und/oder den Pseudolitendaten verantwortlich.
Um die Genauigkeit des ersten Positions- bzw. Positionsbestimmungsverfahrens zu vergrößern, wird das Satellitenpositionsvorhersageverfahren 1800 durch einen GPS-Prozessor 710 des GPS-Verarbeitungssystem 700 implementiert bzw. eingerichtet. Das Satellitenpositionsvorhersageverfahren 1800 sagt die Position von irgendeinem GPS-Satelliten zur laufenden bzw. augenblicklichen Zeit oder für irgendeine zukünftige Zeit voraus.
Unter Verwendung der Satellitenpositionsinformation kann das GPS-Verarbeitungssystem 700 die optimale GPS-Satellitenkonstellation zum Erkennen bestimmen, und zwar unter Verwendung eines Konstellationseffekt-Verfahrens 1300. Das Konstellationseffekt-Verfahren 1300 wird auch vom GPS-Prozessor 710 implementiert bzw. eingerichtet. Gemäß des Konstellationseffekt-Verfahrens 1300 wird eine beste Konstellation aus den Datenquellen ausgewählt, die die GPS-Satelliten 200-206 und Pseudolit(en) 105 aufweisen.
Der GPS-Prozessor 710 berechnet eine erste Positionsabschätzung des Fahrzeugs 102 basierend auf der besten Konstellation und auf Geometrie/Triangulations-Verfahren. Die Genauigkeit der ersten Positionsabschätzung ist teilweise abhängig von der bei der Berechnung verwendeten Anzahl von GPS-Satelliten. Jeder zusätzliche verwendete GPS-Satellit kann die Genauigkeit der ersten Positionsabschätzung vergrößern. Nach der Berechnung wird die erste Positionsabschätzung des Fahrzeugs 102 an einen VPS- Hauptprozessor 1002 der Fig. 10 übertragen.
Mit Bezug auf Fig. 9 weist die IRU 904 Lasergyroskope und Beschleunigungsmesser auf, die Positions-, Geschwindigkeits-, Roll- bzw. Längsneigungs-, Höhen- und Neigungsdaten erzeugen. Die IRU 904 kombiniert diese Information in eine zweite Positionsabschätzung des Fahrzeugs 102. Der Wegmesser 902 kann implementiert werden, um die vom Fahrzeug 102 gelaufene bzw. gefahrene Distanz zu messen. Die Daten von der IRU 904 und vom Wegmesser 902 werden auch über den MPS-Kommunikationsprozessor 906 an den VPS-Hauptprozessor 1002 übertragen, und zwar wie in Fig. 10 gezeigt.
Der VPS-Hauptprozessor 1002 kombiniert die zweite Positionsabschätzung vom MPS 900 (die IRU 904 und vielleicht der Wegmesser 902) mit der ersten Positionsabschätzung vom GPS-Verarbeitungssystem 700, um eine genauere dritte Positionsabschätzung zu erzeugen.
Das VPS 1000 implementiert weiter ein Verfahren zum Eliminieren von irrtümlichen oder falschen dritten Positionsabschätzungen, die ein "Fahrzeugabwandern" bzw. ein "Fahrzeugabweichen" bewirken können. Dieses Verfahren wird Verfahren mit gewichteter Pfadhistorie genannt. Im wesentlichen wird die Pfadhistorie bzw. Pfadgeschichte des Fahrzeugs 102 verwendet, um statistisch die Genauigkeit von zukünftigen Schätzungen der Position des Fahrzeugs 102 zu bestimmen.
Mit Bezug auf die Fig. 1 und 3 sieht eine Basisstation 188 einen geographischen nahen Referenzpunkt für das VPS 1000 vor. Die Basisstation 188 weist ein Host- Verarbeitungssystem 186 auf. Das Host-Verarbeitungssystem 186 weist eine ähnliche Architektur auf, und führt die gleichen Funktionen wie das GPS-Verarbeitungssystem 700 aus. Jedoch führt das Host-Verarbeitungssystem 186 zusätzliche Funktionen zum Vergrößern der Genauigkeit der ersten Positionsabschätzungen aus.
Das Satellitenpositionsvorhersageverfahren 1800 wird durch das Host-Verarbeitungssystem 186 implementiert bzw. eingerichtet, und zwar zusätzlich zu dem oben besprochenen GPS-Verarbeitungssystem 700. Dementsprechend wird das Host-Verarbeitungssystem 186 die gleiche GPS-Satellitenkonstellation erkennen, die vom Fahrzeug 102 beobachtet wird, oder wird den gleichen GPS-Satelliten in einer größeren Konstellation aufweisen.
Berechnungen werden dann an den GPS-Daten und/oder den Pseudolitendaten ausgeführt, um Ableitungen (Biases) abzuleiten, und zwar einschließlich räumlicher Ableitungen und Taktableitungen. Um räumliche Ableitungen zu berechnen, implementiert das Host-Verarbeitungssystem 186 eine Anzahl von Verfahren.
Wie von einem Pfeil 194 gezeigt, werden die räumlichen Ableitungen und Taktableitungen an das GPS-Verarbeitungssystem 700 des Fahrzeugs 102 übertragen. Das GPS- Verarbeitungssystem 700 verwendet diese Ableitungen, um Fehler bei den Fahrzeugpositionsabschätzungen zu eliminieren.

IV. Navigationssystem

A. Überblick

Bei der Betrachtung der Einrichtung eines autonomen Navigationssystems gibt es gewisse grundlegende Fragen, die irgendein autonomes System beantworten können muß, um erfolgreich vom Punkt A zum Punkt B zu navigieren. Die erste Frage ist "Wo sind wir (das Fahrzeug) jetzt?". Die erste Frage wird beantwortet durch den Positionsbestimmungssystemteil der vorliegenden Erfindung, wie oben im Abschnitt III besprochen.
Die nächste oder zweite Frage ist "Wohin fahren wir und wie kommen wir dort hin?". Diese zweite Frage fällt in den Bereich des Navigationssystemteils des beispielhaften Systems, der in diesem Abschnitt (IV) besprochen wird.
Eine weitere (dritte) Frage, eigentlich eine Verfeinerung der zweiten, ist "Wie bewegen wir tatsächlich physisch das Fahrzeug, beispielsweise welche Betätigungsvorrichtungen (Lenkung, Geschwindigkeit, Bremse usw.) sind beteiligt, um dorthin zu kommen?". Dies ist der Bereich des Fahrzeugsteueruntersystems des Navigationssystems, der auch unten besprochen wird.
Wie implizit oben besprochen wurde, kann die autonome Navigation von beispielsweise einem Bergbaufahrzeug gewisse signifikante Vorteile gegenüber der herkömmlichen Navigation bieten. Unter Ihnen ist eine gesteigerte Produktivität eines 24stündigen Betriebes des Fahrzeuges rund um die Uhr. Die Probleme, die von gefährlichen Arbeitsumgebungen oder von Arbeitsumgebungen, wo die Sicht schlecht ist, dargestellt werden, sind insbesondere gut zur Lösung durch ein autonomes System geeignet.
Es gibt beispielsweise einige Bergbau- bzw. Tagebaugelände, wo die Sicht so schlecht ist, daß eine Arbeit für 200 Tage des Jahres nicht möglich ist. Es gibt andere Gebiete, die für menschliches Leben gefährlich sind, da sie durch industrielle oder nukleare Verschmutzung verunreinigt sind. Ein Gebiet kann so abgelegen oder verwüstet sein, daß wenn es erforderlich wäre, daß Menschen dort arbeiten, dies starke Einschränkungen mit sich bringen würde oder unpraktisch sein würde. Die Anwendung des beispielhaften Systems könnte in vorhersehbarer Weise Betriebsvorgänge außerhalb der Erde mit einschließen, beispielsweise Bergbau auf dem Mond, vorausgesetzt, daß die notwendigen GPS-Satelliten in die Umlaufbahn des Mondes gebracht werden.
Bei einer typischen Anwendung, wie in Fig. 3 gezeigt, gibt es mit Bezug auf die Navigation eines Bergbaufahrzeuges auf einem Bergbaugelände drei grundlegende Arbeitsgebiete: die Beladungsstelle, das Liefersegment und die Abladestelle. An der Beladungsstelle kann ein Lieferfahrzeug mit Erz auf eine Vielzahl von Arten beladen werden, beispielsweise durch von Menschen bediente Schaufellader, die entweder direkt oder durch Fernsteuerung gesteuert werden, oder durch autonome Schaufellader. Das Lieferfahrzeug muß dann über ein Gebiet fahren, das Liefersegment genannt wird, welches nur ein paar hundert Meter sein kann oder mehrere Kilometer sein kann. Am Ende des Liefersegmentes liegt die Abladestelle, wo das Erz aus dem Lieferfahrzeug ausgeladen wird, um beispielsweise zerkleinert zu werden oder in anderer Weise bearbeitet zu werden. Die autonome Positionsbestimmung und Navigation kann verwendet werden, um das Lieferfahrzeug entlang des Liefersegmentes zu steuern. Autonom navigierte Tankfahrzeuge und Instandhaltungsfahrzeuge werden auch in Betracht gezogen.
Mit Bezug auf die Fig. 4 und 5 umfaßt die Navigation des autonomen Bergbaulastwagens (AMT = Autonomous Mining Truck) verschiedene Systeme, Vorrichtungen und/oder Funktionen. Das Untersystem des Fahrzeugpositionsbestimmungssystems 1000 des gesamten autonomen Bergbaulastwagensystems wie oben besprochen gibt Positionsdaten aus, die anzeigen, wo das Fahrzeug gelegen ist, die beispielsweise die Nord- bzw. Längen- und die Ost- bzw. Breitenposition aufweisen.
Mit Bezug auf die Fig. 4 und 5 werden Positionsdaten, die vom Fahrzeugspositionsbestimmungssystem ausgegeben werden, von einem Navigator 406 aufgenommen. Der Navigator bestimmt, wo das Fahrzeug hinfahren möchte (aus den Routendaten) und wie es dort hin kommt, und gibt wiederum Daten aus, die aus Lenk- und Geschwindigkeitsbefehlen an einen Fahrzeugsteuerfunktionsblock 408 zusammengesetzt sind, um das Fahrzeug zu bewegen.
Der Fahrzeugsteuerblock gibt dann Befehle auf niedrigem Niveau an die verschiedenen Systeme des Fahrzeugs 102 aus, wie beispielsweise an die Regelungsvorrichtung (governor) die Bremsen und das Getriebe. Wenn das Fahrzeug sich zu seinem Bestimmungsort hin bewegt, blockieren die Fahrzeugsteuerungen, und das Fahrzeugpositionsbestimmungssystem empfängt Rückkoppelungsinformationen von dem Fahrzeug, die beispielsweise irgendwelche Fehlerzustände in den Fahrzeugsystemen, die gegenwärtige Geschwindigkeit usw. anzeigen.
Die Navigation muß auch eine Hindernisbehandlungsfähigkeit (Detektion und Vermeidung) aufweisen, um mit dem Unerwarteten fertig zu werden. Ein Abtastsystem bzw. Scannersystem 404 detektiert Hindernisse in der projizierten Laufbahn des Fahrzeuges, genauso wie Hindernisse, die sich von den Seiten nähern können, und informiert den Navigator darüber.
Es kann erforderlich sein, daß der Navigator dann entscheidet, ob eine Handlung erforderlich ist, um an dem Hindernis vorbeizufahren. Wenn eine Handlung erforderlich ist, entscheidet der Navigator, wie das Hindernis zu vermeiden ist. Und nach dem das Hindernis vermieden bzw. umfahren worden ist, entscheidet der Navigator, wie das Fahrzeug zurück auf einen Pfad zu seinem Bestimmungsort hin kommen soll.
Mit Bezug auf Fig. 22, die als Kontextdiagramm bezeichnet wird, und mit Bezug auf Fig. 24A-24D sind Definitionen der Kommunikationsvorgänge, die als Kreise mit Zahlen darin gezeigt sind, unten beschrieben:
502. Host-Befehle und Anfragen:
Befehle, die von dem Host an den Fahrzeugmanager gegeben werden. Diese Befehle könnten von verschiedener Art sein:
Einleiten/Beenden
Versorgungsparameter;
Nothandlungen; und
Anweisungen
Die Anforderungen fragen nach dem Zustand von verschiedenen Teilen des Navigators.
504. Antworten an den Host:
Dieses sind Antworten auf die Fragen, die von dem Host gestellt wurden.
432. Positionsdaten:
Dies ist eine strömende bzw. nicht abreißende Information, die von dem Fahrzeugpositionsbestimmungssystem (VPS) geliefert wird.
416. Bereichsdaten:
Dies sind Bereichsdaten von dem Linienlaserscanner.
432. VPS-Steuerung:
Dies sind Befehle, die dem Fahrzeugpositionsbestimmungssystem gegeben wurden, um es einzuschalten bzw. hochzufahren, abzuschalten bzw. herunterzufahren und zwischen Betriebszuständen umzuschalten.
416. Scannersteuerung:
Dies sind Befehle, die an den Laserscanner gesandt werden, um eine Bewegung einzuleiten und das Folgegeschwindigkeitsprofil einzustellen.
420. Lenk- und Geschwindigkeitsbefehle:
Dies sind Befehle, die an das Fahrzeug ausgegeben werden, um die Lenkung und Geschwindigkeit zu steuern. Diese Befehle werden mit einer Rate von 2 bis 5 Hertz ausgegeben.
Mit Bezug auf Fig. 5 sind sowohl das Fahrzeugpositionsbestimmungssystem als auch der Navigator auf dem Fahrzeug gelegen und kommunizieren mit der Basisstation 188 zur Aufnahme von GPS-Positionsinformationen auf hohem Niveau und Anweisungen von einem Host-Verarbeitungssystem 186. Das System gewinnt GPS-Positionsinformationen von den GPS-Satelliten 200-206 an der Basisstation und an Bord des Fahrzeugs, so daß ein gemeinsamer Betriebszustandsfehler entfernt werden kann und die Genauigkeit verbessert werden kann. Alternativ können Teile des Fahrzeugpositionsbestimmungssystems und des Navigators an der Basisstation gelegen sein.
Der Host an der Basisstation kann den Navigator anweisen, beispielsweise von einem Punkt A zum Punkt B zu fahren, und kann eine von einem Satz von festen Routen zur Anwendung anweisen. Der Host behandelt auch andere typische Einteilungs- und Zeitplanungsaktivitäten, wie beispielsweise die Koordination von Fahrzeugen und Ausrüstungsgegenständen, um den Wirkungsgrad zu maximieren, Kollisionen zu vermeiden, Instandhaltungen einzuplanen, Fehlerzustände zu detektieren usw. Der Host hat auch eine Betriebsschnittstelle für einen menschlichen Manager.
Es ist herausgefunden worden, daß es wünschenswert ist, den Host an der Basisstation anzuordnen und den Navigator am Fahrzeug, um einen Engpass bei der Kommunikation zu vermeiden, und eine daraus resultierende Verschlechterung der Leistung und des Ansprechens. Da der Host Befehle auf relativ hohem Niveau und vereinfachte Daten an den Navigator sendet, erfordert er relativ wenig Kommunikationsbandbreite. In Situationen jedoch, wo eine Breitbandkommunikation verfügbar ist, kann dies kein Faktor sein.
Ein weiterer Faktor bei der Bestimmung der speziellen Lage von Elementen des Systems ist die Empfindlichkeit der autonomen Navigation für die Zeit. Das Navigationssystem muß kontinuierlich seine absolute und relative Lage überprüfen, um nicht akzeptable Ungenauigkeiten bei der Verfolgung einer Route zu vermeiden. Die erforderliche Frequenz der Überprüfung der Lage steigt mit der Geschwindigkeit des Fahrzeugs, und die Kommunikationsgeschwindigkeit kann ein einschränkender Faktor auch bei einer relativ moderaten Fahrzeuggeschwindigkeit werden.
Bei Anwendungen jedoch wo eine maximale Fahrzeuggeschwindigkeit nicht ein primärer Betrachtungspunkt ist, und/oder wo ein hoher Grad an Verfolgungsgenauigkeit der Straße nicht kritisch ist, kann dieser Kommunikationsfaktor unwichtig sein. Beispielsweise kann es bei einem relativ schnellen Überfahren von großen Ausdehnungen von offenem flachen Land auf einem relativ geraden Pfad nicht nötig sein, die Position so oft auf der Reise zu überprüfen, wie es bei der Navigation während einer Reise entlang einer kurvigen Bergstraße nötig wäre.
Konzeptionell können die Navigationsaspekte willkürlich in die folgenden Hauptfunktionen aufgeteilt werden:
Routenplanung/Pfaderzeugung;
Pfadverfolgung; und
Hindernisbehandlung.
Die Funktion der vorliegenden Erfindung wird unten besprochen.

B. Routenplanung/Pfaderzeugung

1. Einleitung

Die Navigation eines autonomen Fahrzeuges gemäß der vorliegenden Erfindung besteht konzeptionell aus zwei Unterproblemen, der Pfaderzeugung und der Pfadverfolgung, die getrennt gelöst werden.
Die Pfaderzeugung verwendet Zwischenziele von einer Planungsvorrichtung auf hohen Niveau, um einen detaillierten Pfad zu erzeugen, dem das Fahrzeug 102 folgen soll. Es gibt einen gewissen Abstrich zwischen der Vereinfachung der Darstellung von solchen Ebenen und der Leichtigkeit, mit der sie ausgeführt werden können. Beispielsweise ist es ein einfaches Schema, einen Pfad in gerade Linien und kreisförmige Kurven zu zerlegen. Jedoch können solche Pfade nicht präzise in einfacher Weise verfolgt werden, und zwar wegen Ungleichmäßigkeiten der Krümmung an Übergangspunkten von Segmenten, die plötzliche Beschleunigungen erfordern.
Folgend auf die Pfaderzeugung nimmt die Pfadverfolgung als Eingangsgröße den detaillierten, erzeugten Pfad auf und steuert das Fahrzeug 102, so daß es dem Pfad so präzise wie möglich folgt. Es ist nicht genug, einfach einer zuvor aufgestellten Liste von Lenkungsbefehlen zu folgen, da wenn man dabei versagt, die erforderlichen Lenkbewegungen genau zu erreichen, dies Versetzungsfehler im stetigen Zustand (steady state) zur Folge hat. Die Fehler sammeln sich mit der Zeit an. Eine globale Positionsrückkoppelung 432 kann verwendet werden, um weniger als ideale Betätigungsvorrichtungen zu kompensieren. Es sind Verfahren für die vorliegende Erfindung entwickelt worden, die von dem traditionellen Fahrzeugsteuerschemata abweichen, bei denen eine Zeithistorie der Position (eine Laufbahn bzw. Trajektorie) in dem Plan vorgesehen ist, der für das Fahrzeug 102 festgelegt wird.
Diese Verfahren werden in geeigneter Weise als "Pfadverfolgung" bezeichnet, und zwar dahingehend, daß die Lenkbewegung von der Zeit entkoppelt ist; d. h. Lenkbewegungen sind direkt in Bezug zur geometrischen Natur des festgelegten Pfades, was die Geschwindigkeit des Fahrzeugs 102 zu einem unabhängigen Parameter macht.
Mit Bezug auf Fig. 3 kann ein autonomes Fahrzeug 102 erforderlich sein, um ein Liefersegment 320 zu einer Abladestelle 322 zu überqueren, und nachdem es seine Last abgeladen hat, über ein weiteres Liefersegment zu einer Werkstatt 324 zu fahren, und zwar unter der Anweisung des Host-Verarbeitungssystems 186. Das Host-Verarbeitungssystem 186 bestimmt die Bestimmungsorte des Fahrzeugs 102, was "Zyklusplanung" genannt wird. Die Bestimmung, welche Routen genommen werden sollten, um zu einem erwünschten Bestimmungsort zu kommen, müssen durch "Routenplanung" erreicht werden.
"Routenplanung" ist die Bestimmung, welche Pfadsegmente zu nehmen sind, um zu einem erwünschten Bestimmungsort zu kommen. Im allgemeinen kann eine Route als eine Abstraktion oder Darstellung eines Satzes von Punkten zwischen zwei definierten Lagen auf hohem Niveau angesehen werden. Wie man zu einem menschlichen Fahrer sagen kann "Nimm die Route 95 nach Süden von Lobster, Maine nach Miami, Florida", und der Fahrer die Anweisung in eine Abfolge von Operationen übersetzen werden wird (die das Starten des Fahrzeugs 102, das Lösen der Bremse 4406, das Einlegen des Getriebes 4610, die Beschleunigung auf die angewiesene Geschwindigkeitsbegrenzung, das Lenken des Lenkrades 4910, das Umfahren von Hindernissen 4002 usw. miteinschließen können), arbeitet das autonome Navigationssystem der vorliegenden Erfindung in ähnlicher Weise. Wie sie in dem System der vorliegenden Erfindung verwendet wird, ist eine "Route" eine Abfolge von aneinander liegenden "Segmenten" zwischen dem Beginn und dem Ende einer Reise.
Ein autonomes Fahrzeug 102 kann an irgendeiner Position in der Sequenz beginnen und über die Route in jeder Richtung fahren. Ein "Segment" ist der "Pfad" zwischen "Knoten". Ein "Knoten" ist eine "Ausrichtung" auf einem Pfad, die eine Entscheidung erfordert. Beispiele von Knoten sind Beladungsstellen 3318, Abladestellen 322 und Schnittstellen 326.
Es gibt verschiedene Arten von Segmenten. Beispielsweise gibt es lineare und kreisförmige Segmente. Die linearen Segmente (Linien) sind durch zwei Knoten definiert. Kreisförmige Segmente (Bögen) werden durch drei Knoten definiert.
"Lagen" (Postures) werden verwendet, um beispielsweise Teile einer Route, Pfade und Knoten zu modellieren. Lagen können aus einer Position, einer Richtung, einer Krümmung, einer maximalen Geschwindigkeit und anderen Informationen für einen gegebenen Punkt auf dem Pfad bestehen.
Ein "Pfad" ist eine Abfolge von aufeinander folgenden Lagen.
Ein Segment ist daher eine Abfolge von aneinanderfolgenden Lagen zwischen Knoten. Alle Segmente haben eine damit assoziierte Geschwindigkeit, die die maximale Geschwindigkeit festlegt, mit der das Fahrzeug 102 über dieses Segment fahren kann. Der Navigator 406 kann langsamere Geschwindigkeiten anweisen, um andere Anforderungen zu erfüllen, falls nötig.
Die Bestimmung, welche Lagen erforderlich sind, um ein Pfadsegment durch analytische Verfahren, experimentelle Verfahren oder eine Kombination von beiden zu definieren, wird "Pfadplanung" gemäß der vorliegenden Erfindung genannt. Um die Besprechung zu vollenden, wird eine Abfolge von aneinander liegenden Routen, wie oben erwähnt, als "Zyklus" bezeichnet, und die Arbeitsziele eines Fahrzeuges 102 bestimmen seinen "Zyklus".
Um daher eine Route zu definieren, muß man zuerst die Knoten und Segmente definieren. Als nächstes müssen die Knoten und Segmente angewiesen werden. Schließlich müssen die Routen definiert werden durch Festlegen, wo in dem angewiesenen Satz eine Route beginnen soll, und in welcher Richtung der angewiesene Satz zu überfahren ist (siehe Fig. 12, die diese Konzepte der vorliegenden Erfindung veranschaulicht).
Das zuvor erwähnte Verfahren zur Definition von Routen wurde für eine Speichereffizienz in der vorliegenden Erfindung entwickelt. Es ist auch ein bequemer Weg zur Definition von vielen Routen auf einen speziellen Satz von Knoten und Segmenten.
Bei einem Beispiel der vorliegenden Erfindung aus der wirklichen Welt kann ein Bild eines Geländes vorgesehen werden, wo es viele sich schneidende Straßen 326 gibt. Ein Routenprogrammierer würde Knoten an den Schnittpunkten definieren und Segmente, um die Straßen zwischen den Schnittpunkten zu definieren. Die Routen würden daher durch Straßen und Schnittpunkte bestimmt werden. Es wird jedoch viele Wege geben, um vom Punkt A zum Punkt B (viele Routen) mit einem festen Satz von Schnittpunkten und Straßen zu kommen.
Das Pfadverfolgungsverfahren der vorliegenden Erfindung (das unten besprochen wird) verwendet die Routenkrümmung zur Lenkung des Fahrzeugs. Die Verfahren der Routendefinition, die Linien und Bögen verwenden, liefern keine kontinuierliche Krümmung. Clothoid-Kurven sind ein weiterer Weg zur Definition von Routen.
Ein weiteres Verfahren zur Definition von Routen, die von den Erfindern entwickelt werden, paßt B-Splines in die Fahr- bzw. Wegdaten. B-Splines bieten eine kontinuierliche Krümmung und verbessern daher die Verfolgungsleistungen. Da zusätzlich B-Splines frei von Kurven sind, kann eine Route durch eine einfache B-Splinekurve definiert werden. Durch Verwendung von Freiformkurven wird ein robusteres Verfahren (halbautomatisch) zur Einpassung von Routen auf Daten, die durch das Fahren von dem Fahrzeug über die Routen gesammelt werden, durch die vorliegende Erfindung verwendet.
Mit Bezug auf die Fig. 4 und 12 weist im Betrieb das Host-Verarbeitungssystem 186 von der Basisstation 188 ein identifiziertes Fahrzeug 102 an, die Route N von der gegenwärtigen Stelle zu nehmen. Der Navigator 406 wirkt dahingehend, daß er einen Pfad erzeugt, und zwar durch Umsetzen von "Route 1" in eine Reihe von Segmenten, die jeweils eine "angewiesene" oder assoziierte maximale Geschwindigkeitsbegrenzung haben, die zusammen einen erzeugten Pfad bilden, dem das Fahrzeug zu folgen versuchen soll. Durch Festlegen von Routen und Anweisen des autonomen Fahrzeugs 102 mit Befehlen auf hohem Niveau in dieser Weise werden enorme Anforderungen von Daten und Ineffizienzen in der vorliegenden Erfindung beim Geben von Anweisungen vermieden.
Der Navigator 406 speichert die Routen als eine verbundene Liste von Pfadsegmenten anstelle des Satzes von Abfolgen von Sätzen der einzelnen Punkte. Diese Segmente sind auch Abstraktionen des Satzes von Punkten zwischen definierten Stellen oder Knoten.
Ein LINKER (Verbindungsanordnungsvorrichtung) nimmt dann die gegebenen Pfadsegmente und erzeugt eine verbundene Liste der Steuerpunkte, was Flexibilität und wirksame Anordnung gestattet. Pfadsegmente werden gemeinsam von unterschiedlichen Routen verwendet, wie in Fig. 12 gezeigt.
Die Pfadsegmente werden in einem Speicher gespeichert, der TARGA genannt wird, und zwar als ein Satz von Bögen, Linien und Lagen. Beispielsweise erzeugt eine analytische Generatorfunktion Pfade unter Verwendung dieser Bögen, Linien und Lagen. In einem weiteren Ausführungsbeispiel der vorliegenden Erfindung werden B-Splines (Kurven) als eine mathematische Darstellung einer Route verwendet, wie oben erwähnt.
In einem weiteren Ausführungsbeispiel der vorliegenden Erfindung werden "Clothoid-Kurven" bei der Erzeugung von Pfadsegmenten verwendet. Diese werden unten besprochen.

a. Clothoid-Pfadsegmente

Wie oben besprochen, hat der Teil des von der vorliegenden Erfindung angesprochenen und gelösten Navigationsproblems tatsächlich zwei Unterprobleme: Die Pfadplanung und die Pfaderzeugung. Diese werden von der vorliegenden Erfindung getrennt gelöst.
Die Pfadplanung geht voran von einem Satz von Unterzielen, die eine gewisse Pfadoptimierungsfunktion verwenden, und erzeugt eine geordnete Sequenz von "Objektivpunkten", die das Fahrzeug 102 erreichen muss.
Die Herausforderung der Pfaderzeugung ist es, aus den Objektivpunkten (der Pfadplanung) einen kontinuierlichen kollisionsfreien Pfad 3312 zu erzeugen, der glatt genug ist, dass das autonome Fahrzeug 102 ihm leicht folgen kann. Beispielsweise ist es ein einfaches Schema, einen Pfad 3312 in gerade Linien und kreisförmige Kurven zu zerlegen. Der Pfad 3312 wird dann in eine Abfolge von getrennten Zielen bzw. Anweisungen umgewandelt, die and die Betätigungsvorrichtungen des Fahrzeugs 102 geliefert werden, um das Fahrzeug auf dem erwünschten Pfad 3312 zu halten. Es sei bemerkt, dass es bei einer Vereinfachung der Darstellung dieser Pläne Nachteile bei der einfachen Art und Weise gibt, wie sie ausgeführt werden können ( Fig. 21).
Die Fähigkeit eines autonomen Fahrzeugs 102, einen festgelegten Pfad 3312 zu verfolgen, ist von den Charakteristiken des Pfades abhängig. Eine Kontinuität der Krümmung und die Veränderungsrate der Krümmung (Schärfe) des erzeugten Pfades ist von besonderer Wichtigkeit, da diese Parameter Lenkbewegungen vorgeben, die erforderlich sind, dass ein Fahrzeug 102 auf dem erwünschten Pfad 3312 bleibt. Ungleichmäßigkeiten der Krümmung kann man unmölich folgen, da sie eine unendliche Beschleunigung erfordern. Für manche Konfigurationen eines autonomen Fahrzeuges ist das Ausmaß, in dem die Schärfe eines Pfades linear ist, das Ausmaß, in dem Lenkbewegungen wahrscheinlich das Fahrzeug auf dem erwünschten Pfad 3312 halten, da die lineare Schärfe eines Pfades gleich einer ungefähren konstanten Lenkgeschwindigkeit ist.
Ein Verfahren, das von der vorliegenden Erfindung verwendet wird, ist es Pfade als eine Abfolge von geraden Linien und kreisförmigen Bögen zusammenzusetzen. Diese Verfahren leidet unter Diskontinuitäten in der Krümmung, wo sich die Bögen treffen. Ein weiteres Verfahren der vorliegenden Erfindung ist es, Polynom-Splines zu verwenden, um Pfade zwischen Objektivpunkten einzupassen. Splines stellen eine Kontinuität der Krümmung sicher, garantieren jedoch nicht irgendeine Linearität der Schärfe.
Die Tatsache, dass man nicht die erforderliche Krümmung verfolgen kann, hat Versetzugsfehler (Offset) im stetigen Zustand vom erwünschten Pfad 3312 zur Folge. Diese Fehler können durch ein Schließen einer Rückkoppelungsschleife an der Position 3314 kompensiert werden. Dies reicht in jenen Szenarien aus, wo das Ansprechen der Betätigungsvorrichtungen schnell genug ist, um vernachlässigbare Verfolgungs- bzw. Tracking-Fehler zu garantieren, und wo die Positionsabfühlung genau ist, wie beispielsweise auf einem Fabrikboden. Jedoch ist die Pfadverfolgung einfacher, wenn man den Pfad von sich aus einfacher verfolgen kann.
Das Verfahren der vorliegenden Erfindung erzeugt explizite Pfade, die durch eine Abfolge von Objektivpunkten laufen. Ein derivatives Verfahren der vorliegenden Erfindung plant erneut Teile des Pfades dynamisch in den Fall, dass der Verfolgungsfehler groß wird oder der erwünschte Pfad verändert wird.

b. Modellierung eines Fahrzeugpfades

Irgendein Pfad kann als eine Funktion der Pfadlänge (s) durch Positonskoordinaten (x(s), y(s)) 3304 parametriesiert werden. Das heißt, Positionskoordinaten x und y können als explizite Funktionen der Pfadlänge dargestellt werden. Die Ausrichtung (o(s)) 3318 und die Krümmung (c(s)) 3316 können abgeleitet werden:
o(s) = dy(s)/dx(s) (Gl. 1)
c(s) = do(s)/ds (Gl. 2)
Das Quadrupel bzw. die vierfache Anordnung dieser Parameter P = (x, y, 0, c) ist eine Lage 3314, die den Zustand eines autonomen Fahrzeugs 102 zu irgendeinem Zeitpunkt beschreibt.

c. Clothoid-Kurven

Clothoid-Kurven werden in einem Ausführungsbeispiel der vorliegenden Erfindung verwendet. Sie sind eine Familie von Kurven, die lagekontinuierlich sind, und die dahingehend unterschiedlich sind, dass ihre Krümmung linear mit der Länge der Kurve variiert:
c(s) = ks + ci (Gl. 3)
wobei k die Veränderungsrate der Krümmung (Schärfe) der Kurve ist und wobei der Index i den Anfangszustand bezeichnet. Ein Clothoid-Kurvensegment 2002 ist in Fig. 16 gezeigt.
Bei einer gegebenen anfänglichen Lage werden die Schärfe des Clothoid-Segmentes und die Distanz entlang dieses Segmentes, die Position und die Orientierung und die Krümmung an irgendeinem Punkt wie folgt berechnet:

d. Erzeugung eines lagekontinuierlichen Pfades

Praktische Navigationsprobleme erfordern zusammengesetzte Pfade, deren Bereich und Komplexität nicht durch ein einziges Clothoid-Segment erfüllt werden kann. Die meisten Pfade erfordern mehrere Segmente, die durch eine Abfolge von Objektivpunkten laufen.

(1) Existierende Verfahren

Ein Artikel von Hongo et al., betitelt "An Automatic Guidance System of a Self-Controlled Vehicle - The Command System and Control Algorithm", Proceedings IECON, 1985, MIT Press, 1985, schlug ein Verfahren zur Erzeugung von kontinuierlichen Pfaden vor, die aus verbundenen geraden Linien und kreisförmigen Bögen zusammengesetzt sind, und zwar aus einer Abfolge von Objektivpunkten. Während Pfade, die allein aus Bögen und geraden Linien bestehen, leicht zu berechnen sind, läßt ein solches Schema Diskontinuitäten an den Übergängen der Segmente übrig, wie oben besprochen.
Ein Artikel von Kanayama et al., betitelt "Trajectory Generation for Mobile Robots", Robotics Research: The Third International Symposium, ISIR, Gouvieux, Frankreich, 1986, verwendet gepaarte Clothoid-Kurven mit Übergängen aus einer geraden Linie zwischen den Lagen. Die Einschränkung der Übergänge mit geraden Linien kommt aufgrund der Integrale in den Gleichungen (7) und (8) die keine Lösungen für die geschlossene Form haben. Kanayama vereinfacht dieses Problem, indem er fordert, dass Folgendes gilt Ci = 0. Durch Drehung des Referenzrahmens bzw. Referenzkoordinatensystems um das Ausmaß der Anfangsorientierung, oi = 0, wird nur eine geradlinige Annäherung der folgenden Form übrig bleiben:
sin(kξ²)dξ
Kanayamas Verfahren führt zu Pfaden, die an gewissen Punkten schärfer sind und weniger kompakt als nötig, und zwar mit nachteiligen Konsequenzen für die Steuerung. Zusätzlich bringt die Forderung von geradlinigen Übergängen die lokale erneute Planung von Pfaden mit sich, da es keine Garantie gibt, dass ein erneut zu planendes Segment einen nicht gekrümmten Abschnitt einschließen wird.

2. Pfaderzeugung aus einer Abfolge von Punkten

Ein Verfahren der vorliegenden Erfindung mit zwei Schritten zur Erzeugung eines einzigartigen lagekontinuierlichen Pfades aus einer Abfolge von Punkten wird nun beschrieben.
Mit Bezug auf die Figuren (13, 14 und 15) ist der erste Schritt, eine Abfolge von einzigartigen Lagen 2302, 2304, 2306, 2308, 2310 aus den Objektivpunkten abzuleiten. Der zweite Schritt ist es, zwischen diesen Lagen mit den Clothoid-Segmenten zu interpolieren. Die Ausrichtung und Krümmung zum Beginn und Ende der Positionen 2402, 2404 werden vermutet. Es sei Pi, Pf jeweils die Start- und Endlage 2402 bzw. 2404.
Es ist nicht immer möglich, zwei Lagen mit einem Clothoid-Kurvensegment zu verbinden, da vier Gleichungen, Gl. 2, Gl. 4, Gl. 5 und Gl. 6 nicht gleichzeitig mit nur zwei Parametern einer Clothoid-Kurve (Schärfe k und Länge s) gelöst werden können.
Um die vier Gleichungen, Gl. 2, Gl. 4, Gl. 5 und Gl. 6 zu erfüllen, braucht man mindestens zwei Clothoid- Kurvensegmente. Jedoch kann das allgemeine Problem nicht durch zwei Clothoid-Segmente gelöst werden, da wenn ki und kf das gleiche Vorzeichen haben, in den meisten Fällen ein drittes Segment dazwischen erforderlich ist. Ein adäquater Satz der Clothoid-Kurven, die ein Paar von benachbarten assoziierten Lagen verbinden, ist der Satz von drei Clothoid-Segmenten (k, s&sub1;), (-k, s&sub2;), (k, s&sub3;). Diese Indizes bezeichnen die Reihenfolge der Clothoid-Segmente von Pi. Diese Kombination ist aus den folgenden Gründen plausibel:
1. Die Vorzeichen von k für die ersten und letzten Clothoid-Segmente sind die gleichen.
2, k für das zweite Clothoid-Segment ist bezüglich der Größe gleich und hat das entgegengesetzte Vorzeichen wie die ersten und letzten Segmente. Dies ermöglicht, dass die Kurve von drei Clothoid-Segmenten die Krümmungsvariation zwischen dem Beginn und dem Ende der Krümmungen durch Variieren von s&sub1;, s&sub2;, s&sub3; erfüllt, auch wenn das Vorzeichen der ersten und letzten Clothoid-Segmente die Anforderung der Kurvenlage erfüllt.
3. Es gibt vier Variablen in der Kombination: k, s&sub1;, s&sub2;, s&sub3;. Es ist möglich, eine einzigartige Lösung zu finden, die die folgenden vier Gleichungen erfüllt, die die mathematische Beziehung zwischen den Start- und Endlagen beschreiben.
cf = ci + k(s&sub1; - s&sub2; + s&sub3;) (Gl. 7)
wobei gilt
Es sei nun auf das in Fig. 17 gezeigte Verfahren Bezug genommen. Da die Gleichungen 9 und 10 oben Fresnel- Integrale enthalten, für die es keine Lösung in geschlossener Form gibt, werden die Werte k, s&sub1;, s&sub2; und s&sub3; berechnet.
Pfade, die aus dem Verfahren resultieren, haben die folgenden Vorteile gegenüber anderen Verfahren:
- Das Verfahren geht von einer willkürlichen Abfolge von Punkten aus. Die Erzeugung von Lagen ist wichtig für die fortschreitende Planung, wo Ziele gemeinsam als sich eine entwickelnde Abfolge von Punkten dargestellt werden. Pfade, die von dem Verfahren erzeugt werden, laufen durch alle Objektivpunkte, während Pfade vom Verfahren von Kanayama und dem Bogenverfahren nur in der Nähe von vielen der Punkte sind, da diese Verfahren von einer Abfolge von Lagen beginnen.
- Das Verfahren garantiert die Kontinuität der Position, Ausrichtung und Krümmung entlang des Pfades. Weiterhin ist die Schärfe stückweise konstant.
- Pfade, die von dem Verfahren erzeugt werden, liegen immer außerhalb der spitzen Winkel, die durch eine geradlinige Verbindung der Wegpunkte gebildet werden. Die resultierenden Pfade sind insbesondere nützlich zur Interpolation um Hindernisse, die gemeinsam auf der Innenseite der Winkel liegen. Im Gegensatz dazu sind Pfade von Kanayama immer innerhalb der Winkel.

3. Erneute Planung von Clothoid-Pfaden

Die erneute Planung von Clothoiden wird entweder ausgeführt, um den Pfad anfänglich aufzunehmen, oder um das Fahrzeug 102 zurück auf den erwünschten Pfad 3312 durch eine normale Navigation gemäß der vorliegenden Erfindung zu leiten.
Um abrupte Beschleunigungen in einem Versuch zu vermeiden, starke Korrekturen bei der Verfolgung eines zuvor festgelegten Pfades zu machen, wird eine erneute Planung des Pfades von der vorliegenden Erfindung verwendet, um einen neuen Pfad zu erzeugen, der sanft zu dem erwünschten Pfad 3312 von der gegenwärtigen Position konvergiert. Die erneute Planung zersetzt sich in zwei Unterprobleme:
1. Bestimmung des Konvergenzpunktes zum beabsichtigten Pfad 3308.
2. Planung eines Pfades von der gegenwärtigen Position 3302 zum Konvergenzpunkt 3308.
Es wird nun auf Fig. 18 Bezug genommen, die grafisch eine erneute Planung eines Pfades gemäß der vorliegenden Erfindung darstellt. Ein vordefinierter Pfad besteht aus Interpolationen 2804 zwischen Lagen (k, s)m (m = 1, ..., n) 2804-2810 und den Lagen Pm (gelegen am Ende des Segmentes (k, s)m). Unter der Annahme, dass das Fahrzeug 102 vom Pfad zwischen Pm und Pm+i abweicht, wird dann Pm+2 als Lage 334 ausgewählt, zu der der erneut geplante Pfad 2816 konvergiert bzw. läuft. Die Distanz zu Pm+2 ist variabel.
Eine Kurve, die aus zwei Kurvensegmenten zusammengesetzt ist, wird in die Lagen eingepasst (die gegenwärtige Lage und die eine, die als Konvergenzlage bzw. Konvergenzpunkt ausgewählt wurde), um einen erneut geplanten Pfad 2816 zu erhalten, der vier Regellagengleichungen erfüllt: Gl. 7, Gl. 8, Gl. 9, G. 10. Wenn wir annehmen, dass die Schwelle, die bestimmt, ob ein Pfad erneut zu planen ist oder nicht, viel kleiner ist als die Länge von jedem Clothoid- Kurvensegment (k, s)m können wir einen neuen lagekontinuierlichen Pfad finden ((k*k + 1, sk + 1), (K*k + 2, s*k + 2)) unter Verwendung einer kleinen Störung vom bekannten Ausdruck ((kk + 1, 5k + 1, (kk + 2, sk + 2)). Da der erneut geplante Pfad 2816 wahrscheinlich nicht sehr weit vom ursprünglichen Pfad 3312 entfernt ist, können zwei Clothoid-Segmente verwendet werden.

4. Zusammenfassung

Gemäß der vorliegenden Erfindung kann die Erzeugung von kontinuierlichen Pfaden für ein autonomes Fahrzeug 102 Clothoid-Segmente verwenden, um Pfade zu erzeugen, und zwar nicht nur weil der daraus resultierende Pfad lagekontinuierlich ist, sondern auch weil die lineare Krümmung entlang der Kurve zu Lenkwinkeln führt, die ungefähr linear entlang des Pfades variieren, was die Pfadverfolgung erleichtert.
Der Ansatz der vorliegenden Erfindung ist folgender: Zuerst wird eine Abfolge von Lagen unter Verwendung der Objektivpunkte erhalten. Dann wird jede der benachbarten Lagen mit drei Clothoid-Kurvensegmenten verbunden.
Das vorliegende Verfahren bringt zusätzliche Vorteile dahingehend, dass eine Vorverarbeitung der Objektivpunkte nicht nötig ist, wie bei Bögen und Clothoiden ohne Krümmung. Weiterhin ist die Geometrie der erzeugten Pfade immer außerhalb der spitzen Winkel, die durch eine geradlinige Verbindung der Wegpunkte gebildet werden. Dies ist insbesondere nützlich zur Interpolation um Hindernisse, die gewöhnlicherweise auf der Innenseite der Winkel liegen.
Aus dem Satz von gespeicherten Bögen, Linien und Lagen, Clothoid-Kurven, B-Splines usw. werden Punkte entlang eines Pfades mit dem VPS-Lageblock erzeugt.
Vorteile der Handhabung von Routen in dieser Weise durch die vorliegende Erfindung sind neben der Reduzierung der Bandbreitenanforderungen zwischen dem Host und dem Fahrzeug Effekte der Datenkompression, was Datenspeicheranforderungen verringert und dahingehend funktioniert, dass Pfade geglättet werden.

5. B-Splines

B-Splines sind dem Mathematiker und dem Fachmann für Computergrafik wohl bekannt (siehe "Mathematical Elements for Computer Graphics", von David F. Rogers und J. Alan Adams, McGraw-Hill Book Company, New York, NY., Seiten 144-155) und zwar als Mittel zur Beschreibung der Form einer Reihe von Punkten durch Festlegen der Koeffizienten einer Polynomgleichung. Diese Kurveneinpassungsfunktion ist ein Polynom N-ter Ordnung, wobei N vom Anwender festgelegt wird und von der erwünschten Form der Kurve abhängt. Die B-Spline-Kurve kann von irgendeiner Ordnung sein und ist kontinuierlich zu der Ordnung der Kurveneinpassungsfunktion minus eins.
B-Splines werden in einem Ausführungsbeispiel der vorliegenden Erfindung verwendet. B-Splines bieten sich für die Pfaderzeugung bei der vorliegenden Erfindung sehr gut an, da ein willkürlicher langer Pfad durch eine geringe Anzahl von Koeffizienten beschrieben werden kann und somit das Ausmaß der Datenspeicherung verringert wird. Vorausgesetzt, dass die Ordnung der Kurvenanpassungsfunktion hoch genug ist (drei oder größer) wird dann der erzeugte Pfad bezüglich der Krümmung glatt sein, was einen Pfad zur Folge hat, der von sich aus einfach mit den zuvor erwähnten Ausführungsbeispielen der vorliegenden Erfindung zu verfolgen ist.
Fig. 19 zeigt ein Beispiel von B-Spline-Kurven

2. Routenerzeugung und Speicherung

a. Einleitung

In einem Ausführungsbeispiel der vorliegenden Erfindung werden Daten zuerst von dem Fahrzeugpositionsbestimmungssystem 1000 gesammelt und gespeichert, um Routen für ein Gelände 300 zu erzeugen, während ein Mensch das Fahrzeug 102 über das Straßensystem des Arbeitsgeländes 300 fährt. Knoten und Segmente werden dann in die gespeicherten abgefahrenen bzw. Fahrdaten eingepaßt und in Routen für das zuvor erwähnte Verfahren organisiert.
Eine Anwendung auf einer Apollo-Computerworkstation (nun Hewlett-Packard, Palo Alto, Kalifornien) (ein nicht gezeigtes grafisches Anzeigesystem) wurde entwickelt, um grafisch Routendaten auf die gespeicherten abgefahrenen Daten einzupassen und weiter Routen zu definieren (d. h., Geschwindigkeiten, Abfolgen, einen Startpunkt, eine Querrichtung). Irgend eine Grafikworkstation bzw. ein Grafikcomputer, der dem Apollo äquivalent ist, könnte verwendet werden.
Sobald die Routen für ein Gelände definiert sind, werden die Routendaten in eine permanente Speichervorrichtung geschrieben. In einem Ausführungsbeispiel der vorliegenden Erfindung ist die verwendete Speichervorrichtung eine Blasenspeicherkartusche mit einer assoziierten Lese/Schreibvorrichtung. Die Blasenspeichervorrichtung ist dauerhaft und hält die Daten, wenn die Leistungsversorgung abgetrennt wird. Die Apollo-Anwendung kann Daten auf eine Kartusche schreiben und Daten von einer Kartusche lesen.
Wie oben erklärt, können Routen in der vorliegenden Erfindung vordefiniert werden, oder sie können dynamisch erzeugt werden.
Bei Bergbauanwendungen wird im allgemeinen ein Gelände 300 überwacht und Straßen werden vorgeplant, in sorgfältiger Weise ausgelegt und gebaut. Die Routen, die von dem Navigationssystem verwendet werden, können dann entweder aus einer manuell erzeugten Computerdatenbank erhalten werden (speziell erzeugt, um durch das Navigationssystem verwendet zu werden), oder alternativ kann ein Fahrzeug physisch über die tatsächlichen Routen auf dem Gelände gefahren werden, um die Routen zu lernen, wie oben beschrieben. Bei dem Lernverfahren können verschiedene Fahrten über eine gegebene Route ausgeführt werden. Dann werden die Veränderungen der Daten (beispielsweise aufgrund dessen, daß der Fahrer wackelt) zu einem Durchschnitt zusammengefaßt und eine geglättete beste Einpassung wird entwickelt.

b. Routendefinition

In einem Ausführungsbeispiel der vorliegenden Erfindung wird das folgende Verfahren zur Routendefinition verwendet.
1. Definiere Knoten und Segmente, aus denen die Routen aufgebaut sind. Bringe die Knoten- und Segmentdaten in eine Anordnung, die "Routendatenanordnung" genannt wird. Jede Aufzeichnung in der Anordnung enthält die folgende Information:
1. Art des Teils (d. h. Knoten, lineares Segment, kreisförmiges Segment und Markierung des Routenendes)
2. Falls es ein Knotenteil ist, definiere die Längen- und Breitenkoordinaten des Knotens.
Sonst, wenn es ein lineares Segmentteil ist, definiere die Geschwindigkeit entlang des Segmentes.
Sonst, wenn es ein kreisförmiges Segmentteil ist, definiere die Längen- und Breitenkoordinaten der Mitte, den Radius, die Richtung, in der der Kreis durchfahren wird (d. h. im Uhrzeigersinn oder gegen den Uhrzeigersinn) und die Geschwindigkeit entlang des Segmentes)
Sonst, wenn es eine Markierung des Routenendes ist, gibt es keine weitere Information.
2. Verbinde die Knoten- und Segmentdaten miteinander in Abfolgen. Die Abfolgen bzw. Sequenzen sind einfach eine Anordnung von Indizes in der Routendatenanordnung. Jede Abfolge muß mit einer Markierung des Routenendes beginnen, gefolgt durch einen Knoten, dann wird der Rest der Sequenz zwischen Segmenten und Knoten abwechseln, bis die Sequenz durch eine andere Markierung des Routenendes beendet wird. Eine beispielhafte Sequenz wäre, 1, 6, 3, 4, 7, 9, 10, 23, 78, 1 wobei die ganzen Zahlen Indizes in der Routendatenanordnung sind.
3. Schließlich definiere eine Route durch Festlegen eines Index in der Abfolgeanordnung, und definiere, ob durch die Sequenz in der positiven oder negativen Richtung indexmäßig zu laufen ist. Setze den Index und die Indexrichtung in eine Anordnung, die "Routenbeschreibungsanordnung" (routespec-Anordnung) genannt wird. Ein Teil in der Routenbeschreibungsanordnung kann wie folgt aussehen:
6,1 diese Beschreibung definiert eine Route, die beim Knoten 6 beginnt und in der positiven Richtung indiziert ist.
78, -1 diese Beschreibung definiert eine Route, die am Knoten 78 beginnt und in negativer Richtung indiziert ist.
Ein Anwender sagt dem Fahrzeug einfach, welches Teil in der Routenbeschreibungsanordnung als Route zu verwenden ist.
4. Die zuvor erwähnten Daten werden in der Speichervorrichtung in der Reihenfolge gespeichert, in der sie in den Schritten 1 bis 3 definiert wurden.

C. Navigatorroutenverwendung

Im folgenden wird beschrieben, wie der Navigator 406 die definierten Routen aus dem obigen Verfahren der vorliegenden Erfindung verwendet.
Wenn der Navigator 406 eingeschaltet wird, liest er die Routeninformationen aus der Speichervorrichtung 5302 und speichert sie in dem RAM bzw. Arbeitsspeicher (RAM = Random Access Memory) in der schon dargestellten Syntax.
Als nächstes legt der Bediener eine Route fest, der das Fahrzeug 102 folgen soll. Wiederum ist die Route einfach ein Index bzw. Zeiger zu der Routenbeschreibungsanordnung.
Wenn der Navigator 406 entscheidet, daß alle Systeme zum automatischen Betrieb bereit sind, sendet er eine Nachricht an die VPS_Lage-Aufgabe, um sie zum Betrieb zu veranlassen.
Die VPS_Lage-Aufgabe bestimmt dann die Position entlang der Route, die am nächsten zur gegenwärtigen Position 2812 des Fahrzeugs 102 ist. Die Suche nach der nächsten Position 284 auf der Route verläuft wie folgt:
1. Ein Zeiger (pointer) wird auf das erste Segment in der Route gesetzt.
2. Die senkrechte Distanz von der Fahrzeugposition zu dem Segment wird bestimmt.
3. Der Zeiger wird zum nächsten Segment in der Route bewegt.
4. Die senkrechte Distanz von der Fahrzeugposition zum nächsten Segment wird bestimmt.
5. Wiederholung der Schritte 3 und 4 bis die Markierung 2218 des Routenendes erreicht wurde.
6. Bestimmung der Distanz von der Fahrzeugposition zu den Endpunkten 2218 der Route.
7. Setzen eines Zählers auf das Routensegment, welches die nächste Distanz hatte, und Speicherung der Koordinaten der nächsten Distanz.
Die VPS_Lage-Aufgabe verwendet dann die Beschreibung der Route (Linien, Bögen und Geschwindigkeiten) um eine Lage in Intervallen von einem Meter zu erzeugen. Die Aufgabe erzeugt eine vordefinierte Distanz von Lagen plus einem Sicherheitsrahmen und bringt die Lagen in einen Puffer 3000. Zur Erzeugung einer Lage, die einen Meter von einer gegebenen Lage entfernt ist, verwendet die VPS_Lage- Aufgabe das folgende Verfahren:
1. Bestimmung der Art des Segmentes, aus dem die gegebene Lage erzeugt wurde.
2. Anwendung der ordnungsgemäßen Formel für die Art des Segmentes, um die Veränderung der Länge und Breite pro Meter der Segmentlänge zu bestimmen.
3. Addieren der Veränderung der Länge und Breite pro Meter zu der letzten gegebenen Lage.
4. Wenn die erzeugte Lage über dem Ende des gegenwärtigen Segmentes hinaus gelegen ist, Setzen eines Zeigers auf das nächste Segment und Wiederholung der Schritte 2 und 3, sonst Rückkehr zur erzeugten Lage.
Die VPS_Lage-Aufgabe informiert dann die Exekutive, daß sie bereit zur Verfolgung ist.
Wenn das autonome Fahrzeug 102 sich entlang der Lage in dem Puffer 3000 bewegt, wird der Sicherheitsrahmen 3006 entleert bzw. gelöscht.
Wenn der Sicherheitsrahmen unter einer festgelegten Größe ist, erzeugt die VPS_Lage-Aufgabe einen weiteren Sicherheitsrahmen 3006 von Lagen und hängt sie an den gegenwärtigen Puffer 3000 an. Die VPS_Lage-Aufgabe leert den Lagepuffer 3000 durch Überwachung der gegenwärtigen Position 2812 des Fahrzeugs 102 und durch Bewegung eines Zeigers bzw. Pointers 3002 in den Puffer 3000 zur nächsten Lage. Der Lagepuffer 3000 ist als Ring aufgebaut, der im Uhrzeigersinn durchlaufen wird (siehe Fig. 20, Lageringpuffer). D. h., Lagen werden in dem Ring so angeordnet, daß die Richtung einer Fahrzeugbewegung dem Durchlaufen des Lageringpuffers 3000 im Uhrzeigersinn entspricht. Wenn daher sich das Fahrzeug 102 bewegt, wird der Zeiger 3002 zur nächsten Lage im Puffer 3000 im Uhrzeigersinn bewegt werden. Wenn der Zeiger 3002 im Uhrzeigersinn bewegt wird, ist der Speicher in dem Ring hinter der Lage (vom Zeiger aus gegen den Uhrzeigersinn) frei, um überschrieben zu werden.
Der Schritt 7 (in der Suchroutine oben) ist in Aktion, bis die Markierung 2218 für das Routenende zurückgesetzt wird, wobei zu diesem Zeitpunkt die VPS Lage-Aufgabe aufhört, eine Lage zu erzeugen, und die Exekutive informiert wird, daß das Ende der Route erreicht wurde.
Wie oben erwähnt, ist ein Pfad wie eine Reihe oder Abfolge von aneinander liegenden "Lagen". Die Lage schließt die Geschwindigkeit und den Längswinkel ein, die verfolgt werden müssen. Eine Lage kann die Breite, Länge, Ausrichtung, Krümmung (1/Krümmungsradius), die maximale Geschwindigkeit und die Distanz zur nächsten Lageinformation aufweisen.

3. Lageerzeugung

Das Verfolgungsverfahren der vorliegenden Erfindung erfordert gewisse Informationen über die Route, die verfolgt wird. Die Informationen sind in einem Paket enthalten, das "Lage" 3314 genannt wird. Eine einzige Lage 3314 kann eine Position enthalten (Längen- und Breitenkoordinaten), eine Ausrichtung und Krümmungsdaten für eine spezielle Stelle auf der Route. Daher ist ein Weg zur Erzeugung von Lagedaten aus der Routenbeschreibung gemäß der vorliegenden Erfindung erforderlich.
Unter den Navigatoraufgaben (die unten besprochen werden) ist eine Aufgabe, die die Routeninformationen ausliest und Lagen in Intervallen entlang der Route (beispielsweise in Intervallen von einem Meter) erzeugt, die von dem Verfolgungsverfahren verwendet werden. In einem Ausführungsbeispiel der vorliegenden Erfindung erfordert jede Lage 36 Bytes Speicher, was ungefähr 36 K Speicher für jeden Kilometer der Route ergibt. Um die Speicheranforderungen zu verringern puffert der Navigator die Lagedaten.
Die Aufgabe, die die Lagen erzeugt, liest die gegenwärtige Position des Fahrzeugs 102 aus, findet den nächsten Punkt auf der Route zur gegenwärtigen Position, erzeugt dann eine festgelegte Anzahl von Lagen vor dem Fahrzeug 102. Die Anzahl der erzeugten Lagen ist abhängig von der maximalen Stopp- bzw. Anhaltedistanz (Bremsweg) des Fahrzeugs 102. D. h., es sollte immer genug Lagen im Puffer 3000 geben, um das Fahrzeug 102 zu einem Anhaltepunkt zu führen.
In dem Ansatz mit B-Splines zur Routendefinition gemäß der vorliegenden Erfindung jedoch wird die Notwendigkeit eines Lagepuffers eliminiert, da das Verfolgungsverfahren direkt Lageinformationen aus der B-Spline-Kurve erzeugen kann.

C. Pfadverfolgung

Die Pfadspurbildung oder Pfadverfolgung (tracking) ist ein kritischer Aspekt der Fahrzeugnavigation gemäß der vorliegenden Erfindung. Die Technik der vorliegenden Erfindung verwendet eine positionsbasierte Navigation (anstelle einer sichtbasierten Navigation, die bei herkömmlichen Navigationssystemen verwendet wird) um sicher zu stellen, daß der korrekte Pfad 3312 des autonomen Fahrzeugs verfolgt wird. Die vorliegende Erfindung ist auch dahingehend neu, daß sie eine getrennte Steuerung des Lenkwinkels und der Fahrzeuggeschwindigkeit bietet. Fig. 23 veranschaulicht grafisch das Pfadverfolgungssystem der vorliegenden Erfindung.
Für ein autonomes Fahrzeug 102 gemäß der vorliegenden Erfindung ist es zur Verfolgung von festgelegten Pfaden nötig, Referenzeingaben für die Fahrzeug-Servo-Steuervorrichtungen zu erzeugen. Somit kann eine Pfadverfolgung als ein Problem angesehen werden, einen Referenzlenkwinkel bzw. einen in Bezug gebrachten Lenkwinkel und eine Referenzgeschwindigkeit für den nächsten Zeitintervall zu erhalten, um auf den Referenzpfad vor der gegenwärtig abgewichenen Position zurückzukommen.
Allgemein gesagt bestimmt die Pfadverfolgung die Befehle des autonomen Fahrzeuges (Geschwindigkeit, Lenkwinkel) die erforderlich sind, um einem gegebenen Pfad zu folgen. Bei einem gegebenen zuvor festgelegten Lenkwinkel, gefahrenen Radgeschwindigkeitswerten und Fehlerkomponenten werden die Lenkbefehls- und Antriebseingaben in der vorliegenden Erfindung berechnet.

D. Hindernisbehandlung

1. Einleitung

Die Hindernisbehandlung sieht mindestens drei Hauptfunktionen vor: Detektieren von Hindernissen 4002, Vermeidung von Hindernissen 4002 und Rückkehr zum Pfad 3312. Die Funktion des Zurückkehrens zum Pfad ist ähnlich wie die Pfaderzeugung und -verfolgung wie oben beschrieben.
Zusätzlich zur Pfadverfolgung (Verfolgung) erfordert die erfolgreiche Navigation des Fahrzeugs 102, daß das Fahrzeug 102 Hindernisse 4002 in seinem Pfad erkennen kann, was somit gestattet, daß das Fahrzeug stoppt oder in anderer Weise ein solches Hindernis vermeidet, bevor eine Kollision auftritt.
In einem Ausführungsbeispiel der vorliegenden Erfindung wird ein Infrarotlaserscanner bzw. eine Infrarotabtastvorrichtung 404 mit einer einzigen Linie (siehe Fig. 25) in einer Konfiguration verwendet, wo die Abtastung bzw. der Scan horizontal ist (nicht gezeigt). Die Abtastlinie 3810 berührt nicht den Erdboden, so daß irgendwelche Ungleichheiten in den Bereichsdaten den Objekten 4002 in der Umgebung zugeordnet werden können.
Da ein Referenzpfad 3312 verfügbar ist, und die Fahrzeugposition relativ zum Referenzpfad bekannt ist, werden nur die Bereichsdaten und eine Regionsabgrenzung des Referenzpfades 3312 für bedrohliche Objekte 4002 verarbeitet. Die Objekte außerhalb dieser Region oder Grenzzone werden ignoriert. Die Breite der (nicht gezeigten) Grenzzone ist gleich der Fahrzeugbreite zuzüglich einem gewissen ausgewählten Sicherheitspuffer, um Spur- und Positionsbestimmungsfehler auszugleichen. Dieses Verfahren ist bezüglich seiner Nützlichkeit eingeschränkt und wird als "Freiraumüberprüfung" bezeichnet.

2. Detektion von Hindernissen

In einem einfachen Fall kann der Laser 404 in einem Abtastbetriebszustand mit einer einzigen Linie mit darauf folgenden Bereichsmessungen verwendet werden, die in regelmäßigen Winkelintervallen gemacht werden, wenn der Laser über das Blickfeld schwenkt. Wiederum können zur Vereinfachung diese Abtastungen in regelmäßigen Zeitintervallen beginnen. Der Ausdruck "Freiraumüberprüfung" ist verwendet worden, um dieses Verfahren zu beschreiben. In dieser Version ist das Verfahren auf die Verarbeitung von nur zweidimensionalen Daten eingeschränkt worden.
Diese Art eines Hindernisdetektionsverfahrens ist auf die Überprüfung eingeschränkt, zu sehen, ob der Pfad 3312 frei ist, und zwar unter Verwendung eines Abtastbetriebszustandes mit einer einzigen Linie mit darauf folgenden Bereichsmessungen, die in regelmäßigen Winkelintervallen ausgeführt werden, wenn der Scanner bzw. die Abtastvorrichtung 404 über das Sichtfeld läuft. Es schließt nicht irgendwelche Verfahren zum Einrichten bzw. Überprüfen der Existenz von irgend einem Hindernis 4002 ein, noch erzeugt es einen Pfad um dieses herum, wenn der Pfad nicht frei ist. Diese Art eines Verfahrens wird nicht als ein speziell nützliches Hindernisdetektionsverfahren angesehen, außer in sehr genau überwachten bzw. gesteuerten Umgebungen, wie beispielsweise auf einem Fabrikboden.

3. Vermeidung von Hindernissen

Sobald die vorliegende Erfindung ein Hindernis 4002 im Pfad des Fahrzeugs 102 detektiert (siehe Fig. 26) muß sie dann eine Kollision mit dem Objekt vermeiden. Gewisse Annahmen werden bezüglich des Hindernisvermeidungsproblems gemacht:
1. Die Hindernisumgebung ist mit Hindernissen 4002 bevölkert, die durch konvexe Polygone oder konvexe Linien dargestellt werden können;
2. Die Navigationsverfahren haben nur Zugang zu den Informationen über die lokale Umgebung in Form einer lokalen Karte, die alle sichtbaren Stirnseiten des Hindernisses von der Position des Fahrzeugs 102 aus darstellt, die von nicht verarbeiteten Laserbereichsdaten erhalten werden können oder von Daten, die durch Fleckextraktion verarbeitet wurden;
3. Das Fahrzeug 102 ist eine in herkömmlicher Weise gelenkte Bauart, die Beschränkungen bezüglich ihrer Geschwindigkeit und Beschleunigung hat, und Einschränkungen bezüglich des Lenkwinkels und der Veränderungsrate des Lenkwinkels.
Um mit dem Problem der Vermeidung von Hindernissen fertig zu werden, teilt die vorliegende Erfindung dieses in zwei Unterprobleme auf.
Erstens, die Unterscheidung, ob irgendwelche Hindernisse im Weg sind, und falls dies so ist, zu welcher Seite das Fahrzeug weiterfahren sollte. Dann die Auswahl eines Unterziels 4006, welches das Fahrzeug 102 um das Hindernis 4002 herumführen wird, was zu einem Ziel 4008 mit höherem Niveau führt, welches ist, auf den erwünschten Pfad zurückzukehren.
Zweitens, sobald ein Unterziel 4006 ausgewählt ist, eine Lenkentscheidung zu fällen, die das Fahrzeug 102 zu dem Unterziel 4006 hin fährt, während man um das Hindernis 4002 herumlenkt. Ein Unterzielauswahlverfahren und ein Lenkentscheidungsverfahren der vorliegenden Erfindung lösen diese zwei Unterprobleme.
Die oben aufgezählten Annahmen werden in dem folgenden Prozeß behandelt:
Die Hindernislagen werden von dem Laserbereichsscanner 3804 oder 404 erhalten. Die Bereichsdaten, die von dem Scanner 3804 oder 404 erzeugt wurden, werden verarbeitet, um eine Liste von Polygonstirnseiten zu erzeugen, wobei die sichtbaren Teile des Hindernisses 4002 von der Fahrzeugposition aus modelliert werden. Jedesmal wenn neue Bereichsdaten verfügbar werden, wird ein Unterzielauswahlverfahren ausgeführt, um ein Unterziel 4006 zu erzeugen und Regionen der sicheren Navigation (Freiraum 4010) für das Lenkentscheidungsverfahren zu bestimmen. Die Frequenz, mit der das Unterzielauswahlverfahren ausgeführt werden kann, hängt von der Rate ab, mit der der Scanner 3804 oder 404 Daten sammeln kann. Die erreichbare Fahrzeuggeschwindigkeit hängt wiederum von dieser Ausführungsfrequenz ab.
Für das Lenkentscheidungsverfahren ist eine höhere Aufnahme- bzw. Samplingrate wünschenswert, um einen glatten Pfad zu erzeugen. Daher wird das Lenkentscheidungsverfahren öfter ausgeführt als das Unterzielverfahren.
Der grundlegende Fluß des Unterzielverfahrens ist folgender:
1 letztes Anfangsunterziel, Unterziel und Freiraum speichern, setze Ziel blockiert-Flag auf wahr
2 wenn das Endziel sichtbar ist,
erzeuge direktes Ziel wenn das direkte Ziel sichtbar ist
setze Ziel_blockiert-Flag auf falsch
3 sonst
erzeuge ein Anfangsunterziel setze Unterziel auf Anfangsunterziel rekursive Erzeugung von Unterzielen bis das letzte sichtbar ist, wenn das Unterziel nicht erreichbar ist, Abbruch
4 wenn Ziel blockiert-Flag wahr ist
altes Anfangsunterziel, Unterziel und Freiraum wiederherstellen
5 sonst
Erzeugung des Freiraums wenn der Freiraum nicht sicher ist
altes Anfangsunterziel, Unterziel und Freiraum wiederherstellen.
Unterzielverfahren: Erstens (Schritt 1 oben) Anfangsunterziel, Unterziel und Freiraum, die in der vorherigen Iteration erzeugt wurden, werden gespeichert. Dies stellt sicher, daß wenn das neu erzeugte Unterziel nicht sicher ist, das alte Unterziel weiter verfolgt werden kann.
Als nächstes (Schritt 2 oben) wenn das Endziel sichtbar ist, versuche ein direktes Ziel zu erzeugen, welches nicht mit irgendeinem der Hindernisse 4002 assoziiert ist. Obwohl das Endziel in der lokalen Karte sichtbar ist, bedeutet dies nicht notwendigerweise, daß kein Hindernis das Endziel blockiert, da Hindernisse außerhalb des Scannerbereiches (sowohl bezüglich der Distanz als auch bezüglich des Winkels) nicht in der lokalen Karte dargestellt werden. Wenn daher ein direktes Ziel erzeugt wird, soll sichergestellt sein, daß das Ziel in dem Kegelgebiet gelegen ist, welches von dem Scanner 3804 oder 404 bedeckt wird, um die Anordnung eines Unterziels auf oder hinter einem Hinderniss 4002 zu vermeiden, das nicht in der lokalen Karte ist.
Der nächste Schritt (Schritt 3 oben) behandelt die Situation, wo das Endziel durch ein Hindernis 4002 in der lokalen Karte blockiert wird. In diesem Fall wird zuerst das Hindernis 4002, das die Sichtlinie zum Endziel blockiert, bestimmt.
Wenn man ein Flußdiagramm für ein blockierendes Hindernis gegeben hat, gibt es zwei mögliche Wege, um dieses herumzukommen. Wenn beide Kanten des Hindernisses im Bereich des Scanners 3804 oder 404 sind, können wir wählen, um die Kante bzw. den Rand herumzugehen, der die minimale Summe der Abstände vom Fahrzeug 102 zur Kante und von der Kante zur letztendlichen Distanz ergibt. Wenn nur eine Kante des Hindernisses 4002 in dem Bereich ist, wird die Kante gewählt, um die herumgegangen werden soll. Wenn keine der Kanten sichtbar ist, wird immer willkürlich die linke Ecke ausgewählt, um dort herumzugehen. Sobald die Kante, um die herumzugehen ist, bestimmt worden ist, wird das anfängliche Unterziel weg von der Kante um eine Distanz angeordnet, die proportional zur Fahrzeuggröße ist.
Wegen dieser Verschiebung kann das daraus resultierende Unterziel durch andere Hindernisse 4002 blockiert werden. Dies ruft die rekursive Erzeugung des Unterziels auf dem Hindernis auf, welches die Sichtlinie zu den gerade erzeugten Unterzielen blockiert. Dieser rekursive Prozeß fährt fort, bis ein Unterziel erzeugt wird, das vom Fahrzeug 102 aus sichtbar ist. Jedes so erzeugte Unterziel wird bezüglich der Erreichbarkeit überprüft. Mit Erreichbarkeit ist gemeint, daß das Unterziel nicht das Fahrzeug 102 zu einem Spalt zwischen zwei Hindernissen 4002 führt, der zu klein ist, als daß das Fahrzeug dort hindurch fahren könnte. Wenn ein solcher Zustand detektiert wird, wird das Fahrzeug 102 stoppen.
Das direkte Unterziel, das im zweiten Schritt (Schritt 2 oben) erzeugt wurde, könnte möglicherweise vom Fahrzeug 102 aus verdeckt sein. Wenn dies tatsächlich der Fall ist, werden die alten Unterziele von der vorherigen Iteration wiederhergestellt und als nächstes verwendet (Schritt 4 oben).
In dem letzten Schritt (Schritt S oben) soll der Freiraum 4010 für das sichtbare Unterziel erzeugt werden, was eine dreieckige Region ist, die keine Hindernisse enthält. Sobald der Freiraum 4010 erzeugt wird, kann die Sicherheit des Unterziels und des Freiraums 4010 bestimmt werden. Wenn das neue Unterziel und der Freiraum 4010 nicht sicher sind, wird wieder das alte Unterziel und der Freiraum erhalten. Anderenfalls wird das neue Unterziel und der neue Freiraum verwendet.
Das Lenkentscheidungsverfahren der vorliegenden Erfindung besteht aus zwei Hauptkomponenten: Übertragung von Zustandseinschränkungen auf Steuereinschränkungen; und Bestimmung von dem erwünschten Steuervektor.
Sobald die Steuereinschränkungen und der erwünschte Steuervektor berechnet wurden, können die Steuervektoren unter Verwendung von Optimierungstechniken bestimmt werden, die in der Technik wohl bekannt sind.

4. Rückkehr zum Pfad

Die vorliegende Erfindung weist ein Verfahren auf, wie es diagrammartig in Fig. 26 gezeigt ist, wodurch ein sicherer Pfad um ein detektiertes Objekt 4002 herum aufgezeichnet wird und so navigiert wird, daß das Fahrzeug 102 wieder den Referenzpfad erreichen wird, nachdem es das Objekt 4002 vermieden hat.

5. Scannersystem

Mit Bezug auf Fig. 25 weist das beispielhafte System auch ein Laserscannersystem 404 auf. Der Scanner 404 wird verwendet, um Hindernisse 4002 (siehe Fig. 26) zu finden, die sich zufälligerweise im Pfad des Fahrzeugs 102 ansammeln, wie zuvor besprochen.
Quellen von solchen Hindernissen 4002 können verschieden und zahlreich sein, und zwar abhängig von dem speziellen Arbeitsgelände. Sie können umgefallene Bäume und Zweige, Felsen, sich bewegende und parkende Fahrzeuge und Personen aufweisen.
Der Scanner 404 gibt dem autonomen Fahrzeug 102 die Fähigkeit, die umgebende Welt zu detektieren und mit ihr fertig zu werden, wie es die Umstände erfordern.

Claims

1. System für das Navigieren (406) eines Fahrzeugs (102) entlang einer Route (3312), das folgendes aufweist:

Mittel für das Speichern von Routendaten, die eine vorbestimmte Route repräsentieren;

Mittel für das Speichern von Pfaddaten für eine jede vorbestimmte Route;

Mittel für das Auswählen einer vorbestimmten Route, der das Fahrzeug (102) folgt;

Mittel für das Herausziehen von Routendaten, die eine ausgewählte vorbestimmte Route repräsentieren;

Mittel für das Herausziehen von Pfaddaten für die herausgezogenen Routendaten;

Mittel für das Erzeugen eines Pfades aus den herausgezogenen Pfaddaten;

Mittel (5306) für das Assoziieren von Fahrzeugbefehlen mit einem erzeugten Pfad;

Mittel (5306) für das Ausführen der zugeordneten Fahrzeugbefehle, die bewirken, dass das Fahrzeug einem erzeugten Pfad zu folgen versucht;

Mittel (5306) für das periodische Berechnen von Fehlern beim Folgen eines erzeugten Pfades;

Mittel (5306), und zwar ansprechend auf die berechneten Fehler, für das Angleichen bzw. Einstellen der Ausführung der zugeordneten Fahrzeugbefehle für das Reduzieren der berechneten Fehler, so dass das Fahrzeug einem erzeugten Pfad mit einem höheren Genauigkeitsgrad folgt;

Mittel (4150) für das Detektieren von Hindernissen in der Fortbewegungsrichtung des Fahrzeugs;

Mittel (4150) für das Vermeiden einer Kollision mit den Hindernissen, die wiederum Mittel aufweisen für das Anhalten des Fahrzeugs zum Verhindern einer Kollision mit den Hindernissen und Mittel für das Erzeugen eines Pfades um die Hindernisse herum;

wodurch ein autonomes bzw. selbständiges System (406) für das sichere und effiziente Navigieren eines Fahrzeugs entlang einer Route realisiert wird;

dadurch gekennzeichnet, dass

die Mittel für das Erzeugen eines Pfades einen Pfad von aneinander hängenden Anordnungen bzw. Lagen erzeugt mit Änderungsraten für die Krümmung abhängig von den Lenkeinschränkungen des Fahrzeugs.

2. Verfahren (406) für das Navigieren eines Fahrzeugs (102) entlang einer Route (3312), das die folgenden Schritte aufweist:

Speichern von Routendaten, die eine vorbestimmte Route repräsentieren;

Auswählen einer vorbestimmten Route, der das Fahrzeug (102) folgt;

Herausziehen der Routendaten, die eine ausgewählte vorbestimmte Route repräsentieren;

Herausziehen von Pfaddaten für die herausgezogenen Routendaten;

Erzeugen eines Pfades aus den herausgezogenen Pfaddaten;

Assoziieren (5306) von Fahrzeugbefehlen mit einem erzeugten Pfad;

Ausführen (5306) der zugeordneten Fahrzeugbefehle, die bewirken, dass das Fahrzeug einem erzeugten Pfad zu folgen versucht;

Periodisches Berechnen (5306) von Fehlern beim Folgen eines erzeugten Pfades;

Angleichen bzw. Einstellen (5306), und zwar ansprechend auf die berechneten Fehler, der Ausführung der zugeordneten Fahrzeugbefehle zum Reduzieren der berechneten Fehler, so dass das Fahrzeug einem erzeugten Pfad mit einem hohen Genauigkeitsgrad folgt;

Detektieren (4150) einer Kollision mit den Hindernissen (4002) durch Stoppen des Fahrzeugs, um eine Kollision mit den Hindernissen (4002) zu verhindern, Erzeugen eines Pfades um die Hindernisse (4002) herum oder Durchführen von beidem; wodurch ein autonomes Verfahren (406) für ein sicheres und effizientes Navigieren eines Fahrzeugs (102) entlang einer Route realisiert wird; gekennzeichnet dadurch, dass der erzeugte Pfad ein Pfad von aneinander gehängten Anordnungen bzw. Lagen mit einer Änderungsrate der Krümmung abhängig von den Lenkeinschränkungen des Fahrzeugs ist.

3. Verfahren (406) für das Navigieren eines Fahrzeugs (102) entlang einer Route (3312) gemäß Anspruch 2, wobei der Schritt (5306) des periodischen Berechnens von Fehlern beim Folgen eines erzeugten Pfades folgendes aufweist:

Bestimmen der Fahrzeug-Ist-Position (3210, 3212, 3218); Bestimmen der Fahrzeug-Soll-Position (3204); und Vergleichen der Ist- (3210, 3212, 3218) mit der Soll-Position (3204) um so die Fehler beim Folgen des erzeugten Pfades zu berechnen.

4. Verfahren (406) für das Navigieren eines Fahrzeugs (102) entlang einer Route (3312) gemäß Anspruch 2, wobei der Schritt (5306) des Einstellens ansprechend auf die berechneten Fehler für die Durchführung der zugeordneten Fahrzeugbefehle zum Reduzieren der berechneten Fehler, und zwar so dass die Fahrzeugbefehle die berechneten Fehler reduzieren, so dass das Fahrzeug einem erzeugten Pfad mit einem hohen Genauigkeitsgrad folgt, das dynamische Bestimmen eines korrigierenden Lenkwinkels aufweist, so dass der korrigierende Lenkwinkel bewirkt, dass das Fahrzeug (102) von einer Ist-Position (3210, 3212, 3218) zu einer Soll-Position (3204) lenkt.