US6021372A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for calculating a best-route
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-08-08
•
Granted: 2000-02-01
•
Expires: 2017-08-08
Abstract
Abstract In a computer having a multithreaded operating system, a road-mapping program begins a best-route calculation in the background such that much of the calculation is completed before the user finishes providing inputs. In this manner, the user's perceived calculation time is shortened. The user is allowed to input any of a number of variables related to the best-route calculation. The calculation can be initiated without all of the variables necessary to finish it. The calculation is initiated upon the receipt of a predetermined variable, and predicts values for the unreceived variables. As each variable is received, the invention confirms that the predicted value for that variable is confirmed as correct. If the predicted value is incorrect, the calculation is restarted based on the actual value of that variable, in combination with predictions for the variables which have still not been received.
Inventors
- 👤 Paul Sean Harrington
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 17:00
CPC Classifications
G; G01; G01C; G01C21/00; G01C21/26; G01C21/34; G01C21/3446; G01C21/36; G01C21/3605; G01C21/3611; G01C21/3614
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
108 words
A method for calculating a best-route from one location to another location, the best-route calculation based on a plurality of variables, the method comprising the steps of: (a) initiating the best-route calculation based on a predicted value for a first variable in the plurality of variables; (b) receiving a user-input value corresponding to the predicted value and verifying that the predicted value for the first variable is correct by comparing the predicted value to the user-input value; (c) continuing the best-route calculation if the predicted value for the first variable is correct; and (d) reinitiating the best-route calculation if the predicted value for the first variable is incorrect.
Claim 2
Independent Claim
108 words
A method for calculating a best-route from one location to another location, the best-route calculation based on a plurality of variables, the method comprising the steps of: (a) initiating the best-route calculation based on a predicted value for a first variable in the plurality of variables; (b) receiving a user-input value corresponding to the predicted value and verifying that the predicted value for the first variable is correct by comparing the predicted value to the user-input value; (c) continuing the best-route calculation if the predicted value for the first variable is correct; and (d) reinitiating the best-route calculation if the predicted value for the first variable is incorrect.
Claim 3
Dependent Claim
19 words
The method of claim 1, wherein the initiating step further comprises assigning a predetermined value to the first variable.
Claim 4
Dependent Claim
12 words
The method of claim 2, wherein the predetermined value is a route-type.
Claim 5
Dependent Claim
34 words
The method of claim 2, wherein the predetermined value is a stored value maintained in a preferences file comprising values provided by a user, the stored value being a start point of a journey.
Claim 6
Dependent Claim
53 words
The method of claim 1, wherein the initiating step further comprises: (i) accepting a first input; and (ii) initiating the best-route calculation, in a background thread, with the first input as one of the variables in the best-route calculation, and the predicted value as another one of the variables in the best-route calculation.
Claim 7
Dependent Claim
16 words
The method of claim 5, wherein the first input is a starting location of a journey.
Claim 8
Dependent Claim
24 words
The method of claim 5, wherein the first input is an end point of a journey, and the predicted value is a route type.
Claim 9
Dependent Claim
20 words
The method of claim 5, wherein the initiating step comprises initiating a Shortest-Path Spanning Tree calculation in a background thread.
Claim 10
Dependent Claim
56 words
The method of claim 1, wherein the verifying step further comprises: (i) accepting a second input; (ii) comparing the second input to the predicted value; (iii) returning a value of "correct" if the second input matches the predicted value; and (iv) returning a value of "incorrect" if the second input does not match the predicted value.
Claim 11
Dependent Claim
13 words
The method of claim 9, wherein the second input is a route-type value.
Claim 12
Dependent Claim
47 words
The method of claim 9, wherein the reinitiating step further comprises the steps of: (i) terminating the best-route calculation; (ii) storing the results of the terminated best-route calculation; (iii) substituting the second input for the predicted value in the best-route calculation; and (iv) restarting the best-route calculation.
Claim 13
Dependent Claim
85 words
A computer-readable medium having computer-executable instructions for calculating a best route between two locations, comprising the steps of: (a) initiating the best-route calculation based on a predicted value for a first variable in the plurality of variables: (b) receiving a first user-input value corresponding to the predicted value and verifying that the predicted value for the first variable is correct by comparing the predicted value to the user-input value; and (c) continuing the best-route calculation if the predicted value for the first variable is correct.
Claim 14
Dependent Claim
85 words
A computer-readable medium having computer-executable instructions for calculating a best route between two locations, comprising the steps of: (a) initiating the best-route calculation based on a predicted value for a first variable in the plurality of variables: (b) receiving a first user-input value corresponding to the predicted value and verifying that the predicted value for the first variable is correct by comparing the predicted value to the user-input value; and (c) continuing the best-route calculation if the predicted value for the first variable is correct.
Claim 15
Dependent Claim
70 words
The computer-readable medium of claim 12, further comprising computer-executable instructions for performing the steps of: (d) receiving a second input; (e) determining if the best-route calculation has progressed to include the second input; (f) terminating the best-route calculation if the second user input is within the results of the current best-route calculation; (g) continuing the best-route calculation until it reaches the second user input, and then terminating the best-route calculation.
Claim 16
Dependent Claim
26 words
The computer-readable medium of claim 12, further comprising computer-executable instructions for performing the step of: (d) reinitiating the best-route calculation if the predicted value is incorrect.
Claim 17
Dependent Claim
134 words
A computer-readable medium on which is stored a computer program for calculating a best-route from one location to another location, the best-route calculation being based on a plurality of variables, the computer program comprising instructions which, when executed, perform the steps of: (a) accepting a first user input; (a) predicting a value for at least a first one of the plurality of variables; (b) initiating the best-route calculation, in background thread, based on the user input and the predicted value; (c) receiving a user-input value corresponding to the predicted value and verifying that the predicted value for the first variable is correct by comparing the predicted value to the user-input value; (d) continuing the best-route calculation if the predicted value is correct; and (e) reinitiating the best-route calculation if the predicted value is incorrect.
Claim 18
Dependent Claim
134 words
A computer-readable medium on which is stored a computer program for calculating a best-route from one location to another location, the best-route calculation being based on a plurality of variables, the computer program comprising instructions which, when executed, perform the steps of: (a) accepting a first user input; (a) predicting a value for at least a first one of the plurality of variables; (b) initiating the best-route calculation, in background thread, based on the user input and the predicted value; (c) receiving a user-input value corresponding to the predicted value and verifying that the predicted value for the first variable is correct by comparing the predicted value to the user-input value; (d) continuing the best-route calculation if the predicted value is correct; and (e) reinitiating the best-route calculation if the predicted value is incorrect.
Claim 19
Dependent Claim
32 words
The computer-readable medium of claim 15, wherein the verifying step further comprises: (i) accepting a second input from the user (ii) comparing the second input from the user to the predicted value.
Claim 20
Dependent Claim
39 words
The computer-readable medium of claim 16, wherein the reinitiating step further comprises: (i) storing the current results of the best-route calculation in memory; (ii) restarting the best-route calculation based on the first user input and the second user input.
Claim 21
Dependent Claim
170 words
A computer-readable medium having computer-executable modules, comprising: (a) a first program module for accepting a group of user inputs, the group of user inputs including at least a start point; (b) a second program module for calculating a best-route between two locations, by performing the steps of: (i) initiating the best-route calculation in a background thread based on at least one predicted value; (ii) verifying that the predicted value is correct, by performing the steps of: a. receiving a second user input in the group of user inputs from the first program module, the second user input corresponding to a route-type; b. verifying that the second user input matches the predicted value; c. continuing the best-route calculation if the second user input matches the predicted value; d. if the second user input does not match the predicted value, storing the current results of the best-route calculation and restarting the best-route calculation based on the second user input. (c) a third program module containing information upon which the best-route calculation operates.
Claim 22
Dependent Claim
170 words
A computer-readable medium having computer-executable modules, comprising: (a) a first program module for accepting a group of user inputs, the group of user inputs including at least a start point; (b) a second program module for calculating a best-route between two locations, by performing the steps of: (i) initiating the best-route calculation in a background thread based on at least one predicted value; (ii) verifying that the predicted value is correct, by performing the steps of: a. receiving a second user input in the group of user inputs from the first program module, the second user input corresponding to a route-type; b. verifying that the second user input matches the predicted value; c. continuing the best-route calculation if the second user input matches the predicted value; d. if the second user input does not match the predicted value, storing the current results of the best-route calculation and restarting the best-route calculation based on the second user input. (c) a third program module containing information upon which the best-route calculation operates.
Claim 23
Dependent Claim
34 words
The computer-readable medium of claim 18, wherein the first program module is a user interface which allows the user to provide inputs in response to the user interface prompting the user for the inputs.
Claim 24
Dependent Claim
14 words
The computer-readable medium of claim 19, wherein the user interface is a Route Wizard.
Claim 25
Dependent Claim
42 words
The computer-readable medium of claim 18, wherein the first program module is a user interface which allows the user to navigate a pointer controlled by an input device to a location in the user interface and select the location as an input.
Claim 26
Dependent Claim
16 words
The computer-readable medium of claim 18, wherein the third program module comprises a directed weighted graph.
References Cited (Backward Citations)
US4962458A
Cited
US5608635A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-31 | 2003-08-02 | 2004-02-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-31 | 2007-08-02 | 2008-02-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-31 | 2011-08-02 | 2012-02-01 | $7700.00 | Window Closed / Lapsed |