##### Differences

This shows you the differences between two versions of the page.

 — cs-470:kalman-lab [2015/01/06 14:54] (current)ryancha created 2015/01/06 14:54 ryancha created 2015/01/06 14:54 ryancha created Line 1: Line 1: + 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: + # "​Sitting Duck"​-- Just sit there + # 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