Toll object detection in a GNSS system using particle filter

• US 9,886,849 B2
• Filed: 06/01/2015
• Issued: 02/06/2018
• Est. Priority Date: 06/03/2014
• Status: Active Grant

• Current Assignee: Q-Free ASA
• Original Assignee: Q-Free ASA
• Inventors: Lykkja, Ola Martin, Storvik, Geir Olve, Gjevestad, Jon Glenn, Lland, Anders
• Primary Examiner(s): Cheung, Calvin
• Application Number:
  US14/726,654
• Publication Number:
  US 20150348409A1
• Time in Patent Office: 981 Days
• CPC Class Codes: G01S 19/14 specially adapted for specific applications
• CPC Class Codes: G01S 19/393 Trajectory determination or predictive tracking, e.g. Kalman filtering
• CPC Class Codes: G01S 19/42 Determining position
• CPC Class Codes: G07B 15/063 using wireless information transmission between the vehicle and a fixed station identification of vehicles G08G
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]

Abstract

A particle filter, also known as Sequential Monte Carlo Method, used to estimate vehicle position based on GNSS pseudo range measurements and other sensors. The particle filter creates an ensemble of particles and road user charging (road tolling) can be performed on each particle. The resulting distribution of assessed vehicle passages is analyzed to assess if the event actually took place or not. The use of particle filter overcomes limitations occurring while employing traditional Kalman filter based methods.

Claims

1. A method for assessing passages by a vehicle through a tolling object utilizing a global navigation satellite system (GNSS) comprising an on-board unit (OBU) in every vehicle to be surveyed by the system, said OBU receiving signals from satellites to consistently and frequently estimate position coordinates for the vehicles, comprising the steps of:

(A) obtaining an initial vehicle position including a degree of uncertainty (50),

(B) using computer hardware and software to assign (51) a predetermined number of particles for each vehicle, in a meaning understood by the Sequential Monte Carlo mathematical method, comprising a process model, a measurement model and a probability distribution,

(C) using computer hardware and software to assign to each particle;

(i) a common initial probability, and

(ii) an initial state comprising at least three dimensional spatial position,

(D) using computer hardware and software to define epochs in time within each of which the following procedure is conducted;

(i) in a prediction step (52), using said process model to predict with uncertainty the state of each particle in the next epoch, generally represented as x_t=φ

_t(x_t-1)+η

_t, wherein x_t is a state vector, φ

_t(x_t-1) is a function used to predict the state x_t in one epoch from information of the state in the previous epoch, and η

_t is a process noise term, the predictions of all particles within each epoch thereby representing the probability distribution of the state vector x_t given all previous measurements z_t,

(ii) in an updating step (53), using computer hardware and software to update the probability of the particles according to how well each particle'"'"'s state from the prediction step agrees with GNSS pseudo range measurements, according to the equation z_t=h_t(x_t)+ε

_t, wherein z_t is a measurement vector, h_t(x_t) is a possibly time-varying function of the state, and ε

_t is measurement noise, thereby updating the probability distribution,

(iii) using computer hardware and software to assess passage or non-passage (54) by mathematically comparing the spatial definition of the tolling objects in question with the updated particle information from the prediction step (52) while applying a defined confidence level,

(iv) recursively repeating steps (D)(i) through (D)(iii) at a predetermined rate.

2. The method of claim 1, comprising the step of storing any assessment of passage concluded for a predetermined duration.

3. The method of claim 2, wherein the probability of passage of a tolling object selected from the group consisting of a Virtual Gantry (VG), a zone, and a segment is calculated individually for each associated particle, and the probability for the vehicle actually passing the VG, the zone or the segment from the ratio of particles having passed through the VG, the zone or the segment, when the ratio is above a defined confidence limit.

4. The method of claim 2, wherein the assessment of passage or non-passage is derived from the probability distribution π

(x_t|z<sub>0;

t</sub>) by first calculating the expected state E(x_t|z<sub>0;

t</sub>) or median(x_t|z<sub>0;

t</sub>) and variance VAR(x_t|z<sub>0;

t</sub>), and then using VG, zone, and segment detection methods on that state if the variance is below a defined error margin.

5. The method of claim 1, comprising combining use of GNSS pseudo range measurements with use of at least one sensor selected among accelerometers, gyroscopes, vehicle wheel speed sensors, barometric pressure sensors, and magnetic compasses, thereby improving accuracy.

6. The method of claim 5, wherein the probability of passage of a tolling object selected from the group consisting of a Virtual Gantry (VG), a zone, and a segment is calculated individually for each associated particle, and the probability for the vehicle actually passing the VG, the zone or the segment from the ratio of particles having passed through the VG, the zone or the segment, when the ratio is above a defined confidence limit.

7. The method of claim 5, wherein the assessment of passage or non-passage is derived from the probability distribution π

(x_t|z<sub>0;

t</sub>) by first calculating the expected state E(x_t|z<sub>0;

t</sub>) or median(x_t|z<sub>0;

t</sub>) and variance VAR(x_t|z<sub>0;

t</sub>), and then using VG, zone, and segment detection methods on that state if the variance is below a defined error margin.

8. The method of claim 1, wherein step (A) comprises utilizing a priori information, selected from at least one of the group consisting of last known position with a corresponding high uncertainty, estimating a position from pseudo ranges using traditional methods, and estimating by using information from mobile phone networks.

9. The method of claim 1, wherein the coordinate system is an Earth Centred Earth Fixed coordinate system.

