The purpose of this lab is to give you an idea of what the Kalman Filter does and under what conditions it works well (HINT: it doesn't work perfectly in every situation). In addition to tracking enemy tanks, the Kalman Filter will help you compensate for sensor noise, which is introduced in this lab (and will be present in the final tournament). You will be required to do the following:

  • Code up a few simple “clay pigeon” to aim at (two will meet the assumptions of the Kalman filter, one will not)
  • Code up the multivariate Kalman Filter update equations
  • Draw the filter's output for your “clay pigeons”

Note that the numbers provided below are just a starting point. I expect you to have to adjust them to get this to work, that will be the hard part.

What to Turn In

To pass off this lab, you will:

  • Submit all of your code electronically to the ta.
  • Turn in a declaration of time spent by each lab partner
  • Demonstrate to your code to the TA, and be able to discuss the item discussed below, that would have been in the write-up. You must show the TA some graphs and explain them.

Your discussion with the TA should include information about what kinds of transition and covariance matrices you used and how it affected performance. Do meaningful experiments that test the abilities of the filter, and try to make meaningful and insightful observations. Discuss why it works better or worse in various circumstances and what you might do in the Tournament based on your observations in this lab.

Description

Conforming Clay Pigeon

The Kalman Filter makes a number of assumptions about the path that the tracked object is following. Your first task is to code several “Clay Pigeon” that conforms to these assumptions. You will make 2 Conforming Clay Pigeons which behave in the following ways:

  1. “Sitting Duck”– Just sit there
  2. Constant x and y velocity (a straight line)

Non-conforming Clay Pigeon (the "Wild Pigeon")

Your second task is to build a Clay Pigeon that violates the Kalman assumptions in some way (your choice). For fun try to make it as hard to hit as you can. Skill in fooling the Kalman Filter will be an asset when you are competing in the final tournament. I hope it also teaches you something about the Kalman Filter!

The Kalman Agent

Your Kalman Agent must also plot the density of the output of the Kalman Filter (see GnuplotHelp). You will need to plot your filtered estimate of the current location of the clay pigeons and the projected locations. Please code up the plot early rather than at the end of the project; it is a great debugging tool and will really help you understand what is happening with the Kalman Filter.

Use the empty world (remove all obstacles). Both teams should be run with –[color]-tanks=1 (1 player on each team). Your agent should be run with noise by using –default-posnoise=5 (Please comment on the discussion page or talk/email me if you have trouble with this much noise, try various values). Your agent may rotate but may not move. You should successfully track and reliably (maybe not perfectly) shoot the Conforming Clay Pigeons. There may also be instances where the random starting position of the enemy puts it out of range of your tank for an extended period of time.

Part of your task is to tune your Kalman agent to do as well as possible on your Wild Pigeon. In your writeup, explaining exactly why you had difficulty and what you tried to do about it. Communicate the creative efforts you used to mislead the Kalman Filter and what you did to try to overcome these problems.

Example Matrices

To accomplish this lab, it is helpful to understand the “physics” used by the enemy agent. We will represent these physics using matrices as done in the class discussions. You will want to play with the values in these matrices, especially $\Sigma_x$ and $\Sigma_z$, and we encourage you to do so in order to better understand how the Kalman Filter works.

Initially, your clay pigeons will be at some unknown position on the playing field, and the velocity and acceleration will both be zero. You can use that information to create your initial estimates of the mean and covariance. The physics are based on the six values in our state vector (in this order, represented as a column vector):

$X_t = \begin{bmatrix} x_t
\dot{x}_t
\ddot{x}_t
y_t
\dot{y}_t
\ddot{y}_t \end{bmatrix}$

where $x$ and $y$ are the $(x, y)$ position of the enemy agent, $\dot{x}$ is the x component of the agent's velocity, $\ddot{x}$ is the x component of the agent's acceleration, and etc. Note that we use $X_t$ to represent the entire observation at time $t$.

Initialization

Given this state vector, the Kalman Filter will produce a mean estimate for this vector $\mu$ and a covariance matrix for this vector $\Sigma$. So, your initial estimates of the mean and covariance could look like these:

$\mu_0 = \begin{bmatrix} 0
0
0
0
0
0 \end{bmatrix}$

which means that you think the agent begins at the origin with no velocity and no acceleration, and

$\Sigma_0 = \begin{bmatrix} 100 & 0 & 0 & 0 & 0 & 0
0 & 0.1 & 0 & 0 & 0 & 0
0 & 0 & 0.1 & 0 & 0 & 0
0 & 0 & 0 & 100 & 0 & 0
0 & 0 & 0 & 0 & 0.1 & 0
0 & 0 & 0 & 0 & 0 & 0.1 \end{bmatrix}$

which means that you are pretty sure that the agent is not accelerating or going anywhere, but that you are pretty unsure exactly where the agent is.

Motion or Transition

Once every time period ($\Delta t$), the enemy agent will update its state $X$ as follows:

$X_t \sim N(FX_t, \Sigma_x)\,$

In other words, the enemy agent applies the system transition matrix $F$ to its previous state and then adds noise, which is drawn from some distribution. Since the initial state and all subsequent states are random variables, these variables are capitalized to be consistent with our notes in class. The $F$ matrix used in this lab is precisely the one that we derived in class using Newton's laws of motion (with one exception):

$F = \begin{bmatrix} 1 & \Delta t & \Delta t^2/2 & 0 & 0 & 0
0 & 1 & \Delta t & 0 & 0 & 0
0 & -c & 1 & 0 & 0 & 0
0 & 0 & 0 & 1 & \Delta t & \Delta t^2/2
0 & 0 & 0 & 0 & 1 & \Delta t
0 & 0 & 0 & 0 & -c & 1 \end{bmatrix}$

where the $c$ indicates that we have a linear friction force working against this agent. If in this lab, you re-compute every half-second then $\Delta t = 0.5$. Try setting the friction coefficient $c$ to $0.1$ to start out with. Sometimes it works better without it ($C=0$).

Noise

Each $X_t$ is a sample drawn from a multivariate normal distribution. In reality, only $x$ and $y$ accelerations have noise (with a standard deviation of $0.5$), but since there are some other influences on the behavior of the agent (such as being pushed away from walls) you will want play with the covariance matrix. A good place to start is with a covariance matrix that allows acceleration to vary from the model more than velocity or position, like the following:

$\Sigma_x = \begin{bmatrix} 0.1 & 0 & 0 & 0 & 0 & 0
0 & 0.1 & 0 & 0 & 0 & 0
0 & 0 & 100 & 0 & 0 & 0
0 & 0 & 0 & 0.1 & 0 & 0
0 & 0 & 0 & 0 & 0.1 & 0
0 & 0 & 0 & 0 & 0 & 100 \end{bmatrix}$

The noisy measurements of the enemy position will have zero-mean Gaussian noise with a standard deviation of 5 units in each dimension. The sensor model is as follows:

$Z_t \sim N(HX_t, \Sigma_z)\,$

In this equation, $X_t$ is a random variable representing the true (unknown) state, and $Z_t$ is a random variable representing the noisy and limited observations provided by the server. Each observation from the server is a sample from $Z_t$ and is encoded as a 2-dimensional vector. These samples are used to perform inference about $X_t$.

NOTE: As I recall, while you get $x$ and $y$ positions and $\dot{x}$ and $\dot{y}$ velocities for your own tank, you only get $x$ and $y$ for other tanks.

The observation matrix, $H$, selects out the two “position” values from the state vector. It looks like this:

$H = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0
0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix}$

