Navigation system and method using map data

• US 5,311,173 A
• Filed: 08/28/1991
• Issued: 05/10/1994
• Est. Priority Date: 09/16/1988
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Hirayama, Yoshikazu, Matsuoka, Yoji, Kato, Makoto, Homma, Koichi, Shibata, Takanori, Kagami, Akira, Komura, Fuminobu, Kosaka, Michitaka
• Primary Examiner(s): SWARTHOUT, BRENT
• Application Number:
  US07/758,302
• Time in Patent Office: 986 Days
• Field of Search: 340/995, 340/990, 340/988, 73/178 R, 364/449, 364/444
• US Class Current: 340/995.22
• CPC Class Codes: G01C 21/30 Map- or contour-matching

Abstract

In a navigation system which has sensors for detecting a running distance, an azimuth, etc. of a vehicle, and a memory for storing map data; a probability density of a position of the vehicle is calculated on the basis of the sensor outputs and the map data for each of quantization units with which a probability computation determined by detection accuracies of the sensors and quantization of the map data can be executed. In addition, a final stage calculation of DP matching between trajectory data obtained from the on-board sensor data from a start point of the vehicle until a current time and a candidate route estimated from the road map data is iteratively executed, whereby a plurality of estimative vehicular positions and uncertainties (costs) corresponding to the respective estimative positions are iteratively evaluated, and a correct vehicular position is estimated by selecting at least one estimative vehicular position of low uncertainty (cost).

Claims

1. A navigation method using map data in a system which has at least one of first detection means for detecting a running distance of a vehicle and a second detection means for detecting an azimuth of the vehicle, a first memory for storing the map data, a data processor, and a second memory, comprising the steps of:

continuously detecting data, at periodic intervals, of at least one of the running distance and the azimuth by the corresponding detection means;

deciding a quantization unit in any area in said map, corresponding to a current position of the vehicle calculated on the basis of the data detected in said detecting step, wherein said map includes roads and off-road locations, and quantization units each having a conditional probability of location of the vehicle;

calculating a probability density of the decided quantization unit, for each quantization unit decided in said deciding step, using said data processor on the basis of the corresponding map data and the detected data which has been obtained by said detecting step; and

correcting said current position corresponding to the decided quantization unit, based upon the calculated probability density, for each calculated probability density of the calculating step.

2. A navigation method using map data s defined in claim 1, wherein the calculated probability density is a conditional probability density of the vehicular position at a current time calculated in accordance with the data detected by said step of detecting, which data have been obtained until the current time since a start time of the calculation of the vehicular position.

3. A navigation method using map data as defined in claim 1, wherein the calculated probability density is a conditional probability density of a vehicular position series in an identical time interval calculated in accordance with the data detected by said step of detecting, which data have been obtained until the current time since a start time of the calculation of the vehicular position.

4. A navigation method using map data as defined in claim 1, wherein said step of calculating the probability density comprises a step of calculating a numerical conditional probability density representing the probability of the vehicular position at a next time as a function of the vehicular position at a current time, and in accordance with the use of a probable vehicular position indicated by the conditional probability of location of the corresponding quantization unit in the map data.

5. A navigation method using map data as defined in claim 1, further comprising the step of displaying on an image display device an image which is prepared from the map data and the calculated probability density of the vehicular position.

6. A navigation method using map data as defined in claim 1, further comprising the step of generating a voiced instruction which is synthesized in accordance with the map data and the calculated probability density of the current vehicular position.

7. A navigation method using map data as defined in claim 1, further comprising the step of receiving an initial vehicular position, whether the vehicle is on a road in the map or off a road in the map, at a start time of the calculation of the vehicular position, and the step of calculating an initial probability density in said data processor on the basis of the initial vehicular position.

8. A navigation method using map data as defined in claim 1, wherein an astronomical sensor is employed as the vehicular azimuth detection means.

9. A navigation method using map data as defined in claim 1, further comprising:

a step of sensing abnormal detection data by comparing the estimated current positions calculated according to output data of said first detection means and said second detection means; and

a step of determining if the comparison indicates a predefined discrepancy at the compared positions.

10. A navigation method using map data as defined in claim 1, wherein besides said detection means, at least one third detection means for detecting data on the vehicular position is provided, so as to be used for said step of calculating the probability density.

11. A navigation method using map data as defined in claim 1, wherein a sensor for an inclination angle of a body of the vehicle is employed as said third detection means.

12. A navigation method using map data as defined in claim 10, further comprising:

a step of sensing an abnormality by comparing probability densities of the vehicular position calculated according to data from each of said first and second detection means; and

a step of further comparing each of the probability densities calculated according to data from said first and second means with a probability density calculated in accordance with data from a third detection means.

13. A navigation method using map data as defined in claim 1, wherein the map data includes locations, connective relations and attributes of nodes and links that constituted roads, speed limits, and diversion probabilities of traffic flows.

