Die vorliegende Erfindung betrifft ein Verfahren zur Bestimmung einer Trajektorie für ein Fahrzeug in einer Karte, umfassend die Schritte Erzeugen einer Karte mit einem Netz aus initialen Grid-Zellen mit einer vorgegebenen Zellgröße, Übertragen von einer nicht befahrbaren Fläche auf die Karte, Zuordnen der nicht befahrbaren Fläche zu wenigstens einer initialen Grid-Zelle, Zusammenfassen von einer Mehrzahl initialer Grid-Zellen zu einer übergeordneten Grid-Zelle, und Bestimmen der Trajektorie basierend auf den initialen Grid-Zellen und den übergeordneten Grid-Zellen nach einem A ^* -Verfahren.

Die vorliegende Erfindung betrifft außerdem ein Fahrzeugassistenzsystem mit einem Subsystem zur Berechnung einer Trajektorie, wobei das Subsystem ausgeführt ist, das oben angegebene Verfahren durchzuführen.

Weiter betrifft die vorliegende Erfindung ein Fahrzeug mit einem solchen

Fahrzeugassistenzsystem.

Die vorliegende Erfindung betrifft ebenfalls ein Computerprogrammprodukt zur

Durchführung des obigen Verfahrens.

Die Bestimmung einer Trajektorie in einer Karte mit einem Netz aus Grid-Zellen hat verschiedene Einsatzmöglichkeiten. Ein solches Verfahren kann verwendet werden, z.B. um einen fahrbaren und kollisionsfreien Pfad vom aktuellen Standort A zu einer Position B zu finden. Insbesondere kann das Verfahren verwendet werden um z.B. den detaillierten Pfad zu einer schon aufgezeichneten Trajektorie zu finden, sowie um bei einem Pfad mit einem Hindernis einen Pfad um das Hindernis auf der aufgezeichneten Trajektorie herum zu finden. Eine weitere Anwendung ist beispielsweise das

Schrittweise verfolgen von Navigations-Wegpunkten.

Zur Berechnung einer Fahrtrajektorie gibt es prinzipiell verschiedene bekannte

Verfahren. So ist beispielsweise eine explizite Berechnung der Trajektorie bekannt. Dieses Verfahren basiert ist ein deterministischen Verfahren, das auf Formeln basiert. Nachteilig daran ist, dass dieses Verfahren nicht für alle Situationen möglich ist, da es sich um ein explizites Verfahren handelt. Auch sind lokale Verfahren bekannt, beispielsweise basierend auf einem Gradientenabstieg, Potentialfeldern, oder ähnlichen. Nachteilig hieran ist, dass ein gefundener Pfad stark davon abhängt, mit welchem Pfad das Optimierungsverfahren beginnt. Solche Verfahren z.B. denkbar nachdem bereits ein Pfad gefunden wurde. Auch sind sampling-basierte Suchverfahren bekannt. An diesen Verfahren ist nachteilig, dass eine Einbeziehung von Fahrzeugeigenschaften schwierig ist. Wird ein Pfad gefunden, so ist dieser abhängig von den gesetzten Zufallspunkten.

Darüber hinaus ist eine Pfadsuche unter Einbeziehung von Fahrbarkeitsbedingungen basierend auf einer Gridkarte mit Grid-Zellen bekannt. Ein Solches Verfahren ist beispielsweise als A ^* -Algorithmus bekannt. Es werden hierbei Pfade gefunden, die vom Fahrzeug gefahren werden können, wobei der Pfad aus Geraden und Kreisen besteht. Bei diesem Verfahren wird üblicherweise eine einheitliche Zellengröße verwendet. Das Verfahren ist prinzipiell zuverlässig, benötigt aber viel mehr Speicher als andere

Verfahren. Außerdem ist die Berechnung aufwendig, was sich in hohen Laufzeiten des Verfahrens äußert.

In diesem Zusammenhang ist aus der DE 10 2013 209 764 A1 ein Verfahren zum Unterstützen eines Fahrers eines Kraftfahrzeugs bekannt. Das Verfahren umfasst die Schritte Gewinnen von Informationen über eine Umgebung des Kraftfahrzeugs,

Vergleichen der gewonnenen Informationen mit gespeicherten Umgebungsdaten, wobei die zu speichernde Umgebung in einzelnen Zellen, insbesondere in GridTiles, gespeichert sind, Erkennen, ob für die gewonnenen Informationen eine gespeicherte Zelle als Startzelle für ein gespeichertes automatisches Fahrmanöver in den

gespeicherten Umgebungsdaten vorhanden ist, und Ausgeben einer Mitteilung an den Fahrer, dass ein automatisches Fahrmanöver durchgeführt werden kann, falls der Fahrer dies wünscht.

Ausgehend von dem oben genannten Stand der Technik liegt der Erfindung somit die Aufgabe zugrunde, ein Verfahren der oben genannten Art, ein

Fahrzeugassistenzsystem mit einem Subsystem zur Berechnung einer Trajektorie, wobei das Subsystem ausgeführt ist, das oben angegebene Verfahren durchzuführen, ein Fahrzeug mit einem solchen Fahrzeugassistenzsystem, und ein

Computerprogrammprodukt zur Durchführung des obigen Verfahrens bereitzustellen, die eine verbesserte Bestimmung einer Trajektorie für ein Fahrzeug in einer Karte ermöglichen. Insbesondere soll eine Bestimmung der Trajektorie mit wenigen

Ressourcen, beispielsweise Rechenleistung und Speicherbedarf, erfolgen und die Bestimmung der Trajektorie in einer kurzen Zeit ermöglicht werden.

Die Lösung der Aufgabe erfolgt erfindungsgemäß durch die Merkmale der

unabhängigen Ansprüche. Vorteilhafte Ausgestaltungen der Erfindung sind in den Unteransprüchen angegeben.

