





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 tlength trajectory


Throw it out if
inconsistent


Report the
tlength 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


