Information Technology Reference
In-Depth Information
Algorithm
R
UNTIME
V
ERIFICATION
P
ARTICLE
F
ILTERING
Input
: System Model HMM
H
=(
X,O,P
(
X
t
| X
t−
1
)
, P
(
O
t
| X
t
)
, P
(
X
0
)),
Monitor DFA
M
=(
S,Q,P
(
S
t
| S
t−
1
)
, P
(
Q
t
| S
t
)
, P
(
S
0
)
,F
),
Program Events
o
1:
T
, Peek Events
q
1:
T
, Number of particles
N
p
Output
: Joint probability distribution
P
(
X
T
,S
T
|
o
1:
T
,
q
1:
T
) after seeing
o
1:
T
and
q
1:
T
1 [
P
(
O
t
|
X
t−
1
,O
t
)]=P
RECOMPUTE
P
ROBABILITIES
(
H
)
2 (
x
0
,
s
0
,
w
0
) =I
NITIALIZE
P
ARTICLE
D
ISTRIBUTION
(
P
(
X
0
),
P
(
S
0
),
N
p
)
3
X
t−
1
)
, P
(
X
t
|
for
t
= 1
to
T
do
4
if
o
t
=
gap
then
5
for
i
= 1
to
N
p
do
SAMPLE
x
(
i
)
t
FROM
P
(
X
t
| x
(
i
)
t−
1
,o
t
)
6
SAMPLE
s
(
i
)
t
FROM
P
(
S
t
| s
(
i
)
7
t−
1
,o
t
)
w
(
i
)
t
=
w
(
i
)
t−
1
· P
(
o
(
i
)
| x
(
i
)
8
t−
1
)
t
9
end
10
else
11
=
LENGTH OF GAP
12
(
x
t−
1
,
s
t−
1
,
w
t−
1
) =R
ESAMPLE
(
x
t−
1
,
s
t−
1
,
w
t−
1
)
13
for
i
= 1
to
N
p
do
(
x
0
,s
0
,w
0
) = (
x
(
i
)
t−
1
,s
(
i
)
t−
1
,w
(
i
)
14
t−
1
)
15
for
k
= 1
to
do
SAMPLE
o
k
FROM
P
(
O
k
| x
k−
1
)
16
SAMPLE
x
k
FROM
P
(
X
k
| x
k−
1
,o
k
)
17
SAMPLE
s
k
FROM
P
(
S
k
| s
k−
1
,o
k
)
18
w
k
=
w
k−
1
· P
(
o
k
| x
k−
1
)
19
20
end
(
x
(
i
)
t
,s
(
i
)
t
,w
(
i
)
t
) = (
x
k
,s
k
,w
k
)
21
22
end
for
i
= 1
to
N
p
do
w
(
i
)
t
=
w
(
i
)
t
· P
(
q
t
| s
(
i
)
t
23
)
/* handling a peek event
q
t
*/
24
end
25
NORMALIZE WEIGHTS
w
t
26
m
= 0
for
i
= 1
to
N
p
do
m
=
m
+
w
i
27
28
if
1
/m N
p
∨ q
t
=
∅
then
(
x
t
,
s
t
,
w
t
) =R
ESAMPLE
(
x
t
,
s
t
,
w
t
)
29
end
INITIALIZE MATRIX
P
(
X
T
,S
T
|
o
1:
T
,
q
1:
T
)
WITH ZEROS
30
for
i
= 1
to
N
p
do
P
(
x
(
i
T
,s
(
i
)
|
o
1:
T
,
q
1:
T
) =
P
(
x
(
i
T
,s
(
i
)
|
o
1:
T
,
q
1:
T
)+
w
(
i
)
31
T
T
T
32
return
P
(
X
T
,S
T
|
o
1:
T
,
q
1:
T
)
On Line 1 of P
RECOMPUTE
P
ROBABILITIES
, the matrix
P
(
O
t
|
X
t−
1
) is obtained
through a straightforward matrix multiplication of
P
(
X
t
|
X
t−
1
) and
P
(
O
t
|
X
t
).This
is followed by the construction of the 3D-array
P
(
X
t
|
X
t−
1
,O
t
) in Lines 2-8.
P
(
X
t
|
X
t−
1
,O
t
) can be best thought of as an array of transition probability matrices
P
(
X
t
|
X
t−
1
), one for each observation symbol
o
t
. This layout makes it possible for the
RVPF algorithm to choose the appropriate transition probability distribution depending
on the observation symbol generated by the HMM.
