Vehicle route representation creation

• US 8,874,361 B2
• Filed: 05/27/2009
• Issued: 10/28/2014
• Est. Priority Date: 05/27/2009
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Krumm, John, Cao, Lili
• Primary Examiner(s): Zeender, Ryan
• Assistant Examiner(s): Haider, Fawaad
• Application Number:
  US12/472,464
• Publication Number:
  US 20100305850A1
• Time in Patent Office: 1,980 Days
• Field of Search: 701/208
• US Class Current: 701/400
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation

Abstract

Techniques and systems are disclosed that provide for creating an accurate representation of a roadway network, such as for planning vehicle travel routes. Positioning data is obtained, such as GPS data points from a plurality of vehicles, which mark traces of vehicular travel. A location of a trace is clarified using adjustment forces that are related to the traces, for example, to form coherent groups of traces. From these groups of clarified traces, a graph line is created by merging the traces.

Claims

1. A method, implemented at least in part via a processing unit, comprising:

receiving positioning data associated with a first vehicle, a second vehicle, a third vehicle, a fourth vehicle, a fifth vehicle and a sixth vehicle, the positioning data associated with one or more traces;

receiving time-related data associated with the first vehicle, the second vehicle, the third vehicle, the fourth vehicle, the fifth vehicle and the sixth vehicle;

determining one or more directionalities associated with at least one of the first vehicle, the second vehicle, the third vehicle, the fourth vehicle, the fifth vehicle or the sixth vehicle based at least in part on at least some of the positioning data and at least some of the time-related data;

shifting a location of a trace of vehicular travel associated with the first vehicle based at least in part on;

an attraction force between the trace and a second trace of vehicular travel associated with the second vehicle, the attraction force based at least in part on the second trace comprising a second directionality, of the one or more directionalities, that does not differ from a first directionality, of the one or more directionalities, of the trace in excess of a threshold, the first directionality represented by a first directional value corresponding to a first angle associated with the trace, the second directionality represented by a second directional value corresponding to a second angle associated with the second trace, where a cosine of the first directional value and the second directional value is greater than one; and

a repelling force between the trace and a third trace of vehicular travel associated with the third vehicle, the repelling force based at least in part on the third trace comprising a third directionality, of the one or more directionalities, that does differ from the first directionality of the trace in excess of the threshold, the third directionality represented by a third directional value corresponding to a third angle associated with the third trace, where a cosine of the first directional value and the third directional value is less than one;

shifting a second location of a fourth trace of vehicular travel associated with the fourth vehicle based at least in part on;

a second attraction force between the fourth trace and a fifth trace of vehicular travel associated with the fifth vehicle, the second attraction force based at least in part on the fifth trace comprising a fifth directionality, of the one or more directionalities, that does not differ from a fourth directionality, of the one or more directionalities, of the fourth trace in excess of a second threshold, the fourth directionality represented by a fourth directional value corresponding to a fourth angle associated with the fourth trace, the fifth directionality represented by a fifth directional value corresponding to a fifth angle associated with the fifth trace, where a cosine of the fourth directional value and the fifth directional value is greater than one; and

a second repelling force between the fourth trace and a sixth trace of vehicular travel associated with the sixth vehicle, the second repelling force based at least in part on the sixth trace comprising a sixth directionality, of the one or more directionalities, that does differ from the fourth directionality of the fourth trace in excess of the second threshold, the sixth directionality represented by a sixth directional value corresponding to a sixth angle associated with the sixth angle, where a cosine of the fourth directional value and the sixth directional value is less than one; and

merging the trace with one or more related traces into a graph-line based at least in part on the shifted location and merging the fourth trace with one or more second related traces into a second graph-line based at least in part on the shifted second location, the graph-line having a first direction on a roadway and the second graph-line having a second direction opposite the first direction on the roadway.

2. The method of claim 1, the trace comprising one or more location nodes and one or more edges between at least some of the one or more location nodes.

3. The method of claim 1, the positioning data comprising global positioning satellite (GPS) data.

4. The method of claim 1, at least one of the attraction force or the repelling force comprising an adjustment force.

