4_2_Target_Tracking.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6f991635-92a3-4b97-81e8-14548f344d33",
   "metadata": {},
   "source": [
    "# Lab 4.2: Target Tracking"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c48d54ac-c642-48f1-9f94-677eb425fe69",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "%matplotlib widget\n",
    "import rad.css as css\n",
    "import rad.example as ex\n",
    "import rad.quiz as qz\n",
    "from rad.const import c, k\n",
    "from rad.radar import to_db, from_db, deg2rad, rad2deg\n",
    "from math import sqrt, sin, asin, cos, acos, tan, atan2, pi, log, log10\n",
    "css.add_custom_css()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "caae829c-c1c0-44a5-91ed-5caeabb3a169",
   "metadata": {},
   "source": [
    "**Reminders**: \n",
    "\n",
    "- Hit the *<font color=\"DarkBlue\">Run All</font>* button <img width=\"18px\" src=\"img/run_all_icon.png\"> button above before continuing\n",
    "- Useful formulae and definitions are available in [Reference](Reference.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28d31b20-dd2d-43e5-b664-f1bc6865db04",
   "metadata": {},
   "source": [
    "In the previous labs, we have looked at how radar systems generate and transmit pulses, receive incoming signals, detect target echoes, and extract target attribute information from a detection. In this lab, we will begin looking at what to do now that we are getting a steady stream of detections from the sensor; more specifically, we will discuss the process subsequent to detection: *tracking*."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43c8b1e5-a26c-4263-86dd-70fbc07f5f2d",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center\"> <img src=\"img/radar_sys4.png\" justify=\"center\" width=\"700px\"></img> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7053ebd4-f6ec-402a-8bac-2c8d3b6d5cfc",
   "metadata": {
    "tags": []
   },
   "source": [
    "Every time a radar transmits and receives (which can be up to thousands of times per second), it will generate detections. These detections will ideally be created from target echoes, but some portion will be false alarms. In the interactive plot below, we can see the raw detections created by a rotating dish radar system (similar to air traffic control radars). In the scene, there is one moving target. As you proceed through the scans, you can watch the target move across the radar display."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a3c5c60f-0da8-40a2-aa5c-0d056ee9c165",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "ex.ex_4_2_1()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d1ccacb-5340-4f7a-b79c-7940bc423818",
   "metadata": {},
   "source": [
    "An important observation from the example above is that detections from the target follow a continuous path across the radar field of view, whereas false alarms are randomly distributed throughout. This is one of the key ideas that is used to build a **multitarget tracker**, which collects sets of detections over time that are designated to be true targets—these are called *tracks*. Let us now look more formally at a track and how one is formed."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e27ae769-8069-445b-8851-4d65d20bea79",
   "metadata": {},
   "source": [
    "## Tracks"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a31523e-b82b-437f-9fb9-b32125566a4a",
   "metadata": {},
   "source": [
    "As mentioned above, a **track** is a history of detections thought to belong to a true target. For each new set of received detections, the radar has to decide how to assign the new detections with existing tracks; this process is known as **data association**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0a074d7-d1e7-41e4-ba3c-2e143a8352c8",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center\"> <img src=\"img/data_assoc.png\" justify=\"center\" width=\"400px\"></img> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "131d264f-263a-417b-93f4-cce378ff3054",
   "metadata": {},
   "source": [
    "A tracker will not only string together detections, it will also estimate the motion of the target (e.g., position, velocity); this is known as **state estimation**. A target **state** describes its motion at a specific point in time: it usually consists of at least position and velocity but may also include other motion variables like acceleration. An estimate of the target state with an accompanying quantification of uncertainty is known as a **state estimate**. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c09b632-a2fc-4438-8e62-540e0c88c71e",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center\"> <img src=\"img/state_est.png\" justify=\"center\" width=\"400px\"></img> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c2cbf23-ff52-4265-be7f-178b4103ab2c",
   "metadata": {},
   "source": [
    "Knowledge of a target's motion is critical for the radar to be able to decide what regions of space to interrogate next. Typically, it would like to get another observation of the target, and it needs to know where it will be next."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01dd7086-d8b5-4aa9-bbff-80e76074d26a",
   "metadata": {},
   "source": [
    "Thus, the three main objectives of a multitarget tracker are:\n",
    "\n",
    "1. Designate sets of detections as targets while rejecting false alarms\n",
    "2. Estimate target motion\n",
    "3. Inform radar control for further observations\n",
    "\n",
    "In this lab, we will take a closer look at the first two: data association and state estimation."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8029afc5-74fa-42fa-862e-262f4503e574",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Multitarget Tracker Structure"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9b20c14-8afa-4b35-86f5-59c7d84d495b",
   "metadata": {},
   "source": [
    "Multitarget trackers (MTT) tend to run cyclically, updating the current tracks every time new detections are gathered. The main loop for a MTT can be seen  in the following figure:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c32c6b08-3eab-4ff6-809d-1e35c9df1613",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center\"> <img src=\"img/mtt.png\" justify=\"center\" width=\"750px\"></img> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce2c7516-3c3f-4815-84d3-4c4ad5e3d9cd",
   "metadata": {},
   "source": [
    "Let us assume that the last tracker cycle took place at time $t_0$, and we are now getting a new set of detections at time $t$. As the new detections arrive, the first step taken is called **track prediction** (also called *propagation*), which predicts where the tracked targets would be at time $t$. This is done by passing the previous state estimates (last updated at $t_0$) through a model of target motion (often called a *dynamic model*)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e60e38d1-62fc-445c-8e6a-14da132f9b0c",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center\"> <img src=\"img/predict.png\" justify=\"center\" width=\"450px\"></img> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bacb63f-a88d-44a4-a479-b9669b65f8f7",
   "metadata": {},
   "source": [
    "In the following interactive example, we look at track prediction using different dynamic models. In the example, we can select the *<font color=\"DarkBlue\">Initial Range</font>* and *<font color=\"DarkBlue\">Initial Altitude</font>* of a target (shown as a **<font color=\"red\">red</font>** dot), along with their corresponding rates. Further, we can choose a dynamic model to use for prediction: *<font color=\"DarkBlue\">Gravity</font>* or *<font color=\"DarkBlue\">No Gravity</font>*. Try changing initial states and using different dynamic models (to change dynamic model, you will need to reset the animation using the *<font color=\"DarkBlue\">Stop</font>* button)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d9d02b69-1ded-4efa-aee0-88ef32644d86",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "ex.ex_4_2_2()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71089980-bd86-49bc-af86-c5db448d4b56",
   "metadata": {
    "tags": []
   },
   "source": [
    "The next step is to match the new detections with the current set of tracks, so the tracks can be updated. As mentioned above, this step (i.e., mapping detections to tracks) is called **data association**. For scenes with lots of targets and/or false alarms, this step can be difficult. More specifically, it can lead to situations like the figure below, which shows the confusion incurred by densely packed detections near the path of a track."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57f88fa9-f87b-4195-b5b9-1b520381920e",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center\"> <img src=\"img/data_assoc_prob.png\" justify=\"center\" width=\"550px\"></img> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e19dc6a-5849-4571-a03b-630230df9b69",
   "metadata": {},
   "source": [
    "Now that we know which detection goes with which track, we update the state estimates for each track using a **state estimation** algorithm. In short, this fuses the detection information (with its uncertainty information) with the current track state estimates."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ec3fa09-682d-4d75-a297-7b19983ef9dc",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center\"> <img src=\"img/state_est_prob.png\" justify=\"center\" width=\"850px\"></img> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81c6a075-ac1f-4ad0-99af-676443a633e6",
   "metadata": {},
   "source": [
    "Finally, we go through **track initiation and maintenance**, which decides when to start new tracks and when to end stale tracks. This part of the multitarget tracker loop is very expert-driven, and its logic will vary depending on application."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b017cd39-c6b7-490c-ad8d-a41b53860c4b",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center\"> <img src=\"img/track_init.png\" justify=\"center\" width=\"950px\"></img> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9f989d9-8d93-4b2e-a7ea-01f08b1106df",
   "metadata": {},
   "source": [
    "In the following, we will study data association and state estimation in more detail."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c149712-ce2f-4942-ace2-5a5fb12b2bff",
   "metadata": {},
   "source": [
    "## Data Association"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e37263d-4d16-4be7-a748-7b0e94bd5bf2",
   "metadata": {},
   "source": [
    "The main objective of data association is to match new detections with existing tracks; the underlying principle is *<font color=\"BlueViolet\">the closer a detection is to a predicted target state, the more likely it came from that target</font>*. In the figure below, we can see that there are two new detections along with the predicted track state. The detection close to the predicted position is *highly likely to have originated from the target*; the other detection has a low likelihood of being a target detection."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "553fe141-8cae-4aa7-95c5-f0181874d2fc",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center\"> <img src=\"img/assoc_like.png\" justify=\"center\" width=\"700px\"></img> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42ec8687-5802-4317-b454-4248e005707f",
   "metadata": {},
   "source": [
    "Things are often not as simple as the figure above: commonly there will be multiple likely detections near a predicted track state or there could be *no* nearby detections. To help solve these issues, there are many data association algorithms developed in the literature. Here are a few:\n",
    "\n",
    "- **Nearest neighbor**: Greedily associate the nearest detection to each track\n",
    "    - *Pro*: Extremely simple and fast\n",
    "    - *Con*: Poor performance in moderately complex scenes\n",
    "- **Global nearest neighbor**: Find the best way to associate all new detections to tracks to minimize a total distance metric\n",
    "    - *Pro*: Simple, fast\n",
    "    - *Con*: Performance degradation in highly complex scenes\n",
    "- **Multihypothesis tracking**: Perform data association over short history of detections, finding sets of detections to associate to a track\n",
    "    - *Pro*: Can be resilient in highly complex scenes\n",
    "    - *Con*: Complex, requires appreciable tuning\n",
    "\n",
    "In the interactive example below, you can see how nearest neighbor and global nearest neighbor associations compare for different scenes. We can vary the number of *<font color=\"DarkBlue\">Tracks</font>* and *<font color=\"DarkBlue\">Detections</font>* to be used for consideration. Additionally, we can change the *<font color=\"DarkBlue\">Track Accuracy</font>* and *<font color=\"DarkBlue\">Detection Accuracy</font>*; these are illustrated using uncertainty ellipses around the tracks and detections. An uncertainty ellipse shows the area in which the target is confidently known to exist. Finally, we can see how the tracks and detections are associated using the *<font color=\"DarkBlue\">Nearest Neighbor</font>* and *<font color=\"DarkBlue\">Global Nearest Neighbor</font>* algorithms. Associations are shown as **black** lines between associated tracks and detections. To change parameters and obtain a new scene, click the *<font color=\"DarkBlue\">New</font>* button."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e80cc21-49c2-4ddc-8dc5-398247aa84a8",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "ex.ex_4_2_3()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb85eee2-e085-4b73-8595-664c625616cd",
   "metadata": {},
   "source": [
    "For an equal number of tracks and detections with good accuracies, the problem can usually be solved quickly by eye; we can notice, however, that as the number of detection versus tracks grow and/or the accuracies degrade, the association problem is not trivial. This is another reason why initial suppression of false alarms is very helpful for a multitarget tracker."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b4ab014-7951-4578-8411-c643dd2f4586",
   "metadata": {},
   "source": [
    "Now, let us assume that we have associated new detections with our current tracks. Next, we should update our state estimates."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35781989-15fd-488c-804e-e829fcd174c3",
   "metadata": {},
   "source": [
    "## State Estimation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1069f4bb-669f-4eaf-8c85-a5ebc6b91bdb",
   "metadata": {},
   "source": [
    "The goal of state estimation is to create an estimate of a target state using a set of detections, where each detection is seen as a measurement of target position (i.e., range, angle) with known accuracies (discussed in [Lab 4.1: Target Parameter Estimation](4_1_Target_Parameter_Estimation.ipynb)). The general flow of a state estimator is given in the following figure:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60cd8815-de13-4cd5-9baf-eea07024c737",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center\"> <img src=\"img/state_est_flow.png\" justify=\"center\" width=\"950px\"></img> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "757be6fe-c1f7-4740-9e3e-cae42d03f0ec",
   "metadata": {},
   "source": [
    "The state estimation process iteratively updates using a weighted sum of its current estimate with the incoming detection. The weights are chosen based on the type of expected target motion and the specific state estimation algorithm being used. The following are some common state estimation algorithms:\n",
    "\n",
    "- **Alpha-beta filters**: Weights are chosen once and fixed for all operation\n",
    "    - *Pro*: Extremely simple and fast\n",
    "    - *Con*: Poor performance except for very simple target motion\n",
    "- **Kalman and extended Kalman filters**: Weights are chosen at each update based on relative uncertainty of current estimate versus detection\n",
    "    - *Pro*: Simple and fast, works well with many target motions\n",
    "    - *Con*: Exhibits difficulty with highly complex target motion"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad08e5cd-d956-4a1a-b8a0-0dc0da2819f9",
   "metadata": {},
   "source": [
    "The main workhorse for many state estimation processes is the ubiquitous Kalman filter<sup>[[1]](#ref_barshalom)</sup> due to its ease of implementation and flexibility to adapt to many different problems. The extended Kalman filter<sup>[[1]](#ref_barshalom)</sup> (EKF) is a variant of the Kalman filter that allows for target motion models and measurement models that cannot be described as linear functions. We will not delve into the details of state estimation in this course, but it suffices to say that an EKF is generally required for most radar tracking algorithms."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3f2bb7f-43a8-465a-ac54-f988bde730a1",
   "metadata": {},
   "source": [
    "In the interactive example below, we can see the output of an EKF over time as it is being fed new detections. More specifically, we are tracking a low-flying target starting due East (estimates will be in the East and North dimensions) and taking radar measurements of the target once every second. The plotted output shows the error of the state estimate as a function of time (in solid **<font color=\"red\">red</font>**) and the uncertainty bounds on the estimate (in dashed **<font color=\"red\">red</font>**). Try changing the radar parameters to see how the detection accuracies change and, subsequently, the state estimates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "de187518-fd83-4683-a940-e5035177fd95",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "ex.ex_4_2_4()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df531b0d-5d2e-489e-ad29-f90dc020a1ac",
   "metadata": {},
   "source": [
    "We can see a few interesting trends:\n",
    "\n",
    "- The state estimate accuracy improves over time; this is called the **convergence** of a state estimator. This makes intuitive sense as we are getting more information as we observe the target for more time.\n",
    "\n",
    "- There are many different knobs that affect track accuracy, e.g., dish radius affects: (i) beamwidth, which affects angle measurement accuracy, and (ii) SNR, which affects all parameter estimate accuracies. The more accurate we can make the estimates of range, angle, range rate, etc., the tighter the uncertainty bounds around a track.\n",
    "\n",
    "- The error in the East dimension is smaller than the error in the North dimension. This is because the target starts due East and, thus, East aligns with our range dimension. Since North is perpendicular to East, it align with our cross-range dimension. Most radar systems (this example included) have much greater accuracy in the range dimension than in the cross-range dimension."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "349d948a-01e2-44d3-8c0d-8aab57605521",
   "metadata": {},
   "source": [
    "## Tracking"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d63052d-19de-4952-bbc8-7634e969b529",
   "metadata": {},
   "source": [
    "To finish this lab, we will return to Robby to get a feel for the amount of work a multitarget tracker saves a radar operator. In the following interactive example, we will see the output of Robby as multiple targets enter and leave. Press the *<font color=\"DarkBlue\">Scan</font>* button periodically and imagine trying to track the targets by hand; keep in mind what radar parameters would work well. In [Lab 5.1: Radar Design Revisited](5_1_Radar_Design_Revisited.ipynb), we will do hand tracking with a personally designed radar. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4fba561f-eff8-4f8b-810a-266ccdfb2d78",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "ex.ex_4_2_5()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45ad4f78-1afd-4863-885d-994014bfbc28",
   "metadata": {},
   "source": [
    " ## Summary"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e780dbdd-cbc8-4e6f-a6f4-2134eee08fc1",
   "metadata": {},
   "source": [
    "In this lab, we studied the subsequent process to detection: multitarget tracking. In this step of the radar processing chain, detections are strung together into object tracks and their states (i.e., summaries of their motion) are estimated. The multitarget tracker is an important part of the radar system as it eliminates false alarms and gives important target position information to the radar control system to allow for further observations of a target. A multitarget tracker typically relies on algorithms for data association (i.e., mapping of new detections to existing tracks) and state estimation (i.e., calculation of estimate of target state from collection of detections). "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3824ac6-2d07-4ba3-ae50-fad72b9d2284",
   "metadata": {},
   "source": [
    "## Footnotes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de9ae407-9cc2-4b0b-afc2-8fee6d034132",
   "metadata": {},
   "source": [
    "n/a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a8e2e51-f024-4943-9417-0d5662397a79",
   "metadata": {},
   "source": [
    "## References"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f373949-9b9d-49cf-b50c-3f08a96c5762",
   "metadata": {},
   "source": [
    "<a id=\"ref_barshalom\">[1]</a> Y. Bar-Shalom, X. Li, and T. Kirubarajan, *Estimation with Applications to Tracking and Navigation*.\n",
    "John Wiley & Sons, Inc., 2001."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}