Erfindungsgemäß ist somit ein Verfahren zur Bestimmung einer Trajektorie für ein Fahrzeug in einer Karte angegeben, umfassend die Schritte Erzeugen einer Karte mit einem Netz aus initialen Grid-Zellen mit einer vorgegebenen Zellgröße, Übertragen von einer nicht befahrbaren Fläche auf die Karte, Zuordnen der nicht befahrbaren Fläche zu wenigstens einer initialen Grid-Zelle, Zusammenfassen von einer Mehrzahl initialer Grid- Zellen zu einer übergeordneten Grid-Zelle, und Bestimmen der Trajektorie basierend auf den initialen Grid-Zellen und den übergeordneten Grid-Zellen nach einem A ^* -Verfahren, wobei das Zusammenfassen von einer Mehrzahl initialer Grid-Zellen zu einer übergeordneten Grid-Zelle abhängig von einer Entfernung von der nicht befahrbaren Fläche durchgeführt wird, und das Bestimmen der Trajektorie basierend auf den initialen Grid-Zellen und den übergeordneten Grid-Zellen nach einem A ^* -Verfahren das

Bestimmen der Trajektorie der jeweils größten Grid-Zellen umfasst.

Erfindungsgemäß ist außerdem ein Fahrzeugassistenzsystem mit einem Subsystem zur Berechnung einer Trajektorie angegeben, wobei das Subsystem ausgeführt ist, das oben angegebene Verfahren durchzuführen.

Weiter ist erfindungsgemäß ein Fahrzeug mit einem solchen Fahrzeugassistenzsystem angegeben.

Ebenfalls ist erfindungsgemäß ein Computerprogrammprodukt zur Durchführung des obigen Verfahrens angegeben.

Grundidee der vorliegenden Erfindung ist es also, ausgehend von einem A ^* -Verfahren zur Bestimmung einer Trajektorie das üblicherweise verwendete Netz aus initialen Grid- Zellen mit einer vorgegebenen Zellgröße durch ein Netz mit Grid-Zellen mit wenigstens zwei verschiedenen Auflösungen zu ersetzen, wobei die Grid-Zellen in kritischen Bereichen d.h. in der Nähe von nicht befahrbaren Flächen, eine feinere Auflösung haben als Grid-Zellen, die weiter von nicht befahrbaren Flächen entfernt sind. Dadurch kann die Bestimmung der Trajektorie besonders effizient durchgeführt werden, da aufgrund der teilweise größeren Grid-Zellen weniger Speicherplatz erforderlich ist. Da außerdem insgesamt weniger Grid-Zellen zu betrachten sind, um die Trajektorie zu bestimmen, wird außerdem das Bestimmen der Trajektorie beschleunigt.

Grundlage ist ein an sich bekanntes Verfahren, das als A ^* -Verfahren bekannt ist, und das Bestimmen der Trajektorie für eine Karte mit einem Netz mit einer einheitlichen, vorgegebenen Zellgröße ermöglicht. Der A ^* -Algorithmus gehört zur Klasse der informierten Suchalgorithmen. Er dient der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Die Knoten sind hier die Grid-Zellen im Sinne der vorliegenden Erfindung. Der A ^* -Algorithmus gilt als Verallgemeinerung und Erweiterung des Dijkstra-Algorithmus. Im Gegensatz zu uninformierten Suchalgorithmen verwendet der A ^* -Algorithmus eine Schätzfunktion (Heuristik), um zielgerichtet zu suchen und damit die Laufzeit zu verringern. Der Algorithmus ist vollständig und optimal. Das heißt, dass immer eine optimale Lösung gefunden wird, falls eine existiert.

Der A ^* -Algorithmus untersucht immer die Knoten zuerst, die wahrscheinlich schnell zum Ziel führen. Um den vielversprechendsten Knoten zu ermitteln, wird allen bekannten Knoten x jeweils ein Wert f (x) = g (x) + h (x) zugeordnet, der angibt, wie lang der Pfad vom Start zum Ziel unter Verwendung des betrachteten Knotens im günstigsten Fall ist. Der Knoten mit dem niedrigsten Wert wird als nächster untersucht. Für einen Knoten x bezeichnet g (x) die bisherigen Kosten vom Startknoten aus, um x zu erreichen, h (x) bezeichnet die geschätzten Kosten von x bis zum Zielknoten. Die verwendete Heuristik sollte die Kosten nicht überschätzen, da dies zu einem potenziellen Verlust der Optimalität bzgl. der Kostenfunktion führen kann. Für das Beispiel der Wegsuche ist die Luftlinie eine geeignete Schätzung. Andere Schätzungen wie Luftlinie zusammen mit einem Faktor für eine Winkelabweichung können auch sinnvoll sein, resultieren je nach Faktor in Verlust der Optimalität bzgl. der Kostenfunktion.

Die Knoten oder Grid-Zellen werden während der Suche in drei verschiedene Klassen eingeteilt. Unbekannte Knoten wurden während der Suche noch nicht gefunden. Zu ihnen ist noch kein Weg bekannt. Jeder Knoten (außer dem Startknoten) ist zu Beginn des Algorithmus unbekannt. Zu bekannten Knoten ist ein Weg bekannt.

Alle bekannten Knoten werden zusammen mit ihrem f-Wert in einer Open List gespeichert. Aus dieser Liste wird immer der vielversprechendste Knoten ausgewählt und untersucht. Die Implementierung der Open List hat großen Einfluss auf die Laufzeit und wird oft beispielsweise als einfache Prioritätswarteschlange realisiert. Zu Beginn ist nur der Startknoten bekannt.

Zu abschließend untersuchten Knoten ist der kürzeste Weg bekannt. Die abschließend untersuchten Knoten werden in einer Closed List gespeichert, damit sie nicht mehrfach untersucht werden. Um effizient entscheiden zu können, ob sich ein Element auf der Closed List befindet, wird diese oft als Menge implementiert. Alternativ kann die Closed List mittels eines boolean-Wertes an der jeweiligen Position implementiert sein, und ein Zugriff auf die Grid-Zelle wird mittels Hashtabeile durchgeführt. Die Closed List ist zu Beginn leer.

