US5938720A — Route generation in a vehicle navigation system

Claim 1

Independent Claim 118 words

A method for determining a route from a first location to a second location using a vehicle navigation system, the method comprising the steps of: searching a map database for a first number of iterations thereby generating a first route candidate connecting the first and second locations, the first route candidate comprising a plurality of road segments; after generation of the first route candidate, terminating searching the map database after a second number of additional iterations, the second number of additional iterations resulting in at least a portion of a second route candidate beginning at the first location and comprising a plurality of road segments; and automatically selecting a best route candidate as the route without user intervention.

Claim 2

Independent Claim 118 words

A method for determining a route from a first location to a second location using a vehicle navigation system, the method comprising the steps of: searching a map database for a first number of iterations thereby generating a first route candidate connecting the first and second locations, the first route candidate comprising a plurality of road segments; after generation of the first route candidate, terminating searching the map database after a second number of additional iterations, the second number of additional iterations resulting in at least a portion of a second route candidate beginning at the first location and comprising a plurality of road segments; and automatically selecting a best route candidate as the route without user intervention.

Claim 3

Dependent Claim 22 words

The method of claim 1 wherein the second number is determined with reference to a distance between the first and second locations.

Claim 4

Dependent Claim 17 words

The method of claim 1 wherein the second number is determined with reference to the first number.

Claim 5

Dependent Claim 35 words

The method of claim 1 further comprising the step of, where the second number of additional iterations has not yet occurred, terminating the searching step after a second number of route candidates has been generated.

Claim 6

Dependent Claim 29 words

The method of claim 1 wherein the second number is reduced by a bonus amount for each additional route candidate generated after the generation of the first route candidate.

Claim 7

Dependent Claim 19 words

The method of claim 1 wherein the searching step comprises searching the map database beginning from the first location.

Claim 8

Dependent Claim 20 words

The method of claim 6 wherein the searching step also comprises searching the map database beginning from the second location.

Claim 9

Independent Claim 102 words

A method for determining a route from a first location to a second location using a vehicle navigation system, the method comprising the steps of: searching a map database for a plurality of iterations thereby generating at least one route candidate, the searching initially including road segments of a plurality of ranks; during the searching step, identifying a first road segment having a first rank associated therewith; in response to the identifying step, excluding from subsequent iterations of the searching step all other road segments having ranks associated therewith below the first rank; and selecting a best route candidate as the route.

Claim 10

Independent Claim 102 words

A method for determining a route from a first location to a second location using a vehicle navigation system, the method comprising the steps of: searching a map database for a plurality of iterations thereby generating at least one route candidate, the searching initially including road segments of a plurality of ranks; during the searching step, identifying a first road segment having a first rank associated therewith; in response to the identifying step, excluding from subsequent iterations of the searching step all other road segments having ranks associated therewith below the first rank; and selecting a best route candidate as the route.

Claim 11

Dependent Claim 33 words

The method of claim 8 further comprising the step of executing a first number of iterations of the searching step after the first road segment is identified and before performing the excluding step.

Claim 12

Dependent Claim 22 words

The method of claim 9 wherein the first number is determined with reference to a distance between the first and second locations.

Claim 13

Independent Claim 164 words

A method for determining a route using a vehicle navigation system, the route comprising a plurality of contiguous road segments, the method comprising the steps of: determining whether a search region encompasses a portion of the map database characterized by a grid pattern, the grid pattern relating to a density and an orientation of road segments in the portion of the map database; where the search region does not encompass the portion of the map database characterized by the grid pattern, expanding the search region to search the map database for the contiguous road segments, the search region being characterized by a shape and including a first plurality of route candidates; and where the search region encompasses the portion of the map database characterized by the grid pattern, altering the shape of the search region by adjusting cost values in the map database such that the search region includes additional route candidates with fewer turns as compared to the first plurality of route candidates.

Claim 14

Independent Claim 164 words

A method for determining a route using a vehicle navigation system, the route comprising a plurality of contiguous road segments, the method comprising the steps of: determining whether a search region encompasses a portion of the map database characterized by a grid pattern, the grid pattern relating to a density and an orientation of road segments in the portion of the map database; where the search region does not encompass the portion of the map database characterized by the grid pattern, expanding the search region to search the map database for the contiguous road segments, the search region being characterized by a shape and including a first plurality of route candidates; and where the search region encompasses the portion of the map database characterized by the grid pattern, altering the shape of the search region by adjusting cost values in the map database such that the search region includes additional route candidates with fewer turns as compared to the first plurality of route candidates.

Claim 15

Independent Claim 96 words

