navigation Navigation is a field of study that focuses on the process of monitoring and controlling the movement of a craft or vehicle from one place to another.Bowditch, 2003:799. The field of navigation includes four general categories: land navigation, ...

, dead reckoning is the process of calculating current position of some moving object by using a previously determined position, or fix, and then incorporating estimates of speed, heading direction, and course over elapsed time. The corresponding term in biology, used to describe the processes by which animals update their estimates of position or heading, is

path integration Path integration is the method thought to be used by animals for dead reckoning. History Charles Darwin first postulated an inertially-based navigation system in animals in 1873. Dead reckoning is subject to cumulative errors. Advances in navigational aids that give accurate information on position, in particular

satellite navigation A satellite navigation or satnav system is a system that uses satellites to provide autonomous geo-spatial positioning. It allows satellite navigation devices to determine their location (longitude, latitude, and altitude/elevation) to high pr ...

using the

Global Positioning System The Global Positioning System (GPS), originally Navstar GPS, is a satellite-based radionavigation system owned by the United States government and operated by the United States Space Force. It is one of the global navigation satellite sy ...

, have made simple dead reckoning by humans obsolete for most purposes. However,

inertial navigation system An inertial navigation system (INS) is a navigation device that uses motion sensors (accelerometers), rotation sensors ( gyroscopes) and a computer to continuously calculate by dead reckoning the position, the orientation, and the velocity (dir ...

s, which provide very accurate directional information, use dead reckoning and are very widely applied.

Etymology

The term "dead reckoning" was not originally used to abbreviate "deduced reckoning," nor is it a misspelling of the term "ded reckoning." The use of "ded" or "deduced reckoning" is not known to have appeared earlier than 1931, much later in history than "dead reckoning" appearing as early as 1613 in the Oxford English Dictionary. The original intention of "dead" in the term is not clear however. Whether it is used to convey "absolute" as in "dead ahead," reckoning using other objects that are "dead in the water," or using reckoning properly "you’re dead if you don’t reckon right," is not known. 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.

Errors

While dead reckoning can give the best available information on the present position with little math or analysis, it is subject to significant errors of approximation. For precise positional information, both speed and direction must be accurately known at all times during travel. Most notably, dead reckoning does not account for directional drift during travel through a fluid medium. These errors tend to compound themselves over greater distances, making dead reckoning a difficult method of navigation for longer journeys. For example, if displacement is measured by the number of rotations of a wheel, any discrepancy between the actual and assumed traveled distance per rotation, due perhaps to slippage or surface irregularities, will be a source of error. As each estimate of position is relative to the previous one, errors are cumulative, or compounding, over time. The accuracy of dead reckoning can be increased significantly by using other, more reliable methods to get a new fix part way through the journey. For example, if one was navigating on land in poor visibility, then dead reckoning could be used to get close enough to the known position of a landmark to be able to see it, before walking to the landmark itself — giving a precisely known start point — and then setting off again.

Localization of mobile sensor nodes

Localizing a static

sensor node A sensor node, also known as a mote (chiefly in North America), is a node in a sensor network that is capable of performing some processing, gathering sensory information and communicating with other connected nodes in the network. A mote is a no ...

is not a difficult task because attaching a

GPS The Global Positioning System (GPS), originally Navstar GPS, is a satellite-based radionavigation system owned by the United States government and operated by the United States Space Force. It is one of the global navigation satellite sy ...

device suffices the need of localization. But a mobile sensor node, which continuously changes its geographical location with time is difficult to localize. Mostly mobile sensor nodes within some particular domain for data collection can be used, ''i.e'', sensor node attached to an animal within a grazing field or attached to a soldier on a battlefield. Within these scenarios a GPS device for each sensor node cannot be afforded. Some of the reasons for this include cost, size and battery drainage of constrained sensor nodes. To overcome this problem a limited number of reference nodes (with GPS) within a field is employed. These nodes continuously broadcast their locations and other nodes in proximity receive these locations and calculate their position using some mathematical technique like

trilateration Trilateration is the use of distances (or "ranges") for determining the unknown position coordinates of a point of interest, often around Earth (geopositioning). When more than three distances are involved, it may be called multilateration, for e ...

. For localization, at least three known reference locations are necessary to localize. Several localization algorithms based on Sequential Monte Carlo (SMC) method have been proposed in literature. Sometimes a node at some places receives only two known locations and hence it becomes impossible to localize. To overcome this problem, dead reckoning technique is used. With this technique a sensor node uses its previous calculated location for localization at later time intervals. For example, at time instant 1 if node A calculates its position as ''loca_1'' with the help of three known reference locations; then at time instant 2 it uses ''loca_1'' along with two other reference locations received from other two reference nodes. This not only localizes a node in less time but also localizes in positions where it is difficult to get three reference locations.

Animal navigation

In studies of

animal navigation Animal navigation is the ability of many animals to find their way accurately without maps or instruments. Birds such as the Arctic tern, insects such as the monarch butterfly and fish such as the salmon regularly migrate thousands of miles to ...

, dead reckoning is more commonly (though not exclusively) known as

path integration Path integration is the method thought to be used by animals for dead reckoning. History Charles Darwin first postulated an inertially-based navigation system in animals in 1873. In marine navigation a "dead" reckoning plot generally does not take into account the effect of

current Currents, Current or The Current may refer to: Science and technology * Current (fluid), the flow of a liquid or a gas ** Air current, a flow of air ** Ocean current, a current in the ocean *** Rip current, a kind of water current ** Current (stre ...

s or

wind Wind is the natural movement of air or other gases relative to a planet's surface. Winds occur on a range of scales, from thunderstorm flows lasting tens of minutes, to local breezes generated by heating of land surfaces and lasting a few ho ...

. 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, 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 A chip log, also called common log, ship log, or just log, is a navigation tool mariners use to estimate the speed of a vessel through water. The word ''knot'', to mean nautical mile per hour, derives from this measurement method. History All ...

. More modern methods include

pit log Pitometer logs (also known as pit logs) are devices used to measure a ship's speed relative to the water. They are used on both surface ships and submarines. Data from the pitometer log is usually fed directly into the ship's navigation system. H ...

referencing engine speed (''e.g''. in

rpm Revolutions per minute (abbreviated rpm, RPM, rev/min, r/min, or with the notation min−1) is a unit of rotational speed or rotational frequency for rotating machines. Standards ISO 80000-3:2019 defines a unit of rotation as the dimensionl ...

) against a table of total displacement (for ships) or referencing one's indicated airspeed fed by the pressure from a

pitot tube A pitot ( ) tube (pitot probe) measures fluid flow velocity. It was invented by a French engineer, Henri Pitot, in the early 18th century, and was modified to its modern form in the mid-19th century by a French scientist, Henry Darcy. It ...

. This measurement is converted to an

equivalent airspeed Equivalent airspeed (EAS) is calibrated airspeed (CAS) corrected for the compressibility of air at a non-trivial Mach number. It is also the airspeed at sea level in the International Standard Atmosphere at which the dynamic pressure is the same a ...

based upon known atmospheric conditions and measured errors in the indicated airspeed system. A naval vessel uses a device called a

pit sword Pit or PIT may refer to: Structure * Ball pit, a recreation structure * Casino pit, the part of a casino which holds gaming tables * Trapping pit, pits used for hunting * Pit (motor racing), an area of a racetrack where pit stops are conducted * ...

(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 The term “set and drift” is used to describe external forces that affect a boat and keep it from following an intended course. To understand and calculate set and drift, one needs to first understand currents. Ocean currents are the horizonta ...

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 18th-century development of the

marine chronometer A marine chronometer is a precision timepiece that is carried on a ship and employed in the determination of the ship's position by celestial navigation. It is used to determine longitude by comparing Greenwich Mean Time (GMT), or in the modern ...

John Harrison John Harrison ( – 24 March 1776) was a self-educated English carpenter and clockmaker who invented the marine chronometer, a long-sought-after device for solving the problem of calculating longitude while at sea. Harrison's solution revol ...

and the

lunar distance method Lunar most commonly means "of or relating to the Moon". Lunar may also refer to: Arts and entertainment * ''Lunar'' (series), a series of video games * "Lunar" (song), by David Guetta * "Lunar", a song by Priestess from the 2009 album ''Prior t ...

, dead reckoning was the primary method of determining

longitude Longitude (, ) is a geographic coordinate that specifies the east– west position of a point on the surface of the Earth, or another celestial body. It is an angular measurement, usually expressed in degrees and denoted by the Greek lette ...

available to mariners such as

Christopher Columbus Christopher Columbus * lij, Cristoffa C(or)ombo * es, link=no, Cristóbal Colón * pt, Cristóvão Colombo * ca, Cristòfor (or ) * la, Christophorus Columbus. (; born between 25 August and 31 October 1451, died 20 May 1506) was a ...

and John Cabot on their trans-Atlantic voyages. Tools such as the

traverse board The traverse board is a tool formerly used in dead reckoning navigation to easily record the speeds and directions sailed during a watch. Even crew members who could not read or write could use the traverse board. As the mathematician William Bou ...

were developed to enable even illiterate crew members to collect the data needed for dead reckoning.

Polynesian navigation Polynesian navigation or Polynesian wayfinding was used for thousands of years to enable long voyages across thousands of kilometers of the open Pacific Ocean. Polynesians made contact with nearly every island within the vast Polynesian Triangl ...

, however, uses different

wayfinding Wayfinding (or way-finding) encompasses all of the ways in which people (and animals) orient themselves in physical space and navigate from place to place. Wayfinding software is a self-service computer program that helps users to find a location, ...

techniques.

Air

On 21 May 1927

Charles Lindbergh Charles Augustus Lindbergh (February 4, 1902 – August 26, 1974) was an American aviator, military officer, author, inventor, and activist. On May 20–21, 1927, Lindbergh made the first nonstop flight from New York City to Paris, a distance o ...

landed in

Paris, France Paris () is the Capital city, capital and List of communes in France with over 20,000 inhabitants, most populous city of France, with an estimated population of 2,165,423 residents in 2019 in an area of more than 105 km² (41 sq mi), ma ...

after a successful non-stop flight from the United States in the single-engined

Spirit of St. Louis The ''Spirit of St. Louis'' (formally the Ryan NYP, registration: N-X-211) is the custom-built, single-engine, single-seat, high-wing monoplane that was flown by Charles Lindbergh on May 20–21, 1927, on the first solo nonstop transatlant ...

. As the aircraft was equipped with very basic instruments, Lindbergh used dead reckoning to navigate. Dead reckoning in the air is similar to dead reckoning on the sea, but slightly more complicated. The density of the air the aircraft moves through affects its performance as well as winds, weight, and power settings. The basic formula for DR is Distance = Speed x Time. An aircraft flying at 250 knots airspeed for 2 hours has flown 500 nautical miles through the air. The

wind triangle In air navigation, 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. *The air v ...

is used to calculate the effects of wind on heading and airspeed to obtain a magnetic heading to steer and the speed over the ground (groundspeed). Printed tables, formulae, or an

E6B The E6B flight computer is a form of circular slide rule used in aviation and one of the very few analog calculating devices in widespread use in the 21st century. They are mostly used in flight training, because these flight computers have b ...

flight computer are used to calculate the effects of air density on aircraft rate of climb, rate of fuel burn, and airspeed. A course line is drawn on the aeronautical chart along with estimated positions at fixed intervals (say every ½ hour). Visual observations of ground features are used to obtain fixes. By comparing the fix and the estimated position corrections are made to the aircraft's heading and groundspeed. Dead reckoning is on the curriculum for VFR (visual flight rules – or basic level) pilots worldwide. It is taught regardless of whether the aircraft has navigation aids such as GPS, ADF and

VOR VOR or vor may refer to: Organizations * Vale of Rheidol Railway in Wales * Voice of Russia, a radio broadcaster * Volvo Ocean Race, a yacht race Science, technology and medicine * VHF omnidirectional range, a radio navigation aid used in a ...

and is an ICAO Requirement. Many flying training schools will prevent a student from using electronic aids until they have mastered dead reckoning.

Inertial navigation system An inertial navigation system (INS) is a navigation device that uses motion sensors (accelerometers), rotation sensors ( gyroscopes) and a computer to continuously calculate by dead reckoning the position, the orientation, and the velocity (dir ...

s (INSes), which are nearly universal on more advanced aircraft, use dead reckoning internally. The INS provides reliable navigation capability under virtually any conditions, without the need for external navigation references, although it is still prone to slight errors.

Automotive

Dead reckoning is today implemented in some high-end automotive navigation systems in order to overcome the limitations of

GNSS A satellite navigation or satnav system is a system that uses satellites to provide autonomous geo-spatial positioning. It allows satellite navigation devices to determine their location (longitude, latitude, and altitude/elevation) to high pr ...

technology alone. Satellite microwave signals are unavailable in parking garages and tunnels, and often severely degraded in

urban canyon An urban canyon (also known as a street canyon) is a place where the street is flanked by buildings on both sides creating a canyon-like environment, evolved etymologically from the Canyon of Heroes in Manhattan. Such human-built canyons are made ...

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 know the wheel circumference and record wheel rotations 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 For statistics and control theory, Kalman filtering, also known as linear quadratic estimation (LQE), is an algorithm that uses a series of measurements observed over time, including statistical noise and other inaccuracies, and produces estima ...

to integrate the always-available sensor data with the accurate but occasionally unavailable position information from the satellite data into a combined position fix.

Autonomous navigation in robotics

Dead reckoning is utilized in some robotic applications. It is usually used to reduce the need for sensing technology, such as

ultrasonic sensor Ultrasonic transducers and ultrasonic sensors are devices that generate or sense ultrasound energy. They can be divided into three broad categories: transmitters, receivers and transceivers. Transmitters convert electrical signals into ultrasoun ...

s, GPS, or placement of some

linear Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...

and

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 analog or digital output signals. There are two main types of rotary encoder: absolute and increm ...

s, in an

autonomous robot An autonomous robot is a robot that acts without recourse to human control. The first autonomous robots environment were known as Elmer and Elsie, which were constructed in the late 1940s by W. Grey Walter. They were the first robots in history ...

, thus greatly reducing 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 electrical power or

hydraulic Hydraulics (from Greek: Υδραυλική) is a technology and applied science using engineering, chemistry, and other sciences involving the mechanical properties and use of liquids. At a very basic level, hydraulics is the liquid counte ...

pressure to the robot's drive motors over a given amount of time from a general starting point. Dead reckoning is not totally accurate, which can lead to errors in distance estimates ranging from a few millimeters (in

CNC machining Numerical control (also computer numerical control, and commonly called CNC) is the automated control of machining tools (such as drills, lathes, mills, grinders, routers and 3D printers) by means of a computer. A CNC machine processes a ...

) to kilometers (in

UAVs An unmanned aerial vehicle (UAV), commonly known as a drone, is an aircraft without any human pilot, crew, or passengers on board. UAVs are a component of an unmanned aircraft system (UAS), which includes adding a ground-based controlle ...

), based upon the duration of the run, the speed of the robot, the length of the run, and several other factors.

Pedestrian dead reckoning (PDR)

With the increased sensor offering in

smartphone A smartphone is a portable computer device that combines mobile telephone and computing functions into one unit. They are distinguished from feature phones by their stronger hardware capabilities and extensive mobile operating systems, whic ...

s, built-in accelerometers can be used as a

pedometer A pedometer, or step-counter, is a device, usually portable and electronic or electromechanical, that counts each step a person takes by detecting the motion of the person's hands or hips. Because the distance of each person's step varies, a ...

and built-in magnetometer as a compass heading provider. Pedestrian dead reckoning (PDR) can be used to supplement other navigation methods in a similar way to automotive navigation, or to extend navigation into areas where other navigation systems are unavailable. In a simple implementation, the user holds their phone in front of them and each step causes position to move forward a fixed distance in the direction measured by the compass. Accuracy is limited by the sensor precision, magnetic disturbances inside structures, and unknown variables such as carrying position and stride length. Another challenge is differentiating walking from running, and recognizing movements like bicycling, climbing stairs, or riding an elevator. Before phone-based systems existed, many custom PDR systems existed. While a

can only be used to measure linear distance traveled, PDR systems have an embedded magnetometer for heading measurement. Custom PDR systems can take many forms including special boots, belts, and watches, where the variability of carrying position has been minimized to better utilize magnetometer heading. True dead reckoning is fairly complicated, as it is not only important to minimize basic drift, but also to handle different carrying scenarios and movements, as well as hardware differences across phone models.

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 pre-dated the navigational use of the

magnetic compass A compass is a device that shows the cardinal directions used for navigation and geographic orientation. It commonly consists of a magnetized needle or other element, such as a compass card or compass rose, which can pivot to align itself with ...

, and could not ''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, using local knowledge or astronomical observations e.g. of the

Pole Star A pole star or polar star is a star, preferably bright, nearly aligned with the axis of a rotating astronomical body. Currently, Earth's pole stars are Polaris (Alpha Ursae Minoris), a bright magnitude-2 star aligned approximately with its ...

. Then, as it traveled, a mechanism possibly containing differential gears used the different rotational speeds of the two wheels to turn the pointer relative to the body of the chariot by the angle of turns made (subject to available mechanical accuracy), keeping the pointer aiming in its original direction, to the south. Errors, as always with dead reckoning, would accumulate as distance traveled increased.

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).Murphy, Curtiss.
Believable Dead Reckoning for Networked Games
'. Published in Game Engine Gems 2, Lengyel, Eric. AK Peters, 2011, p 308-326. 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:

P_t = P_0 + V_0T + \fracA_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 (e.g. cubic Bézier splines,

centripetal Catmull–Rom spline In computer graphics, the centripetal Catmull–Rom spline is a variant form of the Catmull–Rom spline, originally formulated by Edwin Catmull and Raphael Rom, which can be evaluated using a recursive algorithm proposed by Barry and Goldman. It is ...

s, 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. *

V_b = V_0 + \left (\acute_0 - V_0 \right)\hat

P_t = P_0 + V_bT_t + \frac\acute_0T_t^2

\acute_t = \acute_0 + \acute_0T_t + \frac\acute_0T_t^2

Pos = P_t + \left (\acute_t - P_t \right)\hat

The first equation calculates a blended velocity

V_b

given the client-side velocity at the time of the last server update

V_0

and the last known server-side velocity

\acute_0

. This essentially blends from the client-side velocity towards the server-side velocity for a smooth transition. Note that

\hat

should go from zero (at the time of the server update) to one (at the time at which the next update should be arriving). A late server update is unproblematic as long as

\hat

remains at one. Next, two positions are calculated: firstly, the blended velocity

V_b

and the last known server-side acceleration

\acute_0

are used to calculate

P_t

. This is a position which is projected from the client-side start position

P_0

based on

T_t

, the time which has passed since the last server update. Secondly, the same equation is used with the last known server-side parameters to calculate the position projected from the last known server-side position

\acute_0

and velocity

\acute_0

, resulting in

\acute_t

. Finally, the new position to display on the client

Pos

is the result of interpolating from the projected position based on client information

P_t

towards the projected position based on the last known server information

\acute_t

. The resulting movement smoothly resolves the discrepancy between client-side and server-side information, even if this server-side information arrives infrequently or inconsistently. It is also free of oscillations which spline-based interpolation may suffer from.

Computer science

In computer science, dead-reckoning refers to navigating an array data structure using indexes. Since every array element has the same size, it is possible to directly access one array element by knowing any position in the array. Given the following array: knowing the memory address where the array starts, it is easy to compute the memory address of D:

\text_\text = \text_\text + ( \text_\text * \text_\text )

Likewise, knowing D's memory address, it is easy to compute the memory address of B:

\text_\text = \text_\text - ( \text_\text * ( \text_\text - \text_\text ) )

This property is particularly important for performance when used in conjunction with arrays of

structures A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...

because data can be directly accessed, without going through a pointer dereference.

References

External links

Bowditch Online: "Dead reckoning""Navigation Satellite System"
{{DEFAULTSORT:Dead Reckoning Navigation Tracking Wireless locating Inertial navigation Geopositioning