DE102021100939A1

DE102021100939A1 - Comparing routes

Info

Publication number: DE102021100939A1
Application number: DE102021100939.1A
Authority: DE
Inventors: Andreas HACKELOEER
Original assignee: Bayerische Motoren Werke AG
Current assignee: Bayerische Motoren Werke AG
Priority date: 2021-01-18
Filing date: 2021-01-18
Publication date: 2022-07-21

Abstract

Eine erste und eine zweite Route erstrecken sich zwischen einem gemeinsamen Startpunkt und einem gemeinsamen Zielpunkt und umfassen jeweils eine Beschreibung einer Trajektorie. Ein Verfahren zum Bestimmen einer Abweichung zwischen der ersten und der zweiten Route umfasst Schritte des Bestimmens von Routenabschnitten für beide Routen, jeweils auf der Basis der zugeordneten Beschreibung und bezüglich einer gemeinsamen Wegekarte; wobei sich jeder Routenabschnitt zwischen Knotenpunkten der Wegekarte erstreckt; des Iterierens über die Routenabschnitte der ersten Route und des Bestimmens, für jeden iterierten Routenabschnitt, eines zu ihm korrespondierenden Routenabschnitts der zweiten Route; sowie des Bestimmens von Routenabschnitten der zweiten Route, die zu keinem Routenabschnitt der ersten Route korrespondieren.

A first and a second route extend between a common starting point and a common destination and each include a description of a trajectory. A method for determining a deviation between the first and the second route comprises the steps of determining route segments for both routes, each on the basis of the associated description and in relation to a common route map; each route segment extending between nodes of the route map; iterating over the route sections of the first route and determining, for each iterated route section, a route section of the second route that corresponds to it; and determining route sections of the second route that do not correspond to any route section of the first route.

Description

Die vorliegende Erfindung betrifft das Vergleichen von Routen zwischen einem Startpunkt und einem Zielpunkt. Insbesondere betrifft die Erfindung das Vergleichen von Routen, die mittels unterschiedlicher Router bestimmt wurden.The present invention relates to comparing routes between a starting point and a destination. In particular, the invention relates to comparing routes determined using different routers.

Ein Router ist dazu eingerichtet, eine Route von einem Startpunkt S zu einem Zielpunkt Z zu bestimmen. Dabei verläuft die Route zwischen Knotenpunkten eines Wegenetzes, das auf einer Wegekarte gespeichert ist. Der bestimmten Route kann beispielsweise mittels eines Fahrzeugs gefolgt werden, um den Zielpunkt zu erreichen.A router is set up to determine a route from a starting point S to a destination Z. The route runs between nodes in a network of routes that is stored on a route map. The determined route can be followed, for example, by means of a vehicle in order to reach the destination.

Router sind von unterschiedlichen Anbietern erhältlich, beispielsweise von Google, Apple, HERE, Harman, Garmin oder anderen. Häufig weichen Routen, die mittels verschiedener Router zwischen identischen Start- und Zielpunkten bestimmt wurden, voneinander ab. Es ist davon auszugehen, dass die Router unterschiedlich arbeiten, unterschiedliche Informationen berücksichtigen oder unterschiedliche Randbedingungen voraussetzen.Routers are available from different providers, such as Google, Apple, HERE, Harman, Garmin or others. Routes determined using different routers between identical start and end points often deviate from one another. It can be assumed that the routers work differently, take into account different information or require different boundary conditions.

Um Stärken oder Schwächen eines Routers gegenüber einem anderen Router zu bestimmen, können die jeweils bestimmten Routen miteinander verglichen werden. Die Routen liegen jedoch allgemein nicht als Folge von Wegabschnitten zwischen Knotenpunkten des Wegenetzes vor, sondern es muss auf eine Sequenz von geografischen Positionen zurückgegriffen werden. Die Positionen können durch den Router selbst bereitgestellt sein oder beispielsweise an Bord eines Fahrzeugs aufgezeichnet werden, während es einer bestimmten Route folgt. Der Vergleich zweier Routen kann erschwert sein, wenn die Router ihren Bestimmungen verschiedene Wegekarten zu Grunde legen.In order to determine the strengths or weaknesses of a router compared to another router, the routes determined in each case can be compared with one another. However, the routes are generally not available as a sequence of path sections between nodes in the path network, but rather a sequence of geographic positions must be used. The positions can be provided by the router itself or recorded, for example, on board a vehicle as it follows a particular route. Comparing two routes can be difficult if the routers base their determinations on different route maps.

Eine der vorliegenden Erfindung zu Grunde liegende Aufgabe besteht in der Angabe einer verbesserten Technik zum Vergleichen zweier Routen zwischen einem gemeinsamen Startpunkt und einem gemeinsamen Zielpunkt. Die Erfindung löst die Aufgabe mittels der Gegenstände der unabhängigen Ansprüche. Unteransprüche geben bevorzugte Ausführungsformen wieder.It is an object of the present invention to provide an improved technique for comparing two routes between a common starting point and a common destination. The invention solves the problem by means of the subject matter of the independent claims. Subclaims reflect preferred embodiments.

Eine erste und eine zweite Route erstrecken sich zwischen einem gemeinsamen Startpunkt und einem gemeinsamen Zielpunkt. Beide Routen umfassen jeweils eine Beschreibung einer Trajektorie, bevorzugt in Form einer Vielzahl geographischer Positionen. Alternativ kann eine Route beispielsweise in Form einer Bezierkurve oder eines Spline beschrieben sein. Eine solche Beschreibung kann einen geringeren Speicherplatz erfordern. Auf der Basis der Beschreibung kann eine Sequenz von geografischen Positionen erstellt werden.A first and a second route extend between a common starting point and a common destination. Both routes each include a description of a trajectory, preferably in the form of a large number of geographical positions. Alternatively, a route can be described, for example, in the form of a Bezier curve or a spline. Such a description may require less storage space. Based on the description, a sequence of geographic locations can be created.