10. The method of claim 1, wherein the tolling objects are defined as objects selected among two-dimensional objects defined by latitude and longitude and three-dimensional objects.

11. The method of claim 10, wherein the tolling objects are defined as three-dimensional objects in Earth Centred Earth Fixed coordinate systems.

12. The method of claim 1, wherein in the step of assessing passage or non-passage in (D)(iii), passage is denied if a position ambiguity is detected.

13. The method of claim 1, wherein the probability of passage of a tolling object selected from the group consisting of a Virtual Gantry (VG), a zone, and a segment is calculated individually for each associated particle, and the probability for the vehicle actually passing the VG, the zone or the segment from the ratio of particles having passed through the VG, the zone or the segment, when the ratio is above a defined confidence limit.

14. The method of claim 13, comprising using virtual gantry, zone or segment passage detection based on the derived probability distribution π

(x_t|z<sub>0;

t</sub>) of passing through the required states of a tolling object in the correct order.

15. The method of claim 1, wherein the assessment of passage or non-passage is derived from the probability distribution π

(x_t|z<sub>0;

t</sub>) by first calculating the expected state E(x_t|z<sub>0;

t</sub>) or median(x_t|z<sub>0;

t</sub>) and variance VAR(x_t|z<sub>0;

t</sub>), and then using VG, zone, and segment detection methods on that state if the variance is below a defined error margin.

16. The method of claim 1, comprising using virtual gantry, zone or segment passage detection based on the derived probability distribution π

(x_t|z<sub>0;

t</sub>) of passing through the required states of a tolling object in the correct order.

17. The method of claim 1, wherein discrete state variables are added to the system model to represent an actual toll charging based on an assessed passage.

18. A method for assessing distance driven by a vehicle utilizing a global navigation satellite system (GNSS) comprising an on-board unit (OBU) in every vehicle to be surveyed by the system, said OBU receiving signals from satellites to consistently and frequently estimate position coordinates for the vehicles, comprising the steps of:

(A) obtaining an initial vehicle position including a degree of uncertainty (50),

(B) using computer hardware and software to assign (51) a predetermined number of particles for each vehicle, in a meaning understood by the Sequential Monte Carlo mathematical method, comprising a process model, a measurement model and a probability distribution,

(C) using computer hardware and software to assign to each particle;

(i) a common initial probability, and

(ii) an initial state comprising at least three dimensional spatial position,

(D) using computer hardware and software to define epochs in time within each of which the following procedure is conducted;

(i) in a prediction step (52), using said process model to predict with uncertainty the state of each particle in the next epoch, generally represented as x_t=φ

_t(x_t-1)+η

_t, where x_t is the state vector, φ

_t(x_t-1) is a function used to predict the state x_t in one epoch from information of the state in the previous epoch, while η

_t is a process noise term, the predictions of all particles within each epoch thereby representing the probability distribution of the state vector x_t given all previous measurements z_t,

(ii) in an updating step (53), using computer hardware and software to update the probability of the particles according to how well each particle'"'"'s state from the prediction step agrees with GNSS pseudo range measurements, according to the equation z_t=h_t(x_t)+ε

_t, where z_t is a measurement vector, h_t(x_t) is a possibly time-varying function of the state, and ε

_t is measurement noise, thereby updating the probability distribution,

(iii) using computer hardware and software to assess distance driven by creating the probability distribution (63) of the actual distance from individual particle distances as derived by step (D)(ii), by applying a defined confidence level,

(iv) recursively repeating steps (D)(i) through (D)(iii) at a predetermined rate.

19. A system for assessing passages by a vehicle through a tolling object utilizing a global navigation satellite system (GNSS) comprising an on-board unit (OBU) in every vehicle to be surveyed by the system, said OBU receiving signals from satellites to consistently and frequently estimate position coordinates for the vehicles, comprising computer hardware and adapted computer software programmed to perform the following steps:

(A) obtaining an initial vehicle position including a degree of uncertainty (50),

(B) using computer hardware and software to assign (51) a predetermined number of particles for each vehicle, in a meaning understood by the Sequential Monte Carlo mathematical method, comprising a process model, a measurement model and a probability distribution,

(C) using computer hardware and software to assign to each particle;

(i) a common initial probability, and

(ii) an initial state comprising at least three dimensional spatial position,

(D) using computer hardware and software to define epochs in time within each of which the following procedure is conducted;

(i) in a prediction step (52), using said process model to predict with uncertainty the state of each particle in the next epoch, generally represented as x_t=φ

_t(x_t-1)+η

_t, where x_t is the state vector, φ

_t(x_t-1) is a function used to predict the state x_t in one epoch from information of the state in the previous epoch, while η

_t is a process noise term, the predictions of all particles within each epoch thereby representing the probability distribution of the state vector x_t given all previous measurements z_t,

(ii) in an updating step (53), using computer hardware and software to update the probability of the particles according to how well each particle'"'"'s state from the prediction step agrees with GNSS pseudo range measurements, according to the equation;

z_t=h_t(x_t)+ε

_t, wherein z_t is a measurement vector, h_t(x_t) is a possibly time-varying function of the state, and ε

_t is measurement noise, thus updating the probability distribution,

(iii) using computer hardware and software to assess passage or non-passage by (54) mathematically comparing the spatial definition of the tolling objects in question with the updated particle information from the prediction step (52) while applying a defined confidence level,

(iv) recursively repeating steps (D)(i) through (D)(iii) at a predetermined rate.

20. The system of claim 19, wherein the software is programmed to perform the step of transferring data concerning vehicle passage to a back office for further processing.