function PARTICLE-FILTERING(e, N, dbn) returns a set of samples for the next time step
inputs: e, the new incoming evidence
N, the number of samples to be maintained
dbn, a DBN with prior P(X0), transition model P(X1 | X0), sensor model P(E1 | X1)
persistent: S, a vector of samples of size N, initially generated from P(X0)
local variables: W, a vector of weights of size N
for i = 1 to N do
S[i] ← sample from P(X1 | X0 = S[i]) /* step 1 */
W[i] ← P(e | X1 = S[i]) /* step 2 */
S ← WEIGHTED-SAMPLE-WITH-REPLACEMENT(N, S, W) /* step 3 */
return S
Figure ?? The particle filtering algorithm implemented as a recursive update operation with state (the set of samples). Each of the sampling operations involves sampling the relevant slice variables in topological order, much as in PRIOR-SAMPLE. The WEIGHTED-SAMPLE-WITH-REPLACEMENT operation can be implemented to run in O(N) expected time. The step numbers refer to the description in the text.