Vehicle Route Representation Creation

• US 20100305850A1
• Filed: 05/27/2009
• Published: 12/02/2010
• Est. Priority Date: 05/27/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cao, Lili, Krumm, John
• Granted Patent: US 8,874,361 B2
• Time in Patent Office: Days
• US Class Current: 701/208
• 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 for generating graph-line maps of vehicular routes, comprising:

obtaining a plurality of positioning data marking traces of vehicular travel;

clarifying a location of a trace; and

merging related traces into a graph line.

2. The method of claim 1, traces comprising location nodes and edges between consecutive nodes, the nodes comprising global positioning satellite (GPS) data points.

3. The method of claim 1, comprising utilizing time-related data for nodes of a trace to identify directionality for the nodes and the related portions of the trace.

4. The method of claim 1, comprising clarifying a location of a trace using adjustment forces comprising:

shifting a location of a trace based on an attraction force to an attraction location; and

shifting a location of the shifted trace based on an attraction force to its original location.

5. The method of claim 4, comprising shifting the location of the trace until a net force for the trace is balanced.

6. The method of claim 4, shifting a location of a trace based on an attraction force to an attraction location comprising shifting the location of a first trace toward a second trace.

7. The method of claim 1, clarifying a location of a trace comprising shifting a first trace based on a repelling force between a second trace and the first trace, where the second trace has different directionality than that of the first trace.

8. The method of claim 7, shifting a first trace based on a repelling force comprising using a function of the directionality of the first trace and the second trace to determine a magnitude of the repelling force.

9. The method of claim 1, comprising selecting a magnitude of the adjustment forces related to the trace by utilizing closed form equations to predict outcomes using different parameters.

10. The method of claim 1, merging related traces into a graph line comprising:

determining whether a trace node should be merged with a first graph-line node;

if the trace node is merged to a first graph-line node, creating an edge between the merged first graph-line node and a second graph-line node, if the second graph-line node is present and an edge between the nodes is not present; and

if the trace node is not merged to the first graph-line node;

adding the trace node to the graph line; and

creating an edge between the added trace node and the second graph-line node if the second graph-line node is present.

11. The method of claim 10, determining whether a trace node should be merged with a first graph line node comprising determining whether the locations of the two nodes are comprised within a same vehicular travel segment.

12. The method of claim 11, determining whether the locations of the two nodes are comprised within a same vehicular travel segment comprising:

determining if a distance between the trace node and an edge between the first graph-line node and the second graph-line node meets a desired node-edge distance threshold;

determining if a difference in directionality of the trace node and the edge meets a desired directionality threshold; and

determining if the trace node is closer to the first graph-line node than the second graph-line node.

13. The method of claim 1, merging related traces into a graph line comprising removing edges from the graph line having a number of traces that meets a desired threshold.

14. A system for generating graph-line maps of vehicular routes, comprising:

a data storage component configured to store a plurality of positioning data that marks traces of vehicular travel;

a clarification component operably coupled to the data storage component, and configured to adjust a location of a trace; and

a graph line producing component configured to merge related traces into a graph line.

15. The system of claim 14, the clarification component comprising an attraction force adjustment component configured to shift the location of the trace until a net force for the trace is balanced, comprising:

an attraction location adjuster configured to determine a first attraction force that shifts the location of the trace to an attraction location;

an original location adjuster configured to determine a second attraction force that shifts the location of the trace, which is shifted by the attraction location adjuster'"'"'s determination, to its original position.

16. The system of claim 14, the clarification component comprising a repelling force adjustment component configured to shift a first trace away from a second trace, where the second trace has different directionality than that of the first trace.

17. The system of claim 14, the graph line producing component comprising:

a trace node merging component configured to determine whether a trace node should be merged with a first graph-line node;

a merged node edge creation component configured to create an edge between the merged first graph-line node and a second graph-line node, if the second graph-line node is present and an edge between the nodes is not present, when the trace node is merged with a first graph-line node; and

a non-merged node edge creation component configured to;

add the trace node to the graph line; and

create an edge between the added trace node and the second graph-line node if the second graph-line node is present.

18. The method of claim 17, the trace node merging component comprising:

a distance determination component configured to determine if a distance between the trace node and an edge between the first graph-line node and the second graph-line node meets a desired threshold;

a direction difference determination component configured to determine if a difference in directionality of the trace node and the edge meets a desired threshold; and

a proximity determination component configured to determine if the trace node is closer to the first graph-line node than the second graph-line node.

19. The method of claim 14, comprising a direction determination component configured to identify directionality for segments of a trace and related nodes using time-related data from the nodes of the trace.

20. A method for generating graph-line maps of vehicular routes, comprising:

obtaining a plurality of global positioning satellite (GPS) data marking traces of vehicular travel, the traces comprising location nodes and edges between consecutive nodes, the nodes comprising GPS data points;

clarifying a location of a trace using adjustment forces related to the trace to shift the location of the trace until a net force for the trace is balanced, comprising;

shifting a location of a first trace based on an attraction force to a second trace; and

shifting a location of the shifted trace based on an attraction force to its original location;

clarifying a location of a trace comprising shifting a first trace based on a repelling force between a second trace and the first trace, where the second trace has different directionality than that of the first trace, using a function of the directionality of the first trace and the second trace to determine a magnitude of the repelling force; and

merging related traces into a graph line comprising;

determining whether a trace node should be merged with a first graph-line node;

if the trace node is merged to a first graph-line node, creating an edge between the merged first graph-line node and a second graph-line node, if the second graph-line node is present and an edge between the nodes is not present; and

if the trace node is not merged to the first graph-line node;

adding the trace node to the graph line; and

creating an edge between the added trace node and the second graph-line node if the second graph-line node is present.