Introduction to Estimation

Section 1What is Estimation?

Suppose you want to write a program that automatically navigates a quadcopter to a desired target. To determine the quadcopter's position, you might rely on GPS satellite signals, and fuse them with onboard motion sensor data (accelerometers and gyroscopes) when GPS is unavailable or unreliable. This is a canonical example of an estimation (or filtering) problem that arises throughout aerospace and robotics applications.

In more formal terms, the goal is to estimate the state of a dynamical system — such as the quadcopter's position, velocity, and direction of motion — using data collected from multiple sensors. These sensors provide indirect and imperfect information about the true state of the system.

The challenge is that real-world sensor data is noisy, incomplete, and sometimes misleading. For example:

To overcome these challenges, we must design algorithms that combine models of system dynamics with noisy sensory data in a principled way. The goal is to transform unreliable measurements into robust and trustworthy estimates of the quantities we care about — such as position and velocity.

This process is called filtering: extracting useful information from noisy data over time. The algorithms that perform this task are known as estimation or filtering algorithms, and they are a cornerstone of modern autonomous systems.

Section 2Applications of Estimation

2.1Smartphone

Estimation algorithms operate continuously on your smartphone, often without you noticing:

• Detecting when to rotate the screen by estimating phone orientation from IMU data.
• Counting your steps by filtering IMU signals.
• Automatically adjusting screen brightness using noisy ambient light measurements.

Each of these tasks relies on estimating hidden quantities — orientation, motion, or activity — from imperfect sensor data.

2.2Navigation with GPS

• There are around 30 GPS satellites orbiting the Earth.
• A GPS device receives a signal from each satellite containing: (1) the location of the satellite, and (2) the clock time when the signal was emitted.
• The device uses these signals to produce an estimate of its current location via an estimation algorithm.

In the GPS example, the state is the position of the device, and the sensory data are the signals received from GPS satellites.

Challenges:

In practice, one also needs to estimate the clock offset, velocity, and orientation. The GPS signal is commonly fused with an Inertial Measurement Unit (IMU) comprising an accelerometer and gyroscope, which provide higher-frequency data.

2.3Target Tracking

Target tracking refers to estimating the state (position, velocity, acceleration) of a moving object over time using noisy sensor measurements. Common applications include:

• Radar or sonar tracking of aircraft, missiles, or submarines.
• Vision-based tracking in robotics.
• Surveillance and monitoring systems.

A radar sensor typically provides the range (via time-of-flight), the speed (via Doppler effect), and the bearing (horizontal angle) to the target. Sonar is similar but operates at a slower rate and is more susceptible to multipath effects. The main challenges are the unknown target dynamics and the data association problem when tracking multiple targets simultaneously.

2.4Robotics

Robots must infer their own state (position, velocity, orientation) and sometimes build maps of unknown environments — a problem known as SLAM (Simultaneous Localization and Mapping). All of this must be done while dealing with sensor noise and uncertainty in motion and dynamics. Typical sensors include GPS, cameras, LiDAR, and IMUs.

2.5Weather Forecast

The goal is to predict atmospheric states (temperature, pressure, wind, humidity) over time based on partial and noisy observations (satellite radiances, weather station data) and complex nonlinear atmospheric dynamics. In weather forecasting, estimation methods are referred to as data assimilation.

Key challenge: The atmospheric state lives on a grid of approximately $10^8$ points, making simulation and estimation extremely computationally expensive.

Section 3Mathematical Formulation

We now formulate the estimation problem mathematically. The estimation problems considered in this course involve estimating the state of a dynamic system — one that evolves over time. To describe such a problem, we need a dynamic model for the state and an observation model that relates the state to sensor measurements. We develop these for the problem of navigating a platform (ship, aircraft, etc.) using GPS data.

3.1Dynamic Model

Let $(x(t), y(t), z(t))$ denote the position of the platform. Assuming we can control the velocity, the continuous-time dynamic model is:

Defining the state vector $X(t)$, control input $u(t)$, and dynamic function $\bar{f}$:

The compact continuous-time dynamic model is:

For estimation problems, it is more convenient to work with discrete-time models, where the discrete times correspond to the instants when observations are received. Assuming observations arrive every $\delta$ seconds and velocity is constant between steps:

Adding a process noise term $d(k)$ to account for model uncertainty:

The process noise $d(k)$ is treated as a random variable with known statistical properties. Equation (3.2) is called the stochastic discrete-time dynamic model.

3.2Observation Model

Suppose there are $m$ GPS satellites. Let $\tau_i$ be the clock time of satellite $i$ when the signal is emitted, $\tau_0$ the receiver clock time, and $c$ the speed of light. The pseudo-range is:

The true range from satellite $i$ to the device at $(x,y,z)$ is:

The pseudo-range and true range are related by:

where $\Delta$ is the receiver clock offset and $W_i$ is sensor noise. Since $\Delta$ is unknown, we expand the state to include it:

The general compact form of the observation model is:

3.3Target Tracking Example

Suppose we want to track a target in 2D (horizontal range $x$ and altitude $y$) from noisy radar measurements. With discrete-time updates every $\delta$ seconds and constant acceleration during each interval:

Since the acceleration is unknown, we use the constant velocity model and treat acceleration as zero-mean process noise. Defining:

The linear dynamic model is $X(k+1) = FX(k) + Gd(k)$ where:

The radar gives noisy position measurements, yielding the observation model $Y = HX + W$ with:

Section 4Programming Exercise

The goal is to mathematically formulate an estimation problem and implement an estimation algorithm for a collision avoidance system. The objective is to estimate the distance and relative speed between two vehicles from noisy range measurements. The state is:

where $r(t)$ is the distance and $\dot{r}(t)$ is the relative speed.

Estimation Algorithm. Let $\hat{X}(k)$ denote the estimate of $X(k)$. The update law is:

where $\hat{Y}(k+1) = HF\hat{X}(k)$ is the predicted observation and $K = [\alpha,\ \beta/\delta]^\top$ is the filter gain.

Simulation parameters: $\delta = 0.1$, $X(0) = [1,\ 10]^\top$, $\hat{X}(0) = [0,\ 0]^\top$, $d(k) \sim \mathcal{N}(0, \sigma_d^2)$, $W(k) \sim \mathcal{N}(0, 10^{-4})$.

Produce figures showing state, measurement, and estimate trajectories for:

• $(\alpha, \beta) = (0.1,\ 0.2)$
• $(\alpha, \beta) = (0.5,\ 1.0)$
• $(\alpha, \beta) = (1.0,\ 2.0)$

Discuss the differences in estimator performance across the three gain choices.