Multiple directions to a destination without providing a specific origin

• US 8,060,298 B2
• Filed: 10/11/2007
• Issued: 11/15/2011
• Est. Priority Date: 10/11/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jansen, Markus, Cheung, Matthew, Couckuyt, Jeffrey D
• Primary Examiner(s): Trammell; James
• Assistant Examiner(s): Shafi; Muhammad
• Application Number:
  US11/870,919
• Publication Number:
  US 20090099770A1
• Time in Patent Office: 1,496 Days
• Field of Search: 701200-226, 340988-996
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments

Abstract

The automatic generation of multiple sets of directions for navigating geographically to a specific destination without specification of an origin. Based on the destination, candidate roads or other transportation conduits are selected for analysis. Candidate meta-departure points are analyzed and selected along the roads based on distribution about the destination, cardinal directions relative to the destination, road metadata, distance to the destination, driving time, and other factors. The number of departure points generated to represent routes to the destination from the several logical cardinal directions is minimized. The generated departure points also represent routes that a majority of people would likely take to the destination. Additionally, the generated departure points originate from places that users are likely to be familiar with and can get to without additional guidance. The final instruction sets for navigating to the destination are presented along with a map that identified the departure points.

Claims

1. A computer-implemented navigation system, comprising:

an input component for receiving a destination location to which a user wants to travel, without specifying a starting location;

an analysis component for selecting multiple meta-departure points associated with multiple different routes to the destination location from multiple different logical directions from candidate meta-departure points based on at least one of a geographical distribution or cardinal orientation around or relative to the destination location, such that a minimum of meta-departure points cover a maximum percentage of potential inbound travel routes, independent of knowledge of a specific starting location; and

a routing component for automatically generating multiple sets of instructions corresponding to the different logical directions associated with the multiple meta-departure points for geographically navigating the different routes to the destination location from the multiple meta-departure points.

2. The system of claim 1, wherein the analysis component selects the meta-departure points based on local locations that are likely to be familiar to local users.

3. The system of claim 1, wherein the analysis component selects the meta-departure points based on proximity of the meta-departure points to major transportation routes and to the destination location.

4. The system of claim 1, wherein the analysis component selects the meta-departure points based on a cost function that considers distance and route complexity from the meta-departure points to the destination location.

5. The system of claim 1, wherein the analysis component selects the meta-departure points based on geographical distribution of the meta-departure points relative to the destination location.

6. The system of claim 1, wherein the analysis component selects a minimum number of the meta-departure points that cover a greatest percentage of inbound routes to the destination location.

7. The system of claim 1, wherein the analysis component generates the candidate meta-departure points by searching outward from the destination location relative to major transportation routes until a predetermined number of the candidate meta-departure points is obtained.

8. The system of claim 1, wherein the analysis component generates the candidate meta-departure points from which the meta-departure points are chosen by selecting locations within a predetermined distance from the destination location and searching inward from the locations for the candidate meta-departure points relative to commonly-known transportation routes to the destination location.

9. The system of claim 8, wherein the candidate meta-departure points are distributed about the destination location and according to cardinal directions.

10. The system of claim 1, further comprising a presentation component for presenting separate lists of instructions for guiding the user from the corresponding meta-departure points to the destination location and a map that illustrates the meta-departure points relative to transportation routes and the destination location.

11. A computer-implemented method of providing navigation instructions employing a computer programmed to perform the method, comprising:

receiving destination information associated with a destination, without specifying a starting location;

searching for candidate meta-departure points associated with multiple different routes to the destination from multiple different logical directions, independent of knowledge of a starting location;

selecting final meta-departure locations from the candidate meta-departure points based on at least one of a geographical distribution or cardinal orientation around or relative to the destination location, such that the final meta-departure points cover a largest percentage of potential inbound travel routes;

generating multiple instruction sets corresponding to the multiple different logical directions associated with the final meta-departure points; and

presenting the instruction sets, the instruction sets include directions for navigating geographically the multiple different routes from the final meta-departure points to the destination.

12. The method of claim 11, further comprising presenting a graphical representation of a map that depicts transportation routes related to the destination and identifiers for the final meta-departure points relative to the transportation routes.

13. The method of claim 11, further comprising processing a cost function as part of selecting the candidate meta-departure points.

14. The method of claim 11, further comprising sorting and ranking the candidate meta-departure points to determine the final meta-departure points.

15. The method of claim 11, further comprising setting threshold criteria related to road selection based on distance and driving time.

16. The method of claim 11, further comprising analyzing a road and road metadata as a possible transportation route between the destination and a final meta-departure point.

17. The method of claim 11, further comprising searching for candidate meta-departure points based on an increasing distance from the destination.

18. The method of claim 11, further comprising minimizing a number of candidate meta-departure points along a selected route based on transportation routes of a region and a likelihood that a majority of users in that region would use the transportation routes.

19. The method of claim 11, further comprising identifying candidate meta-departure points proximate a fixed distance from the destination and analyzing roads from the candidate meta-departure points inward to the destination as routes for which the instruction sets are generated and presented.

20. A computer-implemented system, comprising:

computer-implemented means for receiving destination information associated with a destination, without specifying a starting location;

computer-implemented means for searching for candidate meta-departure points associated with multiple different routes to the destination from multiple different logical directions;

computer-implemented means for selecting final meta-departure locations from the candidate meta-departure points based on at least one of a geographical distribution or cardinal orientation around or relative to the destination location, such that the final meta-departure points cover a largest percentage of potential inbound travel routes;

computer-implemented means for generating multiple instruction sets corresponding to the multiple different logical directions associated with the final meta-departure points; and

computer-implemented means for presenting the instruction sets, the instruction sets include directions for navigating geographically the multiple different routes from the final meta-departure points to the destination.