METHOD AND APPARATUS FOR PROBE-BASED ROUTING

• US 20150134850A1
• Filed: 11/14/2013
• Published: 05/14/2015
• Est. Priority Date: 11/14/2013
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: ROLF, Daniel, KARGE, Bjrn, PRAETZ, Ullrich, JEHLICKA, Prokop
• Granted Patent: US 10,033,624 B2
• Time in Patent Office: Days
• US Class Current: 709/241
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length

Abstract

An approach is provided for providing routing calculations and route guidance based on geographic positioning and/or other sensor data from one or more mobile devices independent of map data. A routing platform processes and/or facilitates a processing of one or more probe data samples associated with at least one mobile device to determine one or more device tracks. The routing platform processes and/or facilitates a processing of the one or more device tracks to determine at least one tessellation, wherein the at least one tessellation is a subdivision of a plane or sphere into one or more tiles and a plurality of segments. The routing platform further determines one or more relationships between one or more of the plurality of segments based, at least in part, on a mapping of the one or more device tracks against the at least one tessellation.

Claims

1. A method comprising facilitating a processing of and/or processing (1) data and/or (2) information and/or (3) at least one signal, the (1) data and/or (2) information and/or (3) at least one signal based, at least in part, on the following:

a processing of one or more probe data samples associated with at least one mobile device to determine one or more device tracks;

a processing of the one or more device tracks to determine at least one tessellation, wherein the at least one tessellation is a subdivision of a plane or sphere into one or more tiles and a plurality of segments; and

at least one determination of one or more relationships between one or more of the plurality of segments based, at least in part, on a mapping of the one or more device tracks against the at least one tessellation.

2. A method of claim 1, wherein the (1) data and/or (2) information and/or (3) at least one signal are further based, at least in part, on the following:

at least one determination of one or more legs among the one or more device tracks based, at least in part, on the one or more device tracks intersecting two of the plurality of segments; and

at least one determination of one or more bundles among the one or more legs based, at least in part, on at least one of the one or more legs intersecting identical first and second segments of the plurality of segments,

wherein the one or more relationships are further based, at least in part, on the one or more legs, the one or more bundles, or a combination thereof.

3. A method of claim 1, wherein the (1) data and/or (2) information and/or (3) at least one signal are further based, at least in part, on the following:

at least one determination of at least one navigable route through a network based, at least in part, on at least one bundle-to-bundle transition across the one or more tiles.

4. A method of claim 1, wherein the (1) data and/or (2) information and/or (3) at least one signal are further based, at least in part, on the following:

at least one determination of the at least one tessellation, the one or more tiles, the plurality of segments, or a combination thereof based, at least in part, on latitude/longitude coordinates, one or more probe data sampling intervals, or a combination thereof associated with the one or more device tracks.

5. A method of claim 1, wherein the one or more probe data samples include, at least in part, a device session identification, a recording time, a latitude/longitude, or a combination thereof associated with the at least one mobile device.

6. A method of claim 5, wherein the (1) data and/or (2) information and/or (3) at least one signal are further based, at least in part, on the following:

at least one determination of the one or more device tracks based, at least in part, on the respective device session identification, recording time, latitude/longitude, or a combination thereof associated with the one or more probe data samples.

7. A method of claim 1, wherein the (1) data and/or (2) information and/or (3) at least one signal are further based, at least in part, on the following:

at least one determination of whether the one or more device tracks are valid based, at least in part, on one or more consistency rules, one or more constraints, one or more plausible travel trajectories, or a combination thereof,

wherein the one or more legs are further based, at least in part, on the one or more tracks being valid.

8. A method of claim 7, wherein the one or more constraints include, at least in part, at least one minimum number of probes per the one or more tracks, at least one minimum length of the one or more tracks, a distance and duration between probes matching a speed of the probes, or a combination thereof.

9. A method of claim 1, wherein the (1) data and/or (2) information and/or (3) at least one signal are further based, at least in part, on the following:

a processing of the one or more bundles to determine at least one cost-function associated with a shortest path route, an estimated travel time, an amount of fuel consumption, a favored road type, a popular route, or a combination thereof,

wherein the one or more relationships are further based, at least in part, on the at least one cost-function.

10. A method of claim 1, wherein the (1) data and/or (2) information and/or (3) at least one signal are further based, at least in part, on the following:

at least one filtering of the one or more device tracks based, at least in part, on a time of day, a vehicle type, a specific provider, a real-time latency, one or more vehicle trajectory properties, or a combination thereof to determine one or more traffic patterns,

wherein the one or more relationships are further based, at least in part, on the at least one filtering.

11. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs,

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,

process and/or facilitate a processing of one or more probe data samples associated with at least one mobile device to determine one or more device tracks;

process and/or facilitate a processing of the one or more device tracks to determine at least one tessellation, wherein the at least one tessellation is a subdivision of a plane or sphere into one or more tiles and a plurality of segments; and

determine one or more relationships between one or more of the plurality of segments based, at least in part, on a mapping of the one or more device tracks against the at least one tessellation.

12. An apparatus of claim 11, wherein the apparatus is further caused to:

determine one or more legs among the one or more device tracks based, at least in part, on the one or more device tracks intersecting two of the plurality of segments; and

determine one or more bundles among the one or more legs based, at least in part, on at least one of the one or more legs intersecting identical first and second segments of the plurality of segments,

wherein the one or more relationships are further based, at least in part, on the one or more legs, the one or more bundles, or a combination thereof.

13. An apparatus of claim 11, wherein the apparatus is further caused to:

determine at least one navigable route through a network based, at least in part, on at least one bundle-to-bundle transition across the one or more tiles.

14. An apparatus of claim 11, wherein the apparatus is further caused to:

determine the at least one tessellation, the one or more tiles, the plurality of segments, or a combination thereof based, at least in part, on latitude/longitude coordinates, one or more probe data sampling intervals, or a combination thereof associated with the one or more device tracks.

15. An apparatus of claim 11, wherein the one or more probe data samples include, at least in part, a device session identification, a recording time, a latitude/longitude, or a combination thereof associated with the at least one mobile device.

16. An apparatus of claim 15, wherein the apparatus is further caused to:

determine the one or more device tracks based, at least in part, on the respective device session identification, recording time, latitude/longitude, or a combination thereof associated with the one or more probe data samples.

17. An apparatus of claim 11, wherein the apparatus is further caused to:

determine whether the one or more device tracks are valid based, at least in part, on one or more consistency rules, one or more constraints, one or more plausible travel trajectories, or a combination thereof,

wherein the one or more legs are further based, at least in part, on the one or more tracks being valid.

18. An apparatus of claim 17, wherein the one or more constraints include, at least in part, at least one minimum number of probes per the one or more tracks, at least one minimum length of the one or more tracks, a distance and duration between probes matching a speed of the probes, or a combination thereof.

19. An apparatus of claim 11, wherein the apparatus is further caused to:

process and/or facilitate a processing of the one or more bundles to determine at least one cost-function associated with a shortest path route, an estimated travel time, an amount of fuel consumption, a favored road type, a popular route, or a combination thereof,

wherein the one or more relationships are further based, at least in part, on the at least one cost-function.

20. An apparatus of claim 11, wherein the apparatus is further caused to:

cause, at least in part, at least one filtering of the one or more device tracks based, at least in part, on a time of day, a vehicle type, a specific provider, a real-time latency, one or more vehicle trajectory properties, or a combination thereof to determine one or more traffic patterns,

wherein the one or more relationships are further based, at least in part, on the at least one filtering.

21-48. -48. (canceled)