DE69826340T2

DE69826340T2 - Verfahren und Gerät zur Bestimmung eines alternativen Leitweges in einem Fahrzeugsnavigationssystem

Info

Publication number: DE69826340T2
Application number: DE69826340T
Authority: DE
Inventors: Hidekazu Cupertino Oshizawa; Haruhisa Higashimatsuyama-shi Tamai
Original assignee: Horizon Navigation Inc
Current assignee: TomTom International BV
Priority date: 1997-01-15
Filing date: 1998-01-15
Publication date: 2005-09-29
Anticipated expiration: 2018-01-16
Also published as: US5928307A; CA2225974C; DE69826340D1; JPH10221100A; EP0854463A2; CA2225974A1; EP0854463B1; JP3065978B2; EP0854463A3

Description

Die vorliegende Erfindung betrifft die Routenermittlung in einem Fahrzeugnavigationssystem. Die unten zur Veranschaulichung der vorliegenden Erfindung beschriebenen Anordnungen betreffen das Ermitteln von Ausweichrouten, d. h. Umleitungen, wenn Verkehrsverhältnisse eine ursprünglich ermittelte Route unerwünscht oder unpassierbar werden lassen.
Weil das Aktualisieren von Kartendatenbanken mit hochaktuellen Informationen bezüglich Verkehrsverhältnissen eine äußerst herausfordernde Aufgabe ist (selbst für so genannte intelligente Fahrzeug-/Straßensysteme), ermitteln zurzeit erhältliche Fahrzeugnavigationssysteme oft Routen, auf denen der Benutzer unvorhergesehene oder unvorhersehbare Hindernisse antreffen kann, wie z. B. eine Baustelle oder ein hohes Verkehrsaufkommen. In derartigen Situationen ist es erwünscht, dass das Navigationssystem die Fähigkeit hat, „auf die Schnelle" eine Ausweichroute zu ermitteln, um das Hindernis zu vermeiden.
Einige Systeme sind zum Ermitteln von Routen, die am wahrscheinlichsten die einfachsten und schnellsten, d. h. die optimale Route, sind, von Benutzereingaben in die Routenermittlungsalgorithmen abhängig. Durch vorausschauendes Auswählen von zutreffenden Routenermittlungskriterien kann Wissen über aktuelle Verkehrsverhältnisse von einem Benutzer angewendet werden, um das Ermitteln der besten verfügbaren Route zu vereinfachen. Beispielsweise kann ein Benutzer spezifizieren, dass das System maximal Autobahnen benutzt, oder aber, dass überhaupt keine Autobahnen benutzt werden sollen. Ein Benutzer kann auch angeben, dass die Route eine minimale Anzahl von Straßenbiegungen haben sollte oder dass sie die kürzeste Entfernung zwischen dem Ausgangs- und dem Zielort sein soll. Außerdem kann der Benutzer angeben, das die Route alle bekannten Hindernisse, wie zum Beispiel Mautstationen, vermeiden soll. Dieser Ansatz bietet zwar etwas Flexibilität, Verkehrshindernisse, bezüglich derer der Benutzer wenig oder keine Warnung erhält, kann er aber leider weder vorhersehen noch korrigieren.
Ein Ansatz für das Vermeiden von Hindernissen „auf die Schnelle" erlaubt es dem Benutzer, dem System zu sagen, dass es ein bevorstehendes Fahrmanöver verbieten soll, woraufhin das System eine kurze Umleitung von dem Punkt des verbotenen Fahrmanövers zurück zu einem nachfolgenden Punkt auf der ursprünglichen Route ermittelt.
Im Folgenden wird auf die 1 und 2 der Begleitzeichnungen Bezug genommen, mit denen jeweilige zuvor vorgeschlagene Ansätze zum Erstellen von Ausweichrouten, die den Anmeldern bekannt sind, beschrieben werden können. Bezug nehmend auf 1 ist zu sehen, dass, während ein Benutzer sich östlich auf der Straße 102 entlang der ursprünglichen Route 104 voranbewegt, der Benutzer bemerkt, dass die Straße 106 nach rechts wegen einer Baustelle gesperrt ist. Infolgedessen ist der vom System vorgeschlagene Rechtsabbiegevorgang unmöglich. Indem er sich weigert, den von der Benutzeroberfläche angezeigten Vorgang durchzuführen, macht der Benutzer das System auf das Hindernis aufmerksam. Auf der Basis der Annahme, dass der Rechtsabbiegevorgang von der Straße 102 in die Straße 106 nicht erlaubt ist, ermittelt das System dann eine Ausweichroute 108. Dies resultiert in der Umleitung über die Straßen 110 und 112, die so bald wie möglich zur Straße 106 zurückführt.
Leider ist der oben beschriebene Ansatz zum Beispiel dann problematisch, wenn der gesamte Teil der Straße 106 zwischen den Straßen 102 und 114 gesperrt ist. Eine solche Situation wird von einem anderen Ansatz behandelt, der nun mit Bezug auf 2 beschrieben wird. Wie im vorhergehenden Beispiel macht der Benutzer das System auf die Tatsache aufmerksam, dass der Rechtsabbiegevorgang auf die Straße 106 nicht möglich ist. Gemäß diesem Ansatz vermeidet das System aber den Teil der Straße 106 zwischen den zwei aufeinanderfolgenden Fahrmanövern an der Kreuzung der Straßen 102 und 106 (d. h. die oben erwähnte Abbiegung nach rechts) und der Kreuzung der Straßen 106 und 114 (eine Abbiegung nach links). Durch Ignorieren der Straßensegmente zwischen den nächsten zwei bevorstehenden Fahrmanövern wird eine Ausweichroute 202 ermittelt, die das oben besprochene Problem vermeidet.
Trotz der offensichtlichen Vorteile, die jeder dieser Ansätze bietet, erlaubt keiner es dem Benutzer, bezüglich der Art der Ausweichroute auf der Basis der Wahrnehmung der Verkehrsverhältnisse seitens des Benutzers einen Beitrag einzugeben. Daher ist keiner der oben beschriebenen Ansätze ausreichend, um sich an den hohen Grad an Veränderlichkeit von Verkehrsverhältnissen anzupassen, die ein Benutzer antreffen kam. Ein flexiblerer Ansatz für die Ermittlung von Ausweichrouten „auf die Schnelle" ist daher wünschenswert.
US-A-5521826 beschreibt eine Anordnung, mit der eine Mehrzahl von „kostengünstigsten" Strecken zwischen dem selben Ausgangspunkt und dem selben Zielpunkt identifiziert werden kann, die aber immer eine Berechnung zwischen dem selben Ausgangspunkt und dem selben Zielpunkt beinhaltet.
Ein Merkmal eines Verfahrens und einer Vorrichtung, das unten zur Veranschaulichung der vorliegenden Erfindung für die Ermittlung von Ausweichrouten „auf die Schnelle" in einem Fahrzeugnavigationssystem beispielhaft beschrieben wird, ist, dass es/sie den Benutzer den Teil der ursprünglichen Route angeben lässt, der mit der Ausweichroute zu vermeiden ist. Dadurch kann das Navigationssystem Ausweichrouten erstellen, die eine gewisse Beziehung zu den vom Benutzer angetroffenen tatsächlichen Verkehrsverhältnissen aufweisen. Das heißt, dass der Benutzer auf der Basis der Wahrnehmung der Straßenverhältnisse seitens des Benutzers eine Entfernung von der aktuellen Fahrzeugposition entlang der ursprünglichen Route angeben kann, die mit der Ausweichroute zu vermeiden ist. Das System bereinigt dann einen oder mehrere Parameter, der/die mit jedem der Segmente in der ursprünglichen Route innerhalb der angegebenen Entfernung assoziiert ist/sind, sodass diese Segmente, wenn die Ausweichroute erstellt wird, meist vermieden werden.
Nach einem Aspekt der vorliegenden Erfindung ist ein Verfahren zur Verwendung beim Ermitteln einer Ausweichroute von einem auf einer ursprünglichen Route gelegenen neuen Ausgangsstandort zu einem nachfolgenden Standort auf der ursprünglichen Route mithilfe eines Fahrzeugnavigationssystems vorgesehen, wobei die ursprüngliche Route an einem ursprünglichen Ausgangsstandort beginnt, der vor dem neuen Ausgangsstandort auf der ursprünglichen Route liegt, wobei das Verfahren die folgenden Schritte aufweist:
Ermitteln eines Teils der ursprünglichen Route, der mit der Ausweichroute zu vermeiden ist, wobei der Teil der ursprünglichen Route an dem neuen Ausgangsstandort beginnt und der Teil der ursprünglichen Route eine Mehrzahl von Segmenten hat, die jeweils einen damit assoziierten ursprünglichen Parameter haben,
Bereinigen von ausgewählten der ursprünglichen Parameter nur für Segmente, die mit dem zu vermeidenden Teil der ursprünglichen Route assoziiert sind, wodurch eine Mehrzahl bereinigter Parameter bereitgestellt wird, und
teilweise auf die bereinigten Parameter gestütztes Ermitteln der Ausweichroute vom neuen Ausgangsstandort zu dem nachfolgenden Standort.
Nach einem weiteren Aspekt der vorliegenden Erfindung ist eine Vorrichtung zur Verwendung beim Ermitteln einer Ausweichroute von einem auf einer ursprünglichen Route gelegenen neuen Ausgangsstandort zu einem nachfolgenden Standort auf der ursprünglichen Route, wobei die ursprüngliche Route an einem ursprünglichen Ausgangsstandort beginnt, der vor dem neuen Ausgangsstandort auf der ursprünglichen Route liegt, wobei die Vorrichtung Folgendes hat:
eine Einrichtung zum Ermitteln eines Teils der ursprünglichen Route, der mit der Ausweichroute zu vermeiden ist, wobei der Teil der ursprünglichen Route an dem neuen Ausgangsstandort beginnt und der Teil der ursprünglichen Route eine Mehrzahl von Segmenten hat, die jeweils einen damit assoziierten ursprünglichen Parameter haben,
eine Einrichtung zum Bereinigen von ausgewählten der ursprünglichen Parameter nur für Segmente, die mit dem zu vermeidenden Teil der ursprünglichen Route assoziiert sind, was zu einer Mehrzahl bereinigter Parameter führt, und
eine Einrichtung zum teilweise auf die bereinigten Parameter gestützten Ermitteln der Ausweichroute vom neuen Ausgangsstandort zu dem nachfolgenden Standort.
Gemäß einem weiteren Aspekt der vorliegenden Erfindung ist ein Fahrzeugnavigationssystem vorgesehen, das Folgendes aufweist:
eine Mehrzahl von Sensoren zum Erfassen einer aktuellen Fahrzeugposition und eines Fahrzeugsteuerkurses und zum Erzeugen von dafür bezeichnenden Signalen,
ein Datenbankmedium mit darin gespeicherten geographischen Stellen einer Mehrzahl von Straßensegmenten und Segmentknoten,
einen mit den Sensoren und dem Datenbankmedium verbundenen Prozessor zum Erzeugen einer Ausweichroute von einem auf einer ursprünglichen Route gelegenen neuen Ausgangsstandort zu einem nachfolgenden Standort auf der ursprünglichen Route, wobei die ursprüngliche Route an einem ursprünglichen Ausgangsstandort auf der ursprünglichen Route beginnt, wobei der Prozessor die folgenden Aufgaben hat

