What is Dead Reckoning – Clear Explanation with Python Simulation – Part I – Fusion of Engineering, Control, Coding, Machine Learning, and Science

In this tutorial series, we explain what is dead reckoning. We focus on the application of dead reckoning in mobile robotics. We concisely explain the main idea of dead reckoning and we explain how to use a simple approach for solving the dead reckoning problem and for implementing the solution. In the second part of this tutorial given here, we explain how to simulate dead reckoning in Python for a simple model of a mobile robot.

The dead reckoning implementation approach presented in this tutorial is far from optimal, and we can say that it is actually a “naive” approach. However, this naive approach is very useful for understanding the advantages and disadvantages of dead reckoning and learning how to simulate dead reckoning in Python. In the third and fourth parts of this tutorial series, we will present a more optimal approach for solving the dead reckoning problem.

There are a number of definitions and problem formulations of dead reckoning. In this tutorial, under the term “dead reckoning”, we understand the following. Briefly speaking, dead reckoning is a method for calculating (estimating) the position and orientation of a mobile robot at the current time instant by using information about

The position and orientation of the mobile robot at the previous time instant.
Measurements of the traveled distance and change of orientation of the mobile robot between the previous and current time instants.

Dead reckoning is probably a centuries-old (if not millennia-old) method used for navigation and location determination by using incremental measurements. It was used for incrementally determining the position of a ship on an open sea. In the first tutorial part presented here, we explain how to use a “naive” approach for dead reckoning in mobile robotics. The idea is to use wheel encoder measurements and gyroscopes to update the location and orientation of the robot. After some time the variance of the estimation error will become very large and this method will not work. This is due to the accumulation and integration of the measurement and approximation errors in every step. That is, the dead reckoning method is useful for short-term localization.
This method should be studied and properly understood before implementing more advanced methods for robotic localization such as nonlinear Kalman filters and particle filters.

The YouTube tutorial accompanying this webpage tutorial is given below.

Kinematic Model of Mobile Robot for Dead Reckoning

Before we mathematically define the process of dead reckoning, we first need to introduce a kinematic model of a mobile robot. This is because the dead reckoning method relies upon simplified kinematics models of mobile robots.

The figure below shows a simple mobile robot with two active wheels and a third passive wheel (castor wheel) that for clarity is not shown in this figure. This is a graphical representation of a differential drive mobile robot explained in our previous tutorial given here. However, the main principle of the dead reckoning method that is explained in this tutorial is applicable to other mobile robotic configurations.

Figure 1: Graphical representation of a differential drive robot.

The robot consists of the robot base and two active wheels. In addition to these two wheels, there is a third passive caster wheel that provides the stability of the robotic platform (passive means that is not actively actuated, however, the wheel can still move around two perpendicular axes). This third wheel is not shown on the graph in order not to make the graph too complex. We introduce the following quantities:

Inertial coordinate system $X$ – $Y$ (denoted by uppercase letters $X$ and $Y$ ). This coordinate system is fixed.
Body coordinate system $X_{B}$ – $Y_{B}$ (denoted by uppercase letters $X_{B}$ and $Y_{B}$ ). The body coordinate system is also called the body frame. This coordinate system is rigidly fixed to the robot body or robot base. Its center is at the point $B$ . Usually the point $B$ is the center of the mass or the center of the symmetry of the robot body or the robot base. The body coordinate system moves together with the robot.
The coordinates $x$ and $y$ are horizontal and vertical positions of the body coordinate system $X_{B}$ – $Y_{B}$ with respect to the inertial coordinate system $X$ – $Y$ .
The angle $\theta$ is the angle that the body coordinate system makes with the $X$ axis of the inertial coordinate system. That is, the angle $\theta$ is the rotation of the body coordinate system with respect to the inertial coordinate system. The angle $\theta$ is called the orientation angle or angular orientation. This angle is also called the bearing angle (or simply bearing) or heading angle (or simply heading). Since the body coordinate system is firmly attached to the robot body the angle $\theta$ is the rotation of the robot body.
$v$ is the instantaneous velocity of the center of the body frame.
$\omega$ is the instantaneous angular velocity of the robot.

Definition of (robot) pose

Next, we need to define what is a robot pose. The (robot) pose is the vector $\mathbf{z}$ defined by

(1) $\begin{align*}\mathbf{z}=\begin{bmatrix}x \\ y \\ \theta \end{bmatrix}\end{align*}$

