Robotics Fundamentals Series: Localization

Overview

Localization allows autonomous mobile robots to determine their position in the environment. A GPS (global positioning system) would seem ideal for mobile robot localization, but it faces the following challenges:

• Existing GPS network only provides accuracy to within several meters
• GPS technologies cannot function indoors
• GPS identifies an absolute position, but not a relative position with respect to other objects

To improve localization for autonomous mobile robots, the following approaches are often used: behavior-based navigation and map-based navigation.

Behavior-Based Navigation

Behavior-based robots use sensors to react to the current state of the world, as opposed to an agent’s memory or preconception of that world. An example of a behavior-based robot is DARwin, a soccer playing robot that was developed at Virginia Tech’s RoMeLa.  DARwin uses localization to determine its position on the soccer field.  DARwin uses a camera sensor to locate the goal, while simultaneously locating chalk lines to tell LabVIEW where DARwin is on the field. 

Figure 1. DARwin, a soccer playing robot developed at Virginia Tech’s RoMeLa

Odin, an unmanned vehicle created by Virginia Tech’s Victor Tango team to compete in the 2007 DARPA Urban Challenge also used behavior-based navigation. Although Odin did not rely solely on a behavior-based system, the driving behaviors software component was behavior based. This component used a behavior-based LabVIEW state machine architecture responsible for obeying the rules of the road and guiding the vehicle along the planned route.

With a behavior-based architecture, coordination becomes vital since there is no centralized planning module.  Control is shared amongst a variety of perception-action units, or behaviors. When a robot has conflicting desires, selecting the appropriate action can be a problem. For example, if the robot is an unmanned vehicle in an urban environment, the desire to drive in the right lane due to an upcoming right turn must supersede the desire to drive in the left lane due to a slow moving vehicle.

[+] Enlarge Image

Figure 2. An architecture for behavior-based navigation

 

Map-Based Navigation

With map-based navigation, robots attempt to localize by collecting sensor data, then updating its position with respect to a map of the environment. Map-based navigation has the following advantages:

• The map-based concept makes the robot’s position transparently available to human operators
• The map can used as a medium for communication between human and robot
• The map can also be built by the robot and used by humans

 

[+] Enlarge Image 

Figure 3. An architecture of map-based navigation

Unmanned vehicles competing in the DARPA Urban Challenge use map-based navigation with a map known as a priori map. The priori map is loaded into the robot prior to the start of the competition, and indicates the structural layout and major landmarks. To localize, they integrate data from both the map and on-board sensors, and combine it with knowledge of the vehicle’s motion.  An example of a map-based robot is Victor Tango, an unmanned vehicle created by Virginia Tech to compete in the 2007 DARPA Urban Challenge. 

Figure 4. Virginia Tech's unmanned vehicle which competed in the 2007 DARPA Urban Challenge

One of the main challenges of this type of localization is dealing with the uncertainty in both the driving and sensing of the vehicle.  In general, sensors have error and therefore the data they provide is nondeterministic. This data needs to be integrated in an optimal way. A common solution is to use Kalman filtering.

The Kalman Filter

A powerful technique for achieving sensor fusion for a large number of sensors is the Kalman filter. A Kalman filter optimizes the fusion of sensor signals and system knowledge. The localization component used by team Victor Tango contains a LabVIEW Kalman filter that tracks vehicle position and orientation.

When using a Kalman filter, perception is a multi-step process.  The robot’s total sensory input is treated as a set of extracted features (lines, trees, doors, etc.) that each relate to objects in the environment.  Given a set of possible features, the Kalman filter is used to fuse the distance estimate from each feature to a matching object in the map.  The steps used during the filtering process are listed below.

1. Robot Position Prediction - the position is predicted based on feedback from an encoder. 
2. Observation - the robot collects actual sensor data and extracts appropriate features.
3. Measurement Prediction - based on its predicted position on the map, the robot identifies the features that the robot expects to find and the positions of those features.
4. Matching - the robot identifies the best pairings between the features actually extracted during observation and the expected features due to measurement prediction. 
5. Estimation - the Kalman filter fuses the information provided by all of these matches to update the robot belief about robot position and the environment.

 

[+] Enlarge Image 

Figure 5. Schematic for Kalman filter mobile robot localization

Kalman filters can be easily implemented using the LabVIEW Control Design and Simulation Module, which allows users to design, simulate, and implement control systems with LabVIEW. This module provides Kalman filter libraries that can be used to build a controller and to estimate states. The block diagram below shows how to design a Kalman filter estimator in LabVIEW.

[+] Enlarge Image

Figure 6. Kalman Filter Estimator Example in LabVIEW

See also:

NI LabVIEW Control Design and Simulation Module

To learn more about robotics, refer to the Robotics Fundamentals Series homepage at ni.com/zone. 

---

References

Siegwart, Roland and Nourbakhsh, Illah R. Introduction to Autonomous Mobile Robots, Cambridge, Massachusetts: MIT Press, 2004.

 

Reader Comments | Submit a comment »