Außerdem enthält jeder bekannte oder abschließend besuchte Knoten einen Zeiger auf seinen Vorgängerknoten. Mit Hilfe dieser Zeiger kann der Pfad bis zum Startknoten rückverfolgt werden. Wird ein Knoten x abschließend untersucht, so werden seine Nachfolgeknoten in die Open List eingefügt und x in die Closed List aufgenommen. Die Vorgängerzeiger der Nachfolgeknoten werden auf x gesetzt. Ist ein Nachfolgeknoten bereits auf der Closed List, so wird er nicht erneut in die Open List eingefügt und auch sein Vorgängerzeiger nicht geändert. Ist ein Nachfolgeknoten bereits auf der Open List, so wird der Knoten nur aktualisiert (f-Wert und Vorgängerzeiger), wenn der neue Weg dorthin kürzer ist als der bisherige.

Der Algorithmus terminiert, sobald der Zielknoten abschließend untersucht wird. Der gefundene Weg wird dann mit Hilfe der Vorgängerzeiger rekonstruiert und ausgegeben. Falls die Open List leer ist, gibt es keine Knoten mehr, die untersucht werden könnten. In diesem Fall terminiert der Algorithmus, da es keine Lösung gibt.

Der A ^* -Algorithmus findet allgemein einen optimalen Pfad zwischen zwei Knoten in einem Graphen. Optimal kann dabei am kürzesten, am schnellsten oder auch am einfachsten bedeuten, je nach Art der Gewichtungsfunktion, die den Kanten ihre Länge zuordnet. Theoretisch kann der Algorithmus alle Probleme lösen, die durch einen Graphen dargestellt werden können und bei denen eine Schätzung über die Restkosten bis zum Ziel gemacht werden kann.

Erfindungsgemäß werden dabei die jeweils größten verfügbaren Grid-Zellen verwendet, um die Trajektorie zu bestimmen. Dadurch kann der Algorithmus besonders effizient arbeiten. Im Bereich von nicht befahrbaren Flächen kann jedoch eine hohe Auflösung bereitgestellt werden, was insbesondere dann erforderlich ist, wenn das Fahrzeug zwischen Hindernissen hindurchgeführt werden muss.

Die Trajektorie ist eine Sequenz mit Fahrzeugzuständen mit einer gewünschten Auflösung. Die Trajektorie ist vorzugsweise sicher, kurz, glatt und berücksichtigt kinematische Beschränkungen des Fahrzeugs, beispielsweise einen Wendekreis oder ähnliches.

Die nicht befahrbare Fläche wird typischerweise markiert, indem Grid-Zellen um ein physikalisches Hindernis herum insgesamt der nicht befahrbaren Fläche zugeordnet und als solche markiert werden. Dazu kann beispielsweise ein Kreis um jedes gegenständliche Hindernis gelegt, woraus sich jeweils eine nicht mit einem

Hinterachszentrum befahrbare Fläche ergibt. Darauf basierend kann ein optimaler und kollisionsfreier Pfad bestimmt werden. Die nicht befahrbare Fläche ist also die Summe aller Grid-Zellen, die nicht befahrbar sind. Einzelne nicht befahrbare Flächen werden beispielsweise durch einen Kreisscheibenbereich auf der Karte definiert, der ein gegenständliches Hindernis, beispielsweise einen Baum, eine Wand, ein Fahrzeug, eine Person oder andere umgibt. Die nicht befahrbare Fläche kann somit einzelne, nicht verbundene Bereiche auf der Karte umfassen, die auch individuell jeweils als nicht befahrbare Fläche bezeichnet werden können.

Vorzugsweise kann dabei ein Fahrzeug ebenfalls durch einen Mehrzahl Kreise modelliert werden. Das Fahrzeug kann ein prinzipiell beliebiges Fahrzeug sein, von einem Fahrrad über ein Motorrad, PKW mit verschiedenartigen Antrieben, bis hin zu Lastkraftwagen oder Kettenfahrzeugen. Abhängig von der Art des Fahrzeugs müssen in dem Verfahren unterschiedliche Parameter verwendet geben, die sich beispielsweise aus dessen Abmessungen und seiner Beweglichkeit ergeben. Vorzugsweise wird die übergeordnete Grid-Zelle auf einer übergeordneten Ebene der Karte gespeichert wird. Zeiger auf die Ebene könne verwendet werden, um einen einfachen Zugriff zu realisieren.

Das Fahrzeugassistenzsystem ist beispielsweise ein Navigationssystem, ein autonomes Einparksystem, oder ähnliches, das eine Trajektorie für das Fahrzeug bereitstellen muss.

In einem Fahrzeug kann das Subsystem auch zentral bereitgestellt werden, so dass es von verschiedenen Fahrzeugassistenzsystemen genutzt werden kann. Insbesondere wenn die verschiedenen Fahrzeugassistenzsysteme nicht gleichzeitig verwendet werden, wie es üblicherweise bei dem genannten Navigationssystem sowie dem autonomen Einparksystem gegeben ist, kann das Subsystem die Funktion bereitstellen, ohne dass es zu Konflikten bei der Nutzung des Subsystems kommt.

In vorteilhafter Ausgestaltung der Erfindung das erfolgt das Zusammenfassen von einer Mehrzahl initialer Grid-Zellen zu einer übergeordneten Grid-Zelle nicht in wenigstens einem Bereich von besonderem Interesse. Ein solcher Bereich kann beispielsweise ein Bereich um einen Startpunkt oder einen Zielpunkt der Trajektorie sein. Prinzipiell können hier verschiedene weitere Kriterien definiert werden, um einen Bereich von dem Zusammenfassen der initialen Grid-Zellen zu übergeordneten Grid-Zellen

auszuschließen.

In vorteilhafter Ausgestaltung der Erfindung umfasst der Schritt des Zusammenfassens von einer Mehrzahl initialer Grid-Zellen zu einer übergeordneten Grid-Zelle abhängig von einer Entfernung von der nicht befahrbaren Fläche das Zusammenfassen von einer Mehrzahl initialer Grid-Zellen in einem vorgegebenen Raster entsprechend einer Zellgröße. Somit kann einfach auf die Grid-Zellen zugegriffen werden, indem

