Exploiting the Structure of a Relaxed Plan

The actions in the relaxed plan to the goal from a given state can be used to provide further search advice. YAHSP [Vidal 2004], a planner that produced interesting results in the Fourth International Planning Competition (IPC 4), makes use of the actions of the relaxed plan to suggest actions to add to the current plan to reach the goal. In FF, the notion of `helpful actions' is defined--those that add a fact added by an action chosen at the first time unit in the relaxed plan. In each state encountered during search, a number of actions are applicable, some of which are irrelevant; i.e. they make no progress towards the goal. By only considering the helpful actions when determining the successors to each state, when performing EHC, the number of successor states to be evaluated will be reduced.

Restricting the choice of actions to apply only to those that are `helpful' further reduces the completeness of EHC, beyond what would be the case if all applicable actions were considered. In practice it is observed, however, that the cases where EHC using only helpful actions is unable to find a plan correlate with the cases where EHC with all the applicable actions would be unable to find a plan.