Verfahren zur Manövergenerierung für Kreuzungssituationen

Die Erfindung betrifft ein Verfahren zur Manövergenerierung für Kreuzungssituationen und ein Fahrzeug mit einem Navigationssystem.

In Navigationssystemen müssen an Entscheidungspunkten, beispielsweise Kreuzungen, prägnante und eindeutige Manöver oder Fahranweisungen generiert werden. Bisherige Konzepte versuchen durch Auswertung der Winkelgeometrien und weiterer Attribute entsprechende Manöver zu erzeugen. Bislang wird die konkrete Umsetzung von Zulieferern durchgeführt, so dass sich in der späteren Entwicklung die Manövergenerierung kaum mehr beeinflussen lässt. Des Weiteren können sich die von verschiedenen Lieferanten entwickelten Systeme unterschiedlich verhalten.

Bisherige Lösungen versuchen Kreuzungsgeometrien allgemeingültig zu beschreiben oder bestimmte Abhängigkeiten und Winkelgeometrien auszuwerten. Beispielsweise wird dies in der US 6199013 B1 offenbart.

Der Erfindung liegt nun die Aufgabe zugrunde, die Manövergenerierung für

Kreuzungssituationen zu vereinfachen und eindeutig zu beschreiben.

Diese Aufgabe wird gelöst durch ein Verfahren gemäß Anspruch 1 beziehungsweise ein Fahrzeug gemäß Anspruch 8.

Das erfindungsgemäße Verfahren zur Manövergenerierung für Kreuzungssituationen, wobei in einer Kreuzungssituation eine eingehende Straße, eine in einem Ausgangswinkel zu der eingehenden Straße angesetzte, ausgehende Straße sowie eine linke und/oder rechte

Seitenstraße vorhanden sind, die in einem Linkswinkel beziehungsweise einem Rechtswinkel zu der ausgehenden Straße angesetzt sind, umfasst die Schritte:

- Erstellen eines Koordinatensystems mit einer X-Achse, entlang welcher der Linkswinkel und/oder der Rechtswinkel aufgetragen ist, und einer Y-Achse, entlang welcher der

Ausgangswinkel aufgetragen ist;

- Abbilden der ausgehenden Straße unter dem Ausgangswinkel auf der Y-Achse; - Abbilden der linken und/oder rechten Seitenstraße unter dem Linkswinkel beziehungswiese dem Rechtswinkel auf der X-Achse;

- Ermitteln des einen oder der zwei Schnittpunkte zwischen der Abbildung der ausgehenden Straße und der Abbildung der linken und/oder rechten Seitenstraße;

- Parametrisieren von Ergebnispolygonen jeweils für einzelne Manövertypen anhand möglicher Ausgangswinkel, Linkswinkel und/oder Rechtswinkel;

- Abbilden der Ergebnispolygone in dem Koordinatensystem;

- Bestimmen des oder der Ergebnispolygone, in welchen der oder die Schnittpunkte liegen; und -Generieren eines Manövers anhand des Manövertyps des bestimmten Ergebnispolygons.

Das erfindungsgemäße Verfahren hat den Vorteil, dass Kreuzungsgeometrien gerade nicht allgemeingültig beschrieben werden, sondern eine wenig rechenintensive Reduktion

vorgenommen wird. Es ist zudem eine Flexibilität gegenüber der definierbaren Manövertypen und deren späterer Parametrierung gegeben. Das Verfahren erlaubt eine flexible Definition von Manövertypen, sowohl in Anzahl wie auch Ausprägung. Im Unterschied zu bekannten

Lösungen werden Kreuzungsgeometrien jeweils unter Berücksichtigung der benachbarten Seitenstraßen ausgewertet. Es hat sich in eigenen Untersuchungen gezeigt, dass sich die Prägnanz und Eindeutigkeit eines Manövers, etwa für die Bewertung der Manöverrichtung und der Unterscheidbarkeit von Fahrtrichtungen, vorrangig hieraus ableitet. Im Sinne der Erfindung hat sich ergeben, dass für die Bestimmung eines Manövers vorrangig die Richtung der geplanten Route sowie der jeweils nächstgelegen linken und rechten Straße relevant sind. Diese Informationen werden durch eine grafische Repräsentationsform der definierten

Manövertypen abgebildet, wodurch zugleich eine flexible Konfigurierbarkeit möglich ist.

