Systems and methods for adding landmarks for visual simultaneous localization and mapping

• US 8,086,419 B2
• Filed: 07/20/2010
• Issued: 12/27/2011
• Est. Priority Date: 12/17/2002
• Status: Expired due to Term

• Current Assignee: iRobot Corporation
• Original Assignee: Evolution Robotics Inc. (iRobot Corporation)
• Inventors: Goncalves, Luis Filipe Domingues, Di Bernardo, Enrico, Pirjanian, Paolo, Karlsson, L. Niklas
• Primary Examiner(s): WACHSMAN, HAL D
• Application Number:
  US12/839,793
• Publication Number:
  US 20100280754A1
• Time in Patent Office: 525 Days
• Field of Search: 702/150, 702152-153, 702/155, 702158-160, 701/23, 701 25- 26, 701/28, 701207-211, 701/217, 348/119, 348/135, 348/137, 348/139, 348/142
• US Class Current: 702/152
• 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. Such visual techniques can be used to autonomously generate and update a map. Unlike with laser rangefinders, the visual techniques are 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 uses multiple particles to maintain multiple hypotheses with respect to localization and mapping. One embodiment maintains the particles, thereby permitting the SLAM processes to be performed in software using microprocessor-based computer systems.

Claims

1. A method of adding a new landmark to a map for navigation of a mobile device, the method comprising:

navigating the mobile device using the map, and while navigating the mobile device, performing the following;

retrieving dead reckoning data from at least a time corresponding to a prior update of device pose of the mobile device and a time corresponding to an observation of the new landmark;

retrieving a prior device pose of the mobile device for the map, wherein the prior device pose of the mobile device corresponds to a prior update time; and

adding the new landmark to the map, wherein the pose associated with the new landmark is computed at least in part by using the retrieved dead reckoning data to calculate a change to device pose of the mobile device corresponding to the prior update, wherein the new landmark is used for navigation of the same mobile device;

wherein navigating, retrieving and adding are performed under the control of electronic hardware.

2. The method as defined in claim 1, wherein the prior update to the device pose of the mobile device and the retrieved dead reckoning data are referenced by one or more timestamps.

3. The method as defined in claim 1, further comprising visually observing the new landmark using a digital imaging device.

4. The method as defined in claim 1, wherein navigating, retrieving dead reckoning data, retrieving a prior device pose, and adding are performed in real time.

5. An apparatus comprising:

a computer program embodied in a tangible non-transitory computer-readable medium for adding a new landmark to a map for navigation of a mobile device, the computer program comprising;

program instructions configured to navigate the mobile device using the map;

program instructions configured to retrieve dead reckoning data from at least a time corresponding to a prior update of device pose of the mobile device and a time corresponding to an observation of the new landmark;

program instructions configured to retrieve a prior device pose of the mobile device for the map, wherein the prior device pose of the mobile device corresponds to a prior update time; and

program instructions configured to add the new landmark to the map, wherein the pose associated with the new landmark is computed at least in part by using the retrieved dead reckoning data to calculate a change to device pose of the mobile device corresponding to the prior update, wherein the new landmark is added to the map and the pose is associated with the new landmark while the mobile device is being navigated; and

a processor configured to execute the program instructions of the computer program.

6. The apparatus as defined in claim 5, wherein the computer program further comprises program instructions configured to visually observe the new landmark.

7. A method of adding a new landmark to a plurality of maps in a multiple-particle navigation system for navigation of a mobile device, the method comprising:

navigating the mobile device using the plurality of maps, and while navigating the mobile device, performing the following;

retrieving dead reckoning data from at least a time corresponding to a prior update of device pose of the mobile device and a time corresponding to an observation of the new landmark;

retrieving prior device poses of the mobile device for the plurality of maps, wherein the prior device poses of the mobile device correspond to a prior update time; and

adding the new landmark to the plurality of maps, wherein the poses associated with the new landmark are computed at least in part by using the retrieved dead reckoning data to calculate a change to device pose of the mobile device from the device poses of the mobile device corresponding to the prior update, wherein the new landmark is used for navigation of the same mobile device;

wherein navigating, retrieving and adding are performed under the control of electronic hardware.

8. The method as defined in claim 7, wherein the prior update to device pose of the mobile device and the retrieved dead reckoning data are referenced by one or more timestamps.

9. The method as defined in claim 7, further comprising visually observing the new landmark using a visual sensor coupled to the mobile device.

10. The method as defined in claim 7, wherein navigating, retrieving dead reckoning data, retrieving prior device poses, and adding are performed in real time.

11. An apparatus comprising:

a computer program embodied in a tangible non-transitory computer-readable medium for adding a new landmark to a plurality of maps in a multiple-particle navigation system for navigation of a mobile device, the computer program comprising;

program instructions configured to navigate the mobile device using the plurality of maps;

program instructions configured to retrieve dead reckoning data from at least a time corresponding to a prior update of device pose of the mobile device and a time corresponding to an observation of the new landmark;

program instructions configured to retrieve prior device poses of the mobile device for the plurality of maps, wherein the prior device poses of the mobile device correspond to a prior update time; and

program instructions configured to add the new landmark to the plurality of maps, wherein the poses associated with the new landmark are computed at least in part by using the retrieved dead reckoning data to calculate a change to device pose of the mobile device from the device poses of the mobile device corresponding to the prior update, wherein the new landmark is added to the plurality of maps and the poses are associated with the new landmark while the mobile device is being navigated; and

a processor configured to execute the program instructions of the computer program.

12. The apparatus as defined in claim 11, wherein the computer program further comprises program instructions configured to visually observe the new landmark.