14. A navigation method using map data as defined in claim 13, wherein said map data further includes auxiliary information items that are externally written.

15. A navigation method using map data as defined in claim 14, wherein the auxiliary information items are stored in a rewritable memory.

16. A navigation method using map data as defined in claim 14, wherein some of the auxiliary information items contain data errors resulting from data obtained by one of said first and second detection means.

17. A navigation method using map data as defined in claim 4, wherein the numerical conditional probability density represents the probability that the vehicle is at a particular location, and has a value that is determined to be non-zero when it is apparent that the vehicle runs only through roads in the map data.

18. A navigation method using map data as defined in claim 4, wherein said step of calculating a numerical conditional probability density further comprises:

a step of changing-over the numerical conditional probability density calculating step to a step of calculating the conditional probability density to be a non-zero value when the vehicle is on roads, in the map data, and a zero value when the vehicle is off roads, in the map data, when the vehicle only runs on roads on the map.

19. A navigation method using map data as defined in claim 1, wherein said first detection means is a speed sensor, said second detection means is a vehicular azimuth sensor, said first memory is a road map data memory, and said step of detecting at least one of the running distance and the azimuth includes sensing a speed and an azimuth of a vehicle by means of said speed sensor and said vehicular azimuth sensor, respectively, the method further comprising the steps of:

estimating a current estimative position of the vehicle on the basis of the sensed speed and azimuth and the corresponding map data;

storing, in said second memory, coordinates of a plurality of places on a road as the estimated current positions of the vehicle, together with their calculated probability density; and

iteratively updating the estimated vehicular position by evaluating an estimative vehicular position at a next time and the calculated probability density corresponding thereto, from the sensed speed and azimuth and the corresponding road map data on the basis of the estimated current position and the calculated probability density corresponding thereto.

20. A navigation method using map data as defined in claim 1, wherein said first detection means is a speed sensor, said second detection means is a vehicular azimuth sensor, said memory is a road map data memory, and said step of detecting at least one of the running distance and the azimuth includes sensing a speed and an azimuth of a vehicle by means of said speed sensor and said vehicular azimuth sensor, respectively, further comprising:

a DP matching calculation step of estimating a current estimative position of the vehicle and its calculated probability density corresponding thereto, on the basis of the sensed speed and azimuth and the map data; and

a step of storing, in said second memory, coordinates of the estimated current position of the vehicle and the calculated probability density corresponding thereto.

21. A navigation method using map data as defined in claim 19, further comprising the step of selecting the estimated vehicular position whose calculated probability density is higher than that of other estimated vehicular positions as a representative point, and displaying the estimated vehicular position on an image display device.

22. A navigation method using map data as defined in claim 20, further comprising the step of selecting the estimated vehicular position whose calculated probability density is higher than that of other estimated vehicular positions as a representative point, and displaying the selected estimated vehicular position on an image display device.

23. A navigation method using map data as defined in claim 19, wherein said step of iteratively updating the estimated vehicular position includes a final stage calculation of DP matching between route data obtained from on-board sensor data from a running start point up to a current time and at least one candidate route on the road map data.

24. A navigation method using map data as defined in claim 19, wherein the step of storing the calculated probability density further comprises:

a step of storing the calculated probability density at DP matching calculating stages of predetermined number on a maximum probability route leading to each of the estimated vehicular positions; and

a step of increasing, on account of the probability density concerning the initial stages of the predetermined number, a calculated probability density concerning the estimated vehicular position at a next time.

25. A navigation method using map data as defined in claim 20, wherein the step of storing the calculated probability density further comprises:

a step of storing the calculated probability density at DP matching calculation stages of predetermined number on a maximum probability route leading to each of the estimated vehicular positions; and

a step of increasing, on account of the probability density concerning the initial stages of the predetermined number, a calculated probability density concerning the estimated vehicular position at a next time.

26. A location method for a vehicle in a system which has at least one of first detection means for detecting a running distance of the vehicle and second detection mans for detecting an azimuth of the vehicle, and a memory for storing map data, comprising the steps of:

continuously detecting data, at periodic intervals, concerning at least one of the running distance and the azimuth by the corresponding detection means;

deciding a quantization unit in any area in said map, corresponding to a current position of the vehicle calculated on the basis of the data detected in said detecting step, wherein said map includes roads and off-road locations, and quantization units each having a conditional probability of location of the vehicle;

calculating a probability density of the decided quantization unit using calculation means carried on the vehicle, for each quantization unit decided in said deciding step, and on the basis of the corresponding map data and the detected data which has been obtained by said detecting step;

sending the calculated probability density to a center device; and

correcting said current position corresponding to the decided quantization unit, based upon the calculated probability density, for each calculated probability density of the calculating step.

27. A location method for a vehicle as defined in claim 26, wherein said detecting step is carried out on the vehicle, and the output thereof is sent to said center device so as to calculate the vehicular position in said center device.

28. A location method for a vehicle as defined in claim 27, wherein the vehicular position calculated by said center device is sent back to the vehicle.