Nach einem ersten Aspekt der vorliegenden Erfindung umfasst ein Verfahren zum Bestimmen einer Abweichung zwischen der ersten und der zweiten Route Schritte des Bestimmens von Routenabschnitten für beide Routen, jeweils auf der Basis der zugeordneten Beschreibung und bezüglich einer gemeinsamen Wegekarte, wobei sich jeder Routenabschnitt zwischen Knotenpunkten der Wegekarte erstreckt; des Iterierens über die Routenabschnitte der ersten Route und des Bestimmens, für jeden iterierten Routenabschnitt, eines zu ihm korrespondierenden Routenabschnitts der zweiten Route; sowie des Bestimmens von Routenabschnitten der zweiten Route, die zu keinem Routenabschnitt der ersten Route korrespondieren.According to a first aspect of the present invention, a method for determining a deviation between the first and the second route comprises steps of determining route sections for both routes, each on the basis of the associated description and in relation to a common route map, each route section between nodes of the trail map extends; iterating over the route sections of the first route and determining, for each iterated route section, a route section of the second route that corresponds to it; and determining route sections of the second route that do not correspond to any route section of the first route.

Auf der Basis einer bestimmten Abweichung kann eine verbesserte Analyse durchgeführt werden, worin die Abweichung besteht, aus welchem Grund sie vorliegt oder welche der Routen als besser betrachtet werden kann. Die Bewertung der Routen kann bezüglich eines vorbestimmten Kriteriums erfolgen, beispielsweise der Minimierung einer Reisezeit, der Minimierung einer gefahrenen Strecke oder der Minimierung eines Energieverbrauchs auf der Route. Andere Kriterien sind ebenfalls vorstellbar; außerdem können gleichzeitig mehrere Kriterien in gleichen oder unterschiedlichen Gewichtungen angewandt werden.Based on a certain deviation, an improved analysis can be made as to what the deviation is, why it is there, or which of the routes can be considered better. The routes can be evaluated with regard to a predetermined criterion, for example minimizing travel time, minimizing a route traveled or minimizing energy consumption on the route. Other criteria are also conceivable; moreover, several criteria can be applied simultaneously with the same or different weightings.

Das Iterieren erfolgt bevorzugt entlang des Verlaufs der ersten Route. Dabei können die Routenabschnitte in ihrer Reihenfolge in der Route geprüft werden. Dazu kann vom Startpunkt zum Zielpunkt oder in umgekehrter Richtung vorgegangen werden. Für die Zwecke der vorliegenden Erfindung kann es unerheblich sein, welche Route als erste und welche als zweite bestimmt wird; die Routen können diesbezüglich auch miteinander vertauscht werden. In einer Ausführungsform wird diejenige Route als erste bestimmt, deren Länge bezüglich der Anzahl umfasster Routenabschnitte größer ist. Sollte die erste Route einen Umweg gegenüber der zweiten Route beschreiben, so kann dieser leichter bestimmt werden.The iteration preferably takes place along the course of the first route. The route sections can be checked in their order in the route. This can be done from the starting point to the destination or in the opposite direction. For the purposes of the present invention, it may not matter which route is determined first and which is determined second; the routes can also be interchanged in this respect. In one embodiment, that route is determined first, the length of which is greater in relation to the number of route sections covered. If the first route describes a detour compared to the second route, this can be determined more easily.

Ein Knotenpunkt kann den Startpunkt oder den Zielpunkt umfassen oder am Knotenpunkt können mehr als zwei Routenabschnitte angrenzen. Üblicherweise führen auf der Wegekarte mehr als ein Weg zu beziehungsweise von einem Knotenpunkt. Übliche Knotenpunkte umfassen insbesondere Kreuzungen, Kreisverkehre, Einmündungen, Auf- oder Ausfahrten. Eine Route kann durch eine Sequenz von Knotenpunkten vollständig und eindeutig beschrieben sein.A node can include the starting point or the destination, or more than two route sections can adjoin the node. Usually, more than one route leads to or from a node on the route map. Customary intersections include in particular intersections, roundabouts, junctions, driveways or exits. A route can be completely and unambiguously described by a sequence of nodes.

Die Routenabschnitte können auf der Basis eines Hidden Markov-Modells bestimmt werden. Ein entsprechendes Verfahren ist unter der Bezeichnung „Hidden Markov Map Matching“ bekannt. Das grundsätzliche Verfahren wurde von Paul Newson und John Krumm 2009 in „Hidden Markov Map Matching Through Noise and Sparseness“, Microsoft Research, Microsoft Corporation, beschrieben. Das Verfahren wird üblicherweise verwendet, um auf der Basis einer Sequenz geografischer Positionen bezüglich einer Wegekarte einen befahrenen Weg zu bestimmen. Häufig wird das Verfahren während des Fahrens angewandt, beispielsweise um eine Position bezüglich der Wegekarte anzuzeigen. Das Verfahren hat sich als effizient und robust gegenüber Kartenfehlern, Positionsfehlern und Bestimmungsfehlern erwiesen.The route sections can be determined on the basis of a hidden Markov model. A corresponding method is known as “Hidden Markov Map Matching”. The basic procedure was described by Paul Newson and John Krumm in 2009 in "Hidden Markov Map Matching Through Noise and Sparseness", Microsoft Research, Microsoft Corporation. The method is commonly used to determine a traveled route based on a sequence of geographic positions relative to a route map. The method is often used while driving, for example to display a position in relation to the route map. The method has proven to be efficient and robust against map errors, position errors and determination errors.

Zueinander korrespondierende Routenabschnitte können sich zwischen denselben Knotenpunkten erstrecken. Anders ausgedrückt haben zueinander korrespondierende Routenabschnitte paarweise gleiche Knotenpunkte, zwischen denen sie sich erstrecken. Zueinander korrespondierende Routenabschnitte sind für einen Benutzer, der sie bereist, üblicherweise nicht zu unterscheiden. Erfindungsgemäß kann die Vergleichbarkeit der Routen miteinander durch die Bestimmung der Routenabschnitte bezüglich der gemeinsamen Wegekarte verbessert hergestellt werden.Corresponding route sections can extend between the same nodes. In other words, route sections that correspond to one another have the same node points in pairs, between which they extend. Corresponding route sections are usually indistinguishable for a user who travels them. According to the invention, the comparability of the routes with one another can be improved by determining the route sections with regard to the common route map.

