Erstellen eines logischen Wegenetzes in Parkräumen

Die vorliegende Erfindung bezieht sich auf das Erstellen digitaler Karten für Parkräume aus Sensordaten von Kraftfahrzeugen.

US 10 012 991 B1 offenbart ein Verfahren und eine Vorrichtung zur Steuerung des Betriebs eines autonomen Fahrzeugs. Einem Aspekt zufolge kann das autonome Fahrzeug die Trajektorien anderer Fahrzeuge auf einer Straße verfolgen. Basierend auf den Trajektorien der anderen Fahrzeuge kann das autonome Fahrzeug einen Pool von kombinierten Trajektorien erzeugen. Anschließend kann das autonome Fahrzeug eine der kombinierten Trajektorien als eine repräsentative Trajektorie auswählen. Die repräsentative Trajektorie kann verwendet werden, um die Geschwindigkeit oder die Richtung des autonomen Fahrzeugs zu ändern.

US 2020 0217458 A1 offenbart eine Vorrichtung und ein Verfahren, die Trajektorendaten für ein geografisches Gebiet liefern. Mehrere Sonden- Datensätze werden von einem oder mehreren mobilen Geräten empfangen oder identifiziert. Die Sonden-Datensätze enthalten Zeitwerte in einer ersten Sequenz, die mit Ortswerten in der ersten Sequenz verbunden sind. Mindestens einer der Sondierungsdatensätze ist modifiziert, um die Ortswerte umzukehren, so dass der modifizierte Sondierungsdatensatz in einer ersten Sequenz Zeitwerte enthält, die mit Ortswerten in einer zweiten Sequenz verbunden sind. Ein Algorithmus zum Clustern von Orten wird auf der Grundlage der Vielzahl von Prüfdatensätzen und dem modifizierten Prüfdatensatz basierend auf den Ortswerten durchgeführt.

Es ist daher wünschenswert ein verbessertes Kartensystem bereitzustellen.

Dies erfolgt mittels eines Verfahrens und einer Vorrichtung für ein Kraftfahrzeug, zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug.

Das Verfahren zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug, vorzugsweise ein autonom fahrendes Kraftfahrzeug, weist dabei Bereitstellen von mindestens zwei Trajektorien auf. Dabei ist jede Trajektorie indikativ, für einen von einem Kraftfahrzeug zurückgelegten Weg innerhalb einer Umgebung des Kraftfahrzeuges. Die Trajektorie weist Wegpunkte auf. Jeder Wegpunkt der Trajektorie weist einen dezidierten Punkt des Kraftfahrzeuges entlang des Fahrweges in der Umgebung zu einem entsprechenden Zeitpunkt auf. Und die Umgebung weist vorzugsweise eine Parkumgebung auf. Ferner weist das Verfahren auf: Ermitteln korrespondierender Trajektorienabschnitte aus den Trajektorien. Ermitteln von Wegpunktschwerpunkten korrespondierender Wegpunkte von korrespondierenden Trajektorienabschnitten. Dabei weist jeder Wegpunktschwerpunkt eine Position und Orientierung innerhalb der Umgebung auf. Ermitteln von Schwerpunktclustern, basierend auf den ermittelten Wegpunktschwerpunkten. Ermitteln von Knotenpunkten aus den Schwerpunktclustern. Ermitteln weiterer Wegpunktschwerpunkte, basierend auf im Wesentlichen parallel orientierten Schwerpunktclustern. Ermitteln von Knotenpunktverbindungen, basierend auf den weiteren Wegpunktschwerpunkten und den Knotenpunkten, derart, dass ein Knotenpunkt mit seinen jeweils nächsten Knotenpunktnachbarn linear verbunden wird. Überprüfen ob Knotenpunkte existieren, bei denen es möglich ist, benachbarte Knotenpunkte über mehr als eine Knotenpunktverbindung zu erreichen. Falls solche Knotenpunkte existieren: Ermitteln von Knotenschwerpunkten derjenigen Knotenpunkte, die einander über mehr als eine Knotenpunktverbindung erreichen können. Ersetzen aller Knotenpunktverbindungen zwischen jedem betroffenen Knotenpunkt und den jeweils angebundenen nicht betroffenen Knotenpunkten, durch Knotenpunktverbindungen zwischen dem entsprechenden Knotenschwerpunkt und den nicht betroffenen angebundenen Knotenpunkten. Löschen der betroffenen Knotenpunkte. Ferner weist das Verfahren Ermitteln eines Wegenetzes der Umgebung auf, basierend auf den verbliebenen Knotenpunkten, den Knotenschwerpunkten und den Knotenpunktverbindungen.

Eine Trajektorie gemäß der vorliegenden Erfindung ist dabei eine Bahn, ein Pfad oder ein Weg, den ein Kraftfahrzeug zurücklegt. Somit kann eine Trajektorie ein Bewegungspfad eines Objektes sein, dargestellt durch die zeitliche Sequenz von Koordinaten während der Laufzeit.

Dies hat den Vorteil, dass auf eine effiziente und automatisierte Weise ein Wegenetz, insbesondere in Parkräumen, wie Parkarealen, Parkhäusern und Tiefgaragen, erstellt und aktuell gehalten werden kann.

Gemäß einem weiteren Aspekt der Erfindung ist eine Vorrichtung für ein Kraftfahrzeug vorgesehen. Die Vorrichtung zur Bestimmung eines Wegenetzes für ein Kraftfahrzeug, vorzugsweise ein autonom fahrendes Kraftfahrzeug, weist eine Schnittstelle auf, die dazu eingerichtet ist, um mit zumindest einer spezifischen Fahrzeugkomponente eines Kraftfahrzeuges Informationen zur Ansteuerung zu kommunizieren, und ein Kontrollmodul. Das Kontrollmodul ist dazu eingerichtet, um mindestens zwei Trajektorien bereitzustellen. Dabei ist jede Trajektorie indikativ, für einen von einem Kraftfahrzeug zurückgelegten Weg innerhalb einer Umgebung des Kraftfahrzeuges. Die Trajektorie weist Wegpunkte auf. Jeder Wegpunkt der Trajektorie weist einen dezidierten Punkt des Kraftfahrzeuges entlang des Fahrweges in der Umgebung zu einem entsprechenden Zeitpunkt auf. Und die Umgebung weist vorzugsweise eine Parkumgebung auf. Ferner ist das Kontrollmodul eingerichtet, um: Korrespondierende Trajektorienabschnitte aus den Trajektorien zu ermitteln; Wegpunktschwerpunkte korrespondierender Wegpunkte von korrespondierenden Trajektorienabschnitten zu ermitteln, wobei jeder Wegpunktschwerpunkt eine Position und Orientierung innerhalb der Umgebung aufweist; Schwerpunktcluster zu ermitteln, basierend auf den ermittelten Wegpunktschwerpunkten; Knotenpunkte aus den Schwerpunktclustern zu ermitteln; weitere Wegpunktschwerpunkte zu ermitteln, basierend auf im Wesentlichen parallel orientierten Schwerpunktclustern; Knotenpunktverbindungen zu ermitteln, basierend auf den weiteren Wegpunktschwerpunkten und den Knotenpunkten, derart, dass ein Knotenpunkt mit seinen jeweils nächsten Knotenpunktnachbarn linear verbunden wird; zu überprüfen, ob Knotenpunkte existieren, bei denen es möglich ist, benachbarte Knotenpunkte über mehr als eine Knotenpunktverbindung zu erreichen; und falls solche Knotenpunkte existieren: Knotenschwerpunkte derjenigen Knotenpunkte zu ermitteln, die einander über mehr als eine Knotenpunktverbindung erreichen können; Alle Knotenpunktverbindungen zwischen jedem betroffenen Knotenpunkt und den jeweils angebundenen nicht betroffenen Knotenpunkten durch Knotenpunktverbindungen zwischen dem entsprechenden Knotenschwerpunkt und den nicht betroffenen angebundenen Knotenpunkten zu ersetzen; und die betroffenen Knotenpunkte zu löschen. Ferner ist das Kontrollmodul dazu eingerichtet, um ein Wegenetz der Umgebung zu ermitteln, basierend auf den verbliebenen Knotenpunkten, den Knotenschwerpunkten und den Knotenpunktverbindungen.

