Systems and methods for controlling a density of visual landmarks in a visual simultaneous localization and mapping system

• US 20040167716A1
• Filed: 12/17/2003
• Published: 08/26/2004
• Est. Priority Date: 12/17/2002
• Status: Active Grant

• Current Assignee: iRobot Corporation
• Original Assignee: Evolution Robotics Inc. (iRobot Corporation)
• Inventors: Di Bernardo, Enrico, Pirjanian, Paolo, Karlsson, L. Niklas, Goncalves, Luis Filipe Domingues
• Granted Patent: US 7,145,478 B2
• Time in Patent Office: Days
• US Class Current: 701/217
• CPC Class Codes: G01C 21/12 executed aboard the object being navigated; Dead reckoning
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G05D 1/0231 using optical position detecting means position-fixing by using electromagnetic waves other than radio waves, e.g. optical position detecting means G01S5/16
• CPC Class Codes: G05D 1/0234 using optical markers or beacons optical beacons per se G01S1/70
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0242 using non-visible light signals, e.g. IR or UV signals
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0248 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0278 using satellite positioning signals, e.g. GPS
• CPC Class Codes: G06T 2207/30204 Marker
• CPC Class Codes: G06T 7/55 from multiple images
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: Y10S 901/01 Mobile robot
• CPC Class Codes: Y10S 901/46 Sensing device
• CPC Class Codes: Y10S 901/47 Optical
• CPC Class Codes: Y10S 901/50 Miscellaneous

Abstract

The invention is related to methods and apparatus that use a visual sensor and dead reckoning sensors to process Simultaneous Localization and Mapping (SLAM). These techniques can be used in robot navigation. Advantageously, such visual techniques can be used to autonomously generate and update a map. Unlike with laser rangefinders, the visual techniques are economically practical in a wide range of applications and can be used in relatively dynamic environments, such as environments in which people move. One embodiment further advantageously uses multiple particles to maintain multiple hypotheses with respect to localization and mapping. Further advantageously, one embodiment maintains the particles in a relatively computationally-efficient manner, thereby permitting the SLAM processes to be performed in software using relatively inexpensive microprocessor-based computer systems.

Claims

1. A method for efficiently using memory in an autonomous localization and mapping system for a mobile device, the method comprising:

observing features in the environment with a visual sensor coupled to the mobile device;

receiving dead reckoning data from a sensor coupled to the mobile device;

maintaining a plurality of landmarks for one or more maps in a first memory, where a landmark is referenced in a map in a global reference frame;

copying data corresponding to the plurality of landmarks for the one or more maps from the first memory to a second memory, where the second memory operates faster than the first memory;

using the data stored in the second memory when searching for matching landmarks;

estimating a position for the mobile device within the global reference frame of the one or more maps at least partly in response to the observed features and the dead reckoning data; and

selectively maintaining only a first portion of the plurality of landmarks for the one or more maps in the second memory and releasing a second portion such that memory resources previously allocated to the second portion can be returned to the system, where the first portion corresponds to landmarks that are likely to be in the same vicinity of the global reference frame as the position estimate for the mobile device.

2. The method as defined in claim 1, wherein the plurality of landmarks for the one or more maps are organized in a database.

3. The method as defined in claim 1, wherein the first memory corresponds to flash memory and where the second memory corresponds to solid-state random access memory (RAM).

4. The method as defined in claim 1, wherein the first memory corresponds to a hard disk and where the second memory corresponds to solid-state random access memory (RAM).

5. The method as defined in claim 1, wherein estimating the position for the mobile device further comprises estimating a pose for the mobile device, where the pose includes position and orientation.

6. The method as defined in claim 1, wherein selectively maintaining only the first portion further comprises selecting landmarks based at least partly on an associated landmark pose for the landmark and on a pose estimated for the mobile device.

7. The method as defined in claim 1, wherein selectively maintaining only the first portion further comprises selecting a predetermined number of landmarks that are most likely to be close to the position estimated for the mobile device.

8. The method as defined in claim 1, wherein selectively maintaining only the first portion further comprises selecting landmarks that are likely to be within approximately a predetermined distance from the estimated position of the mobile device.

9. The method as defined in claim 1, further comprising observing a new landmark and adding the landmark to the first memory and the second memory.

10. The method as defined in claim 1, wherein selectively maintaining only the first portion of the plurality of landmarks further comprises at least temporarily maintaining only a randomly selected subset of the plurality of landmarks.

11. The method as defined in claim 1, wherein selectively maintaining only the first portion of the plurality of landmarks further comprises at least temporarily selecting a subset of landmarks from the plurality of landmarks such that the subset has approximately the same density of landmarks throughout the subset of the map.

12. A computer program embodied in a tangible medium for efficiently using memory in an autonomous localization and mapping system for a mobile device, the computer program comprising:

a module with instructions configured to observe features in the environment with a visual sensor coupled to the mobile device;