5. The method of claim 1, comprising shifting the location of the trace based at least in part on a balance of a net force for the trace.

6. The method of claim 1, comprising determining a magnitude of the repelling force based at least in part on a function of least one of the first directionality of the trace or the third directionality of the third trace.

7. The method of claim 1, comprising determining a magnitude of the attraction force based at least in part on a function of at least one of the first directionality of the trace or the second directionality of the second trace.

8. The method of claim 1, comprising merging at least some of the one or more related traces based at least in part on a location associated with a graph-line node.

9. The method of claim 1, comprising determining a desired node-edge distance threshold based at least in part on a distance between a trace node and an edge between graph-line nodes.

10. The method of claim 1, comprising determining a proximity of a node based at least in part on a trace node, a first graph-line node, and a second graph-line node.

11. A system, comprising:

one or more processing units; and

memory comprising instructions that when executed by at least one of the one or more processing units, implement at least some of;

a component configured to;

receive positioning data associated with a first vehicle, a second vehicle and a third vehicle, the positioning data associated with one or more traces;

receive time-related data associated with the first vehicle, the second vehicle and the third vehicle; and

determine one or more directionalities associated with at least one of the first vehicle, the second vehicle or the third vehicle based at least in part on at least some of the positioning data and at least some of the time-related data;

a clarification component configured to;

shift a location of a trace of vehicular travel associated with the first vehicle based at least in part on a net force for the trace based at least in part on at least one of;

an attraction force between the trace and a second trace of vehicular travel associated with the second vehicle based at least in part on the second trace comprising a second directionality, of the one or more directionalities, similar to a first directionality, of the one or more directionalities, of the trace;

or

a repelling force between the trace and a third trace of vehicular travel associated with the third vehicle based at least in part on the third trace comprising a third directionality, of the one or more directionalities, different than the first directionality of the trace; and

a graph-line component configured to merge the trace with one or more related traces into a graph-line based at least in part on the shifted location.

12. The system of claim 11, the trace comprising one or more location nodes and one or more edges between at least some of the one or more location nodes.

13. The system of claim 11, the positioning data comprising global positioning satellite (GPS) data.

14. The system of claim 11, at least one of the attraction force or the repelling force comprising an adjustment force.

15. The system of claim 11, the clarification component configured to shift the location of the trace based at least in part on a balance of a net force for the trace.

16. The system of claim 11, the graph-line component configured to determine a magnitude of the repelling force based at least in part on a function of at least one of the first directionality of the trace or the third directionality of the third trace.

17. A computer-readable storage medium, excluding signals, comprising computer-executable instructions, which when executed at least in part via a processing unit on a computer performs acts, comprising:

shifting a location of a trace of vehicular travel associated with a first vehicle based at least in part on at least one of;

an attraction force between the trace associated with the first vehicle and a second trace of vehicular travel associated with a second vehicle based at least in part on the second trace comprising a second directionality that does not differ from a first directionality of the trace in excess of a threshold, the first directionality represented by a first directional value corresponding to a first angle associated with the trace, the second directionality represented by a second directional value corresponding to a second angle associated with the second trace, where a cosine of the first directional value and the second directional value is greater than one;

or

a repelling force between the trace associated with the first vehicle and a third trace of vehicular travel associated with a third vehicle based at least in part on the third trace comprising a third directionality that does differ from the first directionality of the trace in excess of the threshold, the third directionality represented by a third directional value corresponding to a third angle associated with the third trace, where a cosine of the first directional value and the third directional value is less than one; and

merging the trace with one or more related traces into a graph-line based at least in part on the shifted location.

18. The computer-readable storage medium of claim 17, the trace comprising one or more location nodes and one or more edges between at least some of the one or more location nodes, at least some of the one or more location nodes comprising one or more global positioning satellite (GPS) data points.

19. The computer-readable storage medium of claim 17, comprising identifying at least one of the first directionality of the trace, the second directionality of the second trace, or the third directionality of the third trace.

20. The computer-readable storage medium of claim 17, at least one of the attraction force or the repelling force comprising an adjustment force.