Die Manövergenerierung erfolgt für eine isolierte Kreuzungssituation, die Bestandteil einer Fahrtroute sein kann. Die Berechnung des Manövers kann situativ im Fahrzeug erfolgen. Es kann auch vorgesehen, dass die Manövergenerierung vor der eigentlichen Fahrt für eine Navigationskarte oder eine Navigationsroute durchgeführt wird. Dann können die generierten Manöver an den jeweiligen Kreuzungen hinterlegt werden.

Es kann vorgesehen sein, dass bei der Parametrisierung des Ergebnispolygons alle für den Manövertyp des Ergebnispolygons möglichen Ausgangswinkel, Linkswinkel und/oder Rechtswinkel betrachtet werden und dass das oder die Ergebnispolygone so gewählt werden, dass die dabei entstehenden Schnittpunkte von dem oder den Ergebnispolygonen umschlossen sind. Die Ergebnispolygone können durch eine Liste von Koordinatenpaaren aus x- und y- Koordinaten definiert sein. Geraden zwischen den Koordinatenpaaren bilden dann eine Hüllkurve des Ergebnispolygons. Die Darstellung mit Koordinatenpaaren ist einfach zu erstellen und handzuhaben.

Die Liste kann Variablen mit Koordinatenpaaren enthalten. Durch Variablen oder Bezeichner kann eine Wiederholung von einzelnen oder mehreren Koordinatenpaaren vermieden werden, was die Liste verkürzt und so Speicherplatz und Verarbeitungsgeschwindigkeit optimiert.

Es kann vorgesehen sein, dass entlang der X-Achse ein linker Winkelbereich von -180° bis 0° und daran anschließend ein rechter Winkelbereich von 0° bis 180° aufgetragen ist. Dies ermöglicht eine einfache Berücksichtigung linker und rechter Seitenstraßen in einem Graphen beziehungsweise einem Koordinatensystem.

Es kann ferner vorgesehen sein, dass für Mehrdeutigkeiten bei dem Bestimmen des oder der Ergebnispolygone, in welchen der oder die Schnittpunkte liegen, eine Priorisierungsliste für Manöver verwendet wird. So kann auf einfache Art gewährleistet werden, dass immer eine eindeutige Lösung vorliegt. Eine Mehrdeutigkeit kann zum Beispiel vorliegen, wenn ein

Schnittpunkt auf eine Polygongrenze fällt. Dann werden alle relevanten Manövertypen identifiziert und das Manöver mit der höchsten definierten Priorität ausgewählt.

Das generierte Manöver kann einem Fahrer eines Fahrzeugs optisch und/oder akustisch dargestellt werden. Zum Beispiel mittels eines Navigationssystems oder einer

Infotainmenteinheit kann der Fahrer über das nächste anstehende Manöver informiert werden. Die einfache grafische Ermittlung des Manövers erlaubt eine schnelle Bereitstellung des Manövers, was zu einem schnellen und damit sicheren System führt.

Das erfindungsgemäße Fahrzeug umfasst ein Navigationssystem, das eingerichtet ist, ein Verfahren wie zuvor beschrieben auszuführen. Es gelten die gleichen Vorteile und

Modifikationen wie zuvor beschrieben. Es kann vorgesehen sein, dass ein Teil des Verfahrens in dem Fahrzeug und ein Teil in einem Backend des Herstellers oder eines Dienstanbieters ausgeführt wird.

Weitere bevorzugte Ausgestaltungen der Erfindung ergeben sich aus den übrigen, in den Unteransprüchen genannten Merkmalen. Die verschiedenen in dieser Anmeldung genannten Ausführungsformen der Erfindung sind, sofern im Einzelfall nicht anders ausgeführt, mit Vorteil miteinander kombinierbar.

Die Erfindung wird nachfolgend in Ausführungsbeispielen anhand der zugehörigen

Zeichnungen erläutert. Es zeigen:

Figur 1 eine schematische Definition der Winkelbereiche;

Figur 2 eine schematische Darstellung der Festlegung von Manöverpunkten;

Figur 3 eine schematische Darstellung von Ergebnispolygonen

Figur 4 eine schematische Darstellung einer Kreuzungssituation; und

Figur 5 eine schematische Darstellung der Ermittlung eines Manövers.

Im Sinne der Erfindung werden Manövertypen, deren Anzahl und Ausprägungen, beliebig definiert und parametriert werden. Im Sinne der Erfindung hat sich ergeben, dass für die Bestimmung eines Manövers vorrangig die Richtung der geplanten Route sowie der jeweils nächstgelegen linken und rechten Straße relevant sind. Diese Informationen werden durch eine grafische Repräsentationsform der definierten Manövertypen abgebildet, wodurch zugleich eine flexible Konfigurierbarkeit möglich ist.