Zusätzlich können Routenabschnitte der ersten Route bestimmt werden, die zu keinem Routenabschnitt der zweiten Route korrespondieren. Aneinander angrenzende verbleibende Routenabschnitte können zusammengeführt werden. So kann ein Umweg, den die erste Route gegenüber der zweiten Route beschreibt, leicht bestimmt und bereitgestellt werden.In addition, route sections of the first route can be determined that do not correspond to any route section of the second route. Adjacent remaining route sections can be merged. In this way, a detour that the first route describes compared to the second route can be easily determined and provided.

Das Bestimmen zueinander korrespondierender Routenabschnitte kann mittels eines endlichen Automaten durchgeführt werden. Der endliche Automat bezeichnet ein Konzept, das mittels eines üblichen Konstrukts moderner Software realisiert sein kann. Dabei umfasst der endliche Automat eine vorbestimmte Anzahl Zustände, zwischen denen vorbestimmte Übergänge definiert sind. Aufgrund dieses einfachen Ansatzes kann eine sichere und effiziente Bestimmung einer Abweichung erfolgen.Route sections that correspond to one another can be determined using a finite state machine. The finite state machine denotes a concept that can be realized using a common construct of modern software. The finite state machine includes a predetermined number of states between which predetermined transitions are defined. Due to this simple approach, a deviation can be determined reliably and efficiently.

Der endliche Automat kann in einen ersten Zustand übergehen, wenn zu einem Routenabschnitt der ersten Route ein korrespondierender Routenabschnitt der zweiten Route bestimmt werden kann. Der Automat kann in einen zweiten Zustand übergehen, falls ein korrespondierender Routenabschnitt der zweiten Route nicht bestimmt werden kann. Der erste Zustand kennzeichnet, dass die letzten Routenabschnitte parallel sind beziehungsweise zueinander korrespondieren, während der zweite Zustand kennzeichnet, dass eine Parallelität beziehungsweise ein Korrespondieren nicht vorliegt. Sind alle Routenabschnitte der ersten Route überprüft, so kann in einen dritten Zustand übergegangen werden, der ein Endzustand ist und von dem aus in keinen anderen Zustand mehr übergegangen werden kann.The finite state machine can transition to a first state if a route section of the second route can be determined to correspond to a route section of the first route. The machine can switch to a second state if a corresponding route section of the second route cannot be determined. The first state indicates that the last route sections are parallel or correspond to one another, while the second state indicates that there is no parallelism or correspondence. If all route sections of the first route have been checked, a transition can be made to a third state, which is an end state and from which it is no longer possible to transition to any other state.

Für die Routenabschnitte der zweiten Route kann eine Hash-Tabelle bestimmt werden. Ein Routenabschnitt der zweiten Route, der zu einem vorbestimmten Routenabschnitt der ersten Route korrespondiert, kann auf der Basis der Hash-Tabelle bestimmt werden. Beispielsweise kann ein Hash bezüglich Identifikationen der Knotenpunkte bestimmt werden, die den Routenabschnitt begrenzen. Der Hash kann als Adresse in einer Liste oder Tabelle dienen. Existiert ein passender Eintrag in der Liste von Routenabschnitten der zweiten Route, so ist ein korrespondierender Routenabschnitt gefunden. In der Liste können weitere Informationen bezüglich des betreffenden Routenabschnitts abgelegt sein.A hash table can be determined for the route sections of the second route. A route section of the second route that corresponds to a predetermined route section of the first route can be determined based on the hash table. For example, a hash can be determined regarding identifications of the nodes that delimit the route segment. The hash can serve as an address in a list or table. If there is a matching entry in the list of route sections of the second route, then a corresponding route section has been found. Further information regarding the relevant route section can be stored in the list.

Die Routen können auf der Basis unterschiedlicher Informationen oder Randbedingungen bestimmt sein. So kann auf der Basis einer bestimmten Abweichung zwischen resultierenden Routen ein Einfluss der unterschiedlichen Informationen oder Randbedingungen auf die Bestimmung der Routen bestimmt werden. Eine Randbedingung kann beispielsweise ein Zeitpunkt sein, an dem eine Reise auf der Route angetreten werden oder abgeschlossen sein soll. Informationen können insbesondere aktuelle oder zeitnah bestimmte Verkehrsinformationen (real time traffic information, RTTI) umfassen. So kann beispielsweise eine der Routen unter Berücksichtigung eines Verkehrsaufkommens im Bereich der Route bestimmt sein. So können auf der Basis des Vergleichs der Routen die Informationen miteinander verglichen oder bewertet werden, die der Routenbestimmung zu Grunde liegen. In einer Variante werden Routen, die mittels unterschiedlicher Router bestimmt sind, miteinander verglichen, wobei Randbedingungen möglichst gleich gewählt sein können. In einer anderen Variante werden Routen, die mittels desselben Routers unter verschiedenen Randbedingungen bestimmt sind, miteinander verglichen.The routes can be determined on the basis of different information or boundary conditions. An influence of the different information or boundary conditions on the determination of the routes can thus be determined on the basis of a specific deviation between the resulting routes. A boundary condition can be, for example, a point in time at which a journey on the route is to be started or to be completed. Information can in particular include current traffic information or traffic information determined in a timely manner (real time traffic information, RTTI). For example, one of the routes can be determined taking into account the volume of traffic in the area of the route. Thus, on the basis of the comparison of the routes, the information on which the route determination is based can be compared with one another or evaluated. In one variant, routes that are determined using different routers are compared with one another, with boundary conditions being able to be chosen to be as similar as possible. In In another variant, routes that are determined using the same router under different boundary conditions are compared with one another.

Die erste Route kann mittels eines ersten Routers und die zweite Route mittels eines zweiten Routers bestimmt sein; wobei ein Unterschied zwischen den Routern bestimmt werden kann. Der Unterschied kann insbesondere eine Charakterisierung von Stärken oder Schwächen der Router im direkten Vergleich umfassen. Gegebenenfalls kann auch ein Unterschied zwischen jeweils verwendeten Randbedingungen oder Informationen bestimmt werden.The first route can be determined using a first router and the second route can be determined using a second router; where a difference between the routers can be determined. In particular, the difference can include a characterization of the strengths or weaknesses of the routers in a direct comparison. If appropriate, a difference between the boundary conditions or information used in each case can also be determined.