Since these measurements are corrupted by noise, it is important to know the covariance matrix of this noise. Since the standard deviation of the $x$ and $y$ position noise is 5 and since these two noises are uncorrelated, the covariance matrix is given by:

$\Sigma_z = \begin{bmatrix} 25 & 0
0 & 25 \end{bmatrix}$

NOTE: I may change this, make it a parameter!

Implementation Hints

  • You are more than welcome to implement your own matrix manipulation code. However, you are encouraged to spend your precious time on more important things. Find a reputable source and download a matrix package. If you are using python, I think all of the needed matrix operators are available in numpy. I think numpy is on the lab machines.
  • Here are the three Kalman update equations (NOTE: The third equation is wrong in the second edition of the book! It was fixed for the third edition):

$K_{t+1} = (F \Sigma_t F^T + \Sigma_x) H^T (H(F \Sigma_t F^T + \Sigma_x) H^T + \Sigma_z)^{-1}$

$\mu_{t+1} = F\mu_t + K_{t+1}(z_{t+1} - HF\mu_t)$

$\Sigma_{t+1} = (I - K_{t+1} H)(F \Sigma_t F^T + \Sigma_x)$

  • Be careful not to get confused with the different $\Sigma$ matrices: $\Sigma_x$, $\Sigma_z$ and the various $\Sigma_t$ matrices (one for each time step t).
  • Note that these four matrices are constants, so can be initialized once: $F$,$\Sigma_x$, $H$, $\Sigma_z$.
  • Note also that since $H$ and $F$ are constant, $H^T$ and $F^T$ are also constant, and can be precomputed just once.
  • Initialize your $\mu_0$ and $\Sigma_0$ matrices at the start of each run.
  • Don't be too scared by all the subscripts in the Kalman equations. Just think of $t$ as “the last time” and $t + 1$ as “this time.”
  • Note also that the expression $(F\Sigma_tF^T + \Sigma_x)$ occurs three times in the equations, so you may save some time by calculating that first.
  • To apply predictions into the future, you don't make additional observations, so you shouldn't use the full equations. Instead, use this equation:

$\mu_{t+1} = F\mu_t$

Acknowledgments

Thanks to Chris Monson, Andrew McNabb, David Wingate and Kirt Lillywhite

cs-470/kalman-lab.txt · Last modified: 2015/01/06 21:54 by ryancha
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0