The (robot) pose completely defines the position (location) and orientation of the robot with respect to the fixed inertial frame $X$ – $Y$ . From a purely geometrical point of view, the pose defines the location and orientation of the body frame $X_{B}$ – $Y_{B}$ with respect to the inertial frame $X$ – $Y$ . The pose is also called the kinematic state. The reason for this will be explained later on.

The precise knowledge of the robot pose is important for a number of reasons. First of all, it determines the precise location and orientation of the robot in space. Secondly, the robot pose is used for feedback control. Finally, robot pose information is used in other robotic algorithms, such as path planning, obstacle avoidance, and SLAM algorithms.

Kinematic Model of Mobile Robot for Dead Reckoning

Here we present arguably the simplest possible kinematics model of the mobile robot that can be used to define and solve the dead reckoning problem. We deliberately base this tutorial on the simple kinematics model in order not to blur the main ideas of dead reckoning with too many mathematical details. Although relatively simple, this model can still be used in practical applications. We use two approaches to develop the kinematics model of the robot. The first approach is based on the discretization of the continuous-time model of the differential drive robot. This model is derived in our previous tutorial given here. The second approach is based on a simple kinematics derivation and physical intuition. Both modeling approaches result in identical models. However, the second approach is more intuitive since it is directly based on kinematics and direct physical reasoning.

Let us start with the discretization approach. In our previous tutorial, we derived the following continuous-time kinematics model of robot motion

(2) $\begin{align*}\dot{x}&=v\cos(\theta) \\\dot{y}&=v\sin(\theta) \\\dot{\theta}&=\omega\end{align*}$

By using the forward Euler method, we discretize the model (2), as follows

(3) $\begin{align*}\dot{x} & \approx \frac{x_{k+1}-x_{k}}{h} \\\dot{y} & \approx \frac{y_{k+1}-y_{k}}{h} \\\dot{\theta} & \approx \frac{\theta_{k+1}-\theta_{k}}{h} \end{align*}$

where $h$ is the discretization step, $k$ is the discrete-time instant, and $x_{k}$ and $y_{k}$ are the horizontal and vertical coordinates of the center of the robot body frame at the discrete-time instant $k$ , that is, $x_{k}=x(kh)$ and $y_{k}=y(kh)$ . Similarly, $\theta_{k}$ is the orientation of the robot body frame at the discrete-time instant $k$ , that is, $\theta_{k}=\theta(kh)$ . Next, by using the forward Euler method and by substituting equations (3) in (2), and by replacing the approximation symbols with equality symbols, we obtain

(4) $\begin{align*} \frac{x_{k+1}-x_{k}}{h} & = v_{k}\cos(\theta_{k}) \\ \frac{y_{k+1}-y_{k}}{h} & =v_{k}\sin(\theta_{k}) \\ \frac{\theta_{k+1}-\theta_{k}}{h} & = \omega_{k}\end{align*}$

where $v_{k}$ is the instantaneous velocity at the discrete-time instant $k$ , and $\omega_{k}$ is the instantaneous angular velocity at the discrete-time instant $k$ . Here, it is implicitly assumed that the instantaneous velocity $v_{k}$ and angular velocity $\omega_{k}$ are constant between the discrete-time instants $k$ and $k+1$ .

From (4), we obtain the discretized kinematics model of the robot

(5) $\begin{align*}x_{k+1}& =x_{k}+v_{k}h\cos(\theta_{k}) \\y_{k+1}& =y_{k}+v_{k}h\sin(\theta_{k}) \\\theta_{k+1}& =\theta_{k}+\omega_{k}h \end{align*}$

Next, we need to observe the following

The product $v_{k}h$ is the distance traveled in the direction of the velocity vector $v_{k}$ (the velocity vector is actually determined by the intensity given by $v_{k}$ and direction determined by the angle $\theta_{k}$ ). It should be kept in mind that the velocity vector is constant between the time instants $k$ and $k+1$ . The distance traveled between the time instants $k$ and $k+1$ is denoted by
(6) $\begin{align*}s_{k}=v_{k}h\end{align*}$
Since $\omega_{k}$ is the angular velocity, the product $\omega_{k}h$ is the rotation angle of the robot body between the discrete-time instant $k$ and $k+1$ . We denote this angle by
(7) $\begin{align*}\Delta \theta_{k}=\omega_{k}h \end{align*}$