Bevorzugt wird eine Vielzahl erster und zweiter Routen miteinander verglichen. Miteinander verglichene erste und zweite Routen erstrecken sich jeweils zwischen übereinstimmenden Start- und Zielpunkten. Bevorzugt werden Randbedingungen, wie beispielsweise einen Bestimmungszeitpunkt, einen Zeitpunkt, für den eine Route bestimmt wurde, Einflüsse auf eine Reisezeit wie Wetter, Tag oder Nacht, Sommer oder Winter berücksichtigt. Auch aktuelle Informationen wie Verkehrsinformationen (RTTI) können berücksichtigt werden. Auf der Basis von Ergebnissen der Vielzahl Vergleiche kann eine Korrelation zwischen Abweichungen zwischen den Routen und Randbedingungen oder Informationen bestimmt werden, die der Bestimmung der Routen zu Grunde liegen können. Ergebnisse der Vergleiche können beispielsweise statistisch ausgewertet werden. So kann verbessert auf jeweils verwendete Router rückgeschlossen werden.A large number of first and second routes are preferably compared with one another. Compared first and second routes each extend between matching starting and ending points. Boundary conditions such as a determination time, a time for which a route was determined, influences on a travel time such as weather, day or night, summer or winter are preferably taken into account. Current information such as traffic information (RTTI) can also be taken into account. On the basis of the results of the large number of comparisons, a correlation between deviations between the routes and boundary conditions or information which can form the basis for determining the routes can be determined. Results of the comparisons can be evaluated statistically, for example. In this way, it is possible to draw better conclusions about the router used in each case.

In einer Weiterbildung der vorliegenden Erfindung wird ein Kartenfehler bestimmt, falls sich Längen der Routen um mehr als ein vorbestimmtes Maß voneinander unterscheiden. Das Maß kann eine Anzahl Routenabschnitte oder eine Differenz in der geografischen Länge der Routen beziehungsweise von ihnen umfasster Abschnitte betreffen. Sollte beispielsweise die erste Route eine längere Sequenz von Routensegmenten nicht aufweisen, die von der zweiten Route umfasst sind, so kann die zweite Route von einer Verbindung im Wegenetz ausgegangen sein, die bei der Bestimmung der ersten Route nicht zur Verfügung stand.
Der Kartenfehler kann insbesondere bezüglich einer Karte bestimmt werden, bezüglich der die jeweilige Route bestimmt ist. Eine fälschlich fehlende Verbindung kann einen Kartenfehler bei der Bestimmung der ersten Route aufzeigen. Eine fälschlich angenommene Verbindung kann einen Kartenfehler bei der Bestimmung der zweiten Route aufzeigen.In a development of the present invention, a map error is determined if the lengths of the routes differ from one another by more than a predetermined amount. The measure can relate to a number of route sections or a difference in the geographic length of the routes or sections covered by them. If, for example, the first route does not have a longer sequence of route segments that are covered by the second route, the second route can have started from a connection in the route network that was not available when the first route was determined.
In particular, the map error can be determined with respect to a map with respect to which the respective route is determined. A false missing connection can indicate a map error in determining the first route. An incorrectly assumed connection can indicate a map error when determining the second route.

Nach einem weiteren Aspekt der vorliegenden Erfindung umfasst eine Vorrichtung zur Bestimmung einer Abweichung zwischen einer ersten Route und einer zweiten Route, wobei sich die Routen zwischen einem gemeinsamen Startpunkt und einem gemeinsamen Zielpunkt erstrecken und jeweils eine Beschreibung einer Trajektorie umfassen, folgende Elemente: eine erste Schnittstelle zur Bereitstellung der ersten Route; eine zweite Schnittstelle zur Bereitstellung der zweiten Route; einen Kartenspeicher mit einer Wegekarte; und eine Verarbeitungseinrichtung zur Bestimmung von Routenabschnitten für beide Routen, jeweils auf der Basis der zugeordneten Beschreibung und bezüglich der Wegekarte, wobei sich jeder Routenabschnitt zwischen Knotenpunkten der Wegekarte erstreckt. Dabei ist die Verarbeitungseinrichtung dazu eingerichtet, über die Routenabschnitte der ersten Route zu iterieren und um für jeden iterierten Routenabschnitt einen zu ihm korrespondierenden Routenabschnitt der zweiten Route zu bestimmen; und um Routenabschnitte der zweiten Route zu bestimmen, die zu keinem Routenabschnitt der ersten Route korrespondieren.According to a further aspect of the present invention, a device for determining a deviation between a first route and a second route, the routes extending between a common starting point and a common destination and each including a description of a trajectory, comprises the following elements: a first interface to provide the first route; a second interface for providing the second route; a map memory with a route map; and processing means for determining route legs for both routes, each based on the associated description and in relation to the route map, each route leg extending between nodes of the route map. The processing device is set up to iterate over the route sections of the first route and to determine a route section of the second route that corresponds to each iterated route section; and to determine route segments of the second route that do not correspond to any route segment of the first route.

Die Verarbeitungseinrichtung kann dazu eingerichtet sein, ein hierin beschriebenes Verfahren ganz oder teilweise auszuführen. Dazu kann die Verarbeitungseinrichtung einen programmierbaren Mikrocomputer oder Mikrocontroller umfassen und das Verfahren kann in Form eines Computerprogrammprodukts mit Programmcodemitteln vorliegen. Das Computerprogrammprodukt kann auch auf einem computerlesbaren Datenträger abgespeichert sein. Merkmale oder Vorteile des Verfahrens können auf die Vorrichtung übertragen werden oder umgekehrt.The processing device can be set up to carry out a method described herein in whole or in part. For this purpose, the processing device can comprise a programmable microcomputer or microcontroller and the method can be present in the form of a computer program product with program code means. The computer program product can also be stored on a computer-readable data carrier. Features or advantages of the method can be transferred to the device or vice versa.

Die Erfindung wird nun mit Bezug auf die beigefügten Zeichnungen genauer beschrieben, in denen:

