Localization and mapping system and method for a robotic device

• US 8,483,881 B2
• Filed: 09/01/2006
• Issued: 07/09/2013
• Est. Priority Date: 09/02/2005
• Status: Active Grant

• Current Assignee: Vorwerk & Company Interholding Gesellschaft Mit Beschrã¤Nkter Haftung (Vorwerk & Company KG)
• Original Assignee: Neato Robotics, Inc. (Vorwerk & Company KG)
• Inventors: Ermakov, Vladimir, Woodward, Mark, Augenbraun, Joe
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Nolan, Peter D
• Application Number:
  US11/515,100
• Publication Number:
  US 20070061043A1
• Time in Patent Office: 2,503 Days
• Field of Search: 700/245, 700/250, 700/251, 700/252, 700/253, 700/254, 700/255, 382/153
• US Class Current: 700/259
• CPC Class Codes: A47L 2201/00 Robotic cleaning machines, i.e. with automatic control of the travelling movement or the cleaning operation
• CPC Class Codes: A47L 2201/04 Automatic control of the travelling movement; Automatic obstacle detection
• CPC Class Codes: A47L 5/225 Convertible suction cleaners, i.e. convertible between different types thereof, e.g. from upright suction cleaners to sledge-type suction cleaners
• CPC Class Codes: A47L 9/009 Carrying-vehicles; Arrangements of trollies or wheels; Means for avoiding mechanical obstacles
• CPC Class Codes: B25J 9/0003 Home robots, i.e. small robots for domestic use
• CPC Class Codes: B25J 9/1664 characterised by motion, path, trajectory planning
• CPC Class Codes: B25J 9/1679 characterised by the tasks executed
• CPC Class Codes: G05B 2219/36513 Select out of a plurality of programs, patterns
• CPC Class Codes: G05B 2219/40095 Modify tasks due to modular tooling, other fixture configuration, environment
• CPC Class Codes: G05B 2219/40423 Map task space to sensor space
• CPC Class Codes: G05B 2219/40506 Self motion topology knowledge, configuration mapping
• CPC Class Codes: G05D 1/0225 involving docking at a fixed facility, e.g. base station or loading bay parking aids B62D15/027
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

A multi-function robotic device may have utility in various applications. In accordance with one aspect, a multi-function robotic device may be selectively configurable to perform a desired function in accordance with the capabilities of a selectively removable functional cartridge operably coupled with a robot body. Localization and mapping techniques may employ partial maps associated with portions of an operating environment, data compression, or both.

Claims

1. A method of mapping an operating environment to facilitate localization of a movable robot having a rotating mount, said method comprising:

acquiring optical data, from a stationary object, at a scan point on the stationary object, the scan point being associated with a partial map representing a portion of the operating environment;

identifying features of the portion of the operating environment and associating identified features with said partial map;

traversing the portion of the operating environment represented by said partial map;

acquiring additional optical data, from the stationary object, at the scan point on the stationary object;

updating said partial map responsive to said traversing and said acquiring additional data;

computing a location of the robot in the operating environment by determining an average position and angle for particles selected in accordance with the optical data and the additional optical data; and

selectively repeating said traversing, said acquiring additional data, and said updating so as to avoid-revisiting areas that have already been mapped;

wherein said updating said partial map comprises using the average position and angle for all of the particles; and

wherein said acquiring optical data and said acquiring additional optical data comprise utilizing a source of collimated light and a source of diffuse light on the rotating mount.

2. The method of claim 1 further comprising exiting said partial map and proceeding to a scan point of a different partial map representing a different portion of the operating environment.

3. The method of claim 1 wherein said identifying and said updating comprise computing a distance to an identified feature responsive to the optical data and the additional optical data.

4. A method of mapping an operating environment to facilitate localization of a movable robot having a rotating mount, said method comprising:

segmenting the operating environment into a plurality of partial maps, each respective one of said plurality of partial maps representing a respective portion of the operating environment;

mapping a respective one of said plurality of partial maps by;

acquiring optical data, from a stationary object, at a scan point on the stationary object to identify features associated with the respective portion of the operating environment;

responsive to said acquiring, associating identified features with said respective one of said plurality of partial maps and determining an average position and angle for particles selected in accordance with the optical data;

selectively repeating said acquiring, said associating, and said determining so as to avoid re-visiting areas that have already been mapped;

creating a single map of said respective one of said plurality of partial maps using the average position and angle for all of the particles; and

exiting said respective one of said plurality of partial maps and proceeding to a different one of said plurality of partial maps representing a different portion of the operating environment;

and

selectively repeating said mapping until each respective portion of the operating environment has been mapped;

wherein said acquiring optical data at a scan point comprises utilizing a source of collimated light and a source of diffuse light on the rotating mount at the scan point in each respective portion of the operating environment.

5. The method of claim 4 wherein said associating comprises compressing a data structure maintaining data representative of said respective one of said plurality of partial maps.

6. A method of determining a localization of a movable robot, having a rotating mount, within an operating environment, said method comprising:

segmenting the operating environment into a plurality of partial maps;

acquiring data at a scan point, on a stationary object, related to a distance between the movable robot and a feature in a portion of the operating environment corresponding to the one of said plurality of partial maps currently occupied by the movable robot;

computing a location of the movable robot in accordance with said acquiring, wherein said computing comprises determining an average position and angle for particles selected in accordance with the data and further comprises updating said one of said plurality of partial maps using the average position and angle for all of the particles; and

selectively repeating said acquiring and said computing so as to avoid re-visiting areas that have already been mapped;

wherein said acquiring data at a scan point comprises utilizing a source of collimated light and a source of diffuse light on said rotating mount at the scan point on the stationary object in a portion of the operating environment corresponding to the one of said plurality of partial maps currently occupied by the robot.

7. A movable robot having a rotating mount, the movable robot comprising a non-volatile computer-readable medium encoded with data and instructions for determining a location of the movable robot in an operating environment;

the data and instructions causing the movable robot to;

generate a plurality of particles, each of said plurality of particles having associated hypothesis data representing an hypothesis regarding a position and an inclination of the robot;

acquire data at a scan point, on a stationary object, related to a perspective of the operating environment from a current location of the movable robot utilizing a source of collimated light and a source of diffuse light on the rotating mount at the scan point on the stationary object;

compare said data to said hypothesis data associated with at least some of said plurality of particles;

apply a weight to at least some of said plurality of particles in accordance with the comparison of said data and said hypothesis data; and

selectively repeat the generate, acquire, compare, and apply steps so as to avoid areas that have already been mapped;

wherein a position component of said hypothesis data for each of said plurality of particles is restricted to a subset of locations in the operating environment, and wherein a location of the movable robot in the operating environment is computed by determining an average position and angle for the particles in the subset, and wherein a map of the operating environment is constructed using the average position and angle for all of the particles.

8. The movable robot of claim 7 further encoded with data and instructions;

the data and instructions further causing the movable robot to;

increase a weight for one of said plurality of particles when said associated hypothesis data are similar to said data acquired by the movable robot; and

decrease a weight for one of said plurality of particles when said associated hypothesis data are not similar to said data acquired by the movable robot.

9. The robot of claim 8 further encoded with data and instructions;

the data and instructions further causing the movable robot to discard those of said plurality of particles having a weight below a discard threshold.

10. The robot of claim 8 further encoded with data and instructions;

the data and instructions further causing the movable robot to clone those of said plurality of particles having a weight above a clone threshold.