|
|
|
|
|
|
To track the n
most likely trajectories
|
|
For each new
time step until the end of time
|
|
Create full copy
of the model for the new time step
|
|
Assign command
and observation variables
|
|
Until n consistent
trajectories found
|
|
Enumerate the
next best t-length trajectory
|
|
Throw it out if
inconsistent
|
|
Report the
t-length trajectories
|
|
|
|
An Algorithm
with Only Two Problems!
|
|
Space - Representation grows linearly with time
|
|
Time - Search space grows exponentially with
time - Checks an exponential number of
obviously wrong candidates
|
|
|
|
The assignments
to t capture every possible trajectory
|
|
Trajectories can
be enumerated in prior probability order
|
|
P(trajectory) = S P(t assignment)
|
|
Each trajectory
can be checked for agreement with observations
|
|
|
|
|
|
|
|
|
|
|
|
Avoid committing
to a small number of trajectories
|
|
Build a
structure that compactly represents all evolutions
|
|
Generate
additional trajectories in order as needed
|
|
|
