Systems and methods for navigation using cross correlation on evidence grids

• US 8,855,911 B2
• Filed: 12/09/2010
• Issued: 10/07/2014
• Est. Priority Date: 12/09/2010
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Ma, Yunqian, McKitterick, John B., Hawkinson, Wesley J.
• Primary Examiner(s): Holloway, Jason
• Assistant Examiner(s): Bendidi, Rachid
• Application Number:
  US12/963,893
• Publication Number:
  US 20120150441A1
• Time in Patent Office: 1,398 Days
• Field of Search: 701/400, 701/408, 701/409, 701/445, 701/454, 701/455, 701/466, 701/467, 701/469, 701/482, 701/500, 701/505, 701/509, 701/510, 701/532, 701/533
• US Class Current: 701/400
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01S 5/16 using electromagnetic waves other than radio waves

Abstract

Systems and methods for navigation using cross correlation on evidence grids are provided. In one embodiment, a system for using cross-correlated evidence grids to acquire navigation information comprises: a navigation processor coupled to an inertial measurement unit, the navigation processor configured to generate a navigation solution; a sensor configured to scan an environment; an evidence grid creator coupled to the sensor and the navigation processor, wherein the evidence grid creator is configured to generate a current evidence grid based on data received from the sensor and the navigation solution; a correlator configured to correlate the current evidence grid against a historical evidence grid stored in a memory to produce displacement information; and where the navigation processor receives correction data derived from correlation of evidence grids and adjusts the navigation solution based on the correction data.

Claims

1. A method for acquiring navigation information, the method comprising:

calculating a navigation solution, with a navigation processor, from motion information received from an inertial measurement unit;

scanning an environment with a sensor;

creating a current evidence grid based on data received from scanning the environment and the navigation solution, wherein an evidence grid represents the environment with a collection of cells, where each cell has a probability that an associated location in the environment is occupied by a feature;

correlating the current evidence grid against a historical evidence grid to find a matching position and produce displacement information, wherein correlating the current evidence grid against a historical evidence grid comprises performing one or more translations or rotations to align the current evidence grid and the historical evidence grid; and

correcting the navigation solution based on the displacement information.

2. The method of claim 1, wherein correcting the navigation solution further comprises:

updating a Kalman filter with information derived from the displacement information.

3. The method of claim 1, wherein creating a current evidence grid further comprises marking voxels of the current evidence grid to represent features of the environment captured by the sensor.

4. The method of claim 3, wherein positions of features of the environment are binary encoded within the current evidence grid.

5. The method of claim 3, wherein positions of features of the environment are probabilistically encoded within the current evidence grid.

6. The method of claim 1, wherein correlating the current evidence grid against a historical evidence grid comprises performing one or more translations or rotations to identify a matching position based on when the current evidence grid and the historical evidence grid are maximally correlated.

7. The method of claim 1, wherein creating the current evidence grid comprises:

scanning the environment with a sensor; and

encoding a set of data received from the sensor within an evidence grid.

8. The method of claim 1, wherein scanning the environment with a sensor comprises performing a plurality of scans of the current environment.

9. The method of claim 1, wherein correlating the current evidence grid against a historical evidence grid further comprises:

identifying a neighborhood of possible evidence grid translations and rotations, wherein the neighborhood defines a range of translations and rotations through which the current evidence grid and the historical evidence grid are translated and rotated; and

translating and rotating the current evidence grid and the historical evidence grid within the neighborhood.

10. The method of claim 1, further comprising:

transmitting a displacement record to a Kalman filter, wherein the displacement record contains the displacement information; and

updating a navigation processor with information received from the Kalman filter, wherein the navigation processor receives motion information from an inertial measurement unit and provides a navigation solution for a navigation system.

11. A system for correcting errors in an inertial navigation system, the system comprising

a navigation processor configured to provide a navigation solution;

a sensor configured to scan an environment

an evidence grid creator configured to create a current evidence grid based on data received from the sensor and the navigation solution, wherein an evidence grid represents a collection of cells in the environment, where each cell has a probability that the cell is occupied by a feature in the environment;

a correlator configured to correlate the current evidence grid against a historical evidence grid stored in memory to find a matching position and produce displacement information, wherein the correlator performs one or more translations or rotations to align the current evidence grid and the historical evidence grid; and

a measurement unit configured to correct the navigation solution based on the displacement information.

12. The system of claim 11 further comprising a Kalman filter configured to update the navigation solution.

13. The system of claim 11, further comprising a neighborhood identifier configured to identify a neighborhood of possible evidence grid translations and rotations, wherein the neighborhood defines a range of translations and rotations through which the current evidence grid and the historical evidence grid are to be translated and rotated.

14. A system for using cross-correlated evidence grids to acquire navigation information, the system comprising:

a navigation processor coupled to an inertial measurement unit, the navigation processor configured to generate a navigation solution;

a sensor configured to scan an environment;

an evidence grid creator coupled to the sensor and the navigation processor, wherein the evidence grid creator is configured to generate a current evidence grid based on data received from the sensor and the navigation solution, wherein an evidence grid represents a collection of cells in the environment, where each cell has a probability that the cell is occupied by a feature in the environment;

a correlator configured to correlate the current evidence grid against a historical evidence grid stored in a memory to produce displacement information, wherein the correlator performs one or more translations or rotations to align the current evidence grid and the historical evidence grid; and

where the navigation processor receives correction data derived from correlation of evidence grids and adjusts the navigation solution based on the correction data.

15. The system of claim 14, wherein the evidence grid creator is further configured to mark voxels of the current evidence grid to represent features of the environment captured by the sensor.

16. The system of claim 15, wherein the evidence grid creator encodes positions of features of the environment with a binary encoding within the current evidence grid.

17. The system of claim 15, wherein the evidence grid creator encodes positions of features of the environment with a probabilistic encoding within the current evidence grid.

18. The system of claim 14, wherein the correlator performs one or more translations or rotations to identify a matching position based on when the current evidence grid and the historical evidence grid are maximally correlated.

19. The system of claim 14, wherein the historical evidence grid is generated from one or more previous current evidence grids.

20. The system of claim 14, wherein the evidence grid creator uses a plurality of scans of the scanned environment to create the evidence grid of the scanned environment.