Method and apparatus for simultaneous localization and mapping of mobile robot environment

Abstract

Techniques that optimize performance of simultaneous localization and mapping (SLAM) processes for mobile devices, typically a mobile robot. In one embodiment, erroneous particles are introduced to the particle filtering process of localization. Monitoring the weights of the erroneous particles relative to the particles maintained for SLAM provides a verification that the robot is localized and detection that it is no longer localized. In another embodiment, cell-based grid mapping of a mobile robot's environment also monitors cells for changes in their probability of occupancy. Cells with a changing occupancy probability are marked as dynamic and updating of such cells to the map is suspended or modified until their individual occupancy probabilities have stabilized. In another embodiment, mapping is suspended when it is determined that the device is acquiring data regarding its physical environment in such a way that use of the data for mapping will incorporate distortions into the map, as for example when the robotic device is tilted.

1 . A mobile robotic system comprising:
 a. a mobile robot; and   b. a system for controlling movement of the robot, the system comprising;
 i. a data acquisition system that generates data identifying the robot's physical environment, said data acquisition system having a preferred orientation for operation with respect to the robot's physical environment; 
 ii. processing apparatus, responsive to the data acquisition system, to map or model the robot's physical environment and the data acquisition system's location within the robot's physical environment; and 
 iii. a sensing unit that determines whether the data acquisition system has lost its preferred orientation for operation with respect to the robot's physical environment; 
 iv. wherein the processing apparatus includes apparatus that responds to the sensing unit to suspend or modify the use of data generated by the data acquisition system for mapping or modeling the robot's physical environment when the sensing unit has determined that the data acquisition system has lost its preferred orientation for operation with respect to the robot's physical environment. 
   
     
     
         2 . A mobile robotic system as claimed in  claim 1  wherein the data acquisition system comprises a distance-measuring device to identify items in the robot's operating environment. 
     
     
         3 . A mobile robotic system as claimed in  claim 2  wherein the distance-measuring device comprises light-emitting and light-receiving apparatus to emit light to measure distance based on reflected light. 
     
     
         4 . A mobile robotic system as claimed in  claim 2  wherein the distance-measuring device comprises a laser rangefinder. 
     
     
         5 . A mobile robotic system as claimed in  claim 1  wherein the sensing unit comprises an accelerometer. 
     
     
         6 . A mobile robotic system as claimed in  claim 1  wherein the processing apparatus is physically separate from the mobile robot and is in communication with the mobile robot. 
     
     
         7 . A mobile robotic system comprising:
 a. a mobile robot; and   b. a system for controlling movement of the robot, the system comprising:
 i. a data acquisition system that generates data identifying the robot's physical environment, said data acquisition system having a preferred orientation for operation with respect to the robot's physical environment; and 
 ii. processing apparatus, responsive to the data acquisition system, to generate a map of the robot's physical environment and the data acquisition system's location within the robot's physical environment; 
 iii. wherein the processing apparatus includes apparatus that responds to the data generated by the data acquisition system to suspend or modify the use of data generated by the data acquisition system when a portion of the map above a threshold limit corresponds to a predetermined shift of one or more elements in the map. 
   
     
     
         8 . A mobile robotic system as claimed in  claim 7  wherein the data acquisition system comprises a distance-measuring device to identify items in the robot's physical environment. 
     
     
         9 . A mobile robotic system as claimed in  claim 8  wherein the distance-measuring device comprises light-emitting and light-receiving apparatus to emit light to measure distance based on reflected light. 
     
     
         10 . A mobile robotic system as claimed in  claim 8  wherein the distance-measuring device comprises a laser rangefinder. 
     
     
         11 . A mobile robotic system as claimed in  claim 1  wherein the processing apparatus is physically separate from the mobile robot and is in communication with the mobile robot. 
     
     
         12 . A mobile device tracking system comprising:
 a. apparatus that generates a map of the device's physical environment, said generating occurring either concurrently with or prior to tracking the device's position, said generating apparatus updating said map either concurrently with or prior to tracking the device's position; and   b. a processing apparatus to determine the device's current location within said map by generating particles, each of said particles representing a potential position and/or orientation of the device within its physical environment, wherein a data set of said particles may be generated and maintained iteratively to track changing position of the device within its physical environment, the processing apparatus including:
 i. apparatus that assigns a weight to each particle, particle weight being a relative measure of the particle's likelihood of accurately representing the robot's position with respect to other particles; 
 ii. apparatus that introduces erroneous particles whose potential positions are selected so that their assigned weights should be uniformly low with respect to the weights of the particles described in (b); and 
 iii. apparatus that compares the weights of the erroneous particles and the weights of the particles described in (b) to determine whether the mobile device has become delocalized when a substantial number of erroneous particles have weights that are no longer uniformly low with respect to the weights of the particles described in (b). 
   
     
     
         13 . A mobile device tracking system as claimed in  claim 12  wherein the erroneous particles are selected so as to avoid introduction of additional error into the current estimate of the mobile device's position. 
     
     
         14 . A mobile device tracking system as claimed in  claim 12  wherein the mobile device is a robot. 
     
     
         15 . A mobile device tracking system as claimed in  claim 12  wherein the determination of delocalization includes calculating and monitoring the averaged weight or the median weight of the erroneous particles over multiple iterations. 
     
     
         16 . A system for identifying and marking dynamic areas of a map of a physical environment of a mobile device, the system comprising:
 a. a data acquisition system that generates data identifying the mobile device's physical environment; and   b. processing apparatus, responsive to the data acquisition system, to map or model the mobile device's physical environment and the data acquisition system's location within the mobile device's physical environment in a cell-based grid in which cells are assigned probabilities indicating certainty about whether the physical space corresponding to a cell is occupied by an object or contains empty space;   c. wherein the processing apparatus includes apparatus that:
 i. assigns and updates probabilities to each cell within the grid map from the data generated by the data acquisition system; 
 ii. determines if changes in a cell's probability of occupancy indicate that a cell currently identified as empty has become occupied or a cell currently identified as occupied has become empty; and 
 iii. marks such cells so as not to be updated with regard to their probability of containing an obstacle or not while said probability is changing. 
   
     
     
         17 . A system as claimed in  claim 16  wherein the marked cells also include a zone, of predetermined size, surrounding the marked cells. 
     
     
         18 . A system claimed in  claim 16  wherein the mobile device is a robot, the system further comprising a distance-measuring device, said distance-measuring device comprising light-emitting and light-receiving apparatus to emit light to measure distance based on reflected light, said data acquisition system being responsive to said distance-measuring device to generate said data identifying the mobile device's physical environment. 
     
     
         19 . A system as claimed in  claim 18  wherein the distance-measuring device comprises a laser rangefinder. 
     
     
         20 . A method for controlling movement of a robot, the method comprising:
 a. generating data identifying a physical environment of the robot;   b. mapping or modeling the robot's physical environment using said data;   c. determining whether the robot has lost its preferred orientation for operation;   d. if the robot has lost its preferred orientation, suspending said mapping while the robot has lost its preferred orientation, and resuming said mapping when the robot has resumed its preferred orientation; and   e. controlling movement of the robot in accordance with (a) to (d).   
     
     
         21 . A method as claimed in  claim 20  wherein said generating comprises measuring distances from objects in the robot's physical environment using a laser rangefinder. 
     
     
         22 . A method as claimed in  claim 20  wherein said determining comprises measuring delocalization of said robot with an accelerometer. 
     
     
         23 . A method for controlling movement of a robot, the method comprising:
 a. generating data identifying the physical environment of the robot and the robot's location within the robot's physical environment;   b. suspending or modifying the use of data generated by the data acquisition system when a portion of the map above a threshold limit corresponds to a predetermined shift of one or more elements in the map; and   c. controlling movement of the robot in accordance with (a) and (b).   
     
     
         24 . A method for controlling movement of a robot, the method comprising:
 a. generating a map of the robot's physical environment, said generating occurring either concurrently with or prior to tracking the robot's position;   b. updating said map either concurrently with or prior to tracking the device's position;   c. determining the robot's current location within said map by generating particles, each of said particles representing a potential position and/or orientation of the robot within its physical environment, wherein a data set of said particles may be generated and maintained iteratively to track changing position of the device within its physical environment, said determining including:   i. assigning a weight to each particle, particle weight being a relative measure of the particle's likelihood of accurately representing the robot's position with respect to other particles; and   ii. introducing erroneous particles whose potential positions are selected so that their assigned weights should be uniformly low with respect to the weights of the particles representing a potential position and/or orientation of the robot; and   iii. comparing the weights of the erroneous particles and the weights of the particles representing a potential position and/or orientation of the robot to determine whether the robot has become delocalized when a substantial number of erroneous particles have weights that are no longer uniformly low with respect to the weights of the particles representing a potential position and/or orientation of the robot.   d. The method further comprising controlling movement of the robot in accordance with (a) to (c).   
     
     
         25 . A method for controlling movement of a robot, the method comprising:
 a. generating data identifying the robot's physical environment; and   b. mapping or modeling the robot's physical environment and location within the robot's physical environment in a cell-based grid in which cells are assigned probabilities indicating certainty about whether the physical space corresponding to a cell is occupied by an object or contains empty space;   c. assigning and updating probabilities to each cell within the grid map from the generated data;   d. determining whether changes in a cell's probability of occupancy indicate that a cell currently identified as empty has become occupied or a cell currently identified as occupied has become empty;   e. marking such cells so as not to be updated with regard to their probability of containing an obstacle or not while said probability is changing; and   f. controlling movement of the robot in accordance with (a) to (c).