A method for connecting a first route generated by a vehicle navigation system to a second route generated by the vehicle navigation system, the method comprising the steps of: generating the first and second routes, the first and second routes being connected at a connection point forming a combined route; generating a third route from a source point on the first route near the connection point to a destination point on the second route near the connection point; and replacing a portion of the combined route between the source and destination points with the third route.

Claim 16

Independent Claim 96 words

A method for connecting a first route generated by a vehicle navigation system to a second route generated by the vehicle navigation system, the method comprising the steps of: generating the first and second routes, the first and second routes being connected at a connection point forming a combined route; generating a third route from a source point on the first route near the connection point to a destination point on the second route near the connection point; and replacing a portion of the combined route between the source and destination points with the third route.

Claim 17

Independent Claim 81 words

A method for connecting a first route generated by a vehicle navigation system to a second route generated by the vehicle navigation system, the method comprising the steps of: generating the first and second routes; connecting the first and second routes at a connection point forming a combined route; determining whether the first and second routes intersect at an intersection point; and where the first and second routes intersect, removing unnecessary portions of the combined route coupled to the intersection point.

Claim 18

Independent Claim 81 words

A method for connecting a first route generated by a vehicle navigation system to a second route generated by the vehicle navigation system, the method comprising the steps of: generating the first and second routes; connecting the first and second routes at a connection point forming a combined route; determining whether the first and second routes intersect at an intersection point; and where the first and second routes intersect, removing unnecessary portions of the combined route coupled to the intersection point.

Claim 19

Independent Claim 116 words

A method for generating a partial route in a vehicle navigation system prior to generation of a complete route between an origin and a destination, the method comprising the steps of: searching a map database to generate a plurality of partial route candidates, each of the partial route candidates having a travel cost and a heuristic cost associated therewith, each of the partial route candidates beginning at the origin and not reaching the destination; terminating the searching step where the travel cost associated with at least one of the partial route candidates reaches a first threshold value; and selecting as the partial route one of the partial route candidates having the lowest heuristic cost associated therewith.

Claim 20

Independent Claim 116 words

A method for generating a partial route in a vehicle navigation system prior to generation of a complete route between an origin and a destination, the method comprising the steps of: searching a map database to generate a plurality of partial route candidates, each of the partial route candidates having a travel cost and a heuristic cost associated therewith, each of the partial route candidates beginning at the origin and not reaching the destination; terminating the searching step where the travel cost associated with at least one of the partial route candidates reaches a first threshold value; and selecting as the partial route one of the partial route candidates having the lowest heuristic cost associated therewith.

Claim 21

Dependent Claim 23 words

The method of claim 14 wherein the first threshold value is determined with reference to the distance between the first and second locations.

Claim 22

Dependent Claim 31 words

The method of claim 14 wherein the terminating step comprises terminating the searching step where the travel costs associated with all of the partial route candidates reach the first threshold value.

Claim 23

Dependent Claim 30 words

The method of claim 14 wherein the first threshold value is set such that a limited access road entrance is included in at least one of the partial route candidates.

Claim 24

Dependent Claim 43 words

The method of claim 17 wherein total costs associated with limited access roads are reduced to favor use of the limited access roads in route generation, the total cost comprising a sum of travel and heuristic costs associated with the limited access roads.

Claim 25

Dependent Claim 67 words

The method of claim 17 wherein a second threshold value is determined with reference to the distance between the first and second locations, and the method further comprises the step of, where the second threshold value is less than the first threshold value, truncating the at least one of the partial route candidates such that the travel cost associated therewith does not exceed the second threshold value.

Claim 26

Dependent Claim 59 words

The method of claim 14 wherein the vehicle navigation system operates in a mode in which selected travel costs are adjusted to generate adjusted travel costs for route generation purposes, the method further comprising the step of, while the vehicle navigation system is operating in the mode, keeping track of the selected travel costs for partial route termination purposes.

Claim 27

Dependent Claim 32 words

The method of claim 20 wherein the mode comprises a freeway mode in which the vehicle navigation system decreases travel costs associated with freeways to favor use of freeways for route generation.

Claim 28

Dependent Claim 34 words

The method of claim 20 wherein the mode comprises a surface street mode in which the vehicle navigation system increases travel costs associated with freeways to favor use of surface streets for route generation.

Claim 29

Independent Claim 113 words

A method for terminating partial route generation in a vehicle navigation system, the partial route comprising a plurality of contiguous road segments stored in a map database, the method comprising the steps of: searching the map database for the contiguous road segments; terminating partial route generation upon selecting as part of the partial route a first road segment having access to a limited access road, the limited access road having two directions associated therewith; identifying a second road segment in the partial route from which access to both directions of the limited access road is possible; and removing any of the contiguous road segments in the partial route beyond the second road segment.

Claim 30