sichergestellt ist, dass die Grid-Zellen jeweils in einem ihrer Ebene entsprechenden Raster angeordnet sind. Eine Überschneidung von Grid-Zellen in ihrer Ebene wird verhindert.

In vorteilhafter Ausgestaltung der Erfindung umfasst das Zusammenfassen von einer Mehrzahl initialer Grid-Zellen zu einer übergeordneten Grid-Zelle das Ermitteln einer potenziellen übergeordneten Grid-Zelle und das Überprüfen der potentiellen

übergeordneten Grid-Zelle auf eine Kollision mit der nicht befahrbaren Fläche. Es erfolgt somit eine Überprüfung der gesamten Karte basierend zunächst auf den initialen Grid- Zellen.

In vorteilhafter Ausgestaltung der Erfindung umfasst das Zusammenfassen von einer Mehrzahl initialer Grid-Zellen zu einer übergeordneten Grid-Zelle das Ermitteln einer potenziellen übergeordneten Grid-Zelle und das Überprüfen der initialen Grid-Zellen der potentiellen übergeordneten Grid-Zelle auf eine Kollision mit der nicht befahrbaren Fläche, wobei die Mehrzahl initialer Grid-Zellen zu der übergeordneten Grid-Zelle zusammengefasst werden, wenn keine der Mehrzahl der initialen Grid-Zellen mit der nicht befahrbaren Fläche kollidiert. Hierbei handelt es sich also um eine elementare Überprüfung, ob eine Zusammenfassung der initialen Grid-Zellen zu der

übergeordneten Grid-Zelle möglich ist.

In vorteilhafter Ausgestaltung der Erfindung umfasst das Zusammenfassen von einer Mehrzahl initialer Grid-Zellen zu einer übergeordneten Grid-Zelle das Ermitteln einer potenziellen übergeordneten Grid-Zelle und das Überprüfen von zu der potentiellen übergeordneten Grid-Zelle benachbarten initialen Grid-Zellen auf eine Kollision mit der nicht befahrbaren Fläche umfasst, wobei die Mehrzahl initialer Grid-Zellen zu der übergeordneten Grid-Zelle zusammengefasst werden, wenn keine der benachbarten initialen Grid-Zellen mit der nicht befahrbaren Fläche kollidiert. Dadurch wird

sichergestellt, dass zusammengefasste initiale Grid-Zellen nicht unmittelbar an nicht befahrbare Flächen angrenzen können, wodurch die Trajektorie zuverlässig und ohne eine Gefahr von Kollisionen mit der nicht befahrbaren Fläche und damit einer Kollision mit einem Hindernis bestimmt werden kann. Benachbarte initiale Grid-Zellen können unmittelbar benachbarte Grid-Zellen sein, die sich beispielsweise entlang der Seiten der potentiellen übergeordneten Grid-Zelle erstrecken. Allerdings hat es sich als besonders vorteilhaft erwiesen, lediglich die initialen Grid-Zellen am den Ecken der potentiellen übergeordneten Grid-Zelle zu überprüfen. Aufgrund der Erzeugung der nicht

befahrbaren Fläche um die jeweiligen Hindernisse herum wird dadurch mit einer hinreichenden Sicherheit Sichergestellt, dass sich im Bereich der potentiellen übergeordneten Grid-Zelle keine nicht befahrbare Fläche befindet. Die benachbarten initialen Grid-Zellen können zusätzlich zu anderen Grid-Zellen oder alleine auf eine Kollision überprüft werden. In vorteilhafter Ausgestaltung der Erfindung umfasst der Schritt des Zusammenfassens von einer Mehrzahl initialer Grid-Zellen zu einer übergeordneten Grid-Zelle abhängig von einer Entfernung von der nicht befahrbaren Fläche das Zusammenfassen von einer Mehrzahl initialer Grid-Zellen zu übergeordneten Grid-Zellen mit einer ersten Zellgröße und das iterative Zusammenfassen von übergeordneten Grid-Zellen mit einer ersten Zellgröße zu weiter übergeordneten Grid-Zellen mit einer weiter vergrößerten Zellgröße. Das iterative Durchführen des Verfahrens ermöglicht es somit, ausgehend von einer gewünschten detaillierten Karte die Grid-Zellen in verschiedenen Ebenen

zusammenzufassen, so dass sowohl in der Nähe von nicht befahrbaren Flächen eine Kollision zuverlässig verhindert werden kann, wie auch eine effiziente Bestimmung der Trajektorie in Bereichen um die nicht befahrbaren Flächen ermöglicht wird. Abhängig von verschiedenen Randbedingungen zur Bestimmung der Trajektorie können dabei unterschiedlich viele Ebenen für das Zusammenfassen der Grid-Zellen gewählt werden. Für viele Anwendungen hat es sich als vorteilhaft erwiesen, vier verschieden große Grid-Zellen zu verwenden. Durch das iterative Durchführen des Verfahrens wird implizit bei zunehmender Entfernung von der nicht befahrbaren Fläche eine jeweils größere Zellgröße ermöglicht.

In vorteilhafter Ausgestaltung der Erfindung umfasst der das Zusammenfassen von einer Mehrzahl übergeordneter Grid-Zellen mit einer ersten Zellgröße zu einer weiter übergeordneten Grid-Zelle mit einer weiter vergrößerten Zellgröße das Ermitteln einer potenziellen weiter übergeordneten Grid-Zelle und das Überprüfen der potentiellen weiter übergeordneten Grid-Zelle, ob sie ausschließlich übergeordnete Grid-Zellen der ersten Zellgröße aufweist. Wenn somit weiter übergeordnete Grid-Zellen gebildet werden sollen, wird überprüft die potentiell weiter übergeordnete Grid-Zelle