Dies hat den Vorteil, dass auf eine effiziente und automatisierte Weise ein Wegenetz, insbesondere in Parkräumen, wie Parkarealen, Parkhäusern und Tiefgaragen, erstellt und aktuell gehalten werden kann.

Gemäß eines noch weiteren Aspektes der Erfindung wird ein Computerprogrammprodukt bereitgestellt, mit Programmcode zur Durchführung eines erfindungsgemäßen Verfahrens, wenn das Computerprogrammprodukt auf einer erfindungsgemäßen Recheneinheit, einer erfindungsgemäßen Vorrichtung oder eines erfindungsgemäßen Systems ausgeführt wird. Dies hat den Vorteil, dass eine Möglichkeit bereitgestellt werden kann, mit der die Kartenaktualisierung beziehungsweise Kartenerstellung und Kommunikation zwischen Kraftfahrzeug und einer Vorrichtung automatisiert durchgeführt werden kann.

Gemäß einer ersten Ausgestaltung erfolgt das Ermitteln weiterer Wegpunktschwerpunkte zusätzlich basierend auf mindestens einem Knotenpunkt mindestens eines der im Wesentlichen parallel orientierten Schwerpunktclustern.

Dies hat den Vorteil, dass auf das Wegenetz noch effizienter erstellt werden kann. Gemäß einer weiteren Ausgestaltung weist das Ermitteln von Knotenpunktverbindungen, basierend auf den weiteren Wegpunktschwerpunkten und den Knotenpunkten ein Ersetzen der Knotenpunkte, die zum Ermitteln der weiteren Wegpunktschwerpunkte herangezogen wurden, durch die entsprechenden weiteren Wegpunktschwerpunkte auf.

Dies hat den Vorteil, dass auf das Wegenetz optimierter beziehungsweise genauer erstellt werden kann.

Gemäß einer weiteren Ausgestaltung sind die Schwerpunktcluster indikativ für Streckenabschnitte eines Wegenetzes der Umgebung.

Dies hat den Vorteil, dass auf das Wegenetz noch effizienter erstellt werden kann.

Gemäß einer weiteren Ausgestaltung sind die Knotenpunkte indikativ für Startpunkte, Endpunkte und Kreuzungspunkte des Wegenetzes der Umgebung.

Dies hat den Vorteil, dass auf das Wegenetz noch effizienter erstellt werden kann.

Gemäß einer weiteren Ausgestaltung weist ein Schwerpunktcluster nur zwei Knotenpunkte auf. Dies hat den Vorteil, dass auf das Wegenetz optimierter beziehungsweise genauer erstellt werden kann.

Gemäß einer weiteren Ausgestaltung weist das Verfahren ferner Aufteilen des ermittelten Wegenetzes der Umgebung in eine erste Ebene auf, die indikativ ist, für ein Straßennetz der Umgebung, und in eine zweite Ebene, die indikativ ist, für Fahrspuren der Umgebung.

Dies hat den Vorteil, dass das erstellte Wegenetz einfacher verarbeitbar ist.

Gemäß einer weiteren Ausgestaltung weist das Verfahren ferner Bereitstellen des Wegenetzes an ein Kraftfahrzeug auf.

Dabei kann das Kraftfahrzeug sein, welches die mindestens beiden Trajektorien bereitgestellt hat. Das Kraftfahrzeug, an welches das Wegenetz bereitgestellt wird, kann jedoch auch ein weiteres Kraftfahrzeug sein.

Dies hat den Vorteil, dass das bereitgestellte Wegenetz an viele Kraftfahrzeuge, somit also breit, verteilt werden kann.

Verschiedene Aspekte der vorliegenden Offenbarung beziehen sich auf eine Vorrichtung, umfassend ein oder mehrere Prozessoren und ein oder mehrere Speichergeräte, ausgebildet zum Durchführen des zuvor vorgestellten Verfahrens.

Verschiedene Aspekte der vorliegenden Offenbarung beziehen sich auf ein Programm mit einem Programmcode zum des zuvor vorgestellten Verfahrens, wenn der Programmcode auf einem Computer, einem Prozessor, einem Kontrollmodul oder einer programmierbaren Hardwarekomponente ausgeführt wird.

Im Folgenden werden die Merkmale des Verfahrens, der entsprechenden Vorrichtung, eines entsprechenden Computerprogramms sowie des Fahrzeugs in Bezug auf das Verfahren beschrieben. Merkmale, die im Zusammenhang mit dem Verfahren beschrieben werden, können dabei ebenfalls in die entsprechende Vorrichtung, das entsprechende Computerprogramm und das entsprechende Fahrzeug übernommen werden.

Verschiedene Aspekte der vorliegenden Offenbarung beziehen sich auf ein computerimplementiertes Verfahren zum Steuern von ein oder mehreren Einstellungen eines Fahrzeugs, sowie auf eine entsprechende Vorrichtung und ein entsprechendes Computerprogramm. Dabei kann das Verfahren, die Vorrichtung und das Computerprogramm genutzt werden, um die ein oder mehreren Einstellungen anzupassen (das heißt, zu verändern), basierend auf den nachfolgenden Kriterien. Dabei sind nicht alle Fahrzeug-Einstellungen gleichsam geeignet für die das vorliegende Konzept. Insbesondere ist das vorliegende Konzept für ein oder mehrere Einstellungen geeignet, die durch die ein oder mehreren Insassen des Fahrzeugs über eine Benutzerschnittstelle (des Fahrzeugs) veränderbar sind, das heißt, Einstellungen, die von den Benutzern auch selbst geändert werden können, ohne dass hierdurch eine Änderung von Hardware oder Software des Fahrzeugs notwendig würde. Eine mögliche Beschränkung auf solche Einstellungen hat zudem den Vorteil, dass die Handlungen der Insassen, das heißt, die Veränderung der Einstellungen durch die Insassen, aufgezeichnet werden können und zum Training des Maschinenlern-Modells eingesetzt werden können. Folglich kann das Verfahren ein Aufzeichnen eines Veränderns der Einstellungen durch die Insassen, zusammen mit entsprechenden Umgebungsindikatoren, umfassen. Beispielsweise können sich die ein oder mehreren Einstellungen des Fahrzeugs sich auf Funktionen eines Innenraums des Fahrzeugs beziehen, etwa auf Komfortfunktionen des Fahrzeugs. Dies können beispielweise ein oder mehreren Einstellungen des Fahrzeugs zumindest eines von einer Klimaanlageneinstellung des Fahrzeugs, einer Sitzeinstellung des Fahrzeugs, einer Beleuchtungseinstellung des Fahrzeugs, einer Scheibenwischereinstellung des Fahrzeugs sein. Aber auch eine Fahrwerkseinstellung des Fahrzeugs kann zu den Einstellungen zählen, etwa eine Umstellung zwischen einer Komfort- und einer Sport-Fahrwerkseinstellung. Auch weitere Einstellungen sind denkbar.

