Dead reckoning
Encyclopedia
Navigation
Navigation is the process of monitoring and controlling the movement of a craft or vehicle from one place to another. It is also the term of art used for the specialized knowledge used by navigators to perform navigation tasks...
, 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
Fix (position)
In position fixing navigation, a position fix or simply a fix is a position derived from measuring external reference points.The term is generally used with manual or visual techniques such as the use of intersecting visual or radio position lines rather than the use of more automated and accurate...
, 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 system
Inertial navigation system
An inertial navigation system is a navigation aid that uses a computer, motion sensors and rotation sensors to continuously calculate via dead reckoning the position, orientation, and velocity of a moving object without the need for external references...
s, 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
Propagation of uncertainty
In statistics, propagation of error is the effect of variables' uncertainties on the uncertainty of a function based on them...
.
Animal navigation
In studies of animal navigation, dead reckoning is more commonly (though not exclusively) known as path integrationPath integration
Path integration is the name given to the method thought to be used by animals for dead reckoning.Charles Darwin and J.J. Murphy first postulated an inertially-based navigation system in animals in 1873...
, 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.
Marine navigation
In marine navigation a "dead" reckoning plot generally does not take into account the effect of currentOcean current
An ocean current is a continuous, directed movement of ocean water generated by the forces acting upon this mean flow, such as breaking waves, wind, Coriolis effect, cabbeling, temperature and salinity differences and tides caused by the gravitational pull of the Moon and the Sun...
s or wind
Wind
Wind is the flow of gases on a large scale. On Earth, wind consists of the bulk movement of air. In outer space, solar wind is the movement of gases or charged particles from the sun through space, while planetary wind is the outgassing of light chemical elements from a planet's atmosphere into space...
. Aboard ship a dead reckoning plot is considered important in evaluating position information and planning the movement of the vessel.
Dead reckoning begins with a known position, or fix
Fix (position)
In position fixing navigation, a position fix or simply a fix is a position derived from measuring external reference points.The term is generally used with manual or visual techniques such as the use of intersecting visual or radio position lines rather than the use of more automated and accurate...
, 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
Chip log
A chip log, also called common log, ship log or just log, is a navigation tool used by mariners to estimate the speed of a vessel through water.-Construction:...
. More modern methods include pit log referencing engine speed (e.g. in rpm
Revolutions per minute
Revolutions per minute is a measure of the frequency of a rotation. It annotates the number of full rotations completed in one minute around a fixed axis...
) against a table of total displacement (for ships) or referencing one's indicated airspeed fed by the pressure from a Pitot tube
Pitot tube
A pitot tube is a pressure measurement instrument used to measure fluid flow velocity. The pitot tube was invented by the French engineer Henri Pitot Ulo in the early 18th century and was modified to its modern form in the mid-19th century by French scientist Henry Darcy...
. This measurement is converted to an equivalent airspeed
Equivalent airspeed
Equivalent airspeed is the airspeed at sea level in the International Standard Atmosphere at which the dynamic pressure is the same as the dynamic pressure at the true airspeed and altitude at which the aircraft is flying. In low-speed flight, it is the speed which would be shown by an airspeed...
based upon known atmospheric conditions and measured errors in the indicated airspeed system. A naval vessel uses a device called a pit sword
Pit sword
The pit sword is a blade of metal or plastic that extends into the water beneath the hull of a nautical vessel. It is part of the pitometer log, a device for measuring the ship's speed through the water.-External links:**...
(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
Set and drift
In navigation set and drift are characteristics of the current or the velocity of water over the ground in which a ship is sailing.Drift is the magnitude, or speed of the current and set is the bearing in the direction the current is flowing. Bearing is measured in degrees clockwise from either...
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
Marine chronometer
A marine chronometer is a clock that is precise and accurate enough to be used as a portable time standard; it can therefore be used to determine longitude by means of celestial navigation...
, dead reckoning was the primary method of determining longitude
Longitude
Longitude is a geographic coordinate that specifies the east-west position of a point on the Earth's surface. It is an angular measurement, usually expressed in degrees, minutes and seconds, and denoted by the Greek letter lambda ....
available to mariners such as Christopher Columbus
Christopher Columbus
Christopher Columbus was an explorer, colonizer, and navigator, born in the Republic of Genoa, in northwestern Italy. Under the auspices of the Catholic Monarchs of Spain, he completed four voyages across the Atlantic Ocean that led to general European awareness of the American continents in the...
and John Cabot
John Cabot
John Cabot was an Italian navigator and explorer whose 1497 discovery of parts of North America is commonly held to have been the first European encounter with the continent of North America since the Norse Vikings in the eleventh century...
on their trans-Atlantic voyages. Tools such as the Traverse board
Traverse board
The traverse board is a memory aid formerly used in dead reckoning navigation to easily record the speeds and directions sailed during a watch. Even an illiterate crew member could use the traverse board....
were developed to enable even illiterate crew members to collect the data needed for dead reckoning.
Air navigation
Traditionally, in air navigationAir navigation
The basic principles of air navigation are identical to general navigation, which includes the process of planning, recording, and controlling the movement of a craft from one place to another....
, displacement or position caused by wind were taken into account, using a tool called a wind triangle
Wind triangle
The wind triangle is a graphical representation of the relationship between aircraft motion and wind. It is used extensively in dead reckoning navigation.The wind triangle is a vector diagram, with three vectors....
. 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 system
Inertial navigation system
An inertial navigation system is a navigation aid that uses a computer, motion sensors and rotation sensors to continuously calculate via dead reckoning the position, orientation, and velocity of a moving object without the need for external references...
s, 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 systemAutomotive navigation system
An automotive navigation system is a satellite navigation system designed for use in automobiles. It typically uses a GPS navigation device to acquire position data to locate the user on a road in the unit's map database. Using the road database, the unit can give directions to other locations...
s in order to overcome the limitations of GPS/GNSS technology alone. Satellite microwave signals are unavailable in parking garages and tunnel
Tunnel
A tunnel is an underground passageway, completely enclosed except for openings for egress, commonly at each end.A tunnel may be for foot or vehicular road traffic, for rail traffic, or for a canal. Some tunnels are aqueducts to supply water for consumption or for hydroelectric stations or are sewers...
s, and often severely degraded in urban canyon
Urban canyon
An urban canyon is an artefact of an urban environment similar to a natural canyon. It is manifested by streets cutting through dense blocks of structures, especially skyscrapers, which causes a canyon effect...
s 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
Anti-lock braking system
An anti-lock braking system is a safety system that allows the wheels on a motor vehicle to continue interacting tractively with the road surface as directed by driver steering inputs while braking, preventing the wheels from locking up and therefore avoiding skidding.An ABS generally offers...
, electronic stability control
Electronic stability control
Electronic stability control is a computerized technology that may potentially improve the safety of a vehicle's stability by detecting and minimizing skids. When ESC detects loss of steering control, it automatically applies the brakes to help "steer" the vehicle where the driver intends to go...
) and can be read by the navigation system from the controller-area network bus. The navigation system then uses a Kalman filter
Kalman filter
In statistics, the Kalman filter is a mathematical method named after Rudolf E. Kálmán. Its purpose is to use measurements observed over time, containing noise and other inaccuracies, and produce values that tend to be closer to the true values of the measurements and their associated calculated...
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 robotAutonomous robot
Autonomous robots are robots that can perform desired tasks in unstructured environments without continuous human guidance. Many kinds of robots have some degree of autonomy. Different robots can be autonomous in different ways...
, such as ultrasonic sensor
Ultrasonic sensor
Ultrasonic sensors work on a principle similar to radar or sonar which evaluate attributes of a target by interpreting the echoes from radio or sound waves respectively. Ultrasonic sensors generate high frequency sound waves and evaluate the echo which is received back by the sensor...
s, GPS, or placement of some linear
Linear encoder
A linear encoder is a sensor, transducer or readhead paired with a scale that encodes position. The sensor reads the scale in order to convert the encoded position into an analog or digital signal, which can then be decoded into position by a digital readout or motion controller.The encoder can be...
and rotary encoder
Rotary encoder
A rotary encoder, also called a shaft encoder, is an electro-mechanical device that converts the angular position or motion of a shaft or axle to an analog or digital code. The output of incremental encoders provides information about the motion of the shaft which is typically further processed...
s, 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
Pneumatic cylinder
Pneumatic cylinders are mechanical devices which utilize the power of compressed gas to produce a force in a reciprocating linear motion....
or hydraulic cylinder
Hydraulic cylinder
A Hydraulic cylinder is a mechanical actuator that is used to give a unidirectional force through a unidirectional stroke. It has many applications, notably in engineering vehicles.- Operation :...
) 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
Clock rate
The clock rate typically refers to the frequency that a CPU is running at.For example, a crystal oscillator frequency reference typically is synonymous with a fixed sinusoidal waveform, a clock rate is that frequency reference translated by electronic circuitry into a corresponding square wave...
of the robot's on board computer can lead to differences in distances ranging from a few millimeters (in CNC machining
Numerical control
Numerical control refers to the automation of machine tools that are operated by abstractly programmed commands encoded on a storage medium, as opposed to controlled manually via handwheels or levers, or mechanically automated via cams alone...
) to kilometers (in UAV's
Unmanned aerial vehicle
An unmanned aerial vehicle , also known as a unmanned aircraft system , remotely piloted aircraft or unmanned aircraft, is a machine which functions either by the remote control of a navigator or pilot or autonomously, that is, as a self-directing entity...
), 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
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 StarPole star
The term "Pole Star" usually refers to Polaris, which is the current northern pole star, also known as the North Star.In general, however, a pole star is a visible star, especially a prominent one, that is approximately aligned with the Earth's axis of rotation; that is, a star whose apparent...
. 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
Compass
A compass is a navigational instrument that shows directions in a frame of reference that is stationary relative to the surface of the earth. The frame of reference defines the four cardinal directions – north, south, east, and west. Intermediate directions are also defined...
.
Etymology
There is disagreement about the derivation of the phrase. It is sometimes thought (particularly among sailors and pilots in the USA) to come from deduced reckoning and is sometimes given in modern sources as an alternatively spelled ded reckoning. According to the Oxford English DictionaryOxford English Dictionary
The Oxford English Dictionary , published by the Oxford University Press, is the self-styled premier dictionary of the English language. Two fully bound print editions of the OED have been published under its current name, in 1928 and 1989. The first edition was published in twelve volumes , and...
, the phrase dead reckoning dates from Elizabethan times (1605–1615). 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.
Dead reckoning in literature
In Walden, Henry David ThoreauHenry David Thoreau
Henry David Thoreau was an American author, poet, philosopher, abolitionist, naturalist, tax resister, development critic, surveyor, historian, and leading transcendentalist...
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
Herman Melville
Herman Melville was an American novelist, short story writer, essayist, and poet. He is best known for his novel Moby-Dick and the posthumous novella Billy Budd....
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:
where
are the encoder ticks recorded on drive one, 
are the encoder ticks recorded on drive two, 
is the radius of each drive wheel, 
is the separation between the wheels, and 
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). 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:
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) 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.
See also
- Abbe errorAbbe errorAbbe error, named after Ernst Abbe, also called sine error, describes the magnification of angular error over distance. For example, when one measures a point that is 1 meter away at 45 degrees, an angular error of 1 degree corresponds to a positional error of over 1.745 cm, equivalent to a...
- Air navigationAir navigationThe basic principles of air navigation are identical to general navigation, which includes the process of planning, recording, and controlling the movement of a craft from one place to another....
- Attitude and Heading Reference SystemsAttitude and Heading Reference SystemsAn attitude heading reference system consists of sensors on three axes that provide heading, attitude and yaw information for aircraft. They are designed to replace traditional mechanical gyroscopic flight instruments and provide superior reliability and accuracy.AHRS consist of either solid-state...
- Celestial navigationCelestial navigationCelestial navigation, also known as astronavigation, is a position fixing technique that has evolved over several thousand years to help sailors cross oceans without having to rely on estimated calculations, or dead reckoning, to know their position...
- Client-side predictionClient-side predictionClient-side prediction is a network programming technique used in video games intended to conceal negative effects of high latency connections...
- ExtrapolationExtrapolationIn mathematics, extrapolation is the process of constructing new data points. It is similar to the process of interpolation, which constructs new points between known points, but the results of extrapolations are often less meaningful, and are subject to greater uncertainty. It may also mean...
- Inertial navigation systemInertial navigation systemAn inertial navigation system is a navigation aid that uses a computer, motion sensors and rotation sensors to continuously calculate via dead reckoning the position, orientation, and velocity of a moving object without the need for external references...
- Spherical trigonometrySpherical trigonometrySpherical trigonometry is a branch of spherical geometry which deals with polygons on the sphere and the relationships between the sides and the angles...
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