Multidimensional evidence grids and system and methods for applying same

• US 7,446,766 B2
• Filed: 02/08/2006
• Issued: 11/04/2008
• Est. Priority Date: 02/08/2005
• Status: Active Grant

• Current Assignee: Seegrid Corporation
• Original Assignee: Seegrid Corporation
• Inventors: Moravec, Hans
• Primary Examiner(s): Nguyen; Kimbinh T
• Application Number:
  US11/350,195
• Publication Number:
  US 20060178828A1
• Time in Patent Office: 1,000 Days
• Field of Search: 345/419, 345/424, 345/427, 345/629, 701/211, 352/57
• US Class Current: 345/424
• CPC Class Codes: G05D 1/0251 extracting 3D information from a plurality of images taken from different locations, e.g. stereo vision stereoscopic image analysis H04N13/00; depth recovery from images G06T7/593
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• CPC Class Codes: G05D 1/0257 using a radar radar systems designed for anti-collision purposes between land vehicles or between land vehicle and fixed obstacles G01S13/931
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59

Abstract

A method of generating an evidence grid representing an environment comprises the steps of collecting a set of stereo images at multiple locations within the environment using stereo sensors, and processing the set of stereo images to determine occupancy and distance data associated with each point in space represented in the set of stereo images; applying a sensor model to each point in space to determine a probability of occupancy of each voxel representing each point in space; and generating an evidence grid of the environment by combining the probabilities for each voxel.

Claims

1. A method of generating a multidimensional evidence grid representing an environment, the method comprising:

A1. using learned sensor models to determine the settings and parameters to be used in stereo processing and evidence grid generation;

A2. collecting stereo data at multiple locations within the environment using stereo sensors during a training run using machine odometry to determine imaging locations;

B. from the stereo data, generating probability clouds comprising voxels, each voxel representing an occupancy of a corresponding point in space;

C. from the probability clouds, generating maps comprising combined probabilities of voxels associated with the points in space; and

D. combining the maps to form a multidimensional evidence grid representing the environment with a plurality of voxels, each voxel embodying a resulting probability of occupancy corresponding point in space.

2. The method of claim 1, further comprising:

E. navigating a mobile apparatus through the environment using the evidence grid.

3. The method of claim 2 wherein the navigating of step E comprises:

1) acquiring glimpse stereo data using the stereo sensors;

2) determining glimpse probabilities of occupancy from the glimpse stereo data and associating the glimpse probabilities with voxels in the evidence grid;

3) determining the location of the mobile apparatus by comparing the glimpse probabilities with the probabilities associated with corresponding voxels in the evidence grid; and

4) using a sensor model specifically tuned to enhance the performance of navigation.

4. The method of claim 3, further comprising:

F. updating the evidence grid as a function of the glimpses.

5. The method of claim 4, wherein step F comprises:

1) combining the glimpse stereo data with the stereo data and repeating steps B through E.

6. The method of claim 1 wherein the stereo sensors comprises stereo cameras.

7. The method of claim 1, wherein the stereo sensors comprises sensors oriented on different, parallel planes.

8. The method of claim 1 wherein a high probability of occupancy of a voxel indicates the presence of a tangible object at the point in space represented by the voxel.

9. The method of claim 1 wherein the multidimensional evidence grid is a three dimensional evidence grid.

10. The method of claim 1 wherein the collecting of stereo data includes removing noise and errors attributed to the stereo sensors and represented in sensor models.

11. The method of claim 1 wherein occupancy relates to the absence or presence of an object, a part of an object or a feature.

12. A mobile apparatus configured for automated navigation within an environment, the mobile apparatus comprising:

A. a mobile body configured for motorized translation within an environment;

B. a translator configured to translate the mobile body in response to a set of navigation instructions;

C. a set of stereo sensors configured for acquiring stereo data within the environment, including collecting stereo data at multiple locations within the environment using stereo sensors during a training run to determine imaging locations;

D. a storage device including learned sensor models and a multidimensional evidence grid comprising a plurality of voxels representing the environment and having associated with each voxel a probability of occupancy; and

E. a processor configured for executing a set of navigation logic configured for;

1) taking glimpses of the environment using the stereo sensors, wherein a glimpse comprises glimpse stereo data taken during navigation;

2) associating probability and location data from the glimpse stereo data with voxels in the evidence grid;

3) determining the location of the mobile apparatus by comparing the glimpse stereo data associated with the voxels with the probabilities associated with corresponding voxels in the evidence grid; and

4) using a sensor model specifically tuned to enhance the performance of navigation.

13. The mobile apparatus of claim 12, further comprising an engagement mechanism movably coupled to the mobile body and configured to support an object.

14. The mobile apparatus of claim 13 wherein the apparatus is a forklift.

15. The mobile apparatus of claim 13 wherein the apparatus is a stacker.

16. The mobile apparatus of claim 13 wherein the apparatus is an order picker.

17. The mobile apparatus of claim 12 wherein the engagement mechanism comprises engagement logic configured for engaging and supporting the object, the engagement logic comprising object identification logic configured for determining parametric information of the object as a function of object sensor data obtained by the set of stereo sensors.

18. The apparatus of claim 17 wherein the parametric information comprises information representing a size and a shape of the object.

19. The method of claim 12, wherein the navigation logic further comprises logic for updating the evidence grid as a function of the glimpses.

20. The mobile apparatus of claim 12 wherein the stereo sensors comprises stereo cameras.

21. The mobile apparatus of claim 12 wherein the stereo sensors comprises sensors oriented on different, parallel planes.

22. The mobile apparatus of claim 12 wherein a high probability of occupancy of a voxel indicates the presence of a tangible object at the point in space represented by the voxel.

23. The mobile apparatus of claim 12 wherein the multidimensional evidence grid is a three dimensional evidence grid.