Method and system for generating driving directions

• US 7,054,745 B1
• Filed: 09/03/2003
• Issued: 05/30/2006
• Est. Priority Date: 09/03/2003
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Couckuyt, Jeffrey Darren, Vance, Amos Dylan
• Primary Examiner(s): Camby, Richard M.
• Application Number:
  US10/654,229
• Time in Patent Office: 1,000 Days
• Field of Search: 701 23- 25, 701200-213, 340989-99528, 342/357.1, 342/357.06
• US Class Current: 701/211
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network

Abstract

A method and system for generating driving directions composes computer-based instructions that emulate a human driving perspective. Language-based instructions guide a driver along a route that encompasses a sequence of roads and intersections. An algorithm applies rules based on human perception to route components. The algorithm diagnoses road name changes so that instructions are clear and concise. The algorithm analyzes road and intersection geometry at confusing areas, such as road forks, roundabouts, ferry crossings, cloverleaf interchanges, and ramps, to generate instructions that conform to a driver'"'"'s natural perspective. The algorithm analyzes the configuration of an intersection with respect to a driver'"'"'s field of view to compose a clear and concise instruction. When appropriate, the algorithm produces compound instructions for adjacent intersections.

Claims

1. A method for generating a set of instructions to guide a driver along a route, wherein the route comprises a first node, a second node, a third node, a first road coupled to the first node, a second road coupled between the first node and the second node, and a third road coupled between the second node and the third node, and a fourth road coupled to the third node, and wherein the method comprises the steps of:

generating a first instruction operative to guide the driver from the first road, through the first node, and onto the second road;

generating a second instruction operative to guide the driver from the second road through the second node, and onto third road; and

combining the first instruction and the second instruction into a combined instruction operative to guide the driver from the first road, through the first node, through the second road, through the second node, and onto the third road wherein, based upon the configuration of the first node and the second node, the first instruction and the second instruction are combined into the combined instruction when the driver would perceive the first node and the second node as a single integrated feature of the route.

2. The method of claim 1, wherein the first instruction has a first number of words, the second instruction has a second number of words, and the combined instruction has fewer words than the sum of the first number and the second number.

3. The method of claim 1, further comprising the step of generating a third instruction operative to guide the driver from the third road, through the third node, and onto the fourth road, wherein the combining step comprises combining the first instruction, the second instruction, and the third instruction into a combined instruction operative to guide the driver from the first road, through the first node, through the second road, through the second node, though the third road, through the third node, and onto the fourth road.

4. The method of claim 1, wherein the route further comprises a series of nodes and roads, and the method further comprises the steps of:

sequentially processing each node in the series;

generating a set of instructions on the basis of the sequentially processing step;

sequentially reprocessing each node in the series; and

responsive to the sequentially reprocessing step, refining the set of instructions.

5. The method of claim 4, wherein the step of generating a set of instructions comprises generating an initial set of instructions on the basis of the sequentially processing step, and wherein the refining step comprises responsive to the sequentially reprocessing step, refining the initial set of instructions to provide a refined set of instructions, and wherein the initial set of instructions has a greater number of instructions than the refined set.

6. The method of claim 1, wherein the combining step comprises if the distance between the first node and the second node is less than a threshold, combining the first instruction and the second instruction into a combined instruction operative to guide the driver from the first road, through the first node, through the second road, through the second node, and onto the third road.

7. The method of claim 1, further comprising the step of generating a driving itinerary that comprises the combined instruction.