ausschließlich Grid-Zellen der ersten Zellgröße umfasst. Nur in einem solchen Bereich kann eine weiter übergeordnete Grid-Zelle gebildet werden.

In vorteilhafter Ausgestaltung der Erfindung umfasst das Zusammenfassen von einer Mehrzahl übergeordneter Grid-Zellen mit einer ersten Zellgröße zu einer weiter übergeordneten Grid-Zelle mit einer weiter vergrößerten Zellgröße das Ermitteln einer potentiellen weiter übergeordneten Grid-Zelle und das Überprüfen der potentiellen weiter übergeordneten Grid-Zelle, ob benachbarte Grid-Zellen übergeordneten Grid- Zellen mit der ersten Zellgröße sind, wobei die Mehrzahl übergeordneter Grid-Zellen mit der ersten Zellgröße zu der weiter übergeordneten Grid-Zelle mit der weiter

vergrößerten Zellgröße zusammengefasst werden, wenn die benachbarten Grid-Zellen übergeordneten Grid-Zellen mit der ersten Zellgröße sind. In Analogie zu der vorherigen Überprüfung der initialen Grid-Zellen erfolgt auch hier eine Überprüfung benachbarter Grid-Zellen, ob sie jeweils zu einer einheitlichen Eben gehören und damit die gleiche Zellgröße aufweisen. Die Zellgröße ist jeweils die gleiche Zellgröße, wie die

übergeordneten Grid-Zellen, die weiter zusammengefasst werden sollen. Es wird sichergestellt, dass potentiell weiter zusammengefasste Grid-Zellen immer an Grid- Zellen angrenzen, wie sie in der potentiell weiter zusammengefassten Grid-Zelle enthalten sind. Benachbarte übergeordnete Grid-Zellen können unmittelbar benachbarte übergeordnete Grid-Zellen sein, die sich beispielsweise entlang der Seiten der potentiellen weiter übergeordneten Grid-Zelle erstrecken. Allerdings hat es sich als besonders vorteilhaft erwiesen, lediglich die übergeordneten Grid-Zellen der ersten Zellgröße am den Ecken der potentiellen weiter übergeordneten Grid-Zelle zu überprüfen. Die benachbarten übergeordneten Grid-Zellen können zusätzlich zu anderen übergeordneten Grid-Zellen oder alleine auf ihre Größe überprüft werden.

In vorteilhafter Ausgestaltung der Erfindung umfasst der Schritt des Zusammenfassens von einer Mehrzahl initialer Grid-Zellen zu einer übergeordneten Grid-Zelle mit ersten Zellgröße und das iterative Zusammenfassen von übergeordneten Grid-Zellen mit einer ersten Zellgröße zu weiter übergeordneten Grid-Zellen mit einer weiter vergrößerten Zellgröße jeweils das Zusammenfassen von einer gleichen Anzahl Grid-Zellen in allen Koordinaten-Richtungen zu der jeweils übergeordneten Grid-Zelle umfasst. Bei einer flächigen, zweidimensionalen Karte werden somit übergeordnete Grid-Zellen derart gebildet, dass sie vier, neun, sechzehn, oder entsprechend mehr untergeordnete Grid- Zellen in einer quadratischen Anordnung umfassen. Vorzugsweise umfassen übergeordnete Grid-Zellen jeweils vier untergeordnete Grid-Zellen.

In vorteilhafter Ausgestaltung der Erfindung umfasst der Schritt des Bestimmens der Trajektorie basierend auf den initialen Grid-Zellen und den übergeordneten Grid-Zellen nach einem A ^* - Verfahren das Bestimmen der Trajektorie basierend nach einem Hybrid A ^* -Verfahren umfasst. Hybrid A ^* betrifft eine Modifikation des konventionellen A ^* Algorithmus, bei dem ein kontinuierlicher Zustand jeder Grid-Zelle gespeichert wird und einen Score des zugeordneten kontinuierlichen Zustands angibt. Im Gegensatz zum konventionellen A ^* -Algorithmus wird also jeder Grid-Zelle ein kontinuierlicher Status des Fahrzeugs zugeordnet. Bei der Bestimmung wird dann einer ersten Grid-Zelle ein Status zugeordnet. Wenn eine Grid-Zelle von der Open-List genommen wird, werden verschiedene Lenkaktionen durchgeführt, um neue Children basierend auf einem resultierenden kinematischen Modell des Fahrzeugs zu erzeugen. Die Lenkaktionen sind beispielsweise geradeaus, maximal rechts und maximal links. Basierend auf neuen Zustände der Children werden treffende Grid-Zellen ermittelt. Wenn ein Knoten mit derselben Grid-Zelle und einem ähnlichen Winkel bereits in der Open-List ist und die neuen Kosten des Knotens niedriges als die bisherigen Kosten sind, wird der kontinuierliche Zustand des Knotens geändert und der Knoten in der Open-List neu priorisiert. Beispielsweise kann eine Winkeldiskretion der exakten Positionen mit 16 bzw. 32 Winkelbereichen zu je 1 1 .25°bzw. 22.5°ver wendet werden. Dabei werden die jeweils größten Grid-Zellen betrachtet, um darin eine Position zu speichern.

In vorteilhafter Ausgestaltung der Erfindung umfasst der Schritt des Bestimmens der Trajektorie basierend auf den initialen Grid-Zellen und den übergeordneten Grid-Zellen nach einem A ^* - Verfahren das Bestimmen einer einzelnen, besten Position für jede Grid- Zelle. Sollte eine bessere Position zur Verfügung stehen wird die bessere Position die bisherige Position überschreiben. Doppelte Einträge zu einer Grid-Zelle werden vermieden.

