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