

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

where the π i are plans of the same length, such that π i ̸ = π i for all 1 ≤ j≠i ≤ n. We call Bsi the belief set indexed by π i . When no ambiguity arises, we write BsPT( π i ) for Bsi. The array BsPTables is used to store the BsP tables representing the levels of the search. The algorithm first checks (line 4) if there are plans of length 0, i.e. if c is a solution. If no conformant plan of such length exists (( Plans = 0) in line 4), then the while loop is entered. At each iteration, conformant plans of increasing length are explored (lines 5 to 8). The step at line 6 expands the BsP table in BsPTables[i - 1] and stores the resulting BsP table in BsPTables[i]. BsP pairs which are redundant with respect to the current search are eliminated from BsPTables[i] (line 7). The possible solutions contained in BsPTables[i] are extracted and stored in Plans (line 8). The loop terminates if either a plan is found ( Plans ≠ ∅), or the space of conformant plans has been completely explored ( BsPTables[i] = 0).

The definitions of the basic functions used in the algorithm are reported in Figure 5.

The function EXPANDBSP TABLE expands the BsP table provided as argument, containing conformant plans of length i - 1, and returns a BsP table with conformant plans of length i. Each BsP in the input BsP table is expanded by EXPANDBSPPAIR. For each possible