Turn detection algorithm for vehicle positioning

• US 6,502,033 B1
• Filed: 10/05/2000
• Issued: 12/31/2002
• Est. Priority Date: 10/05/2000
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Phuyal, Bishnu P.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Hernandez, Olga
• Application Number:
  US09/680,161
• Time in Patent Office: 817 Days
• Field of Search: 701/214, 701/216, 701/217, 701/213, 701/208, 701/224, 701/25, 340/988, 342/357.08, 342/357.06, 342/357.13, 342/357.14
• US Class Current: 701/214
• CPC Class Codes: G01C 21/30 Map- or contour-matching

Abstract

A turn detection algorithm is used by a navigation system for determining position and heading of a vehicle relative to a road network represented by a geographic database used by the navigation system. A dead-reckoned position and heading are determined along a plurality of road segments in the road network using sensor measurements of a distance traveled by the vehicle and a change in heading of the vehicle. A vehicle trajectory history is formed and then continuously updated. The vehicle trajectory history includes sensor-derived data representing the vehicle trajectory over a relatively small, chosen distance. The sensor-derived data in the vehicle trajectory history include total turn (i.e., heading change of the vehicle), vehicle state (e.g., travelling straight, turning or reversing in turn direction within a specified small distance) and type of vehicle maneuver. These data represent the trajectory of the vehicle for that distance and are kept in a memory. Corresponding data for the same distance interval are also obtained from GPS measurements and the geographic database. Using the data in the vehicle trajectory history and the corresponding data from the GPS and geographic database, a corrected dead-reckoned position and heading are determined. In addition, using the data in the vehicle trajectory history and the corresponding data from the GPS and geographic database, bias and scale factor correction parameters for the sensors are also obtained.

Claims

1. A method for determining position and heading of a vehicle relative to a road network represented by a geographic database, wherein the method comprises the steps of:

determining a dead-reckoned position and heading along a plurality of road segments in the road network using sensor measurements obtained over a distance traveled by the vehicle;

forming a vehicle trajectory history, wherein the vehicle trajectory history includes sensor-derived data representing a vehicle trajectory over a relatively small, chosen distance, and wherein the sensor-derived data include data indicating a heading change of the vehicle, data indicating a vehicle state and data indicating a type of vehicle maneuver;

obtaining corresponding data for the distance from GPS measurements;

obtaining corresponding data for the distance from the geographic database;

using the data in the vehicle trajectory history and the corresponding data from the GPS and the geographic database to determine a corrected dead-reckoned position and heading; and

continuously updating said vehicle trajectory history,

wherein the vehicle state includes one of;

travelling straight, turning and reversing in turn direction within a specified small distance, and

wherein the vehicle state of reversing in turn direction within a specified small distance is determined when a heading change for a current and a previous array entry are opposite in sign and both are greater than a threshold.

2. The method of claim 1 wherein the threshold corresponds to approximately 2.5 degree.

3. A method for determining position and heading of a vehicle relative to a road network represented by a geographic database, wherein the method comprises the steps of:

determining a dead-reckoned position and heading along a plurality of road segments in the road. network using sensor measurements obtained over a distance traveled by the vehicle;

forming a vehicle trajectory history, wherein the vehicle trajectory history includes sensor-derived data representing a vehicle trajectory over a relatively small, chosen distance, and wherein the sensor-derived data include data indicating a heading change of the vehicle, data indicating a vehicle state and data indicating a type of vehicle maneuver;

obtaining corresponding data for the distance from GPS measurements;

obtaining corresponding data for the distance from the geographic database;

using the data in the vehicle trajectory history and the corresponding data from the GPS and the geographic database to determine a corrected dead-reckoned position and heading; and

continuously updating said vehicle trajectory history,

wherein the vehicle trajectory history includes gyroscope readings, counts of gyroscope readings, delta gyroscope readings, heading change, maximum values of the gyroscope readings, minimum values of the gyroscope readings and a heading determined from dead reckoning, and further wherein similar data are also included for GPS data and the geographic database.

