MULTIPLE DIRECTIONS TO A DESTINATION WITHOUT PROVIDING A SPECIFIC ORIGIN

• US 20120016583A1
• Filed: 09/23/2011
• Published: 01/19/2012
• Est. Priority Date: 10/11/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cheung, Matthew, Couckuyt, Jeffrey D., Jansen, Markus
• Granted Patent: US 8,688,371 B2
• Time in Patent Office: Days
• US Class Current: 701/426
• 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;

an analysis component for selecting meta-departure points based on the destination location, independent of receiving a starting location;

a routing component for automatically generating instructions for geographically navigating to the destination location from the multiple meta-departure points; and

a processor that executes computer-executable instructions associated with at least one of the input component, the analysis component or the routing component.

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 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 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, comprising acts of:

receiving destination information associated with a destination;

searching for candidate meta-departure points relative to the destination independent of without knowledge of a starting location;

selecting final meta-departure locations from the candidate meta-departure points;

generating instruction sets associated with the final meta-departure points;

presenting the instruction sets, the instruction sets include directions for navigating geographically from the final meta-departure points to the destination; and

utilizing a processor that executes instructions stored in memory to perform at least one of the acts of receiving, searching, selecting, generating or presenting.

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;

computer-implemented means for searching for candidate meta-departure points relative to the destination;

computer-implemented means for selecting final meta-departure locations from the candidate meta-departure points;

computer-implemented means for generating instruction sets associated with the final meta-departure points; and

computer-implemented means for presenting the instruction sets, the instruction sets include directions for navigating geographically from the final meta-departure points to the destination; and

processor means that executes computer-executable instructions associated with at least one of the computer-implemented means for receiving, searching, selecting, generating or presenting.