US6038509A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System for recalculating a path
Assignee: TomTom North America Inc
•
Filing: 1998-01-22
•
Granted: 2000-03-14
•
Expires: 2018-01-22
Abstract
Abstract A typical pathfinding system provides a user with a set of directions for following a path from an origin to a destination in a network. If the user deviates from the path, the system for recalculating a path determines a new path which directs the user from the user's new location, which is off the original path, to the destination. To decrease the amount of time needed to determine the new path to the destination, the system adds links to the network. Each of the added links connect nodes from the original path directly to the destination. A new path is determined from the new location to the destination using the augmented network.
Inventors
- 👤 Richard Frederick Poppen
- 👤 Rodney Jude Fernandez
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 08:35
CPC Classifications
G; G01; G01C; G01C21/00; G01C21/26; G01C21/34; G01C21/3407; G01C21/3415; G01C21/3446
Claims Analysis
Total Claims: 57
Claim 1
Independent Claim
102 words
A method of finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising the steps of: augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and determining said new path from said new origin to said destination using said electronic representation of said network with said new links.
Claim 2
Independent Claim
102 words
A method of finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising the steps of: augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and determining said new path from said new origin to said destination using said electronic representation of said network with said new links.
Claim 3
Dependent Claim
42 words
A method according to claim 1, wherein: said electronic representation of said network being stored in a first set of one or more processor readable files and said new links stored in a second set of one or more processor readable files.
Claim 4
Dependent Claim
22 words
A method according to claim 1, further including the step of: editing said new path to only include travel along original links.
Claim 5
Dependent Claim
15 words
A method according to claim 1, further including the step of: reporting said new path.
Claim 6
Dependent Claim
15 words
A method according to claim 1, further including the step of: determining said new origin.
Claim 7
Dependent Claim
31 words
A method according to claim 5, wherein: said step of determining said new origin estimates said new origin to be a location where a user will be at a future time.
Claim 8
Dependent Claim
16 words
A method according to claim 1, wherein: said subset of said original nodes being rejoining nodes.
Claim 9
Dependent Claim
31 words
A method according to claim 1, wherein: said step of augmenting includes identifying rejoining nodes, each of said new links being connected from one of said rejoining nodes to said destination.
Claim 10
Dependent Claim
31 words
A method according to claim 1, wherein: each node of said subset of said original nodes does not have a direct link to said destination prior to said step of augmenting.
Claim 11
Dependent Claim
41 words
A method according to claim 1, wherein: each node of said subset of said original nodes does not have a direct link to said destination prior to said step of augmenting and is within a predetermined distance from said new origin.
Claim 12
Dependent Claim
39 words
A method according to claim 1, wherein: said subset being defined to include original nodes having a lower bounds which is less than any upper bounds of original nodes that do not have a link directly to said destination.
Claim 13
Dependent Claim
61 words
A method according to claim 1, further including the step of: receiving operator input, wherein said deviation from said original path occurring after travel to a first node and before travel to a second node and said step of determining said new path does not utilize a link representing a path to said second node in response to said operator input.
Claim 14
Dependent Claim
44 words
A method according to claim 1, wherein: an original node having an original link directly to said destination and not being visited prior to said deviation has a corresponding costs for traversing said original link; said step of augmenting includes editing said corresponding cost.
Claim 15
Dependent Claim
18 words
A method according to claim 1, wherein: said step of augmenting includes assigning costs to said new links.
Claim 16
Dependent Claim
48 words
A method according to claim 14, wherein: each new link being associated with an original node; and said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path.
Claim 17
Dependent Claim
12 words
A method according to claim 15, wherein: said cost is travel time.
Claim 18
Dependent Claim
11 words
A method according to claim 15, wherein: said cost is distance.
Claim 19
Dependent Claim
13 words
A method according to claim 15, wherein: said constant is equal to one.
Claim 20
Dependent Claim
26 words
A method according to claim 15, wherein: said constant is greater than or equal to zero; and said constant is less than or equal to one.
Claim 21
Dependent Claim
23 words
A method according to claim 15, further including the steps of receiving operator input; and determining said constant based on said operator input.
Claim 22
Dependent Claim
16 words
A method according to claim 1, wherein: said step of augmenting includes removing an original link.
Claim 23
Dependent Claim
27 words
A method according to claim 21, further including the step of: receiving operator input, said step of removing an original link being based on said operator input.
Claim 24
Dependent Claim
125 words
A method according to claim 1, further including the steps of: identifying rejoining nodes, each of said new links being connected from one of said rejoining nodes to said destination; editing said new path to only include travel along original links; and reporting said new path; wherein said electronic representation of a network is an electronic map, said step of augmenting includes assigning costs to said new links, each new link being associated with an original node, said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path, and said constant is greater than or equal to zero and less than or equal to one.
Claim 25
Dependent Claim
17 words
A method according to claim 1, wherein: said electronic representation of a network is an electronic map.
Claim 26
Dependent Claim
22 words
A method according to claim 24, further including the step of: editing said new path to only include travel along original links.
Claim 27
Dependent Claim
18 words
A method according to claim 24, wherein: said step of augmenting includes assigning costs to said new links.
Claim 28
Dependent Claim
48 words
A method according to claim 26, wherein: each new link being associated with an original node; and said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path.
Claim 29
Independent Claim
144 words
A method of finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising the steps of: augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and determining said new path from said new origin to said destination using said electronic representation of said network with said new links, said deviation from said original path occurring after travel to a first node and before travel to a second nodes, said step of determining said new path does not utilize a link representing travel from said first node to said second node.
Claim 30
Independent Claim
144 words
A method of finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising the steps of: augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and determining said new path from said new origin to said destination using said electronic representation of said network with said new links, said deviation from said original path occurring after travel to a first node and before travel to a second nodes, said step of determining said new path does not utilize a link representing travel from said first node to said second node.
Claim 31
Dependent Claim
132 words
A processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable program code for programming a processor to perform a method for finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, said method comprising the steps of: augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and determining said new path from said new origin to said destination using said electronic representation of said network with said new links.
Claim 32
Dependent Claim
132 words
A processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable program code for programming a processor to perform a method for finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, said method comprising the steps of: augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and determining said new path from said new origin to said destination using said electronic representation of said network with said new links.
Claim 33
Dependent Claim
28 words
A processor readable storage medium according to claim 29, wherein, said method further includes the step of: editing said new path to only include travel along original links.
Claim 34
Dependent Claim
21 words
A processor readable storage medium according to claim 29, wherein, said method further includes the step of: reporting said new path.
Claim 35
Dependent Claim
21 words
A processor readable storage medium according to claim 29, wherein, said method further includes the step of: determining said new origin.
Claim 36
Dependent Claim
34 words
A processor readable storage medium according to claim 29, wherein: each node of said subset of said original nodes does not have a direct link to said destination prior to said step of augmenting.
Claim 37
Dependent Claim
44 words
A processor readable storage medium according to claim 29, wherein: each node of said subset of said original nodes does not have a direct link to said destination prior to said step of augmenting and is within a predetermined distance from said new origin.
Claim 38
Dependent Claim
42 words
A processor readable storage medium according to claim 29, wherein: said subset being defined to include original nodes having a lower bounds which is less than any upper bounds of original nodes that do not have a link directly to said destination.
Claim 39
Dependent Claim
67 words
A processor readable storage medium according to claim 29, wherein, said method further includes the step of: receiving operator input, wherein said deviation from said original path occurring after travel to a first node and before travel to a second node and said step of determining said new path does not utilize a link representing a path to said second node in response to said operator input.
Claim 40
Dependent Claim
21 words
A processor readable storage medium according to claim 29, wherein: said step of augmenting includes assigning costs to said new links.
Claim 41
Dependent Claim
51 words
A processor readable storage medium according to claim 37, wherein: each new link being associated with an original node; and said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path.
Claim 42
Dependent Claim
20 words
A processor readable storage medium according to claim 29, wherein: said electronic representation of a network is an electronic map.
Claim 43
Dependent Claim
121 words
A processor readable storage medium according to claim 39, wherein, said method further includes the steps of: identifying rejoining nodes, each of said new links being connected from one of said rejoining nodes to said destination, editing said new path to only include travel along original links; and reporting said new path; wherein said step of augmenting includes assigning costs to said new links, each new link being associated with an original node, said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path, and said constant is greater than or equal to zero and less than or equal to one.
Claim 44
Dependent Claim
28 words
A processor readable storage medium according to claim 39, wherein, said method further includes the step of: editing said new path to only include travel along original links.
Claim 45
Dependent Claim
21 words
A processor readable storage medium according to claim 39, wherein: said step of determining includes assigning costs to said new links.
Claim 46
Dependent Claim
51 words
A processor readable storage medium according to claim 39, wherein: each new link being associated with an original node; and said assigned cost for a particular new link being equal to a constant multiplied by a cost of traveling between said associated original node and said destination along said original path.
Claim 47
Independent Claim
103 words
A system for finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising: means for augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and means for determining said new path from said new origin to said destination using said electronic representation of said network with said new links.
Claim 48
Independent Claim
103 words
A system for finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising: means for augmenting said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination; and means for determining said new path from said new origin to said destination using said electronic representation of said network with said new links.
Claim 49
Dependent Claim
24 words
A system according to claim 44, further including: means for reporting said new path, said electronic representation of said network being an electronic map.
Claim 50
Independent Claim
131 words
A system for finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising: one or more processor readable storage mediums for storing said electronic representation of said network; and a processor, in communication with said one or more processor readable mediums, said processor programmed to: augment said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination, and determine said new path from said new origin to said destination using said electronic representation of said network with said new links.
Claim 51
Independent Claim
131 words
A system for finding a new path from a new origin to a destination in a network using an electronic representation of said network after a deviation from an original path to said destination, said original path including original nodes and original links, comprising: one or more processor readable storage mediums for storing said electronic representation of said network; and a processor, in communication with said one or more processor readable mediums, said processor programmed to: augment said electronic representation of said network by adding new links to said electronic representation of said network, said new links directly connecting a subset of said original nodes to said destination, and determine said new path from said new origin to said destination using said electronic representation of said network with said new links.
Claim 52
Dependent Claim
17 words
A system according to claim 46, wherein: said electronic representation of said network is an electronic map.
Claim 53
Dependent Claim
20 words
A system according to claim 47, further including: a display, in communication with said processor, for reporting said new path.
Claim 54
Dependent Claim
23 words
A system according to claim 47, wherein: said processor further programmed to edit said new path to only include travel along original links.
Claim 55
Dependent Claim
31 words
A system according to claim 47, wherein: each node of said subset of said original nodes does not have a direct link to said destination prior to adding said new links.
Claim 56
Dependent Claim
46 words
A system according to claim 47, wherein: said deviation from said original path occurring after travel to a first node and before travel to a second node; and said new path does not include a link representing travel from said first node to said second node.
Claim 57
Dependent Claim
18 words
A system according to claim 47, wherein: said processor further programmed to assign costs to said new links.
References Cited (Backward Citations)
US5303159A
Cited
US5652706A
Cited
US5774073A
Cited
US5752217A
Cited
US5878368A
Cited
US5893081A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-14 | 2003-09-13 | 2004-03-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-14 | 2007-09-13 | 2008-03-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-14 | 2011-09-13 | 2012-03-14 | $7700.00 | Window Closed / Lapsed |