  In order to ensure the robust actuation of a plan, execution must be
adaptable to unexpected situations in the world and to exogenous events. This
is critical in domains in which committing to a wrong ordering of actions can
cause the plan failure, even when all the actions succeed. We propose an
approach to the execution of a task plan that permits some adaptability to
unexpected observations of the state while maintaining the validity of the plan
through online reasoning.
  Our approach computes an adaptable, partially-ordered plan from a given
totally-ordered plan. The partially-ordered plan is adaptable in that it can
exploit beneficial differences between the world and what was expected. The
approach is general in that it can be used with any task planner that produces
either a totally or a partially-ordered plan. We propose a plan execution
algorithm that computes online the complete set of valid totally-ordered plans
described by an adaptable partially-ordered plan together with the probability
of success for each of them. This set is then used to choose the next action to
execute.