Es können eine beliebige Anzahl an verschiedenen Manövertypen und Ausprägungen definiert werden, zum Beispiel:

Kein Manöver (da Routenverlauf eindeutig)

Geradeaus

Links/rechts abbiegen

Halb links/rechts abbiegen

Scharf links/rechts abbiegen

Links/rechts halten

Im nachfolgenden wird die Manövergenerierung jeweils für ein Abbiegen nach rechts beschrieben, durch entsprechende Spiegelung ist der Ansatz analog auch für Abbiegemanöver nach links übertragbar. Eine Kreuzungsgeometrie ist gekennzeichnet durch einen Kreuzungspunkt, typischerweise der Mittelpunkt, von dem eine beliebige Anzahl an Kanten, das heißt digitalisierten Straßen, abgehen. Die nachfolgenden Informationen werden bestimmt:

• Eingehende Kante: Die Straße die zum Kreuzungspunkt führt und gleichzeitig den

Ausgangspunkt der Fahrzeugposition bzw. Route darstellt.

• Ausgehende Kante: Die Straße die vom Kreuzungspunkt wegführt und entlang der berechneten Route verläuft.

• Linke/rechte Seitenstraße: Auf die ausgehende Kante bezogen wird die jeweils angrenzende linke/rechte Seitenstraße bezeichnet. Ist keine Seitenstraße vorhanden, so ist stattdessen der Maximalwert (-180° bzw. 180°) zu verwenden.

Im nachfolgenden werden die hieraus folgenden Abhängigkeiten betrachtet:

• Ausgangswinkel zwischen eingehender und ausgehender Kante.

• Linkswinkel zwischen ausgehender Kante und linker Seitenstraße.

• Rechtswinkel zwischen ausgehender Kante und rechter Seitenstraße.

Die Länge der betrachteten Kanten ist individuell adaptierbar und es können auch bei Bedarf mehrere Karten- und/oder Kantensegmente zusammengefasst werden, um eine Minimallänge zu erreichen.

Figur 1 beschreibt die verwendeten Winkelbeziehungen, wobei der Ursprung jeweils die eingehende Straße beziehungsweise Kante 10 darstellt. Zwischen 0°, das heißt der

Verlängerung der eingehenden Kante 10, und dem Winkel der ausgehenden Kante 12 ist der Ausgangswinkel α definiert. Die Winkelbeziehungen zur ausgehenden Straße beziehungsweise Kante 12 und den beiden Seitenstraßen werden auf das Koordinatensystem aus Figur 1 abgebildet. Bei einer nach rechts verlaufenden ausgehenden Kante 12 ist der Ausgangswinkel α positiv, bei einer nach links verlaufenden ausgehenden Kante 12 ist der Ausgangswinkel α negativ.

In Figur 2 ist die Verwendung einer grafischen Repräsentationsform zur Manövergenerierung dargestellt. Die ausgehende Kante 12 sowie die beiden nächstgelegenen Seitenstraßen sind auf ein Koordinatensystem 14 abgebildet. Auf der X-Achse sind die Winkel der an die Kreuzung nächst angrenzenden linken und rechten Seitenstraße in einem Bereich von -180° bis 0° für die linke Seitenstraße und in einem Bereich von 0° bis 180° für die rechte Seitenstraße

aufgetragen. Je nach Kreuzungssituation kann zum Beispiel der Linkswinkel auch in den positiven Bereich reichen. Anders ausgedrückt erstreckt sich der Linkswinkel von -180° bis zu 0° +/- Ausgangswinkel α. Entsprechend erstreckt sich der Rechtswinkel von 180° bis zu 0° -/+ Ausgangswinkel a. Der Nullpunkt beider Seitenstraßen fällt zu einem Nullpunkt zusammen, der in der Mitte der X-Achse angeordnet ist. Entlang der Y-Achse ist der Ausgangswinkel in einem Bereich von 0° bis 180° aufgetragen.

Entsprechend Figur 2 wird der Winkel der ausgehenden Kannte 12, auch als Manöverrichtung bezeichnet, auf die Y-Achse übertragen, so dass eine Ausgangsgerade 16 entsteht, welche parallel zu der X-Achse verläuft. Der Linkswinkel und der Rechtswinkel der jeweils