a module with instructions configured to receive dead reckoning data from a sensor coupled to the mobile device;

a module with instructions configured to maintain a plurality of landmarks for one or more maps in a first memory, where a landmark is referenced in a map in a global reference frame;

a module with instructions configured to copy data corresponding to the plurality of landmarks for the one or more maps from the first memory to a second memory, where the second memory operates faster than the first memory;

a module with instructions configured to use the data stored in the second memory when searching for matching landmarks;

a module with instructions configured to estimate a position for the mobile device within the global reference frame of the one or more maps at least partly in response to the observed features and the dead reckoning data; and

a module with instructions configured to selectively maintain only a first portion of the plurality of landmarks for the one or more maps in the second memory and releasing a second portion such that memory resources previously allocated to the second portion can be returned to the system, where the first portion corresponds to landmarks that are likely to be in the same vicinity of the global reference frame as the position estimate for the mobile device.

13. The computer program as defined in claim 12, wherein the module with instructions configured to selectively maintain only the first portion of the plurality of landmarks further comprises instructions configured to at least temporarily maintain only a randomly selected subset of the plurality of landmarks.

14. The computer program as defined in claim 12, wherein the module with instructions configured to selectively maintain only the first portion of the plurality of landmarks further comprises instructions configured to at least temporarily select a subset of landmarks from the plurality of landmarks such that the subset has approximately the same density of landmarks throughout the subset of the map.

15. A circuit for efficiently using memory in an autonomous localization and mapping system for a mobile device, the circuit comprising:

a circuit configured to observe features in the environment with a visual sensor coupled to the mobile device;

a circuit configured to receive dead reckoning data from a sensor coupled to the mobile device;

a circuit configured to maintain a plurality of landmarks for one or more maps in a first memory, where a landmark is referenced in a map in a global reference frame;

a circuit configured to copy data corresponding to the plurality of landmarks for the one or more maps from the first memory to a second memory, where the second memory operates faster than the first memory;

a circuit configured to use the data stored in the second memory when searching for matching landmarks;

a circuit configured to estimate a position for the mobile device within the global reference frame of the one or more maps at least partly in response to the observed features and the dead reckoning data; and

a circuit configured to selectively maintain only a first portion of the plurality of landmarks for the one or more maps in the second memory and releasing a second portion such that memory resources previously allocated to the second portion can be returned to the system, where the first portion corresponds to landmarks that are likely to be in the same vicinity of the global reference frame as the position estimate for the mobile device.

16. The circuit as defined in claim 15, wherein the first memory corresponds to flash memory and where the second memory corresponds to solid-state random access memory (RAM).

17. The circuit as defined in claim 15, wherein the first memory corresponds to a hard disk and where the second memory corresponds to solid-state random access memory (RAM).

18. The circuit as defined in claim 15, wherein the circuit is embodied in a mobile robot.

19. A method for managing content of a landmark database in a Visual Simultaneous Localization and Mapping System (VSLAM) for a mobile device, the method comprising:

retrieving an estimate of device pose for the mobile device;

determining which landmarks in a map are expected to be observed by the mobile device at least partly based on the estimate of device pose;

tracking over time whether the landmarks that are expected to be observed are observed; and

removing a landmark from the map when the landmark is repeatedly not observed where the landmark was expected to be observed.

20. The method as defined in claim 19, wherein removing the landmark further comprises removing the landmark based on a combination of not observing the landmark and a minimum predetermined period of time for not observing the landmark.

21. The method as defined in claim 19, wherein repeatedly not observed further comprises not observing the landmark about 10 times.

22. A computer program embodied in a tangible medium for managing content of a landmark database in a Visual Simultaneous Localization and Mapping System (VSLAM) for a mobile device, the computer program comprising:

a module with instructions configured to retrieve an estimate of device pose for the mobile device;

a module with instructions configured to determine which landmarks in a map are expected to be observed by the mobile device at least partly based on the estimate of device pose;

a module with instructions configured to track over time whether the landmarks that are expected to be observed are observed; and

a module with instructions configured to remove a landmark from the map when the landmark is repeatedly not observed where the landmark was expected to be observed.

23. The computer program as defined in claim 22, wherein the module with instructions configured to remove the landmark further comprises instructions configured to remove the landmark based on a combination of not observing the landmark and a minimum predetermined period of time for not observing the landmark.

24. A method for managing content of a landmark database in Visual Simultaneous Localization and Mapping System (VSLAM) for a mobile device, the method comprising:

visually obtaining a measurement of a landmark;

analyzing a quality of the measurement, where the quality of the measurement provides an indication of whether the measurement is an outlier;

storing an indication when the measurement has been identified as an outlier; and

removing a landmark from the map when the measurements of the landmark are repeatedly identified as outliers.

25. The method as defined in claim 24, wherein storing the indication further comprises updating a count of how many times the measurement has been identified as an outlier.

