Method and system for generating travel routes based on wireless coverage

• US 8,311,741 B1
• Filed: 11/04/2011
• Issued: 11/13/2012
• Est. Priority Date: 11/04/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lawther, Michael Jan, Macpherson, Luke David, Foster, Andrew
• Primary Examiner(s): Tran, Dalena
• Application Number:
  US13/289,299
• Time in Patent Office: 375 Days
• Field of Search: 701/527, 455/423, 455/446, 455/67.1, 455/447, 455/67.16, 455/404.1, 4554561-4563, 455/457, 340/989, 340/988, 340/990, 340/995.1, 370/338
• US Class Current: 701/527
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality
• CPC Class Codes: G08G 1/096866 where the complete route is shown to the driver
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

Methods and systems for providing routing information to a user are disclosed. Based on a request for routing information between an origin and destination for a travel objective, wireless coverage data for the geographic area associated with the travel objective is received. A graph model for determining routes between the origin and destination is adjusted based at least in part on the wireless coverage data. According to particular aspects of the present disclosure, the graph model can be adjusted based on the wireless coverage data and at least additional parameter such as estimated trip time, average speed, distance, favored routes or traffic information. User information can be optionally provided and used to emphasize or deemphasize wireless coverage data in the determination of the route for the travel objective.

Claims

1. A computer-implemented method of providing route information, comprising:

receiving an origin and a destination for a travel objective;

accessing a graph model associated with a geographic region proximate the travel objective;

the graph model comprising a plurality of edges associated with traversable paths between the origin and the destination;

obtaining wireless coverage data associated with the geographic region;

adjusting the graph model based at least in part on the wireless coverage data, the wireless coverage data comprising estimated time spent without wireless coverage while traversing at least one of the plurality of edges;

determining a route between the origin and destination from the adjusted graph model to provide increased wireless coverage during the travel objective; and

providing the route for presentation to a user.

2. The computer-implemented method of claim 1, wherein adjusting the graph model comprises adjusting a weighting factor assigned to at least one of the plurality of edges in the graph model.

3. The computer-implemented method of claim 2, wherein the route between the origin and destination is determined from the graph model based at least in part on the weighting factor assigned to at least one of the plurality of edges in the graph model.

4. The computer-implemented method of claim 2, wherein the weighting factor assigned to at least one of the plurality of edges of the graph model is adjusted based at least in part on the wireless coverage data and at least one travel parameter associated with the edge.

5. The computer-implemented method of claim 4, wherein the at least one travel parameter comprises estimated travel time, distance, average speed, preferred routing information, or traffic information.

6. The computer-implemented method of claim 4, wherein the method comprises adjusting the weighting factor assigned to at least one of the plurality of edges based at least in part on information associated with the user.

7. The computer-implemented method of claim 6, wherein the method comprises adjusting the weighting factor to emphasize the wireless coverage data over the at least one travel parameter if the information associated with the user indicates the user needs wireless access during travel.

8. The computer-implement method of claim 6, wherein the information associated with the user comprises calendar information associated with the user.

9. The computer-implemented method of claim 8, wherein the method comprises emphasizing wireless coverage data over the at least one travel parameter in the adjustment of the weighting factor if the calendar information indicates the user needs wireless access during travel.

10. The computer-implemented method of claim 8, wherein the method comprises emphasizing the travel parameter over the wireless coverage data in the adjustment of the weighting factor if the calendar information indicates the user needs to arrive at the destination by a particular time.

11. The computer-implemented method of claim 1, wherein the wireless coverage data is obtained from a wireless network service provider.

12. The computer-implemented method of claim 1, wherein the wireless coverage data is obtained from a database of physically collected wireless coverage data.

13. The computer-implemented method of claim 1, wherein the wireless coverage data is obtained in near real time from a plurality of mobile devices.

14. The computer-implemented method of claim 1, wherein generating a route between the origin and destination from the adjusted graph model comprises:

determining a plurality of routes from the origin to the destination from the adjusted graph model; and

selecting one of the plurality of routes for presentation to the user based at least in part on a parameter associated with the route, the parameter being selected from the group consisting of estimated travel time, shortest distance, average speed, preferred routing information, or traffic information.

15. The computer-implemented method of claim 1, wherein the method comprises displaying information associated with the wireless coverage data to the user.

16. A system comprising a processing device and a network interface, the processing device configured to:

receive a request identifying an origin and a destination for a travel objective;

receive wireless coverage data associated with a geographic region associated with the travel objective;

generate a route from the origin and destination, the route being generated at least in part from a graph model having a plurality of edges representing traversable paths between the origin and destination, each of the plurality of edges being assigned a weighting factor determined based at least in part on the wireless coverage data and information associated with a user; and

provide, via the network interface, the route to another processing device.

17. The system of claim 16, wherein each of the plurality of edges is assigned a weighting factor determined based at least in part on at least one additional travel parameter associated with the edge.

18. The system of claim 17, wherein the at least one additional travel parameter comprises estimated travel time, distance, preferred routing information or traffic information.

19. The system of claim 17, wherein the processor is configured to adjust the weighting factor to emphasize the wireless coverage data over the at least one travel parameter if the information associated with the user indicates the user needs wireless access during travel.

20. The system of claim 16, wherein the information associated with the user comprises calendar information associated with the user.

21. A computing device for providing route information to a user, comprising:

a user interface configured to receive an origin and a destination for a travel objective from a user;

a network interface configured to access a remote computing device over a network;

a display device configured to display route information to the user; and

a processing device configured to;

provide the origin and destination via the network interface to the remote computing device;

receive from the remote computing device a route generated, the route being generated at least in part from a graph model having a plurality of edges representing traversable paths between the origin and destination, each of the plurality of edges being assigned a weighting factor determined based at least in part on wireless coverage data and information associated with the user; and

display, via the display device, the route to the user.

22. The computing device of claim 21 wherein each of the plurality of edges is assigned a weighting factor determined based at least in part on at least one additional travel parameter associated with the edge.

23. The computing device of claim 21, wherein the information associated with the user comprises calendar information associated with the user.

24. A computer-readable medium having computer-readable instructions for execution by a processor, causing the processor to perform operations, the operations comprising:

receiving an origin and a destination for a travel objective;

accessing a graph model associated with a geographic region proximate the travel objective, the graph model comprising a plurality of edges representing traversable paths between the origin and the destination;

obtaining wireless coverage data associated with the geographic region;

adjusting a weighting factor assigned to at least one of the plurality edges of the graph model based at least in part on the wireless coverage data, the wireless coverage data comprising estimated time spent without wireless coverage while traversing a particular edge;

generating a route between the origin and destination from the graph model based at least in part on the adjusted weighting factors assigned to the plurality of edges; and

providing the route for presentation to a user.

25. The computer-readable medium of claim 24, wherein the weighting factor assigned to at least one of the plurality of edges of the graph model is adjusted based at least in part on the wireless coverage data and at least one travel parameter associated with the edge.

26. The computer-readable medium of claim 24, wherein the at least one travel parameter comprises estimated travel time, distance, average speed, preferred routing information or traffic information.

27. The computer-readable medium of claim 24, wherein the operations comprise adjusting the weighting factor assigned to at least one of the plurality of edges based at least in part on information associated with the user.

28. The computer-readable medium of claim 27, wherein the operations comprise adjusting the weighting factor to emphasize the wireless coverage data over the at least one travel parameter if the information associated with the user indicated the user needs wireless access during travel.