Generating Optimal Plans in Highly-Dynamic Domains
  Generating optimal plans in highly dynamic environments is challenging. Plans
are predicated on an assumed initial state, but this state can change
unexpectedly during plan generation, potentially invalidating the planning
effort. In this paper we make three contributions: (1) We propose a novel
algorithm for generating optimal plans in settings where frequent, unexpected
events interfere with planning. It is able to quickly distinguish relevant from
irrelevant state changes, and to update the existing planning search tree if
necessary. (2) We argue for a new criterion for evaluating plan adaptation
techniques: the relative running time compared to the "size" of changes. This
is significant since during recovery more changes may occur that need to be
recovered from subsequently, and in order for this process of repeated recovery
to terminate, recovery time has to converge. (3) We show empirically that our
approach can converge and find optimal plans in environments that would
ordinarily defy planning due to their high dynamics.
