
## 4. The Conformant Planning Algorithm

Our conformant planning algorithm is based on the exploration of the space of plans, limiting the exploration to plans which are conformant by construction. The algorithm builds Belief state-Plan (BsP) pairs of the form (Bs . π), where Bs is a non-empty belief state and π is a plan. The idea is to use a BsP pair to associate each explored plan with the maximal belief state where it is applicable, and from which it is guaranteed to result in goal states.

The exploration is based on the basic function SPreImage[α]( Bs ), that, given a beliefstate Bs and an action α , returns the belief state containing all the states where α is applicable, and whose image under α is contained in B s .

Definition 6 (Strong Pre-Image) Let b ̸ = Bs ⊆ S be a belief state and let α be an action.

The strong pre-image of Bs under α, written SPreImage[α](Bs), is defined as follows.

SPreImage[α](Bs) = {s | α is applicable in s, and Image[α](s) ⊆ Bs}
If SPreImage[ α ]( Bs ) is not empty, then α is applicable in it, and it is a conformant soltion to the problem ( SPreImage [ α ]( Bs ), Bs ). Therefore, if the plan π is a conformant solution for the problem ( Bs, G ), then the plan α ; π is a conformant solution to the problem
( SPreImage[a](Bs), G),
Figure 3 depicts the space of BsP pairs built by the algorithm while solving the BTUC
problem. The levels are built from the goal, on the right, towards the initial states, on the left. At level 0, the only BsP pair is ({5, 7} . c), composed by the set of goal states indexed by the 0-length plan ε . (Notice that ε is a conformant solution to every problem with goal set
{5, 7} and initial states contained in {5, 7}.) The dashed arrows represent the application of SPreImage . At level 1, only the BsP pair ({5, 6, 7, 8} . Flush ) is built, since the strong pre-image of the belief state 0 for the actions Dunk 1 and Dunk 2 is empty. At level 2, there are three BsP pairs, with (overlapping) belief states Bs 2 , Bs 3 and Bs 4 , indexed, respectively, by the length 2 plans Dunk 1 ; Flush, Flush, Flush and Dunk 2 ; Flush. (A plan associated with a belief state Bsi is a sequence of actions labeling the path from Bsi to Bso.) Notice that Bs 3 is equal to Bs 1 , and therefore deserves no further expansion. The expansion of belief states 2 and 4 gives the belief states 5 and 6, both obtained by the strong pre-image under Flush, while the strong pre-image under actions Dunk 1 and Dunk 2 returns empty belief states. The further expansion of Bs 5 results in three belief states. The one resulting from the strong pre-image under Flush is not reported, since it is equal to Bs 5 . Beliefstate 7 is also equal to Bs 2 , and deserves no further expansion. Belief state 8 can be obtained by expanding both Bs5 and Bs6. At level 5, the expansion produces Bs10, which contains all the initial states. Therefore, both of the corresponding plans are conformant solutions to the problem.

The conformant planning algorithm ConformantPlan is presented in Figure 4. It takes as input the planning problem in the form of the set of states I and G (the domain D is assumed to be globally available). The algorithm performs a backwards breadth-first search, exploring BsP pairs corresponding to plans of increasing length at each step. The status of the search (each level in Figure 3) is represented by a BsP table, i.e. a set of BsP
pirs

$BsPT=\{\langle B\,s_{1}\,\,.\,\,\pi_{1}\rangle,\,.\,.\,.\,\,\langle B\,s_{n}\,\,.\,\,\pi_{n}\rangle\}$