Dead reckoning

For other uses, see Dead reckoning (disambiguation).

The navigator plots his 9am position, indicated by the triangle, and, using his course and speed, estimates his position at 9:30am and 10am.

In navigation, dead reckoning (also ded (for deduced) reckoning or DR) is the process of calculating one's current position by using a previously determined position, or fix, and advancing that position based upon known or estimated speeds over elapsed time, and course. While traditional methods of dead reckoning are no longer considered primary means of navigation, modern inertial navigation systems, which also depend upon dead reckoning, are very widely used.

By analogy with their navigational use, the words dead reckoning are also used to mean the process of estimating the value of any variable quantity by using an earlier value and adding whatever changes have occurred in the meantime. Often, this usage implies that the changes are not known accurately. The earlier value and the changes may be measured or calculated quantities.

A disadvantage of dead reckoning is that since new values are calculated solely from previous values, any errors and uncertainties of the process are cumulative, so the error and uncertainty in the value grow with time.

Animal navigation

In studies of animal navigation, dead reckoning is more commonly (though not exclusively) known as path integration, and animals use it to estimate their current location based on the movements they made since their last known location. Animals such as ants, rodents, and geese have also been shown to continuously keep track of their locations relative to a starting point and return to it, an important skill to have for creatures that forage for food and then return to a fixed home.^[1]

Marine navigation

In marine navigation a "dead" reckoning plot generally does not take into account the effect of currents or wind. Aboard ship a dead reckoning plot is considered important in evaluating position information and planning the movement of the vessel.^[2]

Dead reckoning begins with a known position, or fix, which is then advanced, mathematically or directly on the chart, by means of recorded heading, speed, and time. Speed can be determined by many methods. Before modern instrumentation, it was determined aboard ship using a chip log. More modern methods include pit log referencing engine speed (e.g. in rpm) against a table of total displacement (for ships) or referencing one's indicated airspeed fed by the pressure from a Pitot tube. This measurement is converted to an equivalent airspeed based upon known atmospheric conditions and measured errors in the indicated airspeed system. A naval vessel uses a device called a pit sword (rodmeter), which uses two sensors on a metal rod to measure the electromagnetic variance caused by the ship moving through water. This change is then converted to ship's speed. Distance is determined by multiplying the speed and the time. This initial position can then be adjusted resulting in an estimated position by taking into account the current (known as set and drift in marine navigation). If there is no positional information available, a new dead reckoning plot may start from an estimated position. In this case subsequent dead reckoning positions will have taken into account estimated set and drift.

Dead reckoning positions are calculated at predetermined intervals, and are maintained between fixes. The duration of the interval varies. Factors including one's speed made good and the nature of heading and other course changes, and the navigator's judgment determine when dead reckoning positions are calculated.

Before the development of the marine chronometer, dead reckoning was the primary method of determining longitude available to mariners such as Christopher Columbus and John Cabot on their trans-Atlantic voyages. Tools such as the Traverse board were developed to enable even illiterate crew members to collect the data needed for dead reckoning.

Air navigation

Traditionally, in air navigation, displacement or position caused by wind were taken into account, using a tool called a wind triangle. Generally speaking, dead reckoning positions were calculated at least once every 300 miles and when making combined turns totaling more than 30 degrees from the initial heading out of the last DR position.

Today, dead reckoning is rarely used in this traditional form for air navigation, but it survives in the form of inertial navigation systems, which are nearly universal on more advanced aircraft. The INS is used in combination with other navigation aids, such as GPS, in order to provide reliable navigation capability under virtually any conditions, with or without external navigation references.

However, dead reckoning is still widely used in civil aircraft not equipped with GPS or radio navigation aids. It is also important for the pilot to be trained in dead reckoning in case of a system failure on more advanced systems.

Automotive navigation