1 eine Vorrichtung zum Vergleichen von Routen;
2 beispielhafte Routen auf einem Wegenetz;
3 einen beispielhaften endlichen Automaten; und
4 ein Ablaufdiagramm eines Verfahrens

illustriert.The invention will now be described in more detail with reference to the accompanying drawings, in which:

1 a device for comparing routes;
2 exemplary routes on a road network;
3 an exemplary finite state machine; and
4 a flowchart of a method

illustrated.

1 zeigt eine Vorrichtung 100 zum Vergleichen von Routen und insbesondere zum Bestimmen einer Abweichung einer ersten Route von einer zweiten Route. Die Routen sind bevorzugt jeweils in Form einer Abfolge geografischer Positionen bestimmt. Den Positionen ist bevorzugt ein vorbestimmtes Geoid zu Grunde gelegt, üblicherweise WGS84. Es kann davon ausgegangen werden, dass die Routen jeweils entlang eines Wegs führen, beispielsweise einer Straße. Die Routen können auf beliebige Weise bestimmt sein, beispielsweise messtechnisch oder algorithmisch bezüglich eines vorbestimmten Wegenetzes. Die Routen verlaufen von einem gemeinsamen Startpunkt zu einem gemeinsamen Zielpunkt. Zur Analyse unterschiedlicher Bestimmungsweisen für die Routen sollen mittels der Vorrichtung 100 Abweichungen der Routen voneinander bestimmt werden. 1 FIG. 1 shows a device 100 for comparing routes and in particular for determining a deviation of a first route from a second route. The routes are preferably each determined in the form of a sequence of geographical positions. The positions are preferably based on a predetermined geoid, usually WGS84. It can be assumed that the routes each lead along a path, for example a road. The routes can be determined in any way, for example by measurement or algorithms with respect to a predetermined route network. The routes run from a common starting point to a common destination. In order to analyze different ways of determining the routes, deviations of the routes from one another are to be determined by means of the device 100 .

Die Vorrichtung 100 umfasst eine Verarbeitungseinrichtung 105, die mit einer ersten Schnittstelle 110 zur Bestimmung der ersten Route und einer zweiten Schnittstelle 115 zur Bestimmung der zweiten Route verbunden ist. Eine dritte Schnittstelle 120 kann zur Bereitstellung eines Bestimmungsergebnisses vorgesehen sein. Zwei oder mehr der Schnittstellen 110 - 120 können miteinander integriert ausgeführt sein.The device 100 comprises a processing device 105 which is connected to a first interface 110 for determining the first route and a second interface 115 for determining the second route. A third interface 120 can be provided for providing a determination result. Two or more of the interfaces 110-120 can be integrated with each other.

Die Vorrichtung 100 ist dazu eingerichtet, die Routen zunächst auf ein gemeinsames Wegenetz zu beziehen, das in einem Kartenspeicher 125 abgespeichert sein kann. Bezüglich einer Sequenz von geografischen Positionen kann ein Map Matching durchgeführt werden, das eine Abfolge von Routenabschnitten bestimmt, die sich jeweils entlang eines Wegs der Wegekarte erstrecken. Liegt eine der Routen bereits in Form einer Sequenz von Routenabschnitten vor, so kann überprüft werden, ob sie jeweils auf einem in der Wegekarte vermerkten Weg verlaufen. Ist dies nicht der Fall, kann eine entsprechende Anpassung durchgeführt werden, beispielsweise indem geografische Positionen entlang des Routenabschnitts bestimmt werden und anschließend ein Map Matching bezüglich dieser Positionen erfolgt.The device 100 is set up to initially relate the routes to a common route network, which can be stored in a map memory 125 . Map matching can be carried out with respect to a sequence of geographic positions, which determines a sequence of route sections, each of which extends along a path on the path map. If one of the routes is already available in the form of a sequence of route sections, it can be checked whether they each run on a route marked on the route map. If this is not the case, a corresponding adjustment can be carried out, for example by determining geographic positions along the route section and then performing map matching with regard to these positions.

Liegen beide Routen als Abfolge von Routenabschnitten bezüglich desselben Wegenetzes vor, so kann eine Abweichung zwischen der ersten und der zweiten Route bestimmt werden, indem über die Routenabschnitte der ersten Route iteriert und jeweils bestimmt wird, ob es für den iterierten Routenabschnitt der ersten Route einen korrespondierenden Routenabschnitt der zweiten Route gibt. Ist dies nicht der Fall, weichen die Routen voneinander ab.If both routes are available as a sequence of route sections relating to the same route network, a deviation between the first and second route can be determined by iterating over the route sections of the first route and determining whether there is a corresponding route section for the iterated route section of the first route Route section of the second route there. If this is not the case, the routes deviate from each other.

2 zeigt beispielhafte Routen auf einem nur ausschnittsweise dargestellten Wegenetz 200. Eine erste Route A umfasst Routenabschnitte A1, A2, A3 und A4, während eine zweite Route B Routenabschnitte B1, B2, B3 und B4 umfasst. Die Routen A und B müssen nicht dieselbe Anzahl Routenabschnitte A1-A4, B1-B4 (kurz: A1-B4) aufweisen und die Anzahl und Lage der hier verwendeten jeweils vier Routenabschnitte A1-B4 sind als beispielhaft zu betrachten. Jeder Routenabschnitt A1-A4, B1-B4 erstreckt sich zwischen zwei Knotenpunkten 205. Eine Verbindung zwischen benachbarten Knotenpunkten 205 wird auch Weg genannt. Die Routen A und B beginnen an einem Startpunkt S und enden an einem Zielpunkt D, wobei die Punkte S und D für die Zwecke der Erfindung zu den Knotenpunkten 205 gezählt werden können. 2 shows exemplary routes on a route network 200 shown only in part. A first route A includes route sections A1, A2, A3 and A4, while a second route B includes route sections B1, B2, B3 and B4. Routes A and B do not have to have the same number of route sections A1-A4, B1-B4 (short: A1-B4) and the number and location of the four route sections A1-B4 used here are to be regarded as examples. Each route section A1-A4, B1-B4 extends between two nodes 205. A connection between adjacent nodes 205 is also called a path. Routes A and B begin at a starting point S and end at a destination point D, where points S and D can be counted as nodes 205 for the purposes of the invention.