nächstgelegenen rechten und linken Seitenstraße werden auf der X-Achse abgebildet, so dass eine Linksgerade 18 und eine Rechtsgerade 20 entstehen, welche parallel zu der Y-Achse verlaufen. Hieraus ergeben sich zwei Schnittpunkte 22 und 24. Die Linksgerade 18 und die Ausgangsgerade 16 schneiden sich in einem linken Schnittpunkt 22. Die Rechtsgerade 20 und die Ausgangsgerade 18 schneiden sich in einem rechten Schnittpunkt 24.

Die diagonale Linie 26 verdeutlicht die möglichen Winkelbereiche der Seitenstraßen in

Abhängigkeit zum Manöverwinkel. In dem Beispiel von Figur 2 beträgt der Manöverwinkel 45°. Entsprechend kann der Linkswinkel beziehungsweise die linke Seitenstraße in dem Bereich von -180° bis 45° und der Rechtswinkel beziehungsweise die rechte Seitenstraße in dem Bereich von 45° bis 180° liegen. Es sei erneut darauf hingewiesen, dass die hier dargestellte Abbildung ausschließlich Manöver nach rechts abbildet. Durch eine Spiegelung ist gleiches Prinzip auch für Manöver nach links anzuwenden.

Die eingangs definierten Manövertypen, wie zum Beispiel rechts abbiegen, werden in dem Koordinatensystem 14 durch Ergebnispolygone abgebildet, separiert nach linken und rechten Manöverbereichen. Fallen beide zuvor ermittelten Schnittpunkte 22 und 24 in die

Polygonflächen eines Manövertyps, so wird der entsprechende Typ ausgewählt. Figur 3 zeigt ein solches Ergebnispolygon 28 beispielhaft für den Fall in dem„kein Manöver" erforderlich ist. Das Ergebnispolygon 28 kann wie dargestellt aus zwei oder mehreren Teilpolygonen oder auch aus einem einzelnen Polygon bestehen.

Bei diesem Ansatz muss sichergestellt sein, dass immer eine eindeutige Zuordnung möglich ist. Alle Kombinationsmöglichkeiten müssen demzufolge über entsprechende Ergebnispolygone 28 abgedeckt sein. Des Weiteren müssen Mehrdeutigkeiten ausgeschlossen sein. Die Anzahl der möglichen Ergebnispolygone 28 ist dabei nicht beschränkt. Fällt ein Schnittpunkt 22, 24 auf eine Polygongrenze, so werden alle relevanten Manövertypen identifiziert und das Manöver mit der höchsten definierten Priorität ausgewählt. Dazu kann eine Priorisierungsliste für Manöver erstellt werden.

Für die Erstellung eines Ergebnispolygons 28 wird zunächst der Manövertyp wie zum Beispiel rechts Abbiegen festgelegt. Als nächstes wird das Ergebnispolygon 28 parametrisiert. Dazu werden alle für diesen Manövertyp möglichen Winkelkombinationen in dem Koordinatensystem 14 aufgetragen und um die entstandenen Schnittpunkte das Ergebnispolygon 28 gezogen.

So wird für jeden möglichen Manövertyp ein Ergebnispolygon 28 definiert. Bei dem Generieren oder Bestimmen eines Manövers wird dann dasjenige Ergebnispolygon 28 ermittelt, in welchem die Schnittpunkte 22 und 24 liegen. Das generierte Manöver entspricht dann dem Manövertyp dieses Ergebnispolygons 28.

Die verwendeten Ergebnispolygone 28 werden durch eine beliebige Anzahl an

Begrenzungslinien abgebildet. Eine Begrenzungslinie ist definiert durch einen eindeutigen Bezeichner und/oder eine Liste von X/Y-Koordinaten. Innerhalb eines Bezeichners oder einer Variable können sowohl reine Koordinaten, wie auch eine Koordinate zusammen mit einer Referenz auf einen anderen Bezeichner verwendet werden. Wird eine Referenz angegeben, so ist der jeweilige Wert der referenzierten Linie auf Höhe der angegebenen Koordinate zu verwenden.

Im Folgenden wird anhand der Figuren 4 und 5 ein Beispiel für die Generierung eines Manövers diskutiert.

Im Nachfolgenden wird von einer Kreuzungssituation 30 wie in Figur 4 dargestellt