26. The method as defined in claim 24, wherein storing the indication further comprises updating a first count of how many times the landmark has been measured and a second count of how many times the measurements have been identified as outliers.

27. The method as defined in claim 24, wherein storing the indication further comprises updating a count of how many consecutive times the measurement has been identified as an outlier.

28. The method as defined in claim 24, wherein a measurement is identified as an outlier at least partly when a visual measurement suggests a pose that is inconsistent with a pose that is estimated by a large proportion of particles.

29. The method as defined in claim 24, wherein a measurement is identified as an outlier at least partly when a difference between a pose estimated by a visual measurement and the pose estimated by SLAM exceeds a predetermined threshold.

30. The method as defined in claim 24, wherein a measurement is identified as an outlier at least partly in response to a calculation of projection error.

31. The method as defined in claim 24, wherein a measurement is identified as an outlier at least partly in response to a measurement of vertical displacement per unit of measured horizontal translation.

32. The method as defined in claim 24, wherein a measurement is identified as an outlier at least partly in response to a number of matching features common to an image and to a landmark.

33. A computer program embodied in a tangible medium for managing content of a landmark database in Visual Simultaneous Localization and Mapping System (VSLAM) for a mobile device, the computer program comprising:

a module with instructions configured to visually obtain a measurement of a landmark;

a module with instructions configured to analyze a quality of the measurement, where the quality of the measurement provides an indication of whether the measurement is an outlier;

a module with instructions configured to store an indication when the measurement has been identified as an outlier; and

a module with instructions configured to remove a landmark from the map when the measurements of the landmark are repeatedly identified as outliers.

34. The computer program as defined in claim 33, wherein the module with instructions configured to store the indication further comprises instructions configured to update a count of how many times the measurement has been identified as an outlier.

35. The computer program as defined in claim 33, wherein the module with instructions configured to store the indication further comprises instructions configured to update a first count of how many times the landmark has been measured and a second count of how many times the measurements have been identified as outliers.

36. A method for efficiently managing content of a landmark database in an autonomous localization and mapping system, the method comprising:

determining a density of landmarks in one or more maps; and

discontinuing the adding of new landmarks to the one or more maps at least partially in response to a determination that the density of landmarks is higher than a threshold.

37. The method as defined in claim 36, wherein discontinuing the adding of new landmarks further comprises discontinuing the adding of landmarks in only selected high-density parts of the one or more maps.

38. The method as defined in claim 36, wherein discontinuing the adding of new landmarks further comprises discontinuing the adding of landmarks in all parts of the one or more maps.

39. The method as defined in claim 36, wherein the predetermined threshold adapts to an operating environment.

40. The method as defined in claim 36, wherein the predetermined threshold is between about 5 to 10 landmarks per square meter of mapped area.

41. A circuit for managing content of a landmark database in an autonomous localization and mapping system, the circuit comprising:

a means for determining a density of landmarks in one or more maps; and

a means for discontinuing the adding of new landmarks to the one or more maps at least partially in response to a determination that the density of landmarks is higher than a threshold.

42. The circuit as defined in claim 41, wherein the means for discontinuing the adding of new landmarks is further configured to add landmarks in only selected high-density parts of the one or more maps.

43. The circuit as defined in claim 41, wherein the means for discontinuing is further configured to adapt the threshold to an operating environment.

44. The circuit as defined in claim 41, wherein the circuit is embodied in a robot for navigation of the robot.

45. A computer program embodied in a tangible medium for efficiently managing content of a landmark database in an autonomous localization and mapping system, the computer program comprising:

a module with instructions configured to determine a density of landmarks ill one or more maps; and

a module with instructions configured to discontinue the adding of new landmarks to the one or more maps at least partially in response to a determination that the density of landmarks is higher than a threshold.

46. The computer program as defined in claim 45, wherein the module with instructions configured to discontinue the adding of new landmarks further comprises instructions configured to discontinue the adding of landmarks in only selected high-density parts of the one or more maps.

47. The computer program as defined in claim 45, wherein the module with instructions configured to discontinue the adding of new landmarks further comprises instructions configured to adapt the threshold to an operating environment.

48. A circuit adapted to efficiently manage content of a landmark database in an autonomous localization and mapping system, the circuit comprising:

a circuit configured to determine a density of landmarks in one or more maps; and

a circuit configured to discontinue the adding of new landmarks to the one or more maps at least partially in response to a determination that the density of landmarks is higher than a threshold.

49. The circuit as defined in claim 48, wherein the circuit configured to discontinue the adding of new landmarks is further configured to discontinue the adding of landmarks in only selected high-density parts of the one or more maps.

50. The circuit as defined in claim 48, wherein the circuit configured to discontinue the adding of new landmarks is further configured to adapt the threshold to an operating environment.

51. The circuit as defined in claim 48, wherein the circuit is embodied in a robot for navigation of the robot.