

![0_image_0.png](0_image_0.png)

states in BSG, in this case the terminal belief state contains exactly the states in BSG. The cost of the solution is three because, through revision, BS30 has a cost of one, which sets BS10 to a cost of two. However, this means now that BSI has cost of three if its best action is DunkP1. Instead, revision sets the best action for BSI to DunkP2 because its cost is currently two.

We then expand BS40 with DunkP1 to find that its successor is BSG. DunkP2 creates a cycle back to BS20 so it is not added to the search graph. We now have our second valid solution because it contains no unexpanded leaf nodes. Revision sets the cost of BS40 to one, BS20 to two, and BSI to three. Since all solutions starting at BSI have equal cost (meaning there are now cheaper solutions), we can terminate with the plan DunkP2, Flush, DunkP1, shown in bold with dashed lines in Figure 2.

As an example of search for a conditional plan in **P OND**, consider the BTCS example whose search graph is also shown in Figure 2. Expanding the initial belief state, we get:

$$\left[\,\mathrm{{\bf{T}}}\,\mathrm{{\bf{T}}}\,\mathrm{{\bf{0}}}\,\right]=0$$
$\downarrow$ 4. 
B1 = {BS10} = Progress(BSI , DunkP1),

$$\{B S_{20}\}=\mathbf{R}$$

B2 = {BS20} = Progress(BSI , DunkP2),
and

B5 = {BS50**, BS**51} = Progress(BSI ,DetectMetal)
= {inP1 ∧¬inP2 ∧¬clog ∧ arm, ¬inP1 ∧ inP2 ∧¬clog ∧ arm}.
Each of the leaf nodes is assigned a cost of zero, and DunkP1 is chosen arbitrarily for the best solution rooted at BSI because the cost of each solution is identical. The cost of including each hyper-edge is the average cost of its children plus its cost, so the cost of using DetectMetal is (0+0)/2
+ 1 = 1. Thus, our root BSI has a cost of one.