Localization and mapping system and method for a robotic device

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.