7.3 amcl

Authors

Andrew Howard ahoward(at)usc.edu,Boyoon Jung boyoon(at)robotics.usc.edu

Synopsis

The amcl driver implements the Adaptive Monte-Carlo Localization algorithm described by Fox [2]. At the conceptual level, the amcl driver maintains a probability distribution over the set of all possible robot poses, and updates this distribution using data from odometry, sonar and/or laser range-finders. The driver also requires a pre-defined map of the environment against which to compare observed sensor values. At the implementation level, the amcl driver represents the probability distribution using a particle filter. The filter is ``adaptive'' because it dynamically adjusts the number of particles in the filter: when the robot's pose is highly uncertain, the number of particles is increased; when the robot's pose is well determined, the number of particles is decreased. The driver is therefore able make a trade-off between processing speed and localization accuracy.

As an example, consider the sequence of images shown in Figure 7.1. This sequence shows the filter converging from an initial configuration in which the pose of the robot is entirely unknown to a final configuration in which the pose of the robot is well determined. At the same time, the number of particles in the filter decreases from 100,000 to less than 100.

The amcl driver has the some of the usual features - and failures - associated with simple Monte-Carlo Localization techniques:

• If the robot's initial pose is specified as being completely unknown, the driver's estimate will usually converge to correct pose. This assumes that the particle filter starts with a large number of particles (to cover the space of possible poses), and that the robot is driven some distance through the environment (to collect observations).
• If the robot's initial pose is specified accurately, but incorrectly, or if the robot becomes lost (e.g., by picking it up and replacing it elsewhere) the driver's estimate will not converge on the correct pose. Such situations require the use of more advanced techniques that have not yet been implemented (see [6], for example).

The amcl driver also has some slightly unusual temporal behavior:

• When the number of particles in the filter is large, data may arrive from the sensors faster than it can be processed. When this happens, data is queued up for later processing, but the driver continues to generate an up-to-date estimate for the robot pose. Thus, for example, at time t = 10 sec, the driver may have only processed sensor readings up until time t = 5 sec, but will nevertheless generate an estimate (prediction) of where the robot is at t = 10 sec. The adaptive nature of the algorithm more-or-less guarantees that the driver will eventual ``catch up'': as more sensor readings are processed, the number of particles will generally decrease, and the sensor update step of the algorithm will run faster.

Figure 7.1: Snap-shots showing the amcl driver in action; convergence in this case is relatively slow.

Caveats

At the time of writing, this driver is still evolving. The sensor models, in particular, are currently over-simplified and under-parameterized (there are lots of magic numbers lurking about the place). Consequently, while this driver is known to work for certain hardware configurations (think Pioneer2DX with a SICKLMS200 laser range-finder), other configurations may require some refinement of the sensor models.

Interfaces

Supported interfaces:

• localize

Required devices:

• position
• Any combination of: sonar, laser and wifi.

Supported configuration requests:

• None.

Configuration file options

Name Type Default Meaning

Notes

• Maps

  The odometric, sonar and laser sensor models make use of a common occupancy grid map. This map is a regular grid in which cells are in one of three states: occupied, empty or unknown (although the behavior for unknown cells is currently undefined). Maps are stored as (uncompressed) images in PGM or PNM/grayscale format: black pixels are treated as occupied cells, white pixels are treated as empty cells, and the remaining colors are treated as unknown. The interpretation of these colors may be reversed (white is occupied, black is unknown) by setting the map_negate flag in the configuration file. This flag is particularly handy if you wish to use the same image file as both a map and a Stage bitmap.

  TODO: WiFi maps

• Coordinate System

  The origin of the global coordinate system corresponds to the center of occupancy grid map. Standard coordinate orientation is used; i.e., positive x is towards the right of the map, positive y towards the top of the map.

• Number of particles

  The number of particles in the filter can be controlled using the configuration file parameters pf_err and pf_z. Specifically, pf_err is the maximum allowed error between the true distribution and the estimated distribution, while pf_z is the upper standard normal quantile for (1 - p), where p is the probability that the error on the estimated distribution will be less than pf_err. If you dont know what that means, dont worry, I'm not exactly sure either. See [2] for a more meaningful explanation.

• Speed

  Many factors affect the speed at which the amcl driver runs, but the following tips might be helpful:

  • Reducing the number of laser range readings being used ( laser_max_samples in the configuration file) will significantly increase driver speed, but may also lead to slower convergence and/or less accurate localization.
  • Increasing the allowed error pf_err and reducing the quantile pf_z will lead to smaller particle sets and will hence increase driver speed. This may also lead, however, to over-convergence.
  As a benchmark, this driver has been successfully deployed on a Pioneer2DX equipped with a SICK LMS200 and a 266MHz Mobile Pentium with 32Mb of RAM.

• Memory

  The two key factors affecting memory usage are:

  • The size and resolution of the map.
  • The maximum number of particles.
  As currently configured, the amcl driver will typically use 10 to 20Mb of memory. On embedded systems, where memory is at a premium, users may have to decrease the map resolution or the maximum number of particles to achieve acceptable preformance.

Example: Using the amcl driver with a Pioneer robot

The following configuration file illustrates the use of the amcl driver on a Pioneer robot equipped with a SICK LMS200 scanning laser range finder:

  position:0 
  (
     driver "p2os_position" 
     port "/dev/ttyS1"
  )
  
  laser:0 
  (
    driver "sicklms200" 
    port "/dev/ttyS2"
  )

  localize:0 
  (
    driver "amcl"
    position_index 0
    laser_index 0
    map_file "mymap.pgm"
    map_scale 0.05
  )

Naturally, the port, map_file and map_scale values should be changed to match your particular configuration.

Example: Using the amcl driver with Stage

The amcl driver is not supported natively in Stage. Users must therefore employ a second Player server configured to use the passthrough driver (see Section 7.31). The basic procedure is as follows.

• Start Stage with a world file something like this:

    ...
    position (port 6665 laser ())
    ...
  

  Stage will create one robot (position device) with a laser, and create a Player server on port 6665.
• Start another Player server using the command

    player -p 7000 amcl.cfg
  

  where the configuration file amcl.cfg looks like this:

    position:0 
    (
      driver "passthrough" 
      port 6665 index 0
    )
  
    laser:0 
    (
      driver "passthrough" 
      port 6665 
      index 0
    ) 
  
    localize:0 
    (
      driver "amcl" 
      position_index 0 
      laser_index 0 
      map_file "cave.pnm"
      map_scale 0.03
      map_negate 1
    )
  

  The second Player server will listen on port 7000; clients connecting to this server will see a robot with position, laser and localize devices. The map file cave.pnm can be the same file used by Stage to create the world bitmap.

Example: Using WiFi signal strength

TODO