${\cal C}{\sl AltAlt}$

The CAltAlt planner uses the regression operator to generate children in an A* search. Regression terminates when search node expansion generates a belief state $BS$ which is logically entailed by the initial belief state $BS_I$ . The plan is the sequence of actions regressed from $BS_G$ to obtain the belief state entailed by $BS_I$ .

For example, in the BTC problem, Figure 1, we have:

$BS_2 =$ Regress$(BS_G,$ DunkP1) = $\neg$ clog $\wedge$ ($\neg$ arm $\vee$ inP1).

The first clause is the execution formula and the second clause is the causation formula for the conditional effect of DunkP1 and $\neg$ arm.

Regressing $BS_2$ with Flush gives:

$BS_4 =$ Regress$(BS_2,$ Flush$) =$ ($\neg$ arm $\vee$ inP1).

For $BS_4$ , the execution precondition of Flush is $\top$ , the causation formula is $\top \vee \neg$ clog $= \top$ , and ($\neg$ arm $\vee$ inP1) comes by persistence of the causation formula.

Finally, regressing $BS_4$ with DunkP2 gives:

$BS_9 =$ Regress$(BS_4,$ DunkP2) = $\neg$ clog $\wedge$ ($\neg$ arm $\vee$ inP1 $\vee$ inP2).

We terminate at $BS_9$ because $BS_I \models BS_9$ . The plan is DunkP2, Flush, DunkP1.

Figure 1: Illustration of the regression search path for a conformant plan in the $BTC$ problem.