Dead reckoning is today implemented in some high-end automotive navigation systems in order to overcome the limitations of GPS/GNSS technology alone. Satellite microwave signals are unavailable in parking garages and tunnels, and often severely degraded in urban canyons and near trees due to blocked lines of sight to the satellites or multipath propagation. In a dead-reckoning navigation system, the car is equipped with sensors that record the wheel rotation and steering direction. These sensors are often already present in cars for other purposes (anti-lock braking system, electronic stability control) and can be read by the navigation system from the controller-area network bus. The navigation system then uses a Kalman filter in order to integrate the reliability and short-term accuracy of the sensor data with the long-term accuracy of the satellite data into a position fix that combines the best of both worlds.

Autonomous Navigation, or Robotic Positioning

Dead reckoning is also utilized in some lower-end, non mission-critical, or tightly constrained (in the sense of time and/or weight) robotic applications. It is usually utilized to reduce the need for sensing technology in an autonomous robot, such as ultrasonic sensors, GPS, or placement of some linear and rotary encoders, thus greatly reducing the cost, and complexity at the expense of performance, and repeatability. The proper utilization of Dead reckoning in this sense would be to supply a known percentage of maximum current or voltage to the robot's drive motors (or pressure in the case of a pneumatic or hydraulic cylinder) over a given amount of time from a general starting point. This raises more problems in the event of a fully autonomous robot, as they usually will contain a battery, which does not supply a constant voltage. This combined with varying on board clock speeds of the robot's on board computer can lead to differences in distances ranging from a few millimeters (in CNC machining) to kilometers (in UAV's), based upon the duration of the run, the speed of the robot, the length of the run, and several other factors. For this reason, most robots designed for automation are equipped with positioning sensors, such as those listed above.

Directional dead reckoning

Main article: South-pointing chariot

The south-pointing chariot was an ancient Chinese device consisting of a two-wheeled horse-drawn vehicle which carried a pointer that was intended always to aim to the south, no matter how the chariot turned. The chariot predated the navigational use of the magnetic compass, and did not include any component that would allow it to detect the direction that was south. Instead, it used a kind of directional dead reckoning. At the start of a journey, the pointer was aimed southward by hand, probably using local knowledge or astronomical observations e.g. of the Pole Star. Then, every time the chariot turned as it travelled, a mechanical mechanism, possibly containing differential gears, used the rotational speeds of the two road wheels to turn the pointer relative to the body of the chariot by an angle that, if the gear ratios in the mechanism exactly matched the dimensions of the chariot, would have exactly counteracted the turn the chariot made, keeping the pointer aiming in its original direction, to the south. Similar to other forms of dead reckoning, the new angle between the pointer and the heading of the chariot, after a turn, was the old angle modified by an angle that should have equalled the angle of the turn. In reality, cumulative errors and uncertainties must have occurred, limiting the chariot's usefulness as a compass.

Etymology

There is disagreement about the derivation of the phrase. It is sometimes thought (particularly among sailors and pilots in the USA^[3]) to come from deduced reckoning and is sometimes given in modern sources as an alternatively spelled ded reckoning. According to the Oxford English Dictionary, the phrase dead reckoning dates from Elizabethan times (1605–1615).^[4] The popular etymology from deduced is not documented in the OED or any other historical dictionary. It is not clear what 'dead' might mean in the context of dead reckoning, and several alternative theories have been promulgated.^[3]

Dead reckoning in literature

In Walden, Henry David Thoreau suggests the following approach to life:

"In the midst of this chopping sea of civilized life, such are the clouds and storms and quicksands and thousand-and-one items to be allowed for, that a man has to live, if he would not founder and go to the bottom and not make his port at all, by dead reckoning, and he must be a great calculator indeed who succeeds."

In "Moby Dick, or, The Whale" Herman Melville states on page 507: "...and in these same perilous seas, gropes he not his way by mere dead reckoning of the error-abounding log?"

Differential steer drive dead reckoning

Here are the dead reckoning equations for the coordinates (x and y), and heading (θ) for a differential drive robot with encoders on both drives:

$\Delta \theta = 2 \pi \frac{R_W} {D} \frac{T_1-T_2} {T_R}$

$\Delta x = R_W \cos(\theta)(T_1+T_2) \frac{\pi} {T_R}$

$\Delta y = R_W \sin(\theta)(T_1+T_2) \frac{\pi} {T_R}$

where T₁ are the encoder ticks recorded on drive one, T₂ are the encoder ticks recorded on drive two, R_W is the radius of each drive wheel, D is the separation between the wheels, and T_R is the number of encoder ticks recorded in a full, in-place rotation.

Dead reckoning for networked games

Networked games and simulation tools routinely use dead reckoning to predict where an actor should be right now, using its last known kinematic state (position, velocity, acceleration, orientation, and angular velocity).^[5] This is primarily needed because it is impractical to send network updates at the rate that most games run, 60 Hz. The basic solution starts by projecting into the future using linear physics^[6]:

$P_t = P_0 + V_0T + \frac{1}{2}A_0T^2$

This formula is used to move the object until a new update is received over the network. At that point, the problem is that there are now two kinematic states: the currently estimated position and the just received, actual position. Resolving these two states in a believable way can be quite complex. One approach is to create a curve (ex cubic Bezier splines, Catmull-Rom splines, and Hermite curves)^[7] between the two states while still projecting into the future. Another technique is to use projective velocity blending, which is the blending of two projections (last known and current) where the current projection uses a blending between the last known and current velocity over a set time.^[5]

$V_b = V_0 + \left (\acute{V}_0 - V_0 \right)\hat{T}$

$P_t = P_0 + V_bT_t + \frac{1}{2}\acute{A}_0T_t^2$

$\acute{P}_t = \acute{P}_0 + \acute{V}_0T_t + \frac{1}{2}\acute{A}_0T_t^2$

$Pos = P_t + \left (\acute{P}_t - P_t \right)\hat{T}$

See also

Nautical portal

• Abbe error
• Air navigation
• Attitude and Heading Reference Systems
• Celestial navigation
• Client-side prediction
• Extrapolation
• Inertial navigation system
• Spherical trigonometry

References

1. ^ Gallistel. The Organization of Learning. 1990.
2. ^ http://www.irbs.com/bowditch/pdf/chapt07.pdf
3. ^ ^{a b} "Is "dead reckoning" short for "deduced reckoning"?". StraightDope.com. 2002-11-21. http://www.straightdope.com/mailbag/mdeadreckoning.html. Retrieved 2009-10-06. 
4. ^ Ridley, Mark (1613). A short treatise of magneticall bodies and motions. London: Nicholas Okes. p. 147. http://echo.mpiwg-berlin.mpg.de/ECHOdocuView/ECHOzogiLib?url=/mpiwg/online/permanent/library/P1BZDEF0/index.meta&start=81&pn=81&mode=texttool. Retrieved 2009-10-06. "[...] keeping a true, not a dead reckoning of his course [...]"  (This is the first usage cited by the Oxford English Dictionary.)
5. ^ ^{a b} Murphy, Curtiss. Believable Dead Reckoning for Networked Games. Published in Game Engine Gems 2, Lengyel, Eric. AK Peters, 2011, p 308-326.
6. ^ Van Verth, James. Essential Mathematics for Games And Interactive Applications. Second Edition. Morgan Kaufmann, 1971, p. 580.
7. ^ Lengyel, Eric. Mathematics for 3D Game Programming And Computer Graphics. Second Edition. Charles River Media, 2004.

External links

• Bowditch Online: "Dead reckoning"
• Straight Dope: Is "dead reckoning" short for "deduced reckoning"?
• Jesse Aronson: "Dead Reckoning: Latency Hiding for Networked Games"
• A paper about pedestrian dead reckoning: "Omni-directional Pedestrian Navigation for First Responders" by Stéphane Beauregard (2006)
• WFR, a Dead Reckoning Robot