The SPUDD planner was applied to the IPPC instances, solving each
optimally. SPUDD uses a dynamic abstraction method for solving MDPs
using algebraic decision diagrams (ADDs) to represent value functions
and policies. ADDs are generalizations of ordered binary decision
diagrams (BDDs) that allow non-boolean labels at terminal nodes. This
representational technique allows one to describe a value function (or
policy) as a function of the variables describing the domain rather
than in the classical "tabular" way. The decision graph used to
represent this function is often extremely compact, implicitly
grouping together states that agree on value at different points in
the dynamic programming computation. As such, the number of expected
value computations and maximizations required by dynamic programming
are greatly reduced. SPUDD was applied to the IPPC instances using a
timer that allowed value iteration to run until the timeout was
exceeded. The timer was dynamically set to be the remaining time in
the competition divided by the number of remaining instances. The
instances were solved in order of difficulty level. The traffic
domain was removed after the second set of instances was attempted, as
the space usage went beyond the available memory.