Finally, by using (6) and (7), the final discretized model of the robot kinematics takes the following form

(8) $\begin{align*}x_{k+1}& =x_{k}+s_{k}\cos(\theta_{k}) \\y_{k+1}& =y_{k}+s_{k}\sin(\theta_{k}) \\\theta_{k+1}& =\theta_{k}+\Delta \theta_{k}\end{align*}$

If we ignore the last equation in (8), the resulting two equations

(9) $\begin{align*}x_{k+1}& =x_{k}+s_{k}\cos(\theta_{k}) \\y_{k+1}& =y_{k}+s_{k}\sin(\theta_{k}) \end{align*}$

describe the translation of the robot body along the direction of the instantaneous velocity vector, where the orientation angle $\theta_{k}$ remains constant. On the other hand, if we ignore the first two equations in (8), and if we only consider the last equation

(10) $\begin{align*}\theta_{k+1}& =\theta_{k}+\Delta \theta_{k}\end{align*}$

then, this equation describes the rotation for the angle of $\Delta \theta_{k}$ . That is, the motion is decomposed (decoupled) into translation and rotation. This is a very well-known fact in kinematics and dynamics of motion of rigid bodies in a plane. Namely, the complex motion of a body in a plane from one pose to another can be decomposed into translation and rotation.

Let us not use this principle to rederive the kinematics model (8) by using a more intuitive approach that does not explicitly rely upon the model discretization.

We formally decompose the motion of the robot from the starting point (at the discrete-time $k$ ) to the endpoint (at the discrete-time instant $k+1$ ) as follows

From the starting point $A$ (location at the discrete-time instant $k$ ) to the endpoint $B$ (location at the discrete-time instant $k+1$ ), the robot moves along a straight line. That is, during the motion from the point $A$ to the point $B$ , the orientation angle $\theta_{k}$ is constant, and the position coordinates $x$ and $y$ are changing.
At the point $B$ , the orientation angle $\theta_{k}$ is changed, such that the orientation becomes $\theta_{k+1}$ .

This is just a formal mathematical decomposition of the motion, since in practice, the actual motion between the two points might not look like this. This is an approximation of the motion that enables us to mathematically analyze the geometry and kinematics of motion. However, if the time interval $h$ between the time instants $k$ and $k+1$ is relatively small this formal decomposition relatively accurately approximates the true motion. Also, it is important to keep in mind that at the time instants $k$ and $k+1$ the locations and orientations correspond to the real locations and orientations of the robot. What happens in between the time instants $k$ and $k+1$ cannot be exactly modeled unless a more complex mathematical model is used.

To repeat, from the mathematical point of view, the motion is decomposed into a series of straight-line motions and orientation changes. Let us illustrate this with the example shown in the figure below.

Figure 2: Illustration of the main assumptions on the robotic motion.

The goal is to move from the point $A$ to the point $C$ . The first step, while we are still in the point $A$ , is to adjust the orientation $\theta_{1}$ , such that the robot can move along the straight line from the point $A$ to the point $B$ . This is shown in the figure below.

Figure 3: Step 1- orientation is adjusted.

In step 2, we move from the point A to the point $B$ along the straight line for the distance $s_{1}$ . This is shown in the figure below.

Figure 4: Step 2- move along the straight line from A to B.

In step 3, we adjust the orientation of the robot for the angle $\theta_{2}$ such that we can move along the straight line from the point $B$ to the point $C$ .

Figure 5: Step 3- adjust the orientation in the point $B$ .

In step 4, we move along the straight line from the point $B$ to the point $C$ for the distance $s_{2}$ .

Figure 6: Step 4- move along the straight line from B to C.

Next, we develop the kinematics model of the robot that mathematically describes this motion. Consider the figure shown below.

Figure 7: Diagram for developing the kinematics model. This diagram shows the translation.

Here, we remind the reader that $x_{k}$ and $y_{k}$ denote the $X$ and $Y$ coordinates of the center of the robot body at the discrete time instant $k$ . That is,

(11) $\begin{align*}x_{k}=x(t=kh),\;\; y_{k}=y(t=kh)\end{align*}$

where $h$ is the discretization step. That is, we look at the location of the robot $(x(t),y(t))$ at the discrete-time instants $t=0,h,2h,3h,\ldots, kh,\ldots$ . Similarly, we have previously defined $\theta_{k}$ as follows