ausgegangen. Die ausgehende Kante 12 verläuft unter einem Ausgangswinkel α von 20° zu der eingehenden Kante 10 beziehungsweise dem Nullwinkel. Die linke Seitenstraße 32 verläuft unter einem Linkswinkel ß von -120° zu der ausgehenden Kante 12. Die rechte Seitenstraße 34 verläuft unter einem Rechtswinkel γ von 135° zu der ausgehenden Kante 12.

Figur 4 verdeutlicht die hier angenommene Situation. Der Routenverlauf beziehungsweise die Fahrtrichtung wird durch die gestrichelte Linie 36 dargestellt. Die Kantenbezeichnungen entsprechen den obigen Definitionen.

Dann werden die obigen Werte auf das verwendete Koordinatensystem 14 abgebildet. Es werden wie oben beschrieben die Ausgangsgerade 16, die Linksgerade 18 und die Rechtsgerade 20 eingetragen Es ergeben sich die beiden Schnittpunkte 22 und 24 mit den Koordinaten -120/20 (Links) und 135/20 (Rechts).

Für jeden Manövertyp müssen ein oder mehrere Ergebnispolygone 28 definiert werden. Das hier beschriebene Konzept beschreibt Polygone über Begrenzungslinien anstatt einzelner Koordinaten. Als Beispiel wird ein Polygon für Situationen angegeben, in denen kein Manöver notwendig ist da ausreichend eindeutig. Die Begrenzungslinien setzen sich hier beispielhaft aus den folgenden Bezeichnen zusammen:

Polygon linker Bereich: 0L,1 L,0D

Polygon rechter Bereich: 1 R,0R,0D

Die folgende Tabelle 1 beschreibt für die relevanten Bezeichner entsprechende Koordinaten, wobei wiederum auf andere Bezeichner referenziert wird. Die daraus resultierenden

Begrenzungslinien sind in Figur 5 visualisiert.

Der Bezeichner OL entspricht der Begrenzungslinie 38 und verläuft auf der Y-Achse, das heißt bei der X-Koordinate -180° und von der Y-Koordinate 0° bis 180°. Der Bezeichner 0R entspricht der Begrenzungslinie 40 und verläuft parallel zu der Y-Achse am rechten Rand des

Koordinatensystems 14. Der Bezeichner OD entspricht der Begrenzungslinie 42 und verläuft auf der X-Achse. Der Bezeichner 1 L entspricht der Begrenzungslinie 44, die entlang der oben angegebenen vier Koordinatenpaare verläuft. Der Bezeichner 1 R entspricht der

Begrenzungslinie 46, die entlang der oben angegebenen vier Koordinatenpaare verläuft.

Hier sind die beiden Ergebnispolygone 28 oder anders ausgedrückt, die beiden Teilpolygone des Ergebnispolygons 28, symmetrisch. Dies muss nicht immer der Fall sein, was von der Parametrisierung abhängt.

Für die Bestimmung des Manövers werden nun die Schnittpunkte 22 und 24 betrachtet welche beide in das definierte Polygon 28 fallen, so dass der entsprechende Manövertyp zur Anwendung kommt. Fällt nur ein Schnittpunkt in das Polygon oder einer der Schnittpunkte in ein anderes Polygon, wird anhand der Priorisierungsliste das Manöver mit der höchsten definierten Priorität ausgewählt.

Das beschriebene Verfahren wird für die Navigation von Straßenfahrzeugen wie zum Beispiel PKWs, LKWs, Bussen, Motorrädern und ähnlichem verwendet. In einem Navigationssystem des Fahrzeugs, gegebenenfalls mit Unterstützung eines Backends oder Servers, wird das Verfahren ausgeführt, um dem Fahrer des Fahrzeugs ein der aktuellen Kreuzungssituation

entsprechendes Manöver vorzuschlagen. Durch die Reduktion der Kreuzungssituation in das Koordinatensystem 14 sinkt der Rechenaufwand und die Bearbeitungsgeschwindigkeit wird erhöht.

Bezugszeichenliste

10 eingehende Kante

12 ausgehende Kante

14 Koordinatensystem

16 Ausgangsgerade

18 Linksgerade

20 Rechtsgerade

22 linker Schnittpunkt

24 rechter Schnittpunkt

26 Linie

28 Ergebnispolygon

30 Kreuzungssituation

32 linke Seitenstraße

34 rechte Seitenstraße

36 gestrichelte Linie

38 Begrenzungslinie OL

40 Begrenzungslinie 0R

42 Begrenzungslinie OD

44 Begrenzungslinie 1 L

46 Begrenzungslinie 1 R α Ausgangswinkel

ß Linkswinkel

Y Rechtswinkel