function CONFORMANTPLAN(I,G)
0 begin 1 2
  
4 5 6 7 8 g 10 11 12 13 end i = 0:
BsPTables[0]:={ {G . ε) };
Plans : = EXTRACTSOLUTION(I, BsPTables[0]); while ((BsPTables[i] ≠ ∅) ∧ (Plans = ∅)) do i : = i + 1; BsPTables[i] : = EXPANDBSPTABLE(BsPTables[i-1]);
BsPTables[i] : = PRUNEBSPTABLE( BsPTables[i], BsPTables, i);
Plans := EXTRACTSOLUTION(I, BsPTables[i]);
done if (BsPTables[i] = 0) then return Fail; else return Plans; Figure 4: The conformant planning algorithm.

action α , the strong pre-image of B s is computed, and if the resulting belief state B s ′ is not empty, i.e. there is a belief state from which α guarantees the achievement of B s, then the plan π is extended with α and 〈 Bs ′ . α; π ⟩ is returned. The expansion of a BsP table is the union of the expansions of each BsP pair. The function EXTRACTSOLUTION takes as input a BsP table and returns the (possibly empty) set of plans which index a belief states containing I. PRUNEBSPTABLE takes as input the BsP table to be pruned, an array of previously constructed BsP tables BsPTables, and an index of the current step. It removes from the BsP table in the input the plans which are not worth being explored because the corresponding belief states have already been visited.

The algorithm has the following properties. First, it always terminates. This follows from the fact that the set of explored belief sets (stored in BsPTables) is monotonically increasing - at each step we proceed only if at least one new belief state is generated.

Because of its finiteness (the set of accumulated belief states is contained in 2 s which is finite), a fix point is eventually reached. Second, it is correct, i.e. when a plan is returned it is a conformant solution to the given problem. The correctness of the algorithm follows from the properties of SPreImage: each plan is associated with a belief state for which it is conformant, i.e. where it is guaranteed to be applicable and from which it results in a belief state contained in the goal. Third, the algorithm is optimal, i.e. it returns plans of minimal length. This property follows from the breadth-first style of the search. Finally, the algorithm is able to decide whether a problem admits no solution, returning Fail in such cases. Indeed, a conformant solution is always associated with a belief state containing the initial states. SPreImage generates the maximal belief state associated with a conformant plan, each new belief state generated in the exploration is compared with the initial states to check if it is a solution, and a plan is pruned only if an equivalent plan has already been explored.