Independent Claim 113 words

A method for terminating partial route generation in a vehicle navigation system, the partial route comprising a plurality of contiguous road segments stored in a map database, the method comprising the steps of: searching the map database for the contiguous road segments; terminating partial route generation upon selecting as part of the partial route a first road segment having access to a limited access road, the limited access road having two directions associated therewith; identifying a second road segment in the partial route from which access to both directions of the limited access road is possible; and removing any of the contiguous road segments in the partial route beyond the second road segment.

Claim 31

Independent Claim 126 words

A method for terminating partial route generation in a vehicle navigation system, the partial route comprising a plurality of contiguous road segments stored in a map database, the method comprising the steps of: expanding a search region to search the map database for the contiguous road segments, the contiguous road segments including road segments of a plurality of ranks; upon selecting as part of the partial route a first road segment comprising a portion of a first limited access road, terminating expansion of the search region along the first limited access road; continuing expansion of the search region in at least one other direction until a second limited access road is encountered; and terminating expansion of the search region upon encountering the second limited access road.

Claim 32

Independent Claim 126 words

A method for terminating partial route generation in a vehicle navigation system, the partial route comprising a plurality of contiguous road segments stored in a map database, the method comprising the steps of: expanding a search region to search the map database for the contiguous road segments, the contiguous road segments including road segments of a plurality of ranks; upon selecting as part of the partial route a first road segment comprising a portion of a first limited access road, terminating expansion of the search region along the first limited access road; continuing expansion of the search region in at least one other direction until a second limited access road is encountered; and terminating expansion of the search region upon encountering the second limited access road.

Claim 33

Independent Claim 88 words

A method for providing route guidance using a vehicle navigation system, comprising the steps of: generating a route from a first location to a second location; generating a first plurality of maneuver instructions for a first plurality of maneuvers corresponding to a first portion of the route; communicating the first plurality of maneuver instructions via a user interface; and generating a second plurality of maneuver instructions for a second plurality of maneuvers corresponding to a remainder of the route during communication of the first plurality of maneuver instructions.

Claim 34

Independent Claim 88 words

A method for providing route guidance using a vehicle navigation system, comprising the steps of: generating a route from a first location to a second location; generating a first plurality of maneuver instructions for a first plurality of maneuvers corresponding to a first portion of the route; communicating the first plurality of maneuver instructions via a user interface; and generating a second plurality of maneuver instructions for a second plurality of maneuvers corresponding to a remainder of the route during communication of the first plurality of maneuver instructions.

Claim 35

Dependent Claim 64 words

The method of claim 25 wherein the route comprises a first partial route from the first location to an intermediate location and a second partial route from the intermediate location to the second location, the first partial route comprising the first portion of the route, and wherein generation of the first plurality of maneuver instructions occurs before generation of the second partial route begins.

Claim 36

Independent Claim 103 words

A method for determining a route from a first location to a second location using a vehicle navigation system, the method comprising the steps of: searching a map database thereby generating at least one route candidate, the map database comprising a first plurality of road segments; during the searching step, dynamically adjusting a cost associated with each of a second plurality of road segments to favor inclusion of a particular link class of road segment in the route, the second plurality of road segments comprising a subset of the first plurality of road segments; and selecting a best route candidate as the route.

Claim 37

Independent Claim 103 words

A method for determining a route from a first location to a second location using a vehicle navigation system, the method comprising the steps of: searching a map database thereby generating at least one route candidate, the map database comprising a first plurality of road segments; during the searching step, dynamically adjusting a cost associated with each of a second plurality of road segments to favor inclusion of a particular link class of road segment in the route, the second plurality of road segments comprising a subset of the first plurality of road segments; and selecting a best route candidate as the route.

Claim 38

Dependent Claim 64 words

The method of claim 27 wherein the cost associated with each of the second plurality of road segments comprises a heuristic cost which relates to the distance between the associated one of the second plurality of road segments and the second location, and a travel cost which relates to the time required to traverse the associated one of the second plurality of road segments.

Claim 39

Dependent Claim 28 words

The method of claim 28 wherein the step of dynamically adjusting the cost comprises adjusting the heuristic costs associated with each of the second plurality of road segments.

Claim 40

Dependent Claim 53 words

The method of claim 28 wherein the step of dynamically adjusting the cost comprises reducing the cost associated with each of the second plurality of road segments by a discount value, the discount value for each of the second plurality of road segments being determined with reference to the travel cost associated therewith.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2002-08-16	2003-02-15	2003-08-17	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2006-08-16	2007-02-15	2007-08-17	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2010-08-16	2011-02-15	2011-08-17	$7700.00	Window Closed / Lapsed

Route generation in a vehicle navigation system

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag