US6144338A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Predictive drop and load algorithm for an object-based geographical information system
Assignee: Northrop Grumman Systems Corp
•
Filing: 1998-03-17
•
Granted: 2000-11-07
•
Expires: 2018-03-17
Abstract
Abstract A method and system are disclosed for providing a more accurate position of a mobile receiver even though a signal received by the mobile receiver indicating the position of the mobile receiver is inaccurate. The received signal is used as an estimated indication of the position of the mobile receiver. A database comprises geometrical objects representing navigable routes. The geometrical objects include a geometry attribute defining the geometry of a complete representation of the navigable route. A geometrical object representing a navigable route is determined where the mobile receiver is probably located. The estimated position of the mobile receiver can then be compared against the geometry of the navigable route and against the previous positions in which the mobile receiver was located. The estimated position of the mobile receiver can be adjusted if necessary to provide a more probable position of the mobile receiver.
Inventors
- 👤 Frederick Bryan Davies
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:28
CPC Classifications
G; G01; G01S; G01S19/00; G01S19/38; G01S19/39; G01S19/40; G01C; G01C21/00; G01C21/20; G01S5/00; G01S5/0009; G01S5/0072
Claims Analysis
Total Claims: 39
Claim 1
Independent Claim
154 words
A method, comprising the steps of: receiving a signal at a mobile receiver; calculating an estimation of the current position of the mobile receiver within a topological region based upon the received signal; accessing one object-based database comprising geometrical objects representing navigable routes, each geometrical object comprising a topological region identifier attribute and a geometry attribute defining the geometry of a complete representation of the navigable route; determining a probable geometrical object representing a navigable route where the mobile receiver is probably located from among geometrical objects having a region identifier attribute associated with the topological region in the one database; and comparing the estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object.
Claim 2
Independent Claim
154 words
A method, comprising the steps of: receiving a signal at a mobile receiver; calculating an estimation of the current position of the mobile receiver within a topological region based upon the received signal; accessing one object-based database comprising geometrical objects representing navigable routes, each geometrical object comprising a topological region identifier attribute and a geometry attribute defining the geometry of a complete representation of the navigable route; determining a probable geometrical object representing a navigable route where the mobile receiver is probably located from among geometrical objects having a region identifier attribute associated with the topological region in the one database; and comparing the estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object.
Claim 3
Dependent Claim
41 words
The method of claim 1, wherein said signal comprises a plurality of GPS satellite signals wherein each of the signals includes errors to reduce the position accuracy of each of the signals and wherein the mobile receiver is a GPS receiver.
Claim 4
Dependent Claim
90 words
The method of claim 2, wherein said comparing step includes the steps of: averaging each signal over a period of time to compensate for a high frequency noise from said plurality of GPS satellite signals and outputting an averaged signal, the averaged signal including a low frequency noise; computing an averaged position of the mobile GPS receiver from the averaged signal; comparing the averaged position to the nearest position that would coincide with a portion of the nearest navigable route represented by a geometrical object to obtain a probable position.
Claim 5
Dependent Claim
47 words
The method of claim 1, comprising maintaining a history of previous probable positions over a period of time and wherein said comparing step includes the step of comparing the probable position to previous probable positions and determining whether the probable position is consistent with previous probable positions.
Claim 6
Dependent Claim
38 words
The method of claim 1, comprising maintaining a history of the previous nearest navigable route represented by a geometrical object and wherein said comparing step includes the step of comparing the navigable route to the previous navigable route.
Claim 7
Dependent Claim
36 words
The method of claim 1, wherein said comparing step includes the step of computing the nearest navigable route by calculating a shortest perpendicular distance between the estimated position and nearby navigable routes represented by geometrical objects.
Claim 8
Dependent Claim
18 words
The method of claim 3, wherein said comparing the averaged position step is performed using a Kalman filter.
Claim 9
Dependent Claim
25 words
The method of claim 1, wherein the geometrical objects represent constrained navigable routes such as roads, streets, sea channels, navigation channels and air corridor routes.
Claim 10
Independent Claim
354 words
A method, comprising the steps of: receiving a signal at a mobile receiver; calculating an estimation of the current position of the mobile receiver based upon the received signal; accessing one object-based database comprising geometrical objects representing topological features and navigable routes, each geometrical object comprising a tessellation identifier attribute and a geometry attribute defining the geometry of a complete representation of the topological feature or navigable route, the topology being divided into a plurality of tessellations; determining a probable geometrical object representing a navigable route where the mobile receiver is probably located and determining a tessellation associated with the determined geometrical object; fetching geometrical objects having a tessellation identifier attribute associated with the determined tessellation from the one database and geometrical objects associated with three additional tessellations adjacent to the determined tessellation wherein the four fetched tessellations form a 2×2 array; loading the fetched geometrical objects into a virtual blackboard; comparing the estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object; drawing topological features using the fetched geometrical objects and drawing a representation of the mobile receiver in the probable position on the display; and continually determining the probable position of the mobile receiver and as the mobile receiver changes its probable position and crosses a boundary between the determined tessellation and an unloaded adjacent tessellation and performing the further steps of: unloading two of the loaded tessellations from the virtual blackboard; fetching geometrical objects having a tessellation identifier associated with two additional unloaded tessellations adjacent to the determined tessellation; loading the fetched geometrical objects of the two additional tessellations into the virtual blackboard, one of which is the tessellation in which the mobile receiver is located; drawing topological features using the fetched geometrical objects of the loaded adjacent tessellation in which the mobile receiver is located and drawing a representation of the mobile receiver in the probable position on the display.
Claim 11
Independent Claim
354 words
A method, comprising the steps of: receiving a signal at a mobile receiver; calculating an estimation of the current position of the mobile receiver based upon the received signal; accessing one object-based database comprising geometrical objects representing topological features and navigable routes, each geometrical object comprising a tessellation identifier attribute and a geometry attribute defining the geometry of a complete representation of the topological feature or navigable route, the topology being divided into a plurality of tessellations; determining a probable geometrical object representing a navigable route where the mobile receiver is probably located and determining a tessellation associated with the determined geometrical object; fetching geometrical objects having a tessellation identifier attribute associated with the determined tessellation from the one database and geometrical objects associated with three additional tessellations adjacent to the determined tessellation wherein the four fetched tessellations form a 2×2 array; loading the fetched geometrical objects into a virtual blackboard; comparing the estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object; drawing topological features using the fetched geometrical objects and drawing a representation of the mobile receiver in the probable position on the display; and continually determining the probable position of the mobile receiver and as the mobile receiver changes its probable position and crosses a boundary between the determined tessellation and an unloaded adjacent tessellation and performing the further steps of: unloading two of the loaded tessellations from the virtual blackboard; fetching geometrical objects having a tessellation identifier associated with two additional unloaded tessellations adjacent to the determined tessellation; loading the fetched geometrical objects of the two additional tessellations into the virtual blackboard, one of which is the tessellation in which the mobile receiver is located; drawing topological features using the fetched geometrical objects of the loaded adjacent tessellation in which the mobile receiver is located and drawing a representation of the mobile receiver in the probable position on the display.
Claim 12
Independent Claim
196 words
A method, comprising the steps of: receiving a signal at a mobile receiver; calculating an estimation of the current position of the mobile receiver based upon the received signal; accessing one object-based database comprising geometrical objects representing topological features and navigable routes, each geometrical object comprising a tessellation identifier attribute and a geometry attribute defining the geometry of a complete representation of the topological feature or navigable route, the topology being divided into a plurality of tessellations; determining a probable geometrical object representing a navigable route where the mobile receiver is probably located and determining a tessellation associated with the determined geometrical object; fetching geometrical objects having a tessellation identifier attribute associated with the determined tessellation from the one database; comparing the estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object; and drawing topological features using the fetched geometrical objects and drawing a representation of the mobile receiver in the probable position on the display.
Claim 13
Independent Claim
196 words
A method, comprising the steps of: receiving a signal at a mobile receiver; calculating an estimation of the current position of the mobile receiver based upon the received signal; accessing one object-based database comprising geometrical objects representing topological features and navigable routes, each geometrical object comprising a tessellation identifier attribute and a geometry attribute defining the geometry of a complete representation of the topological feature or navigable route, the topology being divided into a plurality of tessellations; determining a probable geometrical object representing a navigable route where the mobile receiver is probably located and determining a tessellation associated with the determined geometrical object; fetching geometrical objects having a tessellation identifier attribute associated with the determined tessellation from the one database; comparing the estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object; and drawing topological features using the fetched geometrical objects and drawing a representation of the mobile receiver in the probable position on the display.
Claim 14
Dependent Claim
41 words
The method of claim 10, wherein said signal comprises a plurality of GPS satellite signals wherein each of the signals includes errors to reduce the position accuracy of each of the signals and wherein the mobile receiver is a GPS receiver.
Claim 15
Dependent Claim
47 words
The method of claim 10, comprising maintaining a history of previous probable positions over a period of time and wherein said comparing step includes the step of comparing the probable position to previous probable positions and determining whether the probable position is consistent with previous probable positions.
Claim 16
Dependent Claim
38 words
The method of claim 10, comprising maintaining a history of the previous nearest navigable route represented by a geometrical object and wherein said comparing step includes the step of comparing the navigable route to the previous navigable route.
Claim 17
Dependent Claim
36 words
The method of claim 10, wherein said comparing step includes the step of computing the nearest navigable route by calculating a shortest perpendicular distance between the estimated position and nearby navigable routes represented by geometrical objects.
Claim 18
Dependent Claim
36 words
The method of claim 10, further comprising the step of fetching geometrical objects having a tessellation identifier associated with three additional tessellations adjacent to the determined tessellation wherein the four fetched tessellations form a 2×2 array.
Claim 19
Dependent Claim
19 words
The method of claim 15, further comprising the step of loading the fetched geometrical objects into a virtual blackboard.
Claim 20
Dependent Claim
76 words
The method of claim 16, further comprising the step of continually determining the probable position of the mobile GPS receiver and as the mobile GPS receiver changes its probable position and crosses a boundary between the determined tessellation and a loaded adjacent tessellation performing the further step of drawing topological features using the fetched geometrical objects of the loaded adjacent tessellation and drawing a representation of the GPS receiver in the probable position on the display.
Claim 21
Dependent Claim
14 words
The method of claim 17, wherein said drawing step is performed in real time.
Claim 22
Dependent Claim
138 words
The method of claim 16, further comprising the step of continually determining the probable position of the mobile GPS receiver and as the mobile GPS receiver changes its probable position and crosses a boundary between the determined tessellation and an unloaded adjacent tessellation performing the further steps of: unloading two of the loaded tessellations from the virtual blackboard; fetching geometrical objects having a tessellation identifier associated with two additional unloaded tessellations adjacent to the determined tessellation; loading the fetched geometrical objects of the two additional tessellations into the virtual blackboard, one of which is the tessellation in which the GPS receiver is located; drawing topological features using the fetched geometrical objects of the loaded adjacent tessellation in which the GPS receiver is located and drawing a representation of the GPS receiver in the probable position on the display.
Claim 23
Dependent Claim
14 words
The method of claim 19, wherein said drawing step is performed in real time.
Claim 24
Dependent Claim
10 words
The method of claim 10, wherein the tessellations are rectangular.
Claim 25
Dependent Claim
91 words
The method of claim 11, wherein said comparing step includes the steps of: averaging each signal over a period of time to compensate for a high frequency noise from said plurality of GPS satellite signals and outputting an averaged signal, the averaged signal including a low frequency noise; computing an averaged position of the mobile GPS receiver from the averaged signal; comparing the averaged position to the nearest position that would coincide with a portion of the nearest navigable route represented by a geometrical object to obtain a current probable position.
Claim 26
Dependent Claim
18 words
The method of claim 22, wherein said comparing the averaged position step is performed using a Kalman filter.
Claim 27
Dependent Claim
25 words
The method of claim 10, wherein the geometrical objects represent constrained navigable routes such as roads, streets, sea channels, navigation channels and air corridor routes.
Claim 28
Dependent Claim
159 words
An article, comprising: at least one sequence of machine executable instructions; a medium bearing the executable instructions in machine readable form, wherein execution of the instructions by one or more processors causes the one or more processors to: access at least one object-based database comprising geometrical objects representing navigable routes, each geometrical object comprising a topological region identifier attribute and a geometry attribute defining the geometry of a complete representation of the navigable route; determine a probable geometrical object representing a navigable route where a mobile receiver is probably located from among geometrical objects having a region identifier attribute associated with a topological region in the at least one database; and compare an estimated position of the mobile receiver to the probable geometrical object and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object.
Claim 29
Dependent Claim
159 words
An article, comprising: at least one sequence of machine executable instructions; a medium bearing the executable instructions in machine readable form, wherein execution of the instructions by one or more processors causes the one or more processors to: access at least one object-based database comprising geometrical objects representing navigable routes, each geometrical object comprising a topological region identifier attribute and a geometry attribute defining the geometry of a complete representation of the navigable route; determine a probable geometrical object representing a navigable route where a mobile receiver is probably located from among geometrical objects having a region identifier attribute associated with a topological region in the at least one database; and compare an estimated position of the mobile receiver to the probable geometrical object and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object.
Claim 30
Dependent Claim
209 words
An article comprising: at least one sequence of machine executable instructions; a medium bearing the executable instructions in machine readable form, wherein execution of the instructions by one or more processors causes the one or more processors to: access at least one object-based database comprising geometrical objects representing topological features and navigable routes, each geometrical object comprising a tessellation identifier attribute and a geometry attribute defining the geometry of a complete representation of the topological feature or navigable route, the topology being divided into a plurality of tessellations; determine a probable geometrical object representing a navigable route where a mobile receiver is probably located and determining a tessellation associated with the determined geometrical object; fetch geometrical objects having a tessellation identifier attribute associated with the determined tessellation from the at least one database; compare the estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object; and draw topological features using the fetched geometrical objects and draw a representation of the mobile receiver in the probable position on a display.
Claim 31
Dependent Claim
209 words
An article comprising: at least one sequence of machine executable instructions; a medium bearing the executable instructions in machine readable form, wherein execution of the instructions by one or more processors causes the one or more processors to: access at least one object-based database comprising geometrical objects representing topological features and navigable routes, each geometrical object comprising a tessellation identifier attribute and a geometry attribute defining the geometry of a complete representation of the topological feature or navigable route, the topology being divided into a plurality of tessellations; determine a probable geometrical object representing a navigable route where a mobile receiver is probably located and determining a tessellation associated with the determined geometrical object; fetch geometrical objects having a tessellation identifier attribute associated with the determined tessellation from the at least one database; compare the estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object; and draw topological features using the fetched geometrical objects and draw a representation of the mobile receiver in the probable position on a display.
Claim 32
Dependent Claim
134 words
A computer architecture, comprising: accessing means for accessing at least one object-based database comprising geometrical objects representing navigable routes, each geometrical object comprising a topological region identifier attribute and a geometry attribute defining the geometry of a complete representation of the navigable route; determining means for determining a probable geometrical object representing a navigable route where a mobile receiver is probably located from among geometrical objects having a region identifier attribute associated with a topological region in the at least one database; and comparing means for comparing the estimated position of the mobile receiver to a probable geometrical object and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object.
Claim 33
Dependent Claim
134 words
A computer architecture, comprising: accessing means for accessing at least one object-based database comprising geometrical objects representing navigable routes, each geometrical object comprising a topological region identifier attribute and a geometry attribute defining the geometry of a complete representation of the navigable route; determining means for determining a probable geometrical object representing a navigable route where a mobile receiver is probably located from among geometrical objects having a region identifier attribute associated with a topological region in the at least one database; and comparing means for comparing the estimated position of the mobile receiver to a probable geometrical object and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object.
Claim 34
Dependent Claim
184 words
A computer architecture comprising: accessing means for accessing at least one object-based database comprising geometrical objects representing topological features and navigable routes, each geometrical object comprising a tessellation identifier attribute and a geometry attribute defining the geometry of a complete representation of the topological feature or navigable route, the topology being divided into a plurality of tessellations; determining means for determining a probable geometrical object representing a navigable route where the mobile receiver is probably located and determining a tessellation associated with the determined geometrical object; fetching means for fetching geometrical objects having a tessellation identifier attribute associated with the determined tessellation from the at least one database; comparing the estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object; and drawing topological features using the fetched geometrical objects and drawing a representation of the mobile receiver in the probable position on a display.
Claim 35
Dependent Claim
184 words
A computer architecture comprising: accessing means for accessing at least one object-based database comprising geometrical objects representing topological features and navigable routes, each geometrical object comprising a tessellation identifier attribute and a geometry attribute defining the geometry of a complete representation of the topological feature or navigable route, the topology being divided into a plurality of tessellations; determining means for determining a probable geometrical object representing a navigable route where the mobile receiver is probably located and determining a tessellation associated with the determined geometrical object; fetching means for fetching geometrical objects having a tessellation identifier attribute associated with the determined tessellation from the at least one database; comparing the estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object; and drawing topological features using the fetched geometrical objects and drawing a representation of the mobile receiver in the probable position on a display.
Claim 36
Dependent Claim
158 words
A computer system comprising: a processor; and a memory coupled to said processor, the memory having stored therein sequences of instructions, which, when executed by said processor, cause said processor to perform the steps of: accessing at least one object-based database comprising geometrical objects representing navigable routes, each geometrical object comprising a topological region identifier attribute and a geometry attribute defining the geometry of a complete representation of the navigable route; determining a probable geometrical object representing a navigable route where a mobile receiver is probably located from among geometrical objects having a region identifier attribute associated with a topological region in the one database; and comparing an estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object.
Claim 37
Dependent Claim
158 words
A computer system comprising: a processor; and a memory coupled to said processor, the memory having stored therein sequences of instructions, which, when executed by said processor, cause said processor to perform the steps of: accessing at least one object-based database comprising geometrical objects representing navigable routes, each geometrical object comprising a topological region identifier attribute and a geometry attribute defining the geometry of a complete representation of the navigable route; determining a probable geometrical object representing a navigable route where a mobile receiver is probably located from among geometrical objects having a region identifier attribute associated with a topological region in the one database; and comparing an estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object.
Claim 38
Dependent Claim
206 words
A computer system comprising: a processor; and a memory coupled to said processor, the memory having stored therein sequences of instructions, which, when executed by said processor, cause said processor to perform the steps of: accessing at least one object-based database comprising geometrical objects representing topological features and navigable routes, each geometrical object comprising a tessellation identifier attribute and a geometry attribute defining the geometry of a complete representation of the topological feature or navigable route, the topology being divided into a plurality of tessellations; determining a probable geometrical object representing a navigable route where a mobile receiver is probably located and determining a tessellation associated with the determined geometrical object; fetching geometrical objects having a tessellation identifier attribute associated with the determined tessellation from the at least one database; comparing an estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object; and drawing topological features using the fetched geometrical objects and drawing a representation of the mobile receiver in the probable position on a display.
Claim 39
Dependent Claim
206 words
A computer system comprising: a processor; and a memory coupled to said processor, the memory having stored therein sequences of instructions, which, when executed by said processor, cause said processor to perform the steps of: accessing at least one object-based database comprising geometrical objects representing topological features and navigable routes, each geometrical object comprising a tessellation identifier attribute and a geometry attribute defining the geometry of a complete representation of the topological feature or navigable route, the topology being divided into a plurality of tessellations; determining a probable geometrical object representing a navigable route where a mobile receiver is probably located and determining a tessellation associated with the determined geometrical object; fetching geometrical objects having a tessellation identifier attribute associated with the determined tessellation from the at least one database; comparing an estimated position of the mobile receiver to the probable geometrical object representing a navigable route and if the estimated position differs from a position coinciding with a portion of the probable geometrical object, adjusting the estimated position to a probable position coinciding with a portion of the probable geometrical object; and drawing topological features using the fetched geometrical objects and drawing a representation of the mobile receiver in the probable position on a display.
References Cited (Backward Citations)
US4899293A
Cited
US5337404A
Cited
US5367615A
Cited
US5475802A
Cited
US5488684A
Cited
US5381338A
Cited
US5426780A
Cited
US5357599A
Cited
US5519392A
Cited
US5604892A
Cited
US5455897A
Cited
US5412573A
Cited
US5631970A
Cited
US5499371A
Cited
US5467441A
Cited
US6006158A
Cited
US5528518A
Cited
US5870686A
Cited
US5968109A
Cited
US5986663A
Cited
US5949425A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-07 | 2004-05-08 | 2004-11-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-07 | 2008-05-08 | 2008-11-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-07 | 2012-05-08 | 2012-11-07 | $7700.00 | Window Closed / Lapsed |