Robotics/Navigation/Localization

Localization involves one question: Where is the robot now? Or, robo-centrically, where am I, keeping in mind that "here" is relative to some landmark (usually the point of origin or the destination) and that you are never lost if you don't care where you are.

Although a simple question, answering it isn't easy, as the answer is different depending on the characteristics of your robot. Localization techniques that work fine for one robot in one environment may not work well or at all in another environment. For example, localizations which work well in an outdoors environment may be useless indoors.

All localization techniques generally provide two basic pieces of information:

• what is the current location of the robot in some environment?
• what is the robot's current orientation in that same environment?

The first could be in the form of Cartesian or Polar coordinates or geographic latitude and longitude. The latter could be a combination of roll, pitch and yaw or a compass heading.

Current Location

The current location of a robot can be determined in several very different ways:

Dead Reckoning

Dead reckoning uses odometry to measure how far the robot moves. Trigonometry and the equations of kinematics are all that is needed to calculate its new position.

This method has 2 requirements:

• It needs a way to determine its initial location.
• Its accuracy usually decreases over time as every measurement has an error and errors accumulate.

Dead reckoning is often used with other methods to improve the overall accuracy.

Least Mean Squares

There are numerous solutions to the localization robotics problem. These range from simple Dead Reckoning methods to advanced algorithms with expensive radar or vision system. The most important factor is picking an algorithm to find the robotic location is the availability of accurate relative and global position data. For simple systems with basic relative position sensors and some form of a global position sensor, the most practical and easiest to implement localization method is that of Least Mean Squares.

See Least Squares: http://en.wikipedia.org/wiki/Least_squares for more information on using the method of Least Squares to find solutions for over determined systems.

To look at the Least Mean Square (LMS) algorithm in a general sense first, it is important to look at the general principles that govern it. The goal of all localization methods is to minimize the error between where the robot is and where the robot should be. The algorithm must be able to follow a preset track or find the least error in the robot location (Adaptive Algorithms and Structures, p. 97). These goals for robot localization are applied to the LMS algorithm by adaptively adjusting weights to minimize the error between the actual function and the function generated by the LMS algorithm. As a subset of the Steepest Descent Algorithm (http://en.wikipedia.org/wiki/Gradient_descent), this method was created to minimize the error by estimating the gradient (http://en.wikipedia.org/wiki/Gradient) and is known as the simplest localization method with global position output.

Derivation of LMS Algorithm

The LMS algorithm can be applied to two cases:

• Parallel multiple inputs

• Series single input

File:LinearCombinerConfiguration.jpg

Figure 1: Linear Combiner Configuration [1]

File:CurveFit.jpg

Figure 2: Curve Fit to Data to Minimize Error [3]

File:TransversalCombinerConfiguration.jpg

Figure 3: Transversal Combiner Configuration [1]

In both cases, the gradient is calculated as

ε_k = d_k - X^T_kW_k

where ‘Y_k’ is the desired output, ‘X^T_k’ is the actual input, and ‘W_k’ for the kth input element. Next, the gradient estimate is calculated as

Now that we have the gradient estimate, the weights can be updated by

W_k+1 = W_k - μdel_k = W_k + 2με_kX_k

to minimize the error through iterative change. ‘μ ’ is the gain constant for training the algorithm. The use of training is to adjust how fast the error is corrected for by the weight update function [1]. If the training constant is too high, the system will oscillate and never converge to the minimal error value.

To illustrate the process other than in mathematical format, the LMS algorithm can be demonstrated through the use of pseudo code. The purpose of the code below is for illustration purposes only. This example is intended to provide a step-by-step visualization tool for beginning the coding process.

Procedure LMS

Initialize the Weights repeat choose training pair (x,d) for all k do

   yk = WkXk	 

end for all k do

   εk = Yk - dk 

end for all k do

   Wk(j+1) = Wk(j) + μεkXk

end until termination condition reached

Various Variations

Modified LMS Method

For problems with sequentially arriving data, the Modified LS method can be used to add or delete rows of data. In various time-series problems, a moving ‘window’ can be employed to evaluate data over a predefined timeframe. This method is useful in LMS problems that arise in statistics, optimization, and signal processing [2].

Constrained LMS Method

For curve and surface fitting application problems, the Constrained LMS method is very useful. Such problems require satisfying linear equations systems with various unknowns. This method only provides a useful solution if and only if each input can be scaled by some magnitude and still remains a constant [2].

Direct Methods for Sparse problems

A sparse LMS problem involves solving the LMS problem when the matrix has ‘relatively few’ nonzero elements. “J. H. Wilkinson defined a sparse matrix to be ‘any matrix with enough zeros that it pays to take advantage of them’” [2]. A more precise definition is more difficult to provide. Such problem usually involve large to enormous size and involve numerous unknowns. The following are examples of problem that can be classified as sparse problems: pattern matching, cluster analysis, and surface fitting [2].

Iterative Methods for LMS problems

A second method for solving sparse problems (in addition to the Direct Method mentioned above) is the Iterative Method. In general, the Iterative Method is used for analysis of under-determined, sparse problems to compute a minimum solution based on the norm of the input data [2].

Nonlinear LMS Method

For problems with nonlinear systems, the Nonlinear LMS method is useful for iteratively calculating the relative LMS solution to the problem. This method can be used for unconstrained optimization and various survey methods [2].

Additional Sources for Application and Theory

For further reference and additional reading, the following resources can be used for a more extensive overview of the subject.

• Adaptive Antenna Control by LMS

• LMS Estimation Techniques

• Least Squares

• Least Squares Filter

References

• Adaptive Signal Processing [1]

• Numerical Methods for LS Problem book [2]

• Least Squares Estimation [3]

GPS Global Positioning System

On large terrains GPS can provide more or less accurate coordinates, dead reckoning and the data from its other sensors can fill in the gaps. However on small terrains or indoors the GPS's inaccuracy becomes a problem and the dead reckoning and sensor data becomes the dominant factor in determining the location.

GPS-like Systems

Although GPS isn't very useful indoors, similar techniques as those used in GPS can be used indoors. All a robot needs is to measure it's distance to 3 fixed beacons. Each of these distances describe a sphere with the beacon in its center. 3 spheres will only intersect in one point.

Line following

Probably the easiest way: Draw a line on the ground and use IR reflection sensors to follow it. Useful as a track or to mark the edges of the robot's work area.

This can also be done by putting an electric cable in the ground and sending a modulated signal through it. The robot can detect this cable with magnetic sensors (Hall-sensors or coils).

The complex versions of line-following involves using sensors like vision (camera) which helps reducing overall cost of sensors and implementation and also provides versatility to detect lines of various colours. It allows a great scope for autonomy in the system too.

Landmarks

Placing landmarks is another way to help your robot to navigate through its environment. Landmarks can be active beacons (IR or sound) or passive (reflectors). Using bar code scanners is another possibility.

A special trick, if the environment is known beforehand, is to use collision detection (i.e. sensor bumpers or similar) with known objects. Together with dead reckoning the precision can be extraordinary even when using cheap equipment.

In new environments landmarks often need to be determined by the robot itself. Through the use of sensor data collected by laser, sonar or camera, specific landmark types (e.g. walls, doors, corridors) can be recognised and used for localization.

Current Heading

Determining a robot's heading can be done with a compass sensor. These sensors usually consist of 2 magnetic field sensors placed at a 90° angle.

These sensors measure the earth's magnetic field and can be influenced by other magnetic fields. Speakers, transformers, electric cables and refrigerator magnets can reduce the accuracy of the compass. Compass sensor modules can have built-in filtering for the magnetic fields of AC.