Extending Conformant Fast-Forward to Deal with Disjunctive Goals

Conformant Fast-Forward that handles certain goals is extended to a new system that can deal with uncertain goals, and the new planning system implemented is called Conformant-FF-d that can deal with disjunctive goals. Disjunctive goals are one of the expressions of uncertain goals, and disjunctive goals are widely used in expressing uncertain goals in planning domains. Some key components of Conformant-FF-d system include goal state recognition, reachability analysis and the heuristic function for disjunctive goals. A method that uses a SAT technique to recognize the goal states efficiently is proposed. In order to do reachability analysis, an algorithm based on relaxed planning graph and implication graph is developed, which prunes the belief states that can never reach the goals. The method of reachability analysis reduces the size of the searching space, so the plan can be found in a relatively small searching space other than the whole space. A new heuristic function suitable for disjunctive goals is defined, and the function guides the search algorithm towards goal states effectively. Conformant-FF-d and the POND system are tested on domains which are used in the international planning competition. Experimental results show that Conformant-FF-d can deal with uncertain goals expressed in disjunctive form and outperforms the POND system in both efficiency and scalability.