Die dargestellten Routen A und B sind auf das gemeinsame Wegenetz 200 bezogen und stützen sich auf denselben Vorrat von Knotenpunkten 205. Zwei Routenabschnitte A1-B4 korrespondieren zueinander genau dann, wenn sie sich zwischen denselben Knotenpunkten 205 erstrecken. Vorliegend korrespondieren die Routenabschnitte A1 und B1, sowie A4 und B4 miteinander. Im dargestellten, einfachen Beispiel unterscheiden sich die Routen A und B, indem Route A in einem mittleren Bereich weiter links und Route B weiter rechts verläuft. Eine Abweichung der Route A von Route B liegt vor, wenn A einen Routenabschnitt A1-A4 umfasst, für den kein korrespondierender Routenabschnitt B1-B4 zu finden ist. Vorliegend weicht Route A von Route B durch die Routenabschnitte A2 und A3 ab; und Route B weicht von Route A durch die Routenabschnitte B2 und B3 ab.The routes A and B shown are related to the common route network 200 and are based on the same set of nodes 205. Two route sections A1-B4 correspond to one another precisely when they extend between the same node 205. In the present case, the route sections A1 and B1, as well as A4 and B4, correspond to one another. In the simple example shown, routes A and B differ in that route A runs further to the left in a central area and route B runs further to the right. Route A deviates from route B if A includes a route section A1-A4 for which no corresponding route section B1-B4 can be found. In the present case, route A deviates from route B through route sections A2 and A3; and route B deviates from route A by route legs B2 and B3.

3 zeigt einen beispielhaften endlichen Automaten 300 zur Bestimmung einer Abweichung zwischen einer ersten Route A und einer zweiten Route B. Der Automat 300 umfasst einen Startzustand P, einen Endzustand T und einen Zwischenzustand N. Beispielhaft wird im Folgenden von einer Iteration vom Startpunkt S zum Zielpunkt D ausgegangen. Der Automat 300 behandelt die folgenden Datenstrukturen, die leer initialisiert, mit jeder Transition zwischen den Zuständen P, N, T übergeben und gegebenenfalls modifiziert werden:

Lp: Liste bereits erkannter Paare zueinander korrespondierender Routenabschnitte
Ln: Liste bereits erkannter nicht zueinander korrespondierender Routenabschnitte
Tp: Liste gesammelter Wege im Wegenetz 200, die zu einem Paar zueinander korrespondierender Routenabschnitte gehören
Tn: Liste gesammelter Wege im Wegenetz 200, die zu einem Paar nicht zueinander korrespondierender Routenabschnitte gehören
Ecurr: Routenabschnitt, über den gerade iteriert bzw. der gerade gelesen wird (nicht bei toEOF ( ) )

3 shows an exemplary finite automaton 300 for determining a deviation between a first route A and a second route B. The automaton 300 comprises a starting state P, an end state T and an intermediate state N. An example is given below of an iteration from the starting point S to the destination D went out. The automaton 300 handles the following data structures, which are initialized empty, passed with each transition between the states P, N, T and modified if necessary:

lp: List of previously recognized pairs of corresponding route sections
Ln: List of previously recognized non-corresponding route sections
Tp: List of collected paths in the path network 200 that belong to a pair of route sections that correspond to one another
part: List of collected paths in the path network 200 that belong to a pair of non-corresponding route sections
Ecurr: Route section that is currently being iterated over or that is currently being read (not with toEOF ( ) )

Die Liste L_p nimmt Paare einander zugeordneter Routenabschnitte A1-B4 auf, wobei ein Routenabschnitt A1-A4 von der ersten Route A und ein Routenabschnitt B1-B4 von der zweiten Route B umfasst ist. Die vollständige Transitionsfunktion des endlichen Automaten 300 sieht wie folgt aus: von Zustand Transition nach Zustand Operationen P toNonParallel () N - Erzeuge neues Paar zueinander korrespondierender Routenabschnitte aus T_p und füge es L_p hinzu - Leere T_p - Füge E_curr zu T_n hinzu P toParallel () P - Füge E_curr zu T_p hinzu P toEOF () T - Erzeuge neues Paar zueinander korrespondierender Routenabschnitte aus T_p und füge es L_p hinzu - Leere T_p N toNonParallel () N - Füge E_curr zu T_n hinzu N toParallel () P - Erzeuge neues Paar nicht zueinander korrespondierender Routenabschnitte aus T_n und füge es L_n hinzu - Leere T_n - Füge E_curr zu T_p hinzu N toEOF () T - Erzeuge neues Paar nicht zueinander korrespondierender Routenabschnitte aus T_n und füge es L_n hinzu - Leere T_n T toNonParallel () T - keine (Endzustand erreicht) T toParallel () T - keine (Endzustand erreicht) T toEOF () T - keine (Endzustand erreicht) The list L _p includes pairs of route sections A1-B4 associated with one another, with a route section A1-A4 being included in the first route A and a route section B1-B4 being included in the second route B. The complete transition function of the finite state machine 300 looks like this: of condition transit by state operations P toNonParallel() N - Create a new pair of corresponding route segments from T _p and add them to L _p - Empty T _p - Add E _curr to T _n P toParallel() P - Add E _curr to T _p P toEOF () T - Create a new pair of corresponding route segments from T _p and add them to L _p - Empty T _p N toNonParallel() N - Add E _curr to T _n N toParallel() P - Create a new pair of non-corresponding route segments from T _n and add it to L _n - Empty T _n - Add E _curr to T _p N toEOF () T - Create a new pair of non-corresponding route segments from T _n and add it to L _n - Empty T _n T toNonParallel() T - none (end state reached) T toParallel() T - none (end state reached) T toEOF () T - none (end state reached)

