SYSTEMS AND METHODS FOR USING MULTIPLE HYPOTHESES IN A VISUAL SIMULTANEOUS LOCALIZATION AND MAPPING SYSTEM

• US 20100268697A1
• Filed: 03/15/2010
• Published: 10/21/2010
• 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 8,274,406 B2
• Time in Patent Office: Days
• US Class Current: 707/694
• 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 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;

wherein determining and discontinuing are performed under the control of electronic hardware.

2. The method as defined in claim 1, 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.

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

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

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

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

7. The circuit as defined in claim 6, 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.

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

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

10. A computer program embodied in a tangible non-transitory computer readable 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 in 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.

11. The computer program as defined in claim 10, 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.

12. The computer program as defined in claim 10, 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.

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

14. The circuit as defined in claim 13, 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.

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

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