In vorteilhafter Ausgestaltung der Erfindung umfasst der Schritt des Bestimmens einer einzelnen, besten Position für jede Grid-Zelle das Bestimmen einer Winkelposition. Mit der zusätzlichen Winkelposition kann die Effizienz bei der Bestimmung der Trajektorie verbessert werden. Es kann eine Fokussierung auf leicht erreichbare Grid-Zellen erfolgen, wobei leicht erreichbare Grid-Zellen jeweils abhängig von der aktuellen Winkelposition unterschiedlich sein können. Insbesondere bei Fahrzeugen, die eine eingeschränkte Beweglichkeit aufweisen, kann somit eine zuverlässige Bestimmung einer möglichen Trajektorie erfolgen. Eine eingeschränkte Beweglichkeit kann sich beispielsweise aus einem maximal möglichen Lenkwinkel und/oder einer Fahrzeuglänge ergeben.

In vorteilhafter Ausgestaltung der Erfindung umfasst der Schritt des Bestimmens der Trajektorie basierend auf den initialen Grid-Zellen und den übergeordneten Grid-Zellen nach einem A ^* - Verfahren das Verwenden einer Hash-Tabelle zum Zugriff auf für eine Grid-Zelle gespeicherten Daten umfasst. Die Hash-Tabelle, im deutschen auch als Streuwerttabelle bezeichnet, betrifft eine spezielle Indexstruktur. Als Indexstruktur werden Hashtabeilen verwendet, um Datenelemente in einer großen Datenmenge aufzufinden. Anders als alternative Index-Datenstrukturen zeichnen sich Hashtabeilen durch einen üblicherweise konstanten Zeitaufwand bei Einfüge- bzw. Entfernen- Operationen aus. Beim Einsatz einer Hashtabeile zur Suche in Datenmengen spricht man auch von einem Hashverfahren oder Streuspeicherverfahren.

In vorteilhafter Ausgestaltung der Erfindung umfasst der Schritt des Verwendens einer Hash-Tabelle zum Zugriff auf für die Grid-Zellen gespeicherten Daten das

deterministische Bestimmen einer Position auf der Karte basierend auf einer Position einer Grid-Zelle und einem Zeiger zu der Position innerhalb der Grid-Zelle. Für die Speicherung der Information, auf welcher Ebene sich eine Grid-Zelle befindet, werden nur ca. 1 ,33 Bit benötigt. Demgegenüber werden bei einer üblichen Adressierung mit einem Pointer typischerweise jeweils 32 Bit benötigt. Es ergibt sich eine deutliche Reduzierung des benötigten Speichers für das Verfahren. Für eine beispielhafte Suche auf ca. 25x25 Metern mit 10cm Auflösung, d.h. eine Grid-Zelle hat eine Kantenlänge von 10 cm, kann der Speicherbedarf für die Speicherung von Daten auf der Karte von traditionell typischen ca. 4MB auf lediglich etwa 15kB reduziert werden.

Nachfolgend wird die Erfindung unter Bezugnahme auf die anliegende Zeichnung anhand bevorzugter Ausführungsformen näher erläutert.

Es zeigt

Fig. 1 eine schematische Ansicht eines Schritts zum Zusammenfassen einer

Mehrzahl initialer Grid-Zellen gemäß einer ersten Ausführungsform,

Fig. 2 eine Ansicht einer Karte mit Grid-Zellen unterschiedlicher Größe gemäß der ersten Ausführungsform,

Fig. 3 eine schematische Darstellung eines Verfahrens zur Bestimmung einer

Trajektorie ausgehend von der Karte mit Grid-Zellen unterschiedlicher Größe aus Fig. 2 gemäß der ersten Ausführungsform,

Fig. 4 eine schematische Darstellung eines Vergleichs zweier Pfadsuchen, wobei eine Pfadsuche mit durchgehend hoher Auflösung basierend ausschließlich auf den initialen Grid-Zellen durchgeführt wurde, und die andere Pfadsuche mit Grid-Zellen unterschiedlicher Größe durchgeführt wurde, und

Fig. 5 ein Ablaufdiagramm eines Verfahrens zur Bestimmung einer Trajektorie für ein Fahrzeug in einer Karte gemäß einer ersten, bevorzugten

Ausführungsform.

Die Figur 5 zeigt ein Ablaufdiagramm eines Verfahrens zur Bestimmung einer

Trajektorie für ein Fahrzeug 10 in einer Karte 12 gemäß einer ersten, bevorzugten Ausführungsform. Das Verfahren wird nachstehend unter zusätzlichem Bezug auf die Figuren 1 bis 4 im Detail erläutert.

Das Verfahren beginnt mit einem Schritt S100, der das Erzeugen einer Karte 12 mit einem Netz aus initialen Grid-Zellen 14 mit einer vorgegebenen Zellgröße betrifft. Die Karte 12 umfasst also eine Vielzahl initialer Grid-Zellen 14 mit einer einheitlichen Größe.

In einem anschließenden Schritt S1 10 werden ermittelte nicht befahrbare Flächen 16 auf die Karte 12 übertragen.

Basierend auf Schritt S1 10 werden in einem anschließenden Schritt S120 die nicht befahrbaren Flächen 16 den initialen Grid-Zellen 14 zugeordnet.

Die nicht befahrbare Fläche 16 wird dabei markiert, indem jede entsprechende initiale Grid-Zelle 14 insgesamt der nicht befahrbaren Fläche 16 zugeordnet und als solche markiert wird. Die nicht befahrbare Fläche 16 ist in diesem Ausführungsbeispiel die Summe aller initialer Grid-Zellen 14, die nicht befahrbar sind. In diesem

Ausführungsbeispiel bilden alle initialen Grid-Zellen 14, die nicht mit dem Zentrum einer Hinterachse des Fahrzeugs 10 befahrbar sind, die nicht befahrbare Fläche 16. Die nicht befahrbare Fläche 16 kann somit einzelne, nicht verbundene Bereiche auf der Karte 12 umfassen, die auch individuell jeweils als nicht befahrbare Fläche 16 bezeichnet werden können.

In Schritt S130 erfolgt das Zusammenfassen von einer Mehrzahl initialer Grid-Zellen 14 zu einer übergeordneten Grid-Zelle 18. Das Zusammenfassen der initialen Grid-Zellen 14 erfolgt dabei abhängig von einer Entfernung von nicht befahrbaren Flächen 16. Dazu werden zunächst basierend den initialen Grid-Zellen 14 potenzielle übergeordnete Grid- Zellen 18 ermittelt. Dazu werden die vorhandenen initialen Grid-Zellen 14 ermittelt und es werden jeweils 4 initiale Grid-Zellen 14 mit einer Ausrichtung von zwei initialen Grid- Zellen 14 in jeder Achsenrichtung der Karte 12 zusammengefasst. Die potenziellen übergeordneten Grid-Zellen 18 sind dabei in einem vorgegebenen Raster entsprechend einer ersten Zellgröße angeordnet.

Die initialen Grid-Zellen 14 der potentiellen übergeordneten Grid-Zelle 18 sowie benachbarte initiale Grid-Zellen 14 werden dann auf eine Kollision mit der nicht befahrbaren Fläche 16 überprüft. Details sind beispielsweise in Fig. 1 dargestellt. Dort ist in der Mitte eine potentiell übergeordnete Grid-Zelle 18 dargestellt. Die unmittelbar angrenzenden initialen Grid-Zellen 14 an den Ecken der potentiell übergeordneten Grid- Zelle 18 werden wie auch die initialen Grid-Zellen 14 der potentiell übergeordnete Grid- Zelle 18 auf eine Kollision mit der nicht befahrbaren Fläche 16 überprüft. Es wird also überprüft, ob die initialen Grid-Zellen 14 in den Ecken der potenziellen weiter übergeordneten Grid-Zelle 18, die in Fig. 1 mit einem Kreuz dargestellt sind, mit der nicht befahrbaren Fläche 16 kollidieren. Wenn keine der überprüften initialen Grid-Zellen 14 mit der nicht befahrbaren Fläche 16 kollidiert, werden die entsprechenden initialen Grid-Zellen 14 zu der übergeordneten Grid-Zelle 18 zusammengefasst.

Das Verfahren wird gemäß dem ersten Ausführungsbeispiel iterativ durchgeführt. Wie oben beschrieben werden somit übergeordnete Grid-Zellen 18 mit der ersten Zellgröße zu weiter übergeordneten Grid-Zellen 18 mit einer weiter vergrößerten Zellgröße zusammengefasst, und so weiter. Dazu wird jeweils zunächst eine potenziell weiter übergeordnete Grid-Zelle 18 ermittelt, basierend auf den übergeordneten Grid-Zellen 18 der ersten Zellgröße. Anschließend wird die potentiell weiter übergeordneten Grid-Zelle 18 dahingehend überprüft, ob benachbarte Grid-Zellen 14, 18 übergeordneten Grid- Zellen 18 mit der ersten Zellgröße sind. Die Zellgröße ist jeweils die gleiche Zellgröße, wie die der übergeordneten Grid-Zellen 18, die weiter zusammengefasst werden sollen. Vorliegend werden Grid-Zellen 14, 18 an den Ecken der potentiellen weiter

übergeordneten Grid-Zelle 18 überprüft, ob ihre Zellgröße der Zellgröße der in der potentiell weiter übergeordneten Grid-Zelle 18 enthaltenen übergeordneten Grid-Zellen 18 entspricht. Wenn dies der Fall ist, werden die übergeordneten Grid-Zellen 18 zu der weiter übergeordneten Grid-Zelle 18 zusammengefasst. In den iterativen Schritten des Verfahrens werden dabei jeweils eine gleichen Anzahl Grid-Zellen 14, 18 in allen Koordinaten-Richtungen wie zuvor beschrieben zu der jeweils übergeordneten Grid-Zelle 18 zusammengefasst.

Vorliegend wird das Verfahren durchgeführt, um vier verschieden große übergeordnete Grid-Zellen 14, 18 zu bestimmen, wie sich in Fig. 2 ersehen lässt. Die übergeordneten Grid-Zellen 18 werden jeweils auf einer entsprechenden übergeordneten Ebene der Karte 12 gespeichert. Der Zugriff auf die entsprechende übergeordnete Grid-Zelle 18 wird durch einen Zeiger auf die Ebene realisiert.

Anschließend wird in Schritt S140 die Trajektorie 20 basierend auf den initialen Grid- Zellen 14 und den verschieden großen übergeordneten Grid-Zellen 18 nach einem hybrid A ^* -Verfahren bestimmt.

Gemäß dem hybrid A ^* - Verfahren wird die Trajektorie 20 für die Karte 12 basierend auf den Grid-Zellen 14, 18 bestimmt. Der A ^* -Algorithmus verwendet dabei eine

Schätzfunktion (Heuristik), um zielgerichtet zu suchen und damit die Laufzeit zu verringern.

Der Algorithmus untersucht immer die Knoten bzw. Grid-Zellen 14, 18 zuerst, die wahrscheinlich schnell zum Ziel führen. Um die vielversprechendsten Grid-Zellen 14, 18 zu ermitteln, wird allen bekannten Grid-Zellen 14, 18 x jeweils ein Wert f (x) = g (x) + h (x) zugeordnet, der angibt, wie lang ein Pfad 30 vom Start zum Ziel unter Verwendung des betrachteten Knotens im günstigsten Fall ist. Start 26 und Ziel 28 sind

beispielsweise in Fig. 4 für das Fahrzeug 10 dargestellt. Die Grid-Zelle 14, 18 mit dem niedrigsten Wert wird als nächste untersucht. Für eine Grid-Zelle 14, 18 x bezeichnet g (x) die bisherigen Kosten vom Startknoten aus, um x zu erreichen, h (x) bezeichnet die geschätzten Kosten von x bis zum Ziel 28. Erfindungsgemäß werden dabei die jeweils größten verfügbaren Grid-Zellen 14, 18 verwendet, um die Trajektorie 20 zu bestimmen.