Eine Transition toParallel () wird ausgeführt, falls zu einem aktuell betrachteten Routenabschnitt A1-A4 der ersten Route A ein korrespondierender Routenabschnitt B1-B4 der zweiten Route B gefunden werden konnte. Konnte kein korrespondierender Abschnitt gefunden werden, so wird eine Transition toNonParallel () durchgeführt. Eine Transition toEOF () wird durchgeführt, falls kein weiterer Routenabschnitt A1-A4 der ersten Route A gelesen werden kann.A transition toParallel () is executed if a corresponding route section B1-B4 of the second route B could be found for a currently considered route section A1-A4 of the first route A. If no corresponding section could be found, a transition toNonParallel () is carried out. A transition toEOF () is carried out if no further route section A1-A4 of the first route A can be read.

Als Ergebnis erhält man die Listen L_p und L_n. Hierbei enthält L_p in der Reihenfolge ihres Auftretens in der Iteration die Paare zueinander korrespondierender Routenabschnitte A1-B4, die Wege im Wegenetz 200 repräsentieren. Bezüglich der Routen A und B von 2 wäre L_P={(A1 ,B1), (A4, B4)}. L_n enthält, ebenfalls in der Reihenfolge ihres Auftretens in der Iteration, die Routenabschnitte A1-A4 der Route A, zu denen kein korrespondierender Routenabschnitt B1-B4 existiert, als Wege im Wegenetz. Bezüglich 2 wäre L_n={A2, A3}. Die Routenabschnitte von L_n (hier: A2 und A3) können zu einem Routenabschnitt zusammengefasst werden, wenn sie aneinander angrenzen.The result is the lists L _p and L _n . In this case, L _p contains the pairs of mutually corresponding route sections A1-B4, which represent paths in the path network 200, in the order in which they occur in the iteration. Regarding routes A and B of 2 would be L _P ={(A1 ,B1), (A4, B4)}. L _n contains, likewise in the order of their occurrence in the iteration, the route sections A1-A4 of route A, for which there is no corresponding route section B1-B4, as paths in the path network. With reference to 2 would be L _n ={A2, A3}. The route sections of L _n (here: A2 and A3) can be combined into one route section if they are adjacent to each other.

L_p ist auch bezüglich Route B bereits eindeutig bestimmt. Um auch L_n bezüglich Route B zu bestimmen, kann das gleiche Verfahren erneut ausgeführt werden, wobei über die Routenabschnitte B1-B4 der Route B iteriert wird.L _p is also already uniquely determined with regard to route B. In order to also determine L _n with respect to route B, the same method can be carried out again, iterating over the route sections B1-B4 of route B.

4 zeigt ein Ablaufdiagramm eines Verfahrens 400 zum Vergleichen von Routen. In einem Schritt 405 wird die erste Route A erfasst, in einem Schritt 410 die zweite Route B. Die Routen A und B liegen allgemein als Beschreibung einer Trajektorie vor, üblicherweise als Folge von geografischen Positionen. Sollten dabei unterschiedliche Geoide vorausgesetzt sein oder eine systematische Abweichung der Positionen der einen Route gegenüber der anderen Route bekannt sein, so kann an dieser Stelle eine geeignete Anpassung erfolgen. Sollte eine der Routen in einem anderen Format beschrieben sein, beispielsweise als Spline oder Bezierkurve, so kann daraus eine entsprechende Folge von geografischen Positionen bestimmt werden. 4 FIG. 4 shows a flow diagram of a method 400 for comparing routes. The first route A is recorded in a step 405, and the second route B in a step 410. The routes A and B are generally available as a description of a trajectory, usually as a sequence of geographic positions. If different geoids are assumed or a systematic deviation of the positions of one route compared to the other route is known, a suitable adjustment can be made at this point. If one of the routes is described in a different format, for example as a spline or Bezier curve, a corresponding sequence of geographic positions can be determined from this.

In einem Schritt 415 werden für die erste Route A Knotenpunkte 205 auf einem vorbestimmten Wegenetz 200 bestimmt; und in einem Schritt 420 werden für die zweite Route B Knotenpunkte 205 auf demselben Wegenetz 200 bestimmt. Das Wegenetz 200 liegt bevorzugt in Form einer Wegekarte vor. Die Bestimmung von Knotenpunkten 205 bezüglich einer Folge geografischer Positionen wird auch Map Matching genannt. Es ist bevorzugt, dass das Map Matching auf der Basis eines Hidden Markov-Verfahrens erfolgt. Sollte eine der Routen A, B bereits in Form einer Folge von Knotenpunkten 205 vorliegen, so kann der entsprechende Schritt 415, 420 entfallen.In a step 415, nodes 205 on a predetermined route network 200 are determined for the first route A; and in a step 420, nodes 205 on the same route network 200 are determined for the second route B. The route network 200 is preferably in the form of a route map. The determination of nodes 205 with respect to a sequence of geographic positions is also called map matching. It is preferred that the map matching takes place on the basis of a hidden Markov method. If one of the routes A, B is already present in the form of a sequence of nodes 205, the corresponding step 415, 420 can be omitted.

In einem Schritt 425 kann eine Abweichung der ersten Route A von der zweiten Route B bestimmt werden. Dabei können insbesondere Routenabschnitte A1-A4 bestimmt werden, die von der ersten Route A umfasst sind und für die jeweils kein korrespondierender Routenabschnitt B1-B4 der zweiten Route B gefunden werden kann. Aufeinanderfolgende solche Routenabschnitte A1-A4 können miteinander verbunden werden.In a step 425 a deviation of the first route A from the second route B can be determined. In particular, route sections A1-A4 can be determined that are included in the first route A and for which no corresponding route section B1-B4 of the second route B can be found. Successive such route sections A1-A4 can be connected to each other.

In einem Schritt 430 können Informationen bestimmt werden, die der Bestimmung der Routen A, B zu Grunde liegen. Insbesondere können ein verwendeter Router, dem Router zur Verfügung stehende Informationen, Randbedingungen oder Annahmen bestimmt werden. Diese Informationen können zusammen mit einer bestimmten Abweichung zwischen den Routen beispielsweise in einer Tabelle oder einer Datenbank abgespeichert werden. Dazu ist bevorzugt, dass die bis hier genannten Schritte des Verfahrens 400 für eine Vielzahl Routenpaare durchgeführt werden.In a step 430, information on which the determination of the routes A, B is based can be determined. In particular, a router used, information available to the router, boundary conditions or assumptions can be determined. This information can be stored in a table or database, for example, together with a certain deviation between the routes. To this end, it is preferred that the steps of the method 400 mentioned up to this point are carried out for a large number of pairs of routes.

