# How to take prediction step in particle filter?

I am working on particle filter. I have studied it thoroughly, but stucked at one point during implementation. I have to implement it using MatLab. The issue is this that I am unable to implement the prediction step. As far as I know, it is dependent upon the motion model. motion model is generally dependent upon the noise and previous value of its output.

                      x(t)= P[x(t) | x(t-1)] = f(x(t-1))+noise  //motion model


But I am not getting this point that what should be my prediction step depends upon the motion model. As at time t, it is dependent upon the x(t) and X_predict(t-1), but how do I arrange it, so that my actual and estimated output will have small error. I have tried different methods, but still having the same issue that my actual and estimated values are not approximated, and giving large errors.

I know that weights depend upon the X_predict(t), and if it is not correct, so my estimated output will be wrong.

Kindly guide me how do I proceed.

• Could you clarify what you mean by this? " As at time t, it is dependent upon the x(t) and X_predict(t-1), but how do I arrange it, so that my actual and estimated output will have small error. I have tried different methods, but still having the same issue that my actual and estimated values are not approximated, and giving large errors." Apr 13 '20 at 22:02
• As I mean to say that at time t, the Prediction which I am representing here as X_predict(t) is dependent upon the current value of motion model x(t) and previous value of Prediction step X_predict(t-1). And I want to ask how do I write the prediction step so that my estimated output is approximated same as actual output. I hope my point is now clear. Apr 14 '20 at 5:34
• What do you mean by actual output? Also your motion model shouldn't have a value. It is a stateless function. It should look like something from here Apr 14 '20 at 15:37

The prediction step generates a new set of states from the old set of states. The motion model of the system is used to make this best estimate of what we think the new state might be. The motion model basically uses the information about the previous state and the current control input to determine the new state. Some noise is also added for stochasticity. In cases where you do not have a motion model or any information about the control input, just adding noise is an option but most likely gives a less accurate estimate. In a particle filter, the the accuracy of your best estimate/particle really depends on how well you have propagated your new particles into the next time step using the motion model. As you can imagine, having a higher number of particles to represent the distribution increases the chances that one of them is very close to the actual state.

Like edwinem mentioned, the motion model just describes how the object should move. Consider gravity:

$$\ddot{y} = -g \\$$

If you wanted a motion model for position, then:

$$y = y_0 + \dot{y}t + \frac{1}{2}\ddot{y}t^2 \\ y = y_0 + \dot{y}t - \frac{1}{2}gt^2 \\$$

So if you have a ball at $$y_0 = 5$$, does the ball go down in the next instant or does it go up? The answer to that depends on the previous state of your system. If it had a vertical velocity such that $$\left(\dot{y}t\right)>\left(\frac{1}{2}gt^2\right)$$ then the ball goes up.

If you are finding that your predictions are very far from your measured values, then either your estimated states X_predict(t-1) are wrong or your model is wrong. That is, you're either starting in the wrong location or you're moving in the wrong direction.

:EDIT:

If you don't think anything should be moving, then you could do the same, but now instead of:

$$\ddot{y} = -g\\$$

You could model acceleration as resulting strictly from some noise:

$$\ddot{y} = \sigma\\$$

And then modify the position model to rely on "incremental" updates, such that:

$$y = y_0 + \dot{y}t + \frac{1}{2}\ddot{y}t^2\\$$

becomes:

$$y_k = y_{k-1} + \dot{y}\Delta t + \frac{1}{2}\ddot{y}\Delta t^2 \\$$

And then, if the noisy acceleration is an input to the system, you wind up with:

$$\left[\begin{matrix} \dot{y} \\ \ddot{y} \end{matrix}\right] = \left[\begin{matrix} 0 & 1\\ 0 & 0 \end{matrix}\right]\left[\begin{matrix} y \\ \dot{y}\end{matrix}\right] + \left[\begin{matrix} 0 \\ 1\end{matrix}\right]\sigma$$

If you depict this as:

$$\dot{x} = Ax + Bu \\$$

then you can do a kind of integration, such that:

$$x_k = I*x_{k-1} + \left(\dot{x}\Delta t\right) \\$$

and so you get:

$$\begin{matrix} x_k \\ \left[\begin{matrix} y_k \\ \dot{y}_k \end{matrix}\right]\end{matrix} = \begin{matrix} I \\ \left[\begin{matrix} 1 & 0\\ 0 & 1 \end{matrix}\right]\end{matrix} \begin{matrix} x_{k-1} \\ \left[\begin{matrix} y_{k-1} \\ \dot{y}_{k-1}\end{matrix}\right]\end{matrix} + \left(\begin{matrix} A\Delta t \\ \left[\begin{matrix} 0 & \Delta t\\ 0 & 0 \end{matrix}\right]\end{matrix}\begin{matrix} x_{k-1} \\ \left[\begin{matrix} y_{k-1} \\ \dot{y}_{k-1}\end{matrix}\right]\end{matrix} + \begin{matrix} B\Delta t & \sigma\\ \left[\begin{matrix} 0 \\ \Delta t\end{matrix}\right] & \sigma\end{matrix}\right)$$

which of course reduces to:

$$\left[\begin{matrix} y_k \\ \dot{y}_k \end{matrix}\right] = \left[\begin{matrix} 1 & \Delta t\\ 0 & 1 \end{matrix}\right]\left[\begin{matrix} y_{k-1} \\ \dot{y}_{k-1}\end{matrix}\right] + \left[\begin{matrix} 0 \\ \Delta t\end{matrix}\right]\sigma$$

The above would be a decent first motion model if you had no prior knowledge of how you expected something to move.

• Basiclly I am not working on any robot localization or any other thing related to it. I have just different video frames in which different people or vehicles are moving and I have to track them. So in this case which kind of motion model can I take? Apr 16 '20 at 2:47
• @TariqS - In that case, I've seen models for a Kalman filter that do basically the same equation as above, but if you don't think anything should be accelerating your object then you just leave the driving acceleration as zero in the model and include a "noise" that affects acceleration. I'll edit the answer to give an example. Apr 16 '20 at 13:07
• The motion model is converted into the analytic expression. The measured position from the previous timestep is feed into the equation which generates the new position. The advantage of the matrix equation is, that it describes the prediction step of a particle filter in mathematical precise terms which is needed in a university context. Apr 17 '20 at 18:02