Patent US6678611B2 successfully refreshed from Google Patents.
US6678611B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for route calculation in a navigation application
Assignee: Here Global BV
•
Filing: 2002-09-27
•
Granted: 2004-01-13
•
Expires: 2022-09-27
Abstract
Abstract A program and method for route calculation for use with a navigation system and used with a map database that represents a road network in a geographic region. A route calculation program is adapted to find at least one solution route between a first location on a road network and a second location on the road network. The route calculation program includes a first search tree associated with the first location and a second search tree associated with the second location. Each search tree is adapted to hold gates. Each of the gates represents a physical position on the road network and a direction from the position to another location along a path on the road network. The route calculation program also includes at least one priority queue associated with one of the search trees. The priority queue assigns a priority to one of the gates in the associated search tree based upon an evaluation using a search algorithm. The gate identified as having a higher priority than any other gate in its respective search tree is expanded to determine one or more successor gates thereof. Each of these successor gates so formed is compared to the gates in the other search tree. The process of growing at least one of the search trees by expanding the gate in the search tree that has a higher priority than any other gate in the search tree is continued until a gate in one search tree corresponds to at least one gate in the other search tree.
Inventors
- 👤 Asta Khavakh
- 👤 William McDonough
- 👤 Oleg Voloshin
- 👤 Yaoguang Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:51
CPC Classifications
G; G01; G01C; G01C21/00; G01C21/26; G01C21/34; G01C21/3407; G01C21/3415; G01C21/343; G01C21/3446; G01C21/3453; G01C21/3492
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
188 words
A method of performing a rerouting function using a navigation system having a route calculation program that uses a map database that includes road segment records that represent portions of roads in a road network in a geographic region, comprising the steps of: after calculating a solution route from a first location in said geographic region to a second location in said geographic region, wherein said solution route is represented by a list of road segment records, storing an inbound search tree formed of a plurality of gates, wherein each gate represents a physical location on said road network and an accessible direction relative to said physical location, and wherein said plurality of gates in said inbound search tree represent segments of roads of said road network from which said second location is accessible, upon said navigation system having departed from the solution route, providing data representing a physical location of said navigation system; and growing said inbound search tree until at least one successor gate of the plurality of gates in said inbound search tree corresponds to said data representing the physical location of said navigation system.
Claim 2
Independent Claim
188 words
A method of performing a rerouting function using a navigation system having a route calculation program that uses a map database that includes road segment records that represent portions of roads in a road network in a geographic region, comprising the steps of: after calculating a solution route from a first location in said geographic region to a second location in said geographic region, wherein said solution route is represented by a list of road segment records, storing an inbound search tree formed of a plurality of gates, wherein each gate represents a physical location on said road network and an accessible direction relative to said physical location, and wherein said plurality of gates in said inbound search tree represent segments of roads of said road network from which said second location is accessible, upon said navigation system having departed from the solution route, providing data representing a physical location of said navigation system; and growing said inbound search tree until at least one successor gate of the plurality of gates in said inbound search tree corresponds to said data representing the physical location of said navigation system.
Claim 3
Dependent Claim
22 words
The method of claim 1 wherein each gate identifies an associated segment of a road by referring to a segment database ID.
Claim 4
Dependent Claim
18 words
The method of claim 1 wherein each gate identifies an associated segment of a road with a pointer.
Claim 5
Dependent Claim
20 words
The method of claim 1 wherein, in each gate, the accessible direction is reverse from a direction of vehicle travel.
Claim 6
Dependent Claim
16 words
The method of claim 1 wherein each gate also includes a reference to a predecessor gate.
Claim 7
Dependent Claim
42 words
The method of claim 1 further comprising: after calculating the solution route from the first location to the second location, augmenting the inbound search tree by adding thereto that portion of an outbound search tree that formed part of the solution route.
Claim 8
Dependent Claim
29 words
The method of claim 6 further comprising: maintaining in a memory of the navigation system the inbound search tree as augmented with the portion of the outbound search tree.
Claim 9
Dependent Claim
32 words
The method of claim 1 further comprising: providing a user of the navigation system with guidance for following a route to the second location from the physical location of the navigation system.
Claim 10
Dependent Claim
34 words
The method of claim 1 further comprising: prompting a user of the navigation system to indicate whether a new route should be calculated upon detection that the navigation system departed from the solution route.
Claim 11
Independent Claim
203 words
A method of providing an alternative route using a navigation system having a route calculation program that uses a map database that includes road segment records that represent portions of roads in a road network in a geographic region, wherein said alternative route has minimal overlap with an original solution route, the method comprising the steps of: after calculating the original solution route between a first location in said geographic region and a second location in said geographic region, wherein said solution route comprises a list of road segment records that was obtained by forming at least one search tree formed of a plurality of gates, wherein each gate represents a physical location on said road network and an accessible direction relative to said physical location, incrementing a weighting associated with each of said gates in said at least one search tree that corresponds to said list of road segment records that comprise said solution route, wherein a lower weighting favors inclusion of said gate relative to a higher weighting; growing the search tree by expanding gates to form successor gates; and evaluating which of said successor gates to select for further expansion using said incremented weighting until the alternate route is determined.
Claim 12
Independent Claim
203 words
A method of providing an alternative route using a navigation system having a route calculation program that uses a map database that includes road segment records that represent portions of roads in a road network in a geographic region, wherein said alternative route has minimal overlap with an original solution route, the method comprising the steps of: after calculating the original solution route between a first location in said geographic region and a second location in said geographic region, wherein said solution route comprises a list of road segment records that was obtained by forming at least one search tree formed of a plurality of gates, wherein each gate represents a physical location on said road network and an accessible direction relative to said physical location, incrementing a weighting associated with each of said gates in said at least one search tree that corresponds to said list of road segment records that comprise said solution route, wherein a lower weighting favors inclusion of said gate relative to a higher weighting; growing the search tree by expanding gates to form successor gates; and evaluating which of said successor gates to select for further expansion using said incremented weighting until the alternate route is determined.
Claim 13
Dependent Claim
11 words
The method of claim 10 wherein the weighting indicates traffic conditions.
Claim 14
Dependent Claim
22 words
The method of claim 10 wherein each gate identifies an associated segment of a road by referring to a segment database ID.
Claim 15
Dependent Claim
18 words
The method of claim 10 wherein each gate identifies an associated segment of a road with a pointer.
Claim 16
Dependent Claim
16 words
The method of claim 10 wherein each gate also includes a reference to a predecessor gate.
Claim 17
Dependent Claim
17 words
The method of claim 10 wherein the weighting is provided to the navigation system by wireless transmission.
Claim 18
Dependent Claim
19 words
The method of claim 10 wherein the weighting is provided to the navigation system from a traffic monitoring service.
References Cited (Backward Citations)
US4570227A
Cited
US4763270A
Cited
US4796189A
Cited
US4782447A
Cited
US4794528A
Cited
US4812990A
Cited
US4937753A
Cited
US5103400A
Cited
US5168452A
Cited
US4926336A
Cited
US5031104A
Cited
US5041983A
Cited
US5204817A
Cited
US5371678A
Cited
US5184303A
Cited
US5502640A
Cited
US5272638A
Cited
US5467276A
Cited
US5187667A
Cited
US5311434A
Cited
US5369588A
Cited
US5521826A
Cited
US5508930A
Cited
US5291412A
Cited
US5262775A
Cited
US5608635A
Cited
US5291413A
Cited
US5291414A
Cited
US5303159A
Cited
US5475387A
Cited
US5559511A
Cited
US5652706A
Cited
US5442349A
Cited
US5410485A
Cited
US5428545A
Cited
US5459667A
Cited
US5506774A
Cited
US5506779A
Cited
US5513110A
Cited
US5550538A
Cited
US5557522A
Cited
US5612881A
Cited
US5519619A
Cited
US5638280A
Cited
US5659476A
Cited
US5938720A
Cited
US6128571A
Cited
US5899955A
Cited
US6038509A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-01-12 | 2007-07-14 | 2008-01-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-01-12 | 2011-07-14 | 2012-01-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-01-12 | 2015-07-14 | 2016-01-13 | $7700.00 | Window Closed / Lapsed |