In einem Schritt 435 kann ein Router, der zuvor untersuchte Routen A, B bestimmt hat, charakterisiert werden. Dazu kann insbesondere eine Korrelation zwischen bestimmten Abweichungen und zugeordneten Begleitumständen bestimmt werden. Die Charakterisierung kann absolut oder bezüglich Routen eines oder mehrerer anderer Router bestimmt werden.In a step 435, a router that has determined previously examined routes A, B can be characterized. For this purpose, in particular, a correlation between specific deviations and assigned accompanying circumstances can be determined. The characterization can be determined absolutely or in terms of routes of one or more other routers.

In einem Schritt 440 kann der Router bewertet werden. Insbesondere kann bestimmt werden, unter welchen Umständen der Router gute oder schlechte Routen bereitstellt. Dabei können die Routen A, B eines Routers mit Routen eines anderen Routers verglichen werden. Alternativ können Routen A, B die unter verschiedenen Annahmen, Informationen, Einstellungen oder Randbedingungen mittels desselben Routers bestimmt wurden, miteinander verglichen werden. Für den Vergleich kann von einem vorbestimmten Qualitätsmaß ausgegangen werden, beispielsweise der Kürze einer bestimmten Route A, B oder einer möglichst geringen Reisezeit auf der Route A, B.In a step 440, the router can be evaluated. In particular, it can be determined under what circumstances the router provides good or bad routes. The routes A, B of a router can be compared with routes of another router. Alternatively, routes A, B that were determined using the same router under different assumptions, information, settings or boundary conditions can be compared with one another. A predetermined quality measure can be used as a basis for the comparison, for example the shortness of a specific route A, B or the shortest possible travel time on route A, B.

BezugszeichenlisteReference List

100100: Vorrichtungcontraption
105105: Verarbeitungseinrichtungprocessing facility
110110: erste Schnittstelle (erste Route)first interface (first route)
115115: zweite Schnittstelle (zweite Route)second interface (second route)
120120: dritte Schnittstelle (Abweichung)third interface (deviation)
125125: Kartenspeicher map storage
200200: Wegenetzroad network
205205: Knotenpunktnode
AA: erste Routefirst route
BB: zweite Routesecond route
A1, A2, A3, A4A1, A2, A3, A4: Routenabschnitte der ersten Route ARoute sections of the first route A
B1, B2, B3, B4B1, B2, B3, B4: Routenabschnitte der zweiten Route B Route sections of the second route B
300300: endlicher Automat finite automaton
400400: Verfahrenprocedure
405405: erste Route erfassencapture first route
410410: zweite Route erfassenCapture second route
415415: Map Matching für erste RouteMap matching for first route
420420: Map Matching für zweite RouteMap matching for second route
425425: Abweichung bestimmendetermine deviation
430430: Informationen / Begleitumstände bestimmenDetermine information / accompanying circumstances
435435: Router charakterisierencharacterize routers
440440: Router bewertenRate routers

Claims

Method (400) for determining a deviation between a first route (A) and a second route (B), the routes (A, B) extending between a common starting point (S) and a common destination point (Z) and one each Description of a trajectory include; the method (400) comprising the steps of: - determining (415, 420) route sections for both routes (A, B), each on the basis of the associated description and with respect to a common route map (200); - wherein each route section (A1-B4) extends between nodes (205) of the route map (200); - iterating (425) over the route sections (A1-A4) of the first route (A) and determining, for each iterated route section (A1-A4), a route section (B1-B4) of the second route (B) corresponding to it; and - Determining route sections (B1-B4) of the second route (B) that do not correspond to any route section (A1-B4) of the first route (A).

Method (400) according to claim 1 , wherein a node (205) comprises the starting point (S) or the destination (Z) or adjoins more than two route sections at the node (205).

Method (400) according to claim 1 or 2 , where the route sections (A1-B4) are determined on the basis of a Hidden Markov Model.

Method (400) according to one of the preceding claims, wherein mutually corresponding route sections (A1-B4) extend between the same node points (205).

Method (400) according to one of the preceding claims, wherein route sections (A1-A4) of the first route (A) are determined which do not correspond to any route section (B1-B4) of the second route (B).

Method (400) according to one of the preceding claims, wherein the determination of mutually corresponding route sections (A1-B4) is carried out by means of a finite state machine (300).

Method (400) according to claim 6 , wherein the machine (300) goes into a first state (P) if a route section (A1-A4) of the first route (A) has a corresponding route section (B1-B4) of the second route (B) that can be determined, and to a second state (N) if not.

Method (400) according to one of the preceding claims, wherein a hash table is determined for the route sections (B1-B4) of the second route (B); and a route section (B1-B4) of the second route (B) corresponding to a predetermined route section (A1-A4) of the first route (A) is determined based on the hash table.

Method (400) according to one of the preceding claims, wherein the routes (A, B) are determined on the basis of different information or boundary conditions.

Method (400) according to claim 9 , wherein the first route (A) is determined by a first router and the second route (B) is determined by a second router; and a difference between the routers is determined.

Method (400) according to claim 9 or 10 , wherein a plurality of first and second routes (A, B) are compared.

A method (400) according to any one of the preceding claims, wherein a map error is determined if lengths of the routes (A, B) differ from each other by more than a predetermined amount.

Device (100) for determining a deviation between a first route (A) and a second route (B), the routes (A, B) extending between a common starting point (S) and a common destination (Z) and one each Description of a trajectory include; the device comprising: - A first interface (110) for providing the first route (A); - A second interface (115) for providing the second route (B); - a map memory (125) with a route map (200); - a processing device (105) for determining route sections (A1-B4) for both routes (A, B), each on the basis of the associated description and in relation to the route map (200), each route section (A1-B4) between nodes (205) of the path map (200); - wherein the processing device (105) is set up to iterate over the route sections (A1-A4) of the first route (A) and to for each iterated route section (A1-A4) a route section (B1-B4) corresponding to it of the second determine route (B); and to determine route sections (B1-B4) of the second route (B) which do not correspond to any route section (A1-A4) of the first route (A).