Einige Beispiele werden nun ausführlicher Bezug nehmend auf die beiliegenden Figuren beschrieben. Weitere mögliche Beispiele sind jedoch nicht auf die Merkmale dieser detailliert beschriebenen Ausführungsformen beschränkt. Diese können Modifikationen der Merkmale sowie Entsprechungen und Alternativen zu den Merkmalen aufweisen. Ferner soll die Terminologie, die hierin zum Beschreiben bestimmter Beispiele verwendet wird, nicht einschränkend für weitere mögliche Beispiele sein.

Gleiche oder ähnliche Bezugszeichen beziehen sich in der gesamten Beschreibung der Figuren auf gleiche oder ähnliche Elemente beziehungsweise Merkmale, die jeweils identisch oder auch in abgewandelter Form implementiert sein können, während sie die gleiche oder eine ähnliche Funktion bereitstellen. In den Figuren können ferner die Stärken von Linien, Schichten und/oder Bereichen zur Verdeutlichung übertrieben sein.

Wenn zwei Elemente A und B unter Verwendung eines „oder“ kombiniert werden, ist dies so zu verstehen, dass alle möglichen Kombinationen offenbart sind, das heißt, nur A, nur B sowie A und B, sofern nicht im Einzelfall ausdrücklich anders definiert. Als alternative Formulierung für die gleichen Kombinationen kann „zumindest eines von A und B“ oder „A und/oder B“ verwendet werden. Das gilt Äquivalent für Kombinationen von mehr als zwei Elementen.

Wenn eine Singularform, z. B. „ein, eine“ und „der, die, das“ verwendet wird und die Verwendung nur eines einzelnen Elements weder explizit noch implizit als verpflichtend definiert ist, können weitere Beispiele auch mehrere Elemente verwenden, um die gleiche Funktion zu implementieren. Wenn eine Funktion im Folgenden als unter Verwendung mehrerer Elemente implementiert beschrieben ist, können weitere Beispiele die gleiche Funktion unter Verwendung eines einzelnen Elements oder einer einzelnen Verarbeitungsentität implementieren. Es versteht sich weiterhin, dass die Begriffe „umfasst“, „umfassend“, „aufweist“ und/oder „aufweisend“ bei deren Gebrauch das Vorhandensein der angegebenen Merkmale, Ganzzahlen, Schritte, Operationen, Prozesse, Elemente, Komponenten und/oder einer Gruppe derselben beschreiben, dabei aber nicht das Vorhandensein oder das Hinzufügen eines oder mehrerer anderer Merkmale, Ganzzahlen, Schritte, Operationen, Prozesse, Elemente, Komponenten und/einer Gruppe derselben ausschließen.

Einige Beispiele von Vorrichtungen und/oder Verfahren werden nachfolgend bezugnehmend auf die beiliegenden Figuren lediglich beispielhaft näher erläutert. Es zeigen:

Fig. 1 zeigt ein Flussdiagramm eines erfindungsgemäßen Beispiels eines Verfahrens zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug;

Fig. 2 zeigt ein Flussdiagramm eines weiteren erfindungsgemäßen Beispiels eines Verfahrens zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug; Fig. 3 zeigt ein Flussdiagramm eines weiteren erfindungsgemäßen Beispiels eines Verfahrens zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug;

Fig. 4 zeigt ein Blockdiagramm eines weiteren erfindungsgemäßen Beispiels einer Vorrichtung zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug;

Fig. 5 zeigt einen Graphen eines erfindungsgemäßen Beispiels zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug;

Fig. 6 bis 6c zeigen weitere Graphen eines erfindungsgemäßen Beispiels zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug;

Fig. 7 bis 7a zeigen weitere Graphen eines erfindungsgemäßen Beispiels zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug;

Fig. 8 bis 8a zeigen weitere Graphen eines erfindungsgemäßen Beispiels zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug; und

Fig. 9 bis 9a zeigen weitere Graphen eines erfindungsgemäßen Beispiels zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug.

Fig. 1 zeigt ein Flussdiagramm eines erfindungsgemäßen Beispiels eines Verfahrens zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug. Dabei weist das Verfahren zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug 100, vorzugsweise ein autonom fahrendes Kraftfahrzeug, Bereitstellen 10 von mindestens zwei Trajektorien 110 auf. Dabei ist jede Trajektorie 110 indikativ, für einen von einem Kraftfahrzeug 100 zurückgelegten Weg innerhalb einer Umgebung 200 des Kraftfahrzeuges 100. Die Trajektorie 110 weist Wegpunkte 111 - auch Waypoints genannt - auf.

Jeder Wegpunkt 111 der Trajektorie 110 weist einen dezidierten Punkt des Kraftfahrzeuges 100 entlang des Fahrweges in der Umgebung 200 zu einem entsprechenden Zeitpunkt auf. Und die Umgebung 200 weist vorzugsweise eine Parkumgebung auf. Das Verfahren weist ferner auf: Ermitteln 20 korrespondierender Trajektorienabschnitte 112 aus den Trajektorien 110; Ermitteln 30 von Wegpunktschwerpunkten 113 - auch WaypointCentroids genannt - korrespondierender Wegpunkte 111 von korrespondierenden Trajektorienabschnitten 112, wobei jeder Wegpunktschwerpunkt 113 eine Position und Orientierung innerhalb der Umgebung 200 aufweist; Ermitteln 40 von Schwerpunktclustern 114 - auch CentroidCluster genannt - basierend auf den ermittelten Wegpunktschwerpunkten 113; Ermitteln 50 von Knotenpunkten 115 - auch Intersectioncluster genannt - aus den Schwerpunktclustern 114; Ermitteln 60 weiterer Wegpunktschwerpunkte 116, basierend auf im Wesentlichen parallel orientierten Schwerpunktclustern 114; Ermitteln 70 von Knotenpunktverbindungen 117, basierend auf den weiteren Wegpunktschwerpunkten 116 und den Knotenpunkten 115, derart, dass ein Knotenpunkt 115 mit seinen jeweils nächsten Knotenpunktnachbarn linear verbunden wird; Überprüfen 80 ob Knotenpunkte 115 existieren, bei denen es möglich ist, benachbarte Knotenpunkte über mehr als eine Knotenpunktverbindung 117 zu erreichen; und falls solche Knotenpunkte existieren: Ermitteln 82 von Knotenschwerpunkten 118 - auch T-junctions genannt - derjenigen Knotenpunkte 115, die einander über mehr als eine Knotenpunktverbindung 117 erreichen können; Ersetzen 84 aller Knotenpunktverbindungen 117 zwischen jedem betroffenen Knotenpunkt 115 und den jeweils angebundenen nicht betroffenen Knotenpunkten 115, durch Knotenpunktverbindungen 117 zwischen dem entsprechenden Knotenschwerpunkt 118 und den nicht betroffenen angebundenen Knotenpunkten 115; und Löschen 86 der betroffenen Knotenpunkte 115.

Ferner weist das Verfahren Ermitteln 90 eines Wegenetzes 210 der Umgebung 200 auf, basierend auf den verbliebenen Knotenpunkten 115, den Knotenschwerpunkten 118 und den Knotenpunktverbindungen 117.

Fig. 2 zeigt ein Flussdiagramm eines weiteren erfindungsgemäßen Beispiels eines Verfahrens zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug. Dabei weist das in Fig. 1 gezeigte Verfahren ferner auf, dass das Ermitteln 70 von Knotenpunktverbindungen 117, basierend auf den weiteren Wegpunktschwerpunkten 116 und den Knotenpunkten 115 ein Ersetzen 72 der Knotenpunkte 115 aufweist, die zum Ermitteln 60 der weiteren Wegpunktschwerpunkte 116 herangezogen wurden, durch die entsprechenden weiteren Wegpunktschwerpunkte 116.

Fig. 3 zeigt ein Flussdiagramm eines weiteren erfindungsgemäßen Beispiels eines Verfahrens zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug. Dabei weist das in Fig. 1 und Fig. 2 gezeigte Verfahren zusätzlich auf: Aufteilen 92 des ermittelten Wegenetzes 210 der Umgebung 200 in eine erste Ebene 212, die indikativ ist, für ein Straßennetz der Umgebung 200, und in eine zweite Ebene 214, die indikativ ist, für Fahrspuren der Umgebung 200.

Fig. 4 zeigt ein Blockdiagramm eines weiteren erfindungsgemäßen Beispiels einer Vorrichtung zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug. Dabei weist die Vorrichtung 300 zur Bestimmung eines Wegenetzes 210 für ein Kraftfahrzeug 200, vorzugsweise ein autonom fahrendes Kraftfahrzeug, auf: Eine Schnittstelle 310, die dazu eingerichtet ist, um mit zumindest einer spezifischen Fahrzeugkomponente 110 eines Kraftfahrzeuges 100 Informationen zur Ansteuerung zu kommunizieren; und ein Kontrollmodul 320, das dazu eingerichtet ist, um: Mindestens zwei Trajektorien 110 bereitzustellen, wobei jede Trajektorie 110 indikativ ist, für einen von einem Kraftfahrzeug 100 zurückgelegten Weg innerhalb einer Umgebung 200 des Kraftfahrzeuges 100; die Trajektorie 110 Wegpunkte 111 aufweist; jeder Wegpunkt 111 der Trajektorie 110 einen dezidierten Punkt des Kraftfahrzeuges 100 entlang des Fahrweges in der Umgebung 200 zu einem entsprechenden Zeitpunkt aufweist; und die Umgebung 200 vorzugsweise eine Parkumgebung aufweist. Ferner ist das Kontrollmodul 320 dazu eingerichtet, um korrespondierende Trajektorienabschnitte 112 aus den Trajektorien 110 zu ermitteln; Wegpunktschwerpunkte 113 korrespondierender Wegpunkte von korrespondierenden Trajektorienabschnitten 112 zu ermitteln, wobei jeder Wegpunktschwerpunkt 113 eine Position und Orientierung innerhalb der Umgebung 200 aufweist; Schwerpunktcluster 114 zu ermitteln, basierend auf den ermittelten Wegpunktschwerpunkten 113; Knotenpunkte 115 aus den Schwerpunktclustern 114 zu ermitteln; weitere Wegpunktschwerpunkte 116 zu ermitteln, basierend auf im Wesentlichen parallel orientierten Schwerpunktclustern 114;

