Systems and methods for using multiple hypotheses in a visual simultaneous localization and mapping system

• US 9,110,470 B2
• Filed: 05/06/2014
• Issued: 08/18/2015
• Est. Priority Date: 12/17/2002
• Status: Expired due to Term

• Current Assignee: iRobot Corporation
• Original Assignee: iRobot Corporation
• Inventors: Karlsson, L. Niklas, Pirjanian, Paolo, Goncalves, Luis Filipe Domingues, Di Bernardo, Enrico
• Primary Examiner(s): Swarthout, Brent
• Application Number:
  US14/271,260
• Publication Number:
  US 20140244038A1
• Time in Patent Office: 469 Days
• Field of Search: 340/995.1, 340/988, 318/568.11, 318/568.12, 318/568.16, 700/245, 700/253, 701/23, 901/1
• US Class Current: 1/1
• 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 of localizing a mobile device in a multiple-particle autonomous localization and mapping system using an electronic device, the method comprising:

performing, using an electronic device, autonomous localization and mapping with a plurality of particles, wherein a particle includes a device pose and a map, wherein the map includes at least one landmark;

calculating, using the electronic device, an updated device pose estimate for a particle, wherein the technique used to calculate the updated device pose estimate is selected according to the type associated with the particle; and

using dead reckoning data to estimate a change in pose from a prior update to the particles using the electronic device;

wherein calculating the updated device pose estimate for the particle further comprises using the change in pose estimated from dead reckoning data and using a relative pose to calculate the updated device pose estimate.

2. The method as defined in claim 1, wherein calculating the updated device pose estimate further comprises calculating the updated device pose estimate for a primary particle based at least in part on data from a first sensor, and calculating the updated device pose estimate for a dual particle based at least in part on data from a second sensor, where the second sensor is different from the first sensor.

3. The method as defined in claim 1, wherein calculating the updated device pose estimate further comprises calculating the updated device pose for a primary type of particle based at least in part on data from a dead reckoning sensor, and calculating the updated device pose estimate for a dual type of particle based at least in part on data from a visual sensor.

4. The method as defined in claim 1, wherein calculating the updated device pose estimate further comprises:

using a prior pose estimate and dead reckoning sensor data to compute a new pose for particles of primary type based on the change in pose estimated from the dead reckoning sensor data;

receiving a visually-measured relative pose to the landmark, wherein the landmark has been matched using visual features from a visual sensor coupled to the mobile device, wherein the relative pose corresponds to a visually-measured difference in pose between a landmark pose and a pose corresponding to the visual observation; and

using the landmark pose estimate and the visually-measured relative pose to compute the new pose estimate for particles of dual type.

5. The method as defined in claim 1, wherein the technique used to calculate the updated device pose estimate for a first type of particle further comprises:

using a prior pose estimate, the dead reckoning sensor data, and simulated random noise to compute a new device pose estimate termed perturbed predicted device pose;

using the perturbed predicted device pose and a visually-measured pose of the device relative to the landmark to compute a hypothetical landmark pose;

computing an importance factor for the particle, wherein the importance factor is based at least in part on an uncertainty measure and a comparison between the calculated hypothetical landmark pose and a prior landmark pose estimate; and

using the perturbed predicted pose with the importance factor as the updated device pose.

6. The method as defined in claim 5, wherein the simulated random noise exhibits an uncertainty measure for the dead reckoning sensor data.

7. The method as defined in claim 1, wherein the technique used to calculate the updated device pose for a second type of particle termed dual particle further comprises:

using a landmark pose estimate corresponding to the landmark and a visually-measured relative pose to compute a hypothetical device pose;

perturbing the hypothetical device pose with simulated random noise;

computing an importance factor for the particle, wherein the importance factor is based at least in part on an uncertainty measure and a comparison between the hypothetical device pose and a predicted device pose from a prior pose estimate and the dead reckoning sensor data; and

using the hypothetical device pose with the importance factor as the updated device pose.

8. The method as defined in claim 7, wherein the simulated random noise exhibits an uncertainty measure estimated for a visual sensor.

9. The method as defined in claim 1, further comprising resampling selected particles from the plurality of particles.

10. A circuit for localizing a mobile device in a multiple-particle autonomous localization and mapping system, the circuit comprising:

a circuit configured to perform autonomous localization and mapping with a plurality of particles, wherein a particle includes a device pose and a map, wherein the map includes at least one landmark; and

a circuit configured to calculate an updated device pose estimate for a particle, wherein the technique used to calculate the updated device pose estimate is selected according to the type associated with the particle, wherein the circuit configured to calculate the updated device pose estimate is further configured to calculate the updated device pose for a primary particle based at least in part on data from a dead reckoning sensor and is further configured to calculate the update device pose estimate for a dual particle based at least in part on data from a visual sensor.

11. The circuit as defined in claim 10, wherein the circuit configured to calculate the updated device pose estimate is further configured to calculate the updated device pose estimate for a particle of primary type based at least in part on data from a first sensor and is further configured to calculate the updated device pose estimate for a particle of dual type based at least in part on data from a second sensor, wherein the second sensor is different from the first sensor.

12. The circuit as defined in claim 10, further comprising a circuit configured to resample selected particles from the plurality of particles.

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

14. A method of localizing a mobile device in a multiple-particle autonomous localization and mapping system, using an electronic device, the method comprising:

performing, using the electronic device, autonomous localization and mapping with a plurality of particles, wherein a particle includes a device pose and a map, wherein the map includes at least one landmark;

calculating, using the electronic device, an updated device pose estimate for a particle, wherein the technique used to calculate the updated device pose estimate is selected according to the type associated with the particle;

wherein calculating the updated device pose estimate comprises;

using a prior pose estimate and dead reckoning sensor data to compute a new pose for particles of primary type based on the change in pose estimated from the dead reckoning sensor data, using the electronic device;

receiving a visually-measured relative pose to the landmark, wherein the landmark has been matched using visual features from a visual sensor coupled to the mobile device, wherein the relative pose corresponds to a visually-measured difference in pose between a landmark pose and a pose corresponding to the visual observation; and

using the landmark pose estimate and the visually-measured relative pose to compute the new pose estimate for particles of dual type.

15. The method as defined in claim 14, wherein the technique used to calculate the updated device pose estimate for particles of primary type further comprises:

using the prior pose estimate, the dead reckoning sensor data, and simulated random noise to compute the new device pose estimate termed perturbed predicted device pose;

using the perturbed predicted device pose and a visually-measured pose of the device relative to the landmark to compute a hypothetical landmark pose;

computing an importance factor for the particle, wherein the importance factor is based at least in part on an uncertainty measure and a comparison between the calculated hypothetical landmark pose and a prior landmark pose estimate; and

using the perturbed predicted pose with the importance factor as the updated device pose.

16. The method as defined in claim 15, wherein the simulated random noise exhibits an uncertainty measure for the dead reckoning sensor data.

17. The method as defined in claim 14, wherein the technique used to calculate the updated device pose for the dual particle type further comprises:

using the landmark pose estimate corresponding to the landmark and the visually-measured relative pose to compute a hypothetical device pose;

perturbing the hypothetical device pose with simulated random noise;

computing an importance factor for the particle, wherein the importance factor is based at least in part on an uncertainty measure and a comparison between the hypothetical device pose and a predicted device pose from a prior pose estimate and the dead reckoning sensor data; and

using the hypothetical device pose with the importance factor as the updated device pose.

18. The method as defined in claim 17, wherein the simulated random noise exhibits an uncertainty measure estimated for a visual sensor.