Method for map matching with guaranteed integrity

• US 8,032,299 B2
• Filed: 03/11/2009
• Issued: 10/04/2011
• Est. Priority Date: 03/11/2008
• Status: Active Grant

• Current Assignee: GMV Aerospace and Defence, S.A.
• Original Assignee: GMV Aerospace and Defence, S.A.
• Inventors: Azaola Sáenz, Miguel, Caro Ramón, José, Martínez Olagüe, Miguel Angel, Toledo López, Manuel, Fernández Hernández, Ignacio
• Primary Examiner(s): O'Connor; Gerald J.
• Assistant Examiner(s): Ng; Jonathan K
• Application Number:
  US12/401,975
• Publication Number:
  US 20090234580A1
• Time in Patent Office: 937 Days
• Field of Search: 701/118, 701/200, 701/208, 701/213, 340/988
• US Class Current: 701/208
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01S 19/20 Integrity monitoring, fault detection or fault isolation of space segment

Abstract

The present invention belongs to the field of positioning applications, particularly those requiring or benefiting from the use of geographic information and needing a high service or integrity guarantee, such as positioning by means of a satellite navigation system for users and ground vehicles circulating through a network of streets and highways for example. The invention can be used both for critical safety applications and for those entailing legal or contractual responsibilities.

Claims

1. A method for determining a road or a set of passable roads or areas traveled by a user with a minimum associated probability or integrity which comprises:

receiving from a positioning system information relating to first and second position solutions of said user in a first instant of time t_a and in a second instant t_b after the first instant t_a, respectively, as well as respective position integrity ellipses, I_a and I_b, with respective minimum associated probabilities, P_a and P_b, that the user is located in each of them in t_a and in t_b, respectively, and a position increase Δ

_ab between t_a and t_b with its position increase integrity ellipse I_ab and its associated probability P_ab;

obtaining from a geographic information system, information regarding respective passable areas corresponding to said first and second position solutions;

determining a first passable integral area S_a and a second passable integral area S_b as an intersection for each instant of time of said position integrity ellipses with said passable areas;

propagating said first passable integral area to the subsequent instant t_b by means of the position increase Δ

_ab between the first and second instants of time provided by the positioning system, taking into account the uncertainty associated to said increase determined by the position increase integrity ellipse I_ab, a propagated integral area S_ab being obtained;

eliminating from said propagated integral area S_ab the non-passable areas, a propagated passable integral area S′

_ab being obtained;

determining a final passable integral area S′

_b formed by a road or a set of passable roads in the second instant t_b, either as the smallest of said second passable integral area S_b and said propagated passable integral area S′

_ab or as the intersection of said second passable integral area S_b and of said propagated passable integral area S′

_ab; and

determining the minimum probability P′

_b that the user is located in said final passable integral area S′

_b in the second instant t_b or integrity level of S′

_b according to one of the following;

in the event that said final passable integral area S′

_b is said second passable integral area S_b, as the probability P_b associated to the integrity ellipse I_b of said second position solution, i.e. P′

_b=P_b;

in the event that said final passable integral area S′

_b is said propagated passable integral area S′

_ab, as the product of the probability P_a associated to the first passable area S_a, given by the integrity ellipse I_a of said first position solution, and the probability associated to the integrity ellipse I_ab corresponding to the relative increase of position Δ

_ab between t_a and t_b, i.e. P′

_b=P_a·

P_ab;

in the event that said final passable integral area S′

_b is determined as the intersection of the second passable integral area S_b and said propagated passable integral area S′

_ab, by means of the expression;

P′

_b≧

P_a·

P_ab+P_b−

1.

2. A method according to claim 1, which further comprises repeating the method defined in claim 1 for each position solution provided in each instant t_i, propagating the passable integral area from a previous instant t_j, determining passable roads or areas and their associated probability in several consecutive instants along a trajectory.

3. A method according to claim 1, which further carries out an additional processing or post-processing with a configurable periodicity and along a configurable arc of instants m, which comprises for each instant t_i of said arc:

propagating the passable area of instant t_i, to the immediately previous instant t<sub>i−

1</sub>, by means of the position increase between both instants, taken in the opposite direction, and its associated integrity ellipse, and intersecting with the previously passable area calculated in t<sub>i−

1</sub>, and

carrying out the previous steps on all instants of the arc, from t<sub>i−

1</sub> to t<sub>i−

2</sub>, from t<sub>i−

2</sub> to t<sub>i−

3</sub>, . . . , up to t<sub>i−

m</sub>.

4. A method according to claim 1, wherein the positioning system is a GNSS system, in which the position increase between two instants of time and its integrity are determined by means of the increase of the carrier phase measurement of the satellites between both instants.

5. A method according to claim 4, wherein the positioning system used is a GNSS system hybridized with an inertial dead reckoning system.

6. A method according to claim 4, which further comprises providing a continuous trajectory traveled by the user based on Doppler measurements of the GNSS satellites, determining the instantaneous velocity of the user and the restrictions of the dynamics thereof.

7. A method according to claim 1, wherein the positioning system is a system based on beacons and/or wireless communications, and configured to provide said information relating to position solutions, to position increases between two instants of time and information relating to integrity associated to such position solutions and position increases.

8. A method according to claim 1, which further comprises carrying out a connectivity check upon propagating between instants and obtaining the propagated passable area, ruling out that passable area within said propagated passable area which could not have been accessed taking into account temporary and connectivity restrictions between areas.

9. A method according to claim 1, wherein if the probability that the user is located in the passable area has diminished over time and is below a preestablished threshold, the method is restarted and determines the passable area and its associated probability by only considering information relating to the current instant.

10. A method according to claim 1, providing a solution in three-dimensional environments using 3D maps and areas in space defined by integrity ellipsoid and its associated probability.

11. A method according to claim 1, wherein possible passable areas are propagated by means of dividing the passable area provided by the geographic information system GIS into passable and non-passable cells.

12. A method according to claim 1, wherein possible passable areas are propagated by means of dividing the passable area provided by the geographic information system GIS into polygons demarcating the passable areas.

13. A method according to claim 1, wherein possible passable areas are propagated by means of translating segments to which a certain width is assigned, and the distance of which to other segments is evaluated in order to determine intersections and passable areas.