Dead Reckoning for Walking Robots

Many mobile robot missions and tasks require that the robot, whether autonomous or teleoperated, have some knowledge of its spatial location. To provide knowledge to both people and robots about a robot's location, many mobile robots use "dead reckoning." The purpose of dead reckoning is to monitor and maintain the robot's position and orientation from a fixed, external reference frame. Similar to the odometer in a car, estimating a robot's position is accomplished by summing its incremental movements relative to a starting point. While dead reckoning has been practiced by navigators on ships and competitors in the sport of orienteering, the application to walking machines is new and innovative. Many mobile vehicles employ dead reckoning because it is simple, inexpensive, and robust.

One problem people face when using mobile robots is determining the position and orientation of the robots at any given time. To solve this, a coordinate system called the body frame is assigned to the robot; another coordinate system, called the world frame, is assigned to a fixed frame of reference. Points in one frame are then mapped into the other frame by a translation (represented as a three-dimensional vector) and a rotation (represented as a 3x3 orthonormal matrix). The problem, then, is to find the rigid body transformation (matrix R and vector T)-that is, to determine the position and orientation of the robot in the world based on the positions of the feet- that maps foot positions (Pb) in the body frame into foot positions (Pw) in the world frame. This can be shown as: Pw = R Pb + T.

A general solution to the dead reckoning problem for legged vehicles does not depend on the number of legs or their arrangement on the robot. It assumes that at any given time, the robot can be treated as a rigid body, which means that the feet do not move unless commanded to do so.

The dead reckoning method consists of three major steps. This method has been experimentally validated on the Ambler, an autonomous, six-legged walker, but the results are general and can be applied to any stable walking mechanism. The first step is used to remove erroneous data points so that they do not affect the accuracy of the solution. The second step determines the actual position of the rigid body transformation. And, the third step is used to update the positions of the feet based on the newly calculated body position. The three steps, in this order, are:

1. Identify the feet that have slipped in order to prevent them from being used in further computation.
2. Solve for the rigid body transformation that best transforms foot positions in body coordinates to the world coordinate system, using a technique based on singular value decomposition. In our tests, we used the least-squared error criterion to specify the sense of "best."
3. Update the foot positions, if necessary, based on the new body pose and the current leg joint angles. Ideally, no update should be required, but we have found both in practice and in theory, the least-square solution may cause discrepancies between the current and stored foot positions.

Results showed that the dead reckoned position of the robot consistently lags the actual position by approximately two percent. This systematic error appears to be due to inaccuracies in the kinematic model of the robot. The errors in these tests could be due to either defects of the robot's legs or foot slippage. Since the error is systematic, it is easily corrected.

Results from experiments on the dead reckoning system implemented in the Ambler can be applied to any statically stable walking robot.

Point of Contact:
Eric Krotkov
Robotics Institue
Carnegie Mellon University
Pittsburgh, PA 15213 412-268-3058
epk@cs.cmu.edu

Telerobotics Program page

Please email the site webmaster with any comments, criticisms or corrections for this page.
Maintained by: Dave Lavery
Last updated: May 10, 1996