Predictive drop and load algorithm for an object-based geographical information system

• US 6,144,338 A
• Filed: 03/17/1998
• Issued: 11/07/2000
• Est. Priority Date: 03/17/1998
• Status: Expired due to Term

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: PRC Public Sector Incorporated
• Inventors: Davies, Frederick Bryan
• Primary Examiner(s): Blum, Theodore M.
• Application Number:
  US09/042,812
• Time in Patent Office: 966 Days
• Field of Search: 342/357.13, 701/209, 701/210
• US Class Current: 342/357.33
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01S 19/40 Correcting position, velocity or attitude
• CPC Class Codes: G01S 5/0072 Transmission between mobile stations, e.g. anti-collision systems

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. The method of claim 3, wherein said comparing the averaged position step is performed using a Kalman filter.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. The method of claim 15, further comprising the step of loading the fetched geometrical objects into a virtual blackboard.

17. 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.

18. The method of claim 17, wherein said drawing step is performed in real time.

19. 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.

20. The method of claim 19, wherein said drawing step is performed in real time.

21. The method of claim 10, wherein the tessellations are rectangular.

22. 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.

23. The method of claim 22, wherein said comparing the averaged position step is performed using a Kalman filter.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.