4. The method of claim 3 wherein the vehicle state includes one of:

travelling straight, turning and reversing in turn direction within a specified small distance.

5. The method of claim 3 wherein the vehicle state includes one of:

travelling straight, turning, reversing in turn direction within a specified small distance, or simple maneuvers, small turns, medium turns, and large turns.

6. The method of claim 3 further comprising the step of:

using the data in the vehicle trajectory history and the corresponding data from the GPS and the geographic database to determine bias and scale factor correction parameters for sensors from which the sensor measurements are obtained.

7. The method of claim 3 wherein the chosen distance is at least approximately 25 meters.

8. The method of claim 3 wherein said vehicle trajectory history is stored as entries in an array maintained in a memory of a navigation system.

9. The method of claim 8 wherein said steps of determining, forming obtaining, obtaining and using are performed by a navigation system installed in said vehicle.

10. A program included as part of a navigation system installed in a vehicle and used for determining position and heading of the vehicle relative to a road network represented by a geographic database, wherein the program comprises:

a routine that determines a dead-reckoned position and heading along a plurality of road segments in the road network using sensor measurements obtained over a distance traveled by tire vehicle;

a routine that forms a vehicle trajectory history, wherein the vehicle trajectory history includes sensor-derived data representing a vehicle trajectory over a relatively small, chosen distance, and wherein the sensor-derived data include data indicating a heading change of the vehicle, data indicating a vehicle state and data indicating a type of vehicle maneuver;

a routine that obtains corresponding data for the distance from GPS measurements;

a routine that obtains corresponding data for the distance from the geographic database;

a routine that uses the data in the vehicle trajectory history and the corresponding data from the GPS and the geographic database to determine a corrected dead-reckoned position and heading; and

a routine that continuously updates said vehicle trajectory history,

wherein the vehicle state includes one of;

travelling straight, turning and reversing in turn direction within a specified small distance, and

wherein the vehicle state of reversing in turn direction within a specified small distance is determined when a heading change for a current and a previous array entry are opposite in sign and both are greater than a threshold.

11. The invention of claim 10 wherein the threshold corresponds to approximately 2.5 degree.

12. A program included as part of a navigation system installed in a vehicle and used for determining position and heading of the vehicle relative to a road network represented by a geographic database, wherein the program comprises:

a routine that determines a dead-reckoned position and heading along a plurality of road segments in the road network using sensor measurements obtained over a distance traveled by the vehicle;

a routine that forms a vehicle trajectory history, wherein the vehicle trajectory history includes sensor-derived data representing a vehicle trajectory over a relatively small, chosen distance, and wherein the sensor-derived data include data indicating a heading change of the vehicle, data indicating a vehicle state and data indicating a type of vehicle maneuver;

a routine that obtains corresponding data for the distance from GPS measurements;

a routine that obtains corresponding data for the distance from the geographic database;

a routine that uses the data in the vehicle trajectory history and the corresponding data from the GPS and the geographic database to determine a corrected dead-reckoned position and heading; and

a routine that continuously updates said vehicle trajectory history,

wherein the vehicle trajectory history includes gyroscope readings, counts of gyroscope readings, delta gyroscope readings, heading change, maximum values of the gyroscope readings, minimum values of the gyroscope readings and a heading determined from dead reckoning, and further wherein similar data are also included from GPS data and the geographic database.

13. The invention of claim 12 wherein said vehicle trajectory history is stored as entries in an array maintained in a memory of the navigation system.

14. The invention of claim 12 wherein the vehicle state includes one of:

travelling straight, turning, reversing in turn direction within a specified small distance, or simple maneuvers, small turns, medium turns, and large turns.

15. The invention of claim 12 further comprising:

a routine that uses the data in the vehicle trajectory history and the corresponding data from the GPS and the geographic database to determine bias and scale factor correction parameters for sensors from which the sensor measurements are obtained.

16. The invention of claim 12 wherein the chosen distance is at least approximately 25 meters.

17. The invention of claim 12 wherein the vehicle state includes one of:

travelling straight, turning and reversing in turn direction within a specified small distance.