(a) Ermitteln eines Teils der ursprünglichen Route, der mit der Ausweichroute zu vermeiden ist, wobei der Teil der ursprünglichen Route an dem neuen Ausgangsstandort beginnt und der Teil der ursprünglichen Route eine Mehrzahl von Segmenten hat, die jeweils einen damit assoziierten ursprünglichen Parameter haben,
(b) Bereinigen von ausgewählten der ursprünglichen Parameter nur für Segmente, die mit dem zu vermeidenden Teil der ursprünglichen Route assoziiert sind, wodurch eine Mehrzahl bereinigter Parameter bereitgestellt wird, und
(c) teilweise auf die bereinigten Parameter gestütztes Ermitteln der Ausweichroute vom neuen Ausgangsstandort zu dem nachfolgenden Standort, und

Gemäß noch einem weiteren Aspekt der vorliegenden Erfindung ist ein Computerprogrammprodukt zum Ermitteln einer Ausweichroute von einem auf einer ursprünglichen Route gelegenen neuen Ausgangsstandort zu einem nachfolgenden Standort auf der ursprünglichen Route vorgesehen, der Folgendes hat:
ein computerlesbares Medium und
einen in dem computerlesbaren Medium eingebetteten Computerprogrammmechanismus zum Veranlassen eines Computers zum Durchführen der folgenden Schritte:
Ermitteln eines Teils der ursprünglichen Route, der mit der Ausweichroute zu vermeiden ist, wobei der Teil der ursprünglichen Route an dem neuen Ausgangsstandort beginnt und der Teil der ursprünglichen Route eine Mehrzahl von Segmenten umfasst, die jeweils einen damit assoziierten ursprünglichen Parameter haben,
Bereinigen von ausgewählten der ursprünglichen Parameter nur für Segmente, die mit dem zu vermeidenden Teil der ursprünglichen Route assoziiert sind, was eine Mehrzahl bereinigter Parameter zur Folge hat, und
teilweise auf die bereinigten Parameter gestütztes Ermitteln der Ausweichroute vom neuen Ausgangsstandort zu dem nachfolgenden Standort.
Die folgende Beschreibung und die 3 bis 6 der Zeichnungen beschreiben beispielhaft die Erfindung, die in den angehängten Ansprüchen gekennzeichnet ist, deren Wortlaut den hierdurch gewährten Grad an Schutz bestimmt.
In den Zeichnungen zeigt:
3 ein schematisches Blockdiagramm einer spezifischen Ausgestaltung eines Fahrzeugnavigationssystems zur Verwendung mit der vorliegenden Erfindung,
4A und 4B eine Illustration einer die vorliegende Erfindung veranschaulichenden spezifischen Ausgestaltung,
5 eine Tabelle von Kostenwerten, die einer die vorliegende Erfindung veranschaulichenden spezifischen Ausgestaltung entsprechen, und
6 ein Ablaufdiagramm, das eine die vorliegende Erfindung veranschaulichende spezifische Ausgestaltung illustriert.
Beim Betrachten der vorliegenden Erfindung ist es eventuell hilfreich, auf die US-Patente Nr. 5,345,382, Nr. 5,359,529, Nr. 5,374,933 und Nr. 5,515,283 Bezug zu nehmen.
In 3, auf die jetzt Bezug genommen wird, wird ein Fahrzeugnavigationssystem 10 zur Verwendung mit der vorliegenden Erfindung gezeigt, das Sensoren 12 und 14 und einen GPS-Empfänger 18 hat, die durch die Sensor-/GPS-Schnittstelle 22 mit der Recheneinrichtung 20 verbunden sind. In typischen Ausgestaltungen ist der Sensor für zurückgelegte Entfernung 12 ein Wegstreckenzähler und der Winkelgeschwindigkeitssensor 14 ist ein Gyroskop oder ein mit den Rädern des Fahrzeugs verbundener Differentialwegstreckenzähler. Ein Global-Positioning-System-(GPS)-Datenempfänger 18 ist zum Empfangen von Signalen von z. B. einem satellitengestützten Navigationssystem bereitgestellt. Daten von der Sensor-/GPS-Schnittstelle 22 werden zur Zentraleinheit (CPU) 24 übertragen, die Kalibrierung, Signalverarbeitung, Koppelnavigation, Fahrzeugpositionierung und Routenführungsfunktionen durchführt. Eine Karteninformationen enthaltende Datenbank kann im Datenbankmedium 26 gespeichert sein, wobei den Betrieb der Recheneinrichtung 20 leitende Software zur Ausführung durch die CPU 24 im Hauptspeicher 28 gespeichert ist. Der Speicher 28 kann einen Festwertspeicher (ROM) oder einen wiederprogrammierbaren nichtflüchtigen Speicher wie einen Flash-Speicher oder SRAM umfassen. System-RAM 30 erlaubt das Lesen und Schreiben der zum Ausführen derartiger Softwareprogramme notwendigen Informationen. Das Datenbankmedium 26 kann einen nichtflüchtigen Speicher, ein Festplattenlaufwerk, CD-ROM oder eine integrierte Schaltung umfassen, in/auf dem/der digitalisierte Karteninformationen abgespeichert sind. Ausgabecontroller 32, der einen Graphik-Controller umfassen kann, empfängt von der CPU 24 verarbeitete Daten und überträgt die Daten zur Anzeigekonsole 40, die den Ausgabekommunikator 34 aufweist, der gewöhnlich einen Bildschirm mit assoziierter Audioelektronik und Audiolautsprechern umfasst. Der Fahrer kann Daten, wie einen gewünschten Zielort, über die Benutzeroberfläche 36 eingeben, die gewöhnlich eine Tastatur umfasst.
Die im Datenbankmedium 26 gespeicherte Kartendatenbank umfasst vorzugsweise Positionsdaten wie z. B. Längen- und Breitenkoordinaten zum Beschreiben von Straßenkreuzungen oder -knoten, Straßensegmenten, Landmarken und Stellen von Interesse sowie andere geographische Informationen. Die Datenbank kann ferner Daten umfassen, die Charakteristiken von Straßen oder Orten auf der Karte wie Straßen- und Ortsnamen, Straßenmerkmale wie Mittelstreifen, Einbahnstraßenbegrenzungen, Straßendecke, Geschwindigkeitsbegrenzung, Form, Höhe und sonstige Eigenschaften darstellen. In einer die Erfindung veranschaulichenden Ausgestaltung hat die Kartendatenbank mit einzelnen Knoten und Straßensegmenten assoziierte Kostenwerte. Diese Kostenwerte entsprechen den geschätzten Zeitintervallwerten zum Überqueren des jeweiligen Knotens oder Segments. Knotenkostenwerte berücksichtigen Informationen wie z. B., ob das Fahrzeug Gegenverkehr antreffen würde, wodurch ein Linksabbiegevorgang verzögert würde. Segmentkosten reflektieren Straßensegmentcharakteristiken, wie Geschwindigkeitsbegrenzung und Segmentlänge, die beide die Fahrzeit längs dem Segment beeinflussen. Mit jeder Straße in der Kartendatenbank ist auch eine Verbindungsklasse assoziiert, die sich auf die/den Straßenkategorie oder -typ bezieht. Beispielsweise ist die Kategorie auf höchster Ebene der Hierarchie die Verbindungsklasse AUTOBAHN. Die unterste Ebene hat die Verbindungsklassen ANLIEGERFAHRBAHN und VERSCH., die zum Beispiel Anliegerfahrbahnen und Gassen beinhaltet.
Ein die Erfindung veranschaulichendes Fahrzeugnavigationssystem hat die Aufgabe, eine Route von einem Ausgangsstandort zu einem Zielort gemäß einer Vielfalt verschiedener Verfahren zu erstellen. Einige Beispiele derartiger Verfahren werden in den oben erwähnten US-Patenten beschrieben. Außerdem können in Verbindung mit der vorliegenden Erfindung weitere Verfahren für die Routenerstellung angewendet werden.
Die 4A und 4B dienen zum Illustrieren des Betriebs einer spezifischen die Erfindung veranschaulichenden Ausgestaltung. Anfänglich wird eine ursprüngliche Route 402 (an den Straßen 404, 406 und 408 entlang) von dem oben beschriebenen Fahrzeugnavigationssystem erstellt. Während sich der Benutzer von Ausgangsort S auf der Straße 404 voranbewegt, wird starker Verkehr angetroffen (oder irgendeines einer Vielfalt von Verkehrshindernissen), was eine Taste oder einen Schalter auf der Benutzeroberfläche aktiviert und das System informiert, dass der Benutzer einen Teil der ursprünglichen Route 402 zu vermeiden wünscht. In 4B wird die Bildschirmfolge gezeigt. Wenn der Benutzer sich auf der Straße 404 entlang voranbewegt, wird auf dein Bildschirm 410 das nächste bevorstehende Fahrmanöver, d. h. Linkseinbiegen in Straße 406, angezeigt. Wenn der Benutzer die Taste „Vermeiden" betätigt, wird ein Bildschirm AKTUELLE ROUTE VERMEIDEN 412 angezeigt, in dem der Benutzer auf eine gewünschte Entfernung blättern und die Eingabetaste „Enter" drücken kann. Die Entfernungen können in Meilen sein, wie abgebildet. Alternativ können die Entfernungen dem Benutzer als eine Anzahl von Straßensegmenten, Stadtstraßenblöcken usw. dargestellt werden. In einer anderen Ausgestaltung kann der Benutzer jede beliebige Entfernung in einem Bereich direkt eingeben.
Nachdem der Benutzer die Entfernung ausgewählt hat, erstellt das System eine Ausweichroute 414 und teilt dem Benutzer ein neues bevorstehendes Fahrmanöver mit (Bildschirm 416). Beim Erstellen der Ausweichroute 414 erhöht das System die Kosten, die mit ausgewählten der Segmente in dem Teil der ursprünglichen Route assoziiert sind, die an der Kreuzung der Straßen 404 und 418 beginnt und sich über die ausgewählte Entfernung erstreckt. Die Art und Weise, in der dies in einer bestimmten die Erfindung veranschaulichenden Ausgestaltung erreicht wird, wird mit Bezug auf 4A und Tabelle 500 in 5 verständlich. Wie in 4A gezeigt wird, beinhaltet die ursprüngliche Route 402 die Segmente S1–S13. Beim Erstellen einer Ausweichroute werden die mit jedem dieser Segmente verbundenen Kosten um einen in Tabelle 500 gezeigten Wert erhöht. Die Kostenwerte in Tabelle 500 werden in Sekunden gemessen, man wird aber verstehen, dass solche Kosten auf verschiedene Arten dargestellt werden können.
Wie in der Tabelle gezeigt wird, werden die zu den Segmentkosten, die mit jedem darauffolgenden Segment assoziiert sind, hinzugefügten Kosten bei zunehmender Segmentzahl, d. h. mit zunehmender Entfernung von dem Verkehrshindernis, allmählich auf null verringert. Das Dekrement und die Geschwindigkeit dieser Verringerung hängt von der vom Benutzer angegebenen zu vermeidenden Entfernung der ursprünglichen Route ab. Je näher daher das Segment dem Verkehrshindernis ist, desto wahrscheinlicher ist es, dass der Ausweichrouten-Erstellungsalgorithmus es wegen des drastischen Anstiegs der Kosten ignorieren wird. Desgleichen nimmt bei zunehmender Entfernung der Segmente von dem Verkehrshindernis die Wahrscheinlichkeit, dass der Algorithmus sie ignoriert, ab, bis die Ausweichroute ein Segment von der ursprünglichen Route enthält, d. h. Segment S9.
Man wird verstehen, dass die oben beschriebene Ausgestaltung modifiziert werden kann, sodass sie die Manipulation von Knotenkosten anstelle von oder zusätzlich zu der Manipulation von Segmentkosten enthält. Knotenkosten sind die mit dem Überqueren eines Kartenknotens, wie beispielsweise einer Kreuzung, verbundenen Kosten. Die Knotenkosten für eine bestimmte Kreuzung können ungeachtet einer bestimmten Route ermittelt werden. Sie können auch so ermittelt werden, dass sie speziell das Überqueren der Kreuzung von einem spezifischen Segment zu einem anderen reflektieren. Gemäß einer solchen Ausgestaltung können Knotenkosten weitgehend so manipuliert werden, wie in 5 bezüglich Segmentkosten gezeigt wird. Die manipulierten Knotenkosten können dann zum Ermitteln der Ausweichroute anstelle der Kosten der Segmente oder zusätzlich zu ihnen verwendet werden.
6 ist ein Ablaufdiagramm 600, das den Betrieb einer spezifischen Ausgestaltung der Erfindung illustriert. Das beschriebene Fahrzeugnavigationssystem führt den Benutzer entlang einer ursprünglich berechneten Route (Schritt 601), sofern es in Reaktion auf eine Eingabe von dem Benutzer ein „Route vermeiden"-Signal nicht empfängt (Schritt 602). Das System zeigt dem Benutzer dann einen Bildschirm „AKTUELLE ROUTE VERMEIDEN" an, wie in 4B (Schritt 604) gezeigt wird, sodass der Benutzer angeben kann, wie viel der usprünglichen Route vermieden werden soll. Nach der Auswahl eines zu vermeidenden Teils der aktuellen Route durch den Benutzer (Schritt 606) erstellt das System eine Umleitungsliste, die Segmente der ursprünglichen Route enthält, die an dem aktuellen Standort des Fahrzeugs beginnen und in der Entfernung enden, die vom Benutzer angegeben wurde (Schritt 608). Für ausgewählte Segmente in der Liste erhöht das System dann die mit jedem Segment assoziierten Kosten (Schritt 610).
Wie oben mit Bezug auf die 4A und 5 besprochen, nimmt das Kosteninkrement mit zunehmender Entfernung zwischen den Segmenten der ursprünglichen Route und dem Verkehrshindernis ab. Wenn die mit den ursprünglichen Straßensegmenten assoziierten Kosten auf diese Weise erhöht worden sind, erstellt das System eine Ausweichroute ab dem aktuellen Fahrzeugstandort, d. h. dem Standort des Verkehrhindernisses, bis zu einem nachfolgenden Standort auf der ursprünglichen Route (Schritt 612). Wie oben besprochen wird, neigt das System dazu, wegen der mit den Segmenten der ursprünglichen Route in der Umleitungsliste assoziierten erhöhten Kosten die Ausdehnung entlang dieser Segmente mit dem Algorithmus zum Ermitteln von Ausweichrouten zu vermeiden. Dies gilt besonders für die Segmente der ursprünglichen Route, die dem Anfang der Ausweichroute am nächsten sind, weil mit diesen Segmenten die größte Kostenerhöhung verbunden ist. Je weiter die Segmente der ursprünglichen Route in der Umleitungsliste aber von dem aktuellen Fahrzeugstandort entfernt sind, umso unwahrscheinlicher ist es, dass sie vom Suchalgorithmus vermieden werden. Auf diese Weise weist der Algorithmus zum Bestimmen der Ausweichroute schließlich ein Segment in der Ausweichroute auf, das mit einem Segment in der ursprünglichen Route zusammenfällt. In diesem Fall endet der Algorithmus (Schritt 614).
Es wurden zwar die Erfindung ausgestaltende spezifische Ausgestaltungen beschrieben, man wird aber verstehen, dass Variationen und Modifikationen davon sowie andere Ausgestaltungen durchgeführt werden können, ohne aus dem Umfang des von den angehängten Ansprüchen gewünschten Schutzes zu kommen. Beispielsweise wurden Ausgestaltungen beschrieben, bei denen ein variables Inkrement zu den mit den Straßensegmenten assoziierten Segmentkosten in einem spezifizierten Teil der ursprünglichen Route hinzugefügt wird. Man wird aber erkennen, dass diese Kosten innerhalb des gewünschten Schutzumfangs auf vielerlei Weise manipuliert werden können. Beispielsweise braucht das Kosteninkrement im Gegensatz zur Tabelle 500 nicht für jedes aufeinanderfolgende Segment in der ursprünglichen Route einheitlich dekrementiert zu werden. Das Kosteninkrement kann vielmehr für mehrere aufeinanderfolgende Segmente fest sein.
Darüber hinaus kann für ausgewählte Segmente in der ursprünglichen Route, anstatt die assoziierten Segmentkosten zu erhöhen, der Zugang zu solchen Segmenten (z. B. den ersten fünf Segmenten nach dem Verkehrshindernis) vollständig gesperrt werden. Feste und/oder variable Kosteninkremente können dann zu darauffolgenden Segmenten hinzugefügt werden. So kann eine Vielfalt von Segmentparametern (z. B. Segmentkosten) für die Segmente in dem mit der Ausweichroute zu vermeidenden Teil der ursprünglichen Route auf verschiedenerlei Weise manipuliert werden.