(12) $\begin{align*}\theta_{k}=\theta(t=kh)\end{align*}$

From the discrete-time instant $k$ to the discrete-time instant $k+1$ , the robot travels from the start to the end position shown in the figure above. During that time interval, the robot had traveled the distance of $s_{k}$ . This is precisely the distance introduced in (6). Under the assumption that the orientation $\theta_{k}$ remains constant, from the geometry shown in Figure 7 above, we have

(13) $\begin{align*}x_{k+1}=x_{k}+s_{k}\cos(\theta_{k}) \\y_{k+1}=y_{k}+s_{k}\sin(\theta_{k})\end{align*}$

These equations describe the location of the robot at the time instant $k+1$ , under the assumption that the robot was at the location $(x_{k},y_{k})$ at the discrete time instant $k$ and that it had traveled the distance of $s_{k}$ between the discrete-time instants $k$ and $k+1$ . In addition to these equations, we need to add an equation describing the change of the orientation angle $\theta$ . For that purpose, consider the figure below.

Figure 8: Diagram for developing the kinematics model. This diagram shows the rotation.

In the endpoint, we perform the rotation for the angle $\Delta \theta_{k}$ that is first introduced in equation (7). That is, the final orientation at the discrete-time instant $k+1$ is

(14) $\begin{align*}\theta_{k+1}=\theta_{k}+\Delta \theta_{k}\end{align*}$

By combining (13) and (14), we obtain the final kinematics model of the mobile robot

(15) $\begin{align*}x_{k+1}& =x_{k}+s_{k}\cos(\theta_{k}) \\y_{k+1}& =y_{k}+s_{k}\sin(\theta_{k}) \\\theta_{k+1}& =\theta_{k}+\Delta \theta_{k}\end{align*}$

That is precisely the kinematics model (8) obtained by using discretization.

Dead Reckoning Using Kinematics Model and Python Simulations

Here, we first define the dead reckoning problem, and then, we explain how to use the derived kinematics model (15) (or (8)) to solve the dead reckoning problem. In the second part of this tutorial series (link will be posted later on), we explain how to implement the dead reckoning method in Python and through simulations, we explain several issues with dead reckoning.

First, let us define the pose vector. The pose vector, denoted by $\mathbf{z}_{k}$ , is defined by

(16) $\begin{align*}\mathbf{z}_{k}=\begin{bmatrix} x_{k} \\ y_{k} \\ \theta_{k} \end{bmatrix}\end{align*}$

Next, let us define an estimate of the pose vector. The estimate of the pose vector, denoted by $\hat{\mathbf{z}}_{k}$ , is defined by

(17) $\begin{align*}\hat{\mathbf{z}}_{k}=\begin{bmatrix} \hat{x}_{k} \\ \hat{y}_{k} \\ \hat{\theta}_{k} \end{bmatrix}\end{align*}$

where $\hat{x}_{k}$ , $\hat{y}_{k}$ , and $\hat{\theta}_{k}$ are estimates of $x_{k}$ , $y_{k}$ , and $\theta_{k}$ that are computed by using the dead reckoning method.

The dead reckoning problem can be formally described as follows.

Dead reckoning problem. Let us assume that

The estimate of the robot pose vector $\hat{\mathbf{z}}_{k}$ at the discrete-time instant $k$ is known.
The measurements of the traveled distance $s_{k}$ and orientation change $\Delta \theta_{k}$ are obtained at the discrete-time instant $k+1$ .
The initial values $x_{0}$ , $y_{0}$ , and $\theta_{0}$ are known accurately. That is, the initial pose vector $\mathbf{z}_{0}$ is known accurately.

Then, under these assumptions, obtain an estimate of the robot pose vector $\hat{\mathbf{z}}_{k+1}$ at the time instant $k+1$ . Perform the estimation tasks recursively for $k=0,1,2,3,\ldots$ .

To solve this problem and to implement its solution in Python, we need to clarify several important aspects of this problem.

First of all, we need to explain what is odometry. Often, in robotics literature or during the conversation between robotics engineers you will hear the term “odometry”. People use this term in different contexts and have different understandings of this term. Under the term “odometry” we understand the process of using the data from sensors to estimate/measure the traveled distance and heading direction (orientation of the robot). Some people restrict the term odometry only to the sensing (measurement) process, and some people under the term odometry understand the complete process of sensing and estimating the distance and heading direction. In this tutorial, under the term odometry we understand both the sensing and estimation process. In that sense, dead reckoning is a type of odometry.