Knotenpunktverbindungen 117 zu ermitteln, basierend auf den weiteren Wegpunktschwerpunkten 116 und den Knotenpunkten 115, derart, dass ein Knotenpunkt 115 mit seinen jeweils nächsten Knotenpunktnachbarn linear verbunden wird; zu überprüfen, ob Knotenpunkte 115 existieren, bei denen es möglich ist, benachbarte Knotenpunkte 115 über mehr als eine Knotenpunktverbindung 117 zu erreichen; und falls solche Knotenpunkte existieren: Knotenschwerpunkte 118 derjenigen Knotenpunkte 115 zu ermitteln, die einander über mehr als eine Knotenpunktverbindung 117 erreichen können; alle Knotenpunktverbindungen 117 zwischen jedem betroffenen Knotenpunkt (115 und den jeweils angebundenen nicht betroffenen Knotenpunkten 115 durch Knotenpunktverbindungen 117 zwischen dem entsprechenden Knotenschwerpunkt 118 und den nicht betroffenen angebundenen Knotenpunkten 115 zu ersetzen; und die betroffenen Knotenpunkte 115 zu löschen. Und ferner ist das Kontrollmodul 320 dazu eingerichtet ein Wegenetz 210 der Umgebung 200 zu ermitteln, basierend auf den verbliebenen Knotenpunkten 150, den Knotenschwerpunkten 118 und den Knotenpunktverbindungen 117.

Fig. 5 zeigt einen Graphen eines erfindungsgemäßen Beispiels zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug. Das Straßennetz besteht aus mehreren Objekten, die miteinander in Beziehung stehen, und über diese Beziehungen kann ein Fahrzeug 100 einen Weg durch die Karte planen. Das Straßennetz besteht aus drei Schichten, zwei logischen Graphen und den geometrischen Informationen. Die beiden Graphen sind die Verbindungen/Verbindungsknotenpunkte (links/linkjntersections) und die Fahrspuren/Fahrspurknotenpunkte (lane/lane_intersections), wobei die Verbindungen die höhere logische Ebene darstellen. Die geometrischen Informationen werden durch die formgebenden Linien (shapepointjines) dargestellt. Die Beziehungen zwischen diesen Ebenen sind wie folgt (gemäß dem MTC-Json-Format):

- jede Verbindung ist mit 1-N Fahrspuren verbunden - jede Fahrspur ist mit genau einem Link und einer Shapepointjine verbunden

- jede shapepointjine ist mit genau einer Fahrspur verknüpft

- jede Verbindung/Spur hat genau zwei Kreuzungen, eine am Anfang und eine am Ende

- jeder Schnittpunkt ist mit 1-N Verbindungen/Spuren verbunden und kann Anfang oder Ende mehrerer Verbindungen/Spuren sein.

Diese Beziehungen müssen auch bei der Erstellung des Straßennetzes beziehungsweise des Wegenetzes 210 erzeugt werden.

Fig. 6 bis 6c zeigen weitere Graphen eines erfindungsgemäßen Beispiels zum Bestimmen eines Wegenetzes 210 für ein Kraftfahrzeug 100. Dabei werden die Graphen durch Zusammenführen und Clustern von Posen einer oder mehrerer Spuren erstellt. Die ursprünglichen Trajektorien 110 und das Ergebnis des Clustering sind in den Fig. 6 bis 7a dargestellt.

Zur Erstellung der Straßennetz-Objekte wird das Ergebnis der in Fig. 5 gezeigten Wegpunkt- und Zentroid-Clusterung verwendet. Jeder Schwerpunktcluster 114 - auch CentroidCluster genannt - besteht aus einem Pfad von Wegpunktschwerpunkten 113 - auch WaypointCentroids genannt. In der folgenden Abbildung wird jeder CentroidCluster durch eine andere Linienart dargestellt. Sie zeigen die geometrischen Informationen der zusammengeführten Trajektorien 110 und fungieren als Formpunktlinien „shapepointjines“ der Straßennetze. Die Fahrspuren stellen die shapepointjines in einem logischen Graphen dar und enthalten nur den Start- und Endpunkt jedes CentroidClusters.

In Fig. 6: Es wird eine Knotenpunktstruktur bestehend aus den Knotenpunkten 115 - auch Intersection Cluster genannt - gebildet. Um die Verknüpfungsobjekte für den logischen Graphen der ersten Ebene 212 - auch oberste Ebene genannt - zu erhalten, kann die Knotenpunktstruktur - auch IntersectionCluster-Struktur genannt - hinzugefügt werden, die auch WaypointCentroids 113 enthält. Die anfänglichen Intersectioncluster 115 sind die Start- und Endpunkte der CentroidCluster 114.

In Fig. 6a: Diese Intersectionclusters 115 werden nun erweitert, um weitere WaypointCentroids 113 zu enthalten, die nahe genug am ursprünglichen Schwerpunkt - auch Zentroid genannt - liegen und eine parallele Ausrichtung aufweisen, somit also in die gleiche oder die entgegengesetzte Richtung. Wenn sich verschiedene Intersectionclusters 115 überschneiden sollten, können sie zu einem einzigen Cluster zusammengeführt werden. Alle WaypointCentroids 113 können auch wissen, ob sie Teil eines Intersectionclusters 115 sind.

In Fig. 6b: Die Mittelpunkte dieser Intersectionclusters 115 fungieren später als Verbindungsschnittpunkte. Nun kann eine neue Struktur namens Knotenpunktverbindungen 117 - auch IntersectionClusterConnection genannt - hinzugefügt werden. Diese Objekte können Verweise auf die beteiligten CentroidClusters 114 enthalten. Sie können auch Informationen darüber enthalten, welcher WaypointCentroid 113 von welchem Cluster in der Verbindung ist, Referenzen auf zwei Intersectionclusters 115 und ein Flag, das angibt, ob die Verbindung bidirektional ist.

Um diese IntersectionClusterConnections 117 zu erzeugen, kann über alle CentroidClusters 114 iteriert werden. Jeder CentroidCluster 114 beginnt und endet mit einem Intersectioncluster 115. Wenn also über die Zentroide eines Clusters iteriert wird, wird von einem Intersectioncluster 115 zu einem anderen „gewandert“ und die IntersectionClusterConnection- Objekte 117 iterativ befüllt. Dabei werden nur die WaypointCentroide 113, die Teil eines Intersectioncluster 115 sind, verarbeitet. Dies ist in Fig. 6b durch „Kreise“ dargestellt.

Dies führt direkt zu den gewünschten Verbindungen.

In Fig 6c: Im letzten Schritt kann das Straßennetz für die Kreuzungen vereinfacht werden. In Fig. 6 ist dargestellt, dass die Knotenpunktschwerpunkte 118 - auch T-junctions genannt - drei IntersectionClusters115 aufweist, die alle miteinander verbunden sind. Dies kann derart vereinfacht werden, dass es nur einen Intersectioncluster 115 in der Mitte der Kreuzung gibt, der Verbindungen zu den verschiedenen Richtungen aufweist, die ein Fahrzeug nehmen kann. Da die T-junction 118 in Fig. 6c eine sehr einfache ist, ist in Fig. 7 ein weiteres Beispiel als Kreuzung gezeigt.

Fig. 7 bis 7a zeigen weitere Graphen eines erfindungsgemäßen Beispiels zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug.

Dargestellt ist eine Kreuzung mit vier Intersectionclusters 115, die alle miteinander verbunden sind. Wie im Beispiel der Fig. 6c sollte es nur einen Intersectioncluster 115 mit vier Verbindungen zu den verschiedenen Richtungen geben. Im Sinne der Graphentheorie bilden die Knoten und Kanten der Kreuzung eine maximale Clusterstruktur, die zu einem Knoten geschrumpft werden sollte. Leider ist das Auffinden maximaler Clusterstrukturen in einem Graphen ein NP-komplettes Problem, so dass es nicht möglich ist, die gesamte Clusterstruktur auf einmal in polynomieller Zeit zu verkleinern. Jedoch ist es möglich, relevante IntersectionClusterConnections 117 eine nach der anderen zu schrumpfen.

Somit ist herausfindbar, welche Verbindungen zu einem Intersectioncluster 115 geschrumpft werden müssen, indem über alle Verbindungen im Graphen iteriert wird. Wenn zwei von ihnen einen gemeinsamen Nachbarn haben, sind sie Teil eines Dreiecks und es kann dann jede Verbindung geschrumpft werden, die Teil eines solchen Dreiecks ist. Dabei sollte vorsichtig vorgegangen werden, wenn IntersectionClusterConnections 117 zu Intersectionclusters 115 geschrumpft beziehungsweise zusammengefasst werden. Dabei sollten die beiden zur Verbindung gehörenden Intersectioncluster 115 zusammengeführt werden. Insbesondere sollten die WaypointCentroids 113, die auf die Intersectionclusters 115 verweisen, so angepasst werden, dass sie auf das Neue verweisen (das auch Referenzen zurück auf die Centroids 114 aufweisen sollte). Da die IntersectionClusterConnection 117, die verkleinert werden soll, Teil eines oder mehrerer Dreiecke ist, gibt es auch Verbindungen, die zusammengeführt werden sollten. Um Informationsverluste zu vermeiden, sollte der neu erstellte Intersectioncluster 115, der die geschrumpfte IntersectionClusterConnection 117 repräsentiert, Referenzen auf die CentroidClusters 114 erhalten, die zuvor von der Verbindung gespeichert wurden. Auch wenn später dieser Intersectioncluster 115 mit einem anderen verschmolzen wird, wenn eine andere Verbindung geschrumpft wird, sollte darauf geachtet werden, dass diese Informationen dann noch verfügbar sind. Wenn jede Verbindung, die zu einem Dreieck gehört, geschrumpft wird sollte darauf geachtet werden, dass jede Referenz im gesamten ClusterGraph entsprechend angepasst wird, damit das gewünschte Ergebnis erhalten wird.

Das Letzte, was nun erfolgen sollte, ist die Umwandlung der Intersectionclusters 115 und IntersectionClusterConnections 117 mit den enthaltenen WaypointCentroids 113 und CentroidClusters 114 in Links, Lanes und Shapepoint-Linien, somit also in ein Wegenetz. Der erste und einfachste Teil ist die Erstellung der Verbindungen und ihrer Schnittpunkte. Dabei können die Intersectionclusters 115 direkt in Link Intersections übersetzt werden. Es kann ein Link zwischen diesen Link Intersections erstellt werden, wenn es eine IntersectionClusterConnection 117 zwischen zwei dieser Intersectionclusters 115 gibt. Für die Fahrspuren und die Shapepoint-Linien sollten die CentroidClusters 114 berücksichtigt werden, die innerhalb der IntersectionClusterConnections 117 und in den Intersectionclusters 115 gespeichert sind (da einige der Verbindungen zu Intersectionclusters 115 reduziert wurden und die entsprechenden CentroidClusters 114 darin referenziert wurden). Beachtet werden sollte, dass ein IntersectionCluster(Connection) 114 bzw. 117 nur einen Teil der WaypointCentroids 113 eines CentroidClusters 114 speichern kann.

Das heißt, ein CentroidCluster 114 kann in verschiedene Shapepoint Lines/Lanes aufgeteilt werden. Mittels der WaypointCentroids 113 eines CentroidCluster 114, auf den ein Intersectioncluster 115 oder eine Connection verweist, ist eine Lane Intersection erstellbar, aus dessen ersten und letzten WaypointCentroids 113 und der jeweiligen Lane beziehungsweise Verbindung dazwischen. Es können auch eine Shapepoint-Linie aus diesen WaypointCentroids 113 erstellt werden und Beziehungen zwischen diesen neu erstellten Lanes und Shapepoint- Linien hinzugefügt werden. Vorzugsweise wird noch die Beziehungen zwischen den Links und den Lanes erstellt.

Wenn eine erstellte Fahrspur aus den von einer IntersectionClusterConnection 117 referenzierten WaypointCentroids 113 konstruiert wurde, kann einfach eine Beziehung zu der Verbindung hinzugefügt werden, die aus demselben Objekt erstellt wurde. Wenn die Fahrspur aus den WaypointCentroids 113 erstellt wurde, die von einem Intersectioncluster 115 referenziert werden, entsteht eine Fahrspur innerhalb einer Kreuzung, die den Übergang von einem Link zu einem anderen beschreibt.

Es gibt eine Konvention, dass diese Fahrspur mit dem Link verbunden sein sollte, der in die Kreuzung führt. Aus diesem Grund kann der erste WaypointCentroid, 113 untersucht werden, der zum CentroidCluster 114 gehört und auf den der Intersectioncluster 115 verweist. Wenn dieser erste WaypointCentroid 113 auch auf eine IntersectionClusterConnection 117 verweist, kann eine Beziehung zwischen der erstellten Lane und der von dieser IntersectionClusterConnection 117 erstellten Verbindung hinzugefügt werden. Wenn der erste WaypointCentroid 113 nicht auf eine IntersectionClusterConnection 117 verweist, kann geprüft werden, ob er einen Vorgänger hat, den auf einen Verweis auf eine IntersectionClusterConnections 117 geprüft werden kann. Das erfolgt so lange, bis ein (vielleicht vorheriger) Vorgänger gefunden wurde, der auf eine IntersectionClusterConnection 117 verweist, um die Beziehung wie zuvor beschrieben herzustellen.

Fig. 8 bis 8a zeigen weitere Graphen eines erfindungsgemäßen Beispiels zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug. Die vorangegangenen Schritte führen bereits zu einem vollständig funktionalen Graphen. Es können aber noch einige Verbesserungen vorgenommen werden, bei der der Clustergraph (und die daraus generierten Links, Lanes und Shapepoint- Linien) die Realität noch besser abbildet.

Dabei können die folgenden zwei Schritte angewandt werden:

Entfernen von kurzen toten Endverbindungen Zusammenführen von (teilweise) parallelen Endverbindungen

Ferner können Anpassungen bei der Zusammenführung von Trajektorien vorgenommen werden beim Zusammenführen von Wegpunkten und Clustering zusammengefasster Wegpunkte.

Anpassungen: trace IDs nicht beachten

Nachbarschaftsdiamanten entfernen

Ein „Nachbarschaftsdiamant“ meint, dass zwei Zentroide sowohl einen gemeinsamen Vorgänger als auch einen gemeinsamen Nachfolger haben. In Fig. 8:

Der Diamant kann entfernt werden, indem die beiden Schwerpunkt - auch Zentroide genannt - zu einem zusammengeführt werden.

Nachbarschaftsdreiecke entfernen:

In Fig. 8a: Ein Zentroid z hat mit einem seiner Nachfolger n einen gemeinsamen Nachfolger m. Eine Kante sollte entfernt werden. l.d.R. hat n außer z und m weitere Vorgänger oder Nachfolger. Gibt es weitere Vorgänger, entferne Kante zwischen z und n. Gibt es weitere Nachfolger, entferne Kante zwischen n und m.

Bidirektionale Verbindungen entfernen:

Ein Zentroid hat einen anderen Zentroiden sowohl als Vorgänger als auch als Nachfolger Nutze Ausrichtungswerte, die in Zentroiden gespeichert sind und berechne deren Mittelwert. Entferne die Kantenrichtung, die der Ausrichtung entgegen zeigt.

Fig. 9 bis 9a zeigen weitere Graphen eines erfindungsgemäßen Beispiels zum Bestimmen eines Wegenetzes für ein Kraftfahrzeug. Sie zeigen weitere Ausgestaltungen, die das Verfahren noch weiter optimieren können.

In Fig. 9: Wenn IntersectionClusterConnections 117 vorhanden sind, die sehr kurz sind (z.B. < 10m) und in eine "Sackgasse" führen (oder von dort kommen), wurde sehr wahrscheinlich in einen Parkplatz gefahren. Diese Verbindungen sollte im ClusterGraph und den daraus gewonnenen Roadnet-Objekten nicht vorhanden sein. Dazu kann die Länge dieser Verbindungen berechne werdent, und wenn diese Länge unter einem bestimmten Schwellenwert liegt, wird diese Verbindung gelöscht. Dabei können redundante Intersectionclusters 115 Zurückbleiben, die keine zusätzlichen Informationen für den Graphen liefern, wie in den mittleren Darstellungen der Fig. 9 dargestellt. Daher können sie entfernt und ihre Nachbarverbindungen zusammengeführt werden. Dieses Zusammenführen der Nachbarverbindungen umfasst auch das Zusammenführen der CentroidClusters 114.

Redundanz von Intersectioncluster 115:

Ein Intersectioncluster 115 kann als redundant angesehen werden, wenn die folgenden Bedingungen erfüllt sind:

Anzahl der Nachbarverbindungen == 2 die Fahrtrichtungen der Nachbarverbindungen stimmen überein beide Verbindungen sind bidirektional ODER beide sind NICHT bidirektional und haben die gleiche Fahrtrichtung Verbindung_1_Ende == Verbindung_2_Start ODER Verbindung_2_Ende == Verbindung_1 Start In Fig 9a: Zusammenführen von (teilweise) parallelen Endverbindungen

In verschiedenen Situationen ist es möglich, dass zwei IntersectionClusterConnections 117, die mit demselben Intersectioncluster 115 verbunden sind, (zumindest teilweise) parallele CentroidClusters 114 aufweisen. Diese parallelen Teile können zu einer einzigen neuen IntersectionClusterConnections 117 mit einem neuen Intersectioncluster 115 an dem Punkt zusammengeführt werden, an dem die CentroidClusters 114 nicht mehr parallel sind. An diesem Punkt wird geprüft, ob der Abstand zwischen diesem neuen Intersectioncluster 114 und den verbleibenden End-IntersectionClustern 114 größer als ein bestimmter Schwellenwert ist (wie bei der Entfernung von kurzen toten Endverbindungen). Wenn dies nicht der Fall ist, werden die Intersectionclusters 115 nicht verbunden und die kurzen Endverbindungen werden entfernt, andernfalls werden sie dem ClusterGraph hinzugefügt.

Nachfolgende Absätze erläutern die erwähnten Objekte zur Erstellung des Wegenetzes 210 detaillierter.

Verbindungen

Eine Verbindung beschreibt einen Straßenabschnitt zwischen zwei Verbindungskreuzungen. Jede Verbindung hat einen Startpunkt und einen Endpunkt. Die Anfangs- und Endpunkte werden nicht als unabhängige Merkmale dargestellt. Sie gehören immer zu dem Verbindungsschnittpunkt am Anfang oder Ende der Verbindung. Die Richtung vom Start- zum Endpunkt ist die Vorwärtsrichtung. Eine Verbindung kann unidirektional oder bidirektional sein und beschreibt den zulässigen Verkehrsfluss auf dem Straßenabschnitt.

Verbindungsschnittpunkte

Eine Verbindungskreuzung stellt eine Straßenkreuzung dar, an der sich zwei oder mehr Straßen treffen oder kreuzen. Eine Kreuzung wird auch verwendet, um den Endpunkt einer Sackgasse zu modellieren. Zwei Straßen, die sich kreuzen, aber topologisch nicht miteinander verbunden sind, bilden keine Kreuzung. Eine Kreuzung wird durch genau einen Punkt im Straßennetz dargestellt.

Fahrspuren

Eine Fahrspur beschreibt einen Fahrspurabschnitt zwischen zwei Fahrspurkreuzungen. Jede Fahrspur hat einen Anfangs- und einen Endpunkt. Die Anfangs- und Endpunkte werden nicht als unabhängige Merkmale dargestellt. Sie gehören immer zu der Fahrspurkreuzung am Anfang oder Ende der Fahrspur. Fahrspuren sind immer unidirektional und beschreiben einen logischen Pfad vom Start- zum Endpunkt. Fahrspur-Kreuzungen

Eine Fahrspurkreuzung stellt eine Fahrspurkreuzung dar, an der sich zwei oder mehr Fahrspuren treffen oder trennen. Eine Fahrspurkreuzung wird auch verwendet, um den Endpunkt einer Sackgasse zu modellieren. Zwei Fahrspuren, die sich kreuzen, aber topologisch nicht miteinander verbunden sind, bilden keine Kreuzung. Eine Kreuzung wird durch genau einen Punkt im Fahrspurnetz dargestellt.

Formpunkt_Linien

Eine Formpunktlinie ist die geometrische Darstellung einer Fahrspur, die die üblicherweise verwendete Mittellinie der Fahrspur beschreibt. Sie wird durch eine Polylinie dargestellt. Ein Wegpunkt 111 stellt eine einzelne Position einer einzelnen Trajektorie 110 dar und ist das kleinste Informationsinkrement. Die Trajektorie 110, zu der der Wegpunkt 111 gehört, wird über die Spur-ID festgelegt. Diese Information kann optional verwendet werden. Zusätzlich zu den Poseninformationen (Position und Orientierung) enthält jeder Wegpunkt 111 1die Information, welcher andere Wegpunkt 111 sein Vorgänger und welcher sein Nachfolger in der Trajektorie 110 ist. Nachdem die WaypointCentroids 113 berechnet wurden, weiß jeder Wegpunkt 111 auch, welchem Centroid, also Schwerpunkt, er zugewiesen ist.

WaypointCentroid

Der WaypointCentroid 113 ist das Ergebnis der Gruppierung von Wegpunkten 111 verschiedener Trajektorien 110 und hat eine Pose (Position und Orientierung), die von den ihm zugewiesenen Wegpunkten 111 abhängt. Er enthält Verweise auf diese Wegpunkte 111 und die IDs ihrer Trajektorien 110. Ein Zentroid kann Teil mehrerer CentroidClusters 114 sein und somit mehrere Vorgänger- oder Nachfolger-Zentroide haben. Jeder Zentroid kann auch Informationen darüber enthalten, zu welchem Intersectioncluster 115 oder welchen IntersectionClusterConnections 117 er gehört.

CentroidCluster

Ein CentroidCluster 114 ist eine Polylinie von WaypointCentroids 113.

Intersectioncluster

Die Intersectioncluster 115 sind die Start-, Kreuzungs- und Endpunkte des Straßennetzes (linkjntersections). Jeder Intersectioncluster 115 besteht aus mindestens einem WaypointCentroid 113, kann aber insbesondere bei Kreuzungen auch mehrere Zentroide haben. Deren Position, und damit die Position ihrer Wegpunkte 113, bestimmt die Position des Intersectionclusters 115. Da der Intersectioncluster 115 jedoch Teil eines logischen Graphen ist, ist seine Position nur für die Visualisierung wichtig. Ein Intersectioncluster 115 hat mindestens eine benachbarte IntersectionClusterConnection 117, um ihn mit einem anderen Intersectioncluster 115 zu verbinden.

Zusätzlich kann ein Intersectioncluster 115 Informationen über CentroidClusters 114 und deren Zentroide aufweisen, wenn dieser Intersectioncluster 115 während der Reduktion einer IntersectionClusterConnection 117 erzeugt wurde. Die Verbindungsinformationen zu seinen CentroidClustern 114 und Zentroiden werden in den neuen Intersectioncluster 115 geschrieben.

IntersectionClusterConnection

Eine IntersectonClusterConnection 117 ist eine Verbindung zwischen zwei IntersectionClustern. 115. Sie stellt auch eine Verbindung zwischen Kreuzungen im Straßennetz dar (Link). Eine solche Verbindung kann uni- oder bidirektional sein, was durch das bidirektionale Memberflag festgelegt wird. Wenn die Verbindung unidirektional ist, zeigt sie vom ersten zum zweiten Intersectioncluster 115. Das Member clusters enthält Verweise auf alle CentroidClusters 114, die zumindest teilweise durch die Verbindung repräsentiert werden, und das Member centra ids_of_cl usters enthält Verweise auf die spezifischen WaypointCentroids 113 dieser Cluster, die durch die Verbindung repräsentiert werden.

Hinweis: Eine IntersectionClusterConnection 117 verweist oft nur auf einen Teil der WaypointCentroids 113 eines CentroidClusters 114.

ClusterGraph

Der ClusterGraph ist das Hauptobjekt, das alle relevanten Objekte zur Erstellung von Straßennetzen enthält.

Die Idee der Erfindung besteht darin, mittels der Bewegungsdaten mehrerer Fahrten Punkte zu identifizieren an welchen sich „bestimmte Posen häufen“. Zunächst wird sichergestellt, dass alle Cluster unidirektional sind. Ferner werden in den entstandenen Trajektoriencluster Kreuzungen und parallele Trajektorienabschnitte herausgesucht. Auf dieser Grundlage wird eine Graphenstruktur mit ihren Knoten und Kanten generiert, welche das logische Wegenetz darstellt. Dieses hat zwei Ebenen: die Straße und ihre Fahrspuren.

Diese Ebenen sind logisch miteinander verknüpft, dadurch kann das Routing auf die Information beider Ebenen zugreifen.

Die Aspekte und Merkmale, die im Zusammenhang mit einem bestimmten der vorherigen Beispiele beschrieben sind, können auch mit einem oder mehreren der weiteren Beispiele kombiniert werden, um ein identisches oder ähnliches Merkmal dieses weiteren Beispiels zu ersetzen oder um das Merkmal in das weitere Beispiel zusätzlich einzuführen. Beispiele können weiterhin ein (Computer-)Programm mit einem Programmcode zum Ausführen eines oder mehrerer der obigen Verfahren sein oder sich darauf beziehen, wenn das Programm auf einem Computer, einem Prozessor oder einer sonstigen programmierbaren Hardwarekomponente ausgeführt wird. Schritte, Operationen oder Prozesse von verschiedenen der oben beschriebenen Verfahren können also auch durch programmierte Computer, Prozessoren oder sonstige programmierbare Hardwarekomponenten ausgeführt werden. Beispiele können auch Programmspeichervorrichtungen, z. B. Digitaldatenspeichermedien, abdecken, die maschinen-, Prozessor- oder computerlesbar sind und maschinenausführbare, prozessorausführbare oder computerausführbare Programme und Anweisungen codieren beziehungsweise enthalten. Die Programmspeichervorrichtungen können z. B. Digitalspeicher, magnetische Speichermedien wie beispielsweise Magnetplatten und Magnetbänder, Festplattenlaufwerke oder optisch lesbare Digitaldatenspeichermedien umfassen oder sein. Weitere Beispiele können auch Computer, Prozessoren, Steuereinheiten, (feldprogrammierbare Logik-Arrays ((F)PLAs = (Field) Programmable Logic Arrays), (feldprogrammierbare Gate-Arrays ((F)PGA = (Field) Programmable Gate Arrays), Grafikprozessoren (GPU = Graphics Processor Unit), anwendungsspezifische integrierte Schaltungen (ASIC = application-specific integrated circuit), integrierte Schaltungen (IC= Integrated Circuit) oder Ein-Chip-Systeme (SoC = System-on-a-Chip) abdecken, die zum Ausführen der Schritte der oben beschriebenen Verfahren programmiert sind.

Es versteht sich ferner, dass die Offenbarung mehrerer, in der Beschreibung oder den Ansprüchen offenbarter Schritte, Prozesse, Operationen oder Funktionen nicht als zwingend in der beschriebenen Reihenfolge befindlich ausgelegt werden soll, sofern dies nicht im Einzelfall explizit angegeben oder aus technischen Gründen zwingend erforderlich ist. Daher wird durch die vorhergehende Beschreibung die Durchführung von mehreren Schritten oder Funktionen nicht auf eine bestimmte Reihenfolge begrenzt. Ferner kann bei weiteren Beispielen ein einzelner Schritt, eine einzelne Funktion, ein einzelner Prozess oder eine einzelne Operation mehrere Teilschritte, -funktionen, -prozesse oder -Operationen einschließen und/oder in dieselben aufgebrochen werden.

Wenn einige Aspekte in den vorhergehenden Abschnitten im Zusammenhang mit einer Vorrichtung oder einem System beschrieben wurden, sind diese Aspekte auch als eine Beschreibung des entsprechenden Verfahrens zu verstehen. Dabei kann beispielsweise ein Block, eine Vorrichtung oder ein funktionaler Aspekt der Vorrichtung oder des Systems einem Merkmal, etwa einem Verfahrensschritt, des entsprechenden Verfahrens entsprechen. Entsprechend dazu sind Aspekte, die im Zusammenhang mit einem Verfahren beschrieben werden, auch als eine Beschreibung eines entsprechenden Blocks, eines entsprechenden Elements, einer Eigenschaft oder eines funktionalen Merkmals einer entsprechenden Vorrichtung oder eines entsprechenden Systems zu verstehen.

Die folgenden Ansprüche werden hiermit in die detaillierte Beschreibung aufgenommen, wobei jeder Anspruch als getrenntes Beispiel für sich stehen kann. Ferner ist zu beachten, dass - obwohl ein abhängiger Anspruch sich in den Ansprüchen auf eine bestimmte Kombination mit einem oder mehreren anderen Ansprüchen bezieht - andere Beispiele auch eine Kombination des abhängigen Anspruchs mit dem Gegenstand jedes anderen abhängigen oder unabhängigen Anspruchs umfassen können. Solche Kombinationen werden hiermit explizit vorgeschlagen, sofern nicht im Einzelfall angegeben ist, dass eine bestimmte Kombination nicht beabsichtigt ist. Ferner sollen auch Merkmale eines Anspruchs für jeden anderen unabhängigen Anspruch eingeschlossen sein, selbst wenn dieser Anspruch nicht direkt als abhängig von diesem anderen unabhängigen Anspruch definiert ist.

Bezugszeichenliste

Bereitstellen mindestens zweier Trajektorien

Ermitteln korrespondierender Trajektorienabschnitte

Ermitteln von Wegpunktschwerpunkten

Ermitteln von Schwerpunktclustern

Ermitteln von Knotenpunkten

Ermitteln weiterer Wegpunktschwerpunkte

Ermitteln von Knotenpunktverbindungen

Ersetzen derjenigen Knotenpunkte, die zum Ermitteln der weiteren Wegschwerpunkte herangezogen wurden, durch die entsprechenden weiteren Wegpunktschwerpunkte

Überprüfen ob Knotenpunkte existieren, bei denen es möglich ist, benachbarte

Knotenpunkte über mehr als eine Knotenpunktverbindung zu erreichen

Ermitteln von Knotenschwerpunkten

Ersetzen von Knotenpunktverbindungen

Löschen von betroffenen Knotenpunkten

Ermitteln eines Wegenetzes der Umgebung

Aufteilen des ermittelten Wegenetzes der Umgebung

Bereitstellen des Wegenetzes an ein Kraftfahrzeug

Kraftfahrzeug

T rajektorie

Wegpunkt korrespondierende T rajektorienabschnitte

Wegpunktschwerpunkte

Schwerpunktcluster

Knotenpunkte

Weitere Wegpunktschwerpunkte

Knotenpunktverbindungen Knotenschwerpunkte Umgebung Wegenetz der Umgebung Erste Ebene Zweite Ebene