Claims

Verfahren zum Ermitteln einer Ausweichroute (414) von einem auf einer ursprünglichen Route (402) gelegenen neuen Ausgangsstandort zu einem nachfolgenden Standort auf der ursprünglichen Route (402) mithilfe eines Fahrzeugnavigationssystems, wobei die ursprüngliche Route an einem ursprünglichen Ausgangsstandort beginnt, der vor dem neuen Ausgangsstandort auf der ursprünglichen Route liegt, wobei das Verfahren die folgenden Schritte aufweist: Ermitteln eines Teils der ursprünglichen Route (402), der mit der Ausweichroute (414) zu vermeiden ist, wobei der Teil der ursprünglichen Route (402) an dem neuen Ausgangsstandort beginnt und der Teil der ursprünglichen Route (402) eine Mehrzahl von Segmenten hat, die jeweils einen damit assoziierten ursprünglichen Parameter haben, Bereinigen von ausgewählten der ursprünglichen Parameter nur für Segmente, die mit dem zu vermeidenden Teil der ursprünglichen Route assoziiert sind, wodurch eine Mehrzahl bereinigter Parameter bereitgestellt wird, und teilweise auf die bereinigten Parameter gestütztes Ermitteln der Ausweichroute (414) vom neuen Ausgangsstandort zu dem nachfolgenden Standort.
Verfahren nach Anspruch 1, bei dem der erste Ermittlungsschritt die folgenden Schritte enthält: Bereitstellen einer Eingabevorrichtung (36) für einen Benutzer des Fahrzeugnavigationssystems zum Auswählen einer Länge des Teils der ursprünglichen Route (402), der mit der Ausweichroute zu vermeiden ist, und Ermitteln des Teils der ursprünglichen Route (402) in Reaktion auf (eine) Eingabe(n) vom Benutzer.
Verfahren nach Anspruch 2, bei dem die Eingabevorrichtung (36) eine Mehrzahl von Längenoptionen bereitstellt, aus denen der Benutzer eine auswählt.
Verfahren nach Anspruch 1, bei dem die Eingabevorrichtung (36) es dem Benutzer erlaubt, die Länge des zu vermeidenden Teils der ursprünglichen Route (402) anzugeben.
Verfahren nach Anspruch 1, bei dem die Parameter Segmentkosten beinhalten, wobei der Bereinigungsschritt das Addieren zusätzlicher Kosten zu ausgewählten der Segmentkosten beinhaltet.
Verfahren nach Anspruch 5, bei dem die zusätzlichen Kosten festgesetzt sind.
Verfahren nach Anspruch 5, bei dem die zusätzlichen Kosten im Verhältnis zur Entfernung zwischen dem neuen Ausgangsstandort und einem bestimmten Segment variieren.
Verfahren nach Anspruch 7, bei dem die zusätzlichen Kosten mit zunehmender Entfernung zwischen dem neuen Ausgangsstandort und dem bestimmten Segment abnehmen.
Verfahren nach Anspruch 1, bei dem die Parameter sich auf Segmentzugriff beziehen, wobei der Bereinigungsschritt das Sperren des Zugriffs auf ausgewählte der Segmente zum Ermitteln der Ausweichroute beinhaltet.
Verfahren nach Anspruch 1, bei dem die Parameter Knotenkosten beinhalten, wobei der Bereinigungsschritt das Addieren zusätzlicher Kosten zu ausgewählten der Knotenkosten beinhaltet.
Verfahren nach Anspruch 10, bei dem die zusätzlichen Kosten festgesetzt sind.
Verfahren nach Anspruch 10, bei dem die zusätzlichen Kosten im Verhältnis zur Entfernung zwischen dem neuen Ausgangsstandort und einem bestimmten Knoten variieren.
Verfahren nach Anspruch 12, bei dem die zusätzlichen Kosten mit zunehmender Entfernung zwischen dem neuen Ausgangsstandort und dem bestimmten Knoten abnehmen.
Vorrichtung zur Verwendung beim Ermitteln einer Ausweichroute (414) von einem auf einer ursprünglichen Route (442) gelegenen neuen Ausgangsstandort zu einem nachfolgenden Standort auf der ursprünglichen Route (402), wobei die ursprüngliche Route (402) an einem ursprünglichen Ausgangsstandort beginnt, der vor dem neuen Ausgangsstandort auf der ursprünglichen Route liegt, wobei die Vorrichtung Folgendes hat: eine Einrichtung (10) zum Ermitteln eines Teils der ursprünglichen Route (402), der mit der Ausweichroute (414) zu vermeiden ist, wobei der Teil der ursprünglichen Route (402) an dem neuen Ausgangsstandort beginnt und der Teil der ursprünglichen Route (402) eine Mehrzahl von Segmenten hat, die jeweils einen damit assoziierten ursprünglichen Parameter haben, eine Einrichtung zum Bereinigen von ausgewählten der ursprünglichen Parameter nur für Segmente, die mit dem zu vermeidenden Teil der ursprünglichen Route assoziiert sind, was zu einer Mehrzahl bereinigter Parameter führt, und eine Einrichtung zum teilweise auf die bereinigten Parameter gestützten Ermitteln der Ausweichroute (414) vom neuen Ausgangsstandort zu dem nachfolgenden Standort.
Vorrichtung nach Anspruch 14, die zur Verwendung in einem Fahrzeugnavigationssystem (10) angeordnet ist, wobei die genannte Vorrichtung ferner Folgendes umfasst: eine Mehrzahl von Sensoren (12–16) zum Erfassen einer aktuellen Fahrzeugposition und eines Fahrzeugsteuerkurses und zum Erzeugen von dafür bezeichnenden Signalen, ein Datenbankmedium (26) mit darin gespeicherten geographischen Stellen einer Mehrzahl von Straßensegmenten und Segmentknoten, einen mit den Sensoren (12–16) und dem Datenbankmedium (26) verbundenen Prozessor (24) zum Durchführen der Verfahrensschritte der Ansprüche 1 bis 13 und einen mit dem Prozessor (24) verbundenen Ausgabekommunikator (34), um einem Benutzer des Fahrzeugnavigationssystems die Ausweichroute mitzuteilen.
Prozessorimplementierbare Anweisungen speicherndes Speichermedium zum Steuern eines Prozessors zum Implementieren des Verfahrens nach einem der Ansprüche 1 bis 13.
Prozessorimplementierbare Anweisungen zum Steuern eines Prozessors zum Implementieren des Verfahrens nach einem der Ansprüche 1 bis 13.