Now, the main question is how to measure the distance traveled $s_{k}$ and the change of angle $\Delta \theta_{k}$ ? We can measure $s_{k}$ indirectly by using wheel encoders. By knowing the encoder resolution, wheel geometry, and number of detected encoder pulses, we can obtain the measurement of $s_{k}$ . Also, we can measure $s_{k}$ by using some other method (more about this in our future tutorials). On the other hand, we can measure $\Delta \theta_{k}$ by using a gyroscope, compass, or even using two wheel encoders and combining their measurements (more about this in our future tutorials).

One of the most important issues that limit the accuracy of odometry and dead reckoning is that measurements of $s_{k}$ and $\Delta \theta_{k}$ contain errors. For example, the wheels of the robot can slip. However, the encoder will detect the wheel rotation angle, and the traveled distance computed on the basis of the detected wheel angle will NOT correspond to the actual traveled distance. Also, some random effects can occur that can limit the accuracy of sensors.

This means that in the model (8), we are not directly measuring $s_{k}$ and $\Delta \theta_{k}$ . Instead, we are measuring their corrupted versions $\tilde{s}_{k}$ and $\Delta\tilde{\theta}_{k}$ defined as follows

(18) $\begin{align*}\tilde{s}_{k}=s_{k}+e_{k}\\\Delta \tilde{\theta}_{k}=\Delta \theta_{k}+q_{k}\end{align*}$

where $e_{k}$ and $q_{k}$ are measurement errors. We assume that both $e_{k}$ and $v_{k}$ are normally distributed with zero mean and known variances. That is, we assume

(19) $\begin{align*}e_{k}\sim \mathcal{N}(0,\sigma_{e}^{2}),\;\;q_{k}\sim \mathcal{N}(0,\sigma_{q}^{2})\end{align*}$

where $\sigma_{e}^{2}$ and $\sigma_{q}^{2}$ are the variances of $e_{k}$ and $q_{k}$ , respectively.

Here, it is very important to keep in mind that the true values of $s_{k}$ and $\Delta \theta_{k}$ are not known! The only quantities that we know and that we can use for solving the dead reckoning problem are their measurements $\tilde{s}_{k}$ and $\Delta \tilde{\theta}_{k}$ . These measurements are corrupted by the measurement noise, represented by $e_{k}$ and $q_{k}$ .

In the sequel, we present the simplest possible approach for solving the dead reckoning problem. This approach is suboptimal and in some sense “naive”. However, this approach is still very useful since it can give us the first idea of the behavior of the dead reckoning. The idea for solving this problem is to use the kinematic model (8) and to substitute the true values of the distance $s_{k}$ and angle change $\Delta \theta_{k}$ by their measurements $\tilde{s}_{k}$ and $\Delta\tilde{\theta}_{k}$ . Also, the exact values are substituted by estimates in order to obtain a recursive relation for computing the estimates. The (naive) dead reckoning estimator has the following form:

(20) $\begin{align*}\hat{x}_{k+1}& =\hat{x}_{k}+\tilde{s}_{k}\cos(\hat{\theta}_{k}) \\\hat{y}_{k+1}& =\hat{y}_{k}+\tilde{s}_{k}\sin(\hat{\theta}_{k}) \\\hat{\theta}_{k+1}& =\hat{\theta}_{k}+\Delta \tilde{\theta}_{k} \end{align*}$

We initialize the equations (20) with the exact initial value of the location and orientation, that is

(21) $\begin{align*}\hat{x}_{0}& =x_{0} \\\hat{y}_{0}& =y_{0} \\\hat{\theta}_{0}& =\theta_{0} \end{align*}$

After that, by using the measurements $(\tilde{s}_{0},\Delta \tilde{\theta}_{0})$ , $(\tilde{s}_{1},\Delta \tilde{\theta}_{1})$ , $(\tilde{s}_{2},\Delta \tilde{\theta}_{2})$ , $(\tilde{s}_{3},\Delta \tilde{\theta}_{3})$ , $\ldots$ , we propagate the equation (20), to compute the estimates $(\hat{x}_{1},\hat{y}_{1},\hat{\theta}_{1}), (\hat{x}_{2},\hat{y}_{2},\hat{\theta}_{2}), (\hat{x}_{3},\hat{y}_{3},\hat{\theta}_{3}),\ldots$ .