29. A location method for a vehicle as defined in claim 27, wherein said center device executes at least a processing function of said detecting step.

30. A location method for a vehicle as defined in claim 27, further comprising the steps of:

storing an estimated value of the vehicular position on the basis of the calculated probability density, in a memory, and retrieving and displaying the estimated value.

31. A location method for a vehicle as defined in claim 27, further comprising:

the step of displaying the calculated probability density on an image display device in superposition on the map data.

32. A navigation method using map data, which has at least one of first detection means for detecting a running distance of a vehicle and second detection means for detecting an azimuth of the vehicle, a memory for storing the map data, a data processor, and a buffer memory, comprising:

means for continuously detecting, at periodic intervals, at least one of the running distance and the azimuth by the corresponding detection means;

means for deciding a quantization unit corresponding to a current position of the vehicle in any area in said map, said map including roads and off-road locations, with which a probability computation determined by a specific detection accuracy of said detection means and quantization of the map data can be executed;

means for calculating a probability density of the decided quantization unit by said data processor, for each quantization unit decided by said deciding means, on the basis of the map data and said at least one the running distance and the azimuth which has been obtained by said means for detecting at least one of the running distance and the azimuth; and

means for correcting said current position corresponding to the decided quantization unit, based upon the calculated probability density for each probability density calculated by the calculating means.

33. A location system for a vehicle, which has at least one of first detection means for detecting a running distance of the vehicle and second detection means for detecting an azimuth of the vehicle, and a memory for storing map data, comprising:

means for continuously detecting at periodic intervals, at least one of the running distance and the azimuth by the corresponding detection means;

means for deciding a quantization unit corresponding to a current position of the vehicle in any area in said map, said map including roads and off-road locations, with which a probability computation determined by a specific detection accuracy of said detection means and quantization of the map data can be executed;

means carried on the vehicle for calculating a probability density of the decided quantization unit, for each quantization unit decided by said deciding means, on the basis of the map data and the detected value which has been obtained by said means for detecting at least one of the running distance and the azimuth;

means for sending the calculated probability density to a center device; and

means for correcting said current position corresponding to the decided quantization unit, based upon the calculated probability density for each probability density calculated by the calculating means.

34. A navigation system using map data in a system which has first detection means having a speed sensor, for detecting a running distance of a vehicle, and second detection means including a vehicular azimuth sensor, for detecting an azimuth of the vehicle, a first memory for storing the map data, a data processor, and a second memory, comprising:

means for continuously detecting data, at periodic intervals, concerning at least one of the running distance and the azimuth by the corresponding detection means;

means for deciding a quantization unit in any area in said map, corresponding to a current position of the vehicle calculated on the basis of the data detected by said detecting means, wherein said map includes roads and off-road locations, and quantization units each having a conditional probability of location of the vehicle;

means for calculating a probability density of the decided quantization unit, for each quantization unit decided by said deciding means, on the basis of the corresponding map data and the detected data which has been obtained by said first or second detection means;

means for storing the calculated probability density in said second memory;

means for sensing a speed and an azimuth of a vehicle by said speed sensor and said vehicular azimuth sensor, respectively;

means for estimating a current estimative position of the vehicle on the basis of the sensed speed and azimuth and the map data;

means for correcting said current position corresponding to the decided quantization unit, based upon the calculated probability density for each probability density calculated by the calculating means;

means for storing coordinates of a plurality of places on a road as the estimated current positions of the vehicle, together with the calculated probability density of the respective estimated vehicular positions; and

means for iteratively updating the estimated vehicular position by evaluating an estimative vehicular position at a next time and the calculated probability density corresponding thereto, from the sensed speed and azimuth and the road map data on the basis of the estimated current position and the calculated probability density corresponding thereto.

35. A navigation system using map data in a system which has first detection means having a speed sensor, for detecting a running distance, of a vehicle and second detection means including a vehicular azimuth sensor, for detecting an azimuth of the vehicle, a first memory for storing the map data, a data processor, and a second memory, comprising:

means for detecting data concerning at least one of the running distance and the azimuth by the corresponding detection means;

means for deciding a quantization unit in an area in said map, corresponding to a current position of the vehicle calculated on the basis of the data detected by said detecting means, wherein said map includes roads and off-road locations, and quantization units each having a conditional probability of location of the vehicle;

means for calculating a probability density of the decided quantization unit on the basis of the corresponding map data and the detected data which has been obtained by said first or second detecting means;

means for storing the calculated probability density in said second memory;

means for sensing a speed and an azimuth of a vehicle by said speed sensor and said vehicular azimuth sensor, respectively;

DP matching calculation means for estimating a current estimative position of the vehicle and a corresponding calculated probability density of the current estimative position on the basis of the sensed speed and azimuth and the map data; and

means for storing, in said second memory, coordinates of the estimated current position of the vehicle and the calculated probability density corresponding to the estimated vehicular position.