Die verwendete Heuristik sollte die Kosten nicht überschätzen, da dies zu einem potenziellen Verlust der Optimalität bzgl. der Kostenfunktion führen kann. Für das Beispiel der Wegsuche ist die Luftlinie eine geeignete Schätzung. Andere Schätzungen wie Luftlinie zusammen mit einem Faktor für eine Winkelabweichung können auch sinnvoll sein, resultieren je nach Faktor in Verlust der Optimalität bzgl. der

Kostenfunktion.

Die Grid-Zellen 14, 18 werden während der Suche in drei verschiedene Klassen eingeteilt.

Unbekannte Grid-Zellen 14, 18 wurden während der Suche noch nicht gefunden. Zu ihnen ist noch kein Weg bekannt. Jede Grid-Zelle 14, 18 ist zu Beginn des Algorithmus unbekannt, wobei eine als Start 26 ausgewählt wird. Zusätzlich wird bei dem hybriden A ^* -Algorithmus ein kontinuierlicher Zustand jeder Grid-Zelle 14, 18 gespeichert und ein Score gibt den zugeordneten kontinuierlichen Zustand an. So wird der ersten Grid-Zelle 14, 18 ein Status zugeordnet.

Zu bekannten Grid-Zellen 14, 18 ist ein Weg bekannt. Alle bekannten Grid-Zellen 14, 18 werden zusammen mit ihrem f-Wert in einer Open List 22 gespeichert. Aus dieser Open List 22 wird immer die vielversprechendste Grid-Zelle 14, 18 ausgewählt und untersucht. Die Implementierung der Open List 22 ist hier als einfache Prioritätswarteschlange realisiert. Zu Beginn ist nur die Grid-Zelle 14, 18 am Start 26 bekannt. Wenn eine Grid- Zelle 14, 18 von der Open-List 22 genommen wird, werden ausgehend von einer ermittelten Position in der Grid-Zelle 14, 18 und einer Winkelposition des Fahrzeugs 10 verschiedene Lenkaktionen durchgeführt, um neue Children basierend auf einem resultierenden kinematischen Modell des Fahrzeugs 10 zu erzeugen. Die Position wird durch einen Zeiger 24 angegeben. Die Lenkaktionen sind beispielsweise geradeaus, maximal rechts und maximal links. Basierend auf neuen Zuständen der Children werden treffende Grid-Zellen 14, 18 ermittelt. Wenn eine Grid-Zelle 14, 18 bereits in der Open- List 22 ist und die neuen Kosten der Grid-Zelle 14, 18 niedriger als die bisherigen Kosten sind, wird der kontinuierliche Zustand der Grid-Zelle 14, 18 geändert und der Knoten in der Open-List neu priorisiert. Dabei wird ggf. der Zeiger 24 auf die Position aktualisiert. Es wird somit eine einzelne, beste Position für jede Grid-Zelle 14, 18 bestimmt. Sollte eine bessere Position zur Verfügung stehen, so wird die bisherige Position durch eine bessere Position überschreiben.

Zu abschließend untersuchten Grid-Zellen 14, 18 ist der kürzeste Weg bekannt. Die abschließend untersuchten Grid-Zellen 14, 18 werden in einer Closed List gespeichert, damit sie nicht mehrfach untersucht werden. Die Closed List ist mittels eines boolean- Wertes an der jeweiligen Position implementiert. Ein Zugriff auf die Grid-Zelle 14, 18 wird mittels Hashtabeile durchgeführt.

Außerdem enthält jede bekannte oder abschließend besuchte Grid-Zelle 14, 18 einen Zeiger auf ihre Vorgängerzelle zur Rückverfolgung der Trajektorie 20. Wird eine Grid- Zelle 14, 18 x abschließend untersucht, so werden ihre nachfolgenden Grid-Zellen 14, 18 in die Open List 22 eingefügt und die Grid-Zelle 14, 18 x in die Closed List aufgenommen. Die Vorgängerzeiger der nachfolgenden Grid-Zellen 14, 18 werden auf x gesetzt. Ist eine nachfolgende Grid-Zelle 14, 18 bereits auf der Closed List, so wird sie nicht erneut in die Open List 22 eingefügt. Ihre Position ist dann nirgends gespeichert. . Ist eine nachfolgende Grid-Zelle 14, 18 bereits auf der Open List 22, so werden ihr f- Wert, ihr g-Wert, die kontinuierliche Position und der Vorgängerzeiger aktualisiert, wenn der neue Weg dorthin kürzer ist als der bisherige.

Der Algorithmus terminiert, sobald die Grid-Zelle 14, 18 am Ziel 28 abschließend untersucht wird. Der gefundene Weg wird dann mit Hilfe der Vorgängerzeiger rekonstruiert und ausgegeben. Falls die Open List 22 leer ist ohne dass das Ziel 28 abschließend untersucht wurde, terminiert der Algorithmus, da es keine Lösung gibt.

In dem Verfahren wird eine Hash-Tabelle zum Zugriff auf die Grid-Zellen 14, 18 verwendet. Dabei werden Positionen auf der Karte 12 basierend auf einer Position einer Grid-Zelle 14, 18 und dem Zeiger 24 zu der Position innerhalb der Grid-Zelle 14, 18 deterministisch bestimmt.

Das Ergebnis der Bestimmung der Trajektorie 20 des obigen Verfahrens wird in Fig. 4 in dem unteren Diagramm dargestellt. Im Vergleich dazu ist zusätzlich in Fig. 4 das Ergebnis der Pfadsuche mit Grid-Zellen 14, 18 mit einer einheitlichen Größe dargestellt. Die gefundenen Trajektorien 20 sind hier vergleichbar, wobei die vorliegende Erfindung durch die übergeordneten Grid-Zellen 18 weniger verschiedene Pfade 30 betrachten muss, wodurch das Verfahren schneller ist und weniger Arbeitsspeicher benötigt. Bezugszeichenliste

Fahrzeug 10

Karte 12 initiale Grid-Zelle 14 nicht befahrbare Fläche 16 übergeordnete Grid-Zelle 18

Trajektorie 20

Open List 22

Zeiger 24

Start 26

Ziel 28

Pfad 30