Conditional Planning in the Discrete Belief Space

1 Introduction

When the sequence of states that will be visited during plan execution cannot be exactly predicted, for example because of nondeterminism, it is necessary to produce plans that apply different actions depending on how the plan execution has proceeded so far. Such plans are called conditional plans.

Construction of conditional plans is particularly difficult when there is no full observability; that is, when during plan execution it is not possible to uniquely determine what the current state of the world is. Planning problems having this property are said to be partially observable, and their solution requires that the sets of possible current world states - the belief states - are (implicitly) maintained during plan execution and (implicitly) represented by a plan.

The earliest work on planning with partial observability was in the framework of partially observable Markov decision processes (POMDPs) [Smallwood and Sondik, 1973; Kaelbling et al., 1998]. Planning with POMDPs is computationally difficult. For unbounded horizon lengths an unbounded number of probability distributions corresponding to belief states needs to be considered, and finding optimal plans is not in general solvable [Madani et al., 1999]. A natural approach for easing the computational difficulty of POMDP planning is to consider horizons of a bounded length [Mundhenk et al., 2000]. A second approach which has been pursued with algorithms for conditional planning [Weld et al., 1998; Bonet and Geffner, 2000; Bertoli et al., 2001], ignores probabilities and hence directly yields a finitary problem. Main decision problems related to non-probabilistic planning with partial observability are 2-EXP-complete [Rintanen, 2004a].

∗This research was partly supported by DFG grant RI 1177/2-1.

A main difference between POMDPs and corresponding non-probabilistic problems is that the latter do not use probabilistic notions like success probability or expected cost, and require that a plan must reach the goals with certainty. An implication of success probability 1 is that uncertainty about observations and sensing can be ignored: if an observation is correct with a probability strictly less than 1 then it is as good as no observation at all.

For this planning problem we present an iterative algorithm that has some resemblance to iterative algorithms for solving POMDPs. The algorithm maintains a data structure representing those belief states for which a conditional plan has been shown to exist. Initially this data structure represents those belief states consisting of goal states only. Then this data structure is repeatedly extended by performing search backwards from the goal belief states.

The structure of the paper is as follows. Section 2 defines the planning problem. Sections 3 and 4 respectively describe the formal framework and analyze its properties. Section 5 proposes a planning algorithm and Section 6 presents experimental results obtained with an implementation of the algorithm. Section 7 concludes the paper.

2 The Planning Problem

In this section we present a formalization of planning in which states are atomic objects without internal structure.

Definition 1 A problem instance is 〈S, I,O,G, P〉 where S is the set of states, I ⊆ S is the set of initial states, O is the set of actions o ⊆ S × S, G ⊆ S is the set of goal states and P = (C1, . . . ,Cn) is a partition of S into classes of observationally indistinguishable states satisfying ⋃{C1, . . . , Cn} = S and Ci ∩ Cj = ∅ for all i, j such that 1 ≤ i < j ≤ n.

Making an observation tells which set Ci the current state belongs to. Distinguishing states in a given Ci is not possible.

An action is a relation between states and their successor states. An action o is applicable in a state s if sos′ for some s′ ∈ S. Define the image of a set B of states with respect to an action o as imgo (B) = {s′ ∈ S|s ∈ B, sos′ }. The preimage is preimgo (B) = {s ∈ S|∅ ̸= imgo ({s}) ⊆ B}, consisting of those states from which o is guaranteed to reach a state in B. An action o is deterministic if it is a partial function.

Plans are directed graphs with two kinds of nodes: action nodes and observation nodes.

Definition 2 Let 〈S, I, O, G, (C1, . . . , Cn)〉 be a problem instance. A plan is a triple 〈N, b, l〉 where

• N is a finite set of nodes,
• b ∈ N is the initial node,
• l : N → (O×N)∪22S ×N is a function that assigns each node an action and a successor node 〈o, n〉 ∈ O × N or a set of states and successor nodes 〈C, n〉 ∈ 22S ×N where C = ⋃{C′1 , . . . , C′m} for some {C′1 , . . . , C′m} ⊆ {C1, . . . ,Cn}. In the first case the node is an action node and in the second an observation node.

For all n ∈ N and {〈C,m〉, 〈C′ ,m′ 〉} ⊆ l(n) the observations C and C′ may not intersect: C ∩ C′ = ∅. Nodes with l(n) = ∅ are terminal.

We restrict to acyclic plans. Acyclicity means that the graph 〈N, E〉, where 〈n, n′ 〉 ∈ E iff l(n) = 〈o, n′ 〉 for some o or 〈C, n′ 〉 ∈ l(n) for some C, is acyclic. 1

Plan execution starts from the initial node b and any of the initial states. For an action node with label 〈o, n〉 in state s execute o and continue from n and a state in imgo (s). For an observation node identify 〈C, n〉 in the node label so that s ∈ C, and then continue from n and s. A plan solves a problem instance if all of its executions terminate in a terminal node and a goal state. Execution of an acyclic plan can have at most as many steps as there are nodes in the plan.

3 ProblemRepresentation

Now we introduce the representation for sets of state sets for which a plan for reaching goal states exists.

In the following example states are viewed as valuations of state variables, and the observational classes correspond to valuations of those state variables that are observable.

Example 3 Consider the blocks world with the state variables clear(X) observable, allowing to observe the topmost block of each stack. With three blocks there are 7 observational classes because there are 7 valuations of {clear(A), clear(B), clear(C)} with at least one block clear.

Consider the problem of trying to reach the state in which all blocks are on the table. For each block there is an action for moving it onto the table from wherever it was before. If a block cannot be moved nothing happens. Initially we only have the empty plan for the goal states.

1 Construction of cyclic plans requires looking at more global properties of transition graphs than what is needed for acyclic plans. The difficulties of cyclic plans in our framework are similar to those in the MDP/POMDP framework when using average rewards instead of finite horizons or discounted rewards [Puterman, 1994].

Then we compute the preimages of this set with actions that respectively put the blocks A, B and C onto the table, and split the resulting sets to the different observational classes.

Now for these 7 belief states we have a plan consisting of one or zero actions. But we also have plans for sets of states that are only represented implicitly. These involve branching. For example, we have a plan for the state set consisting of the four states in which respectively all blocks are on the table, A is on C, A is on B, and B is on A. This plan first makes observations and branches, and then executes the plan associated with the belief state obtained in each case. Because 3 observational classes each have 2 belief states, there are 23 maximal state sets with a branching plan. From each class only one belief state can be chosen because observations cannot distinguish between belief states in the same class.

We can find more belief states that have plans by computing preimages of existing belief states. Let us choose the belief states in which respectively all blocks are on the table, B is on C, C is on B, and C is on A, and compute their union's preimage with A-onto-table. The preimage intersected with the observational classes yields new belief states: for the class with A and B clear there is a new 2-state belief state covering both previous belief states in the class, and for the class with A clear there is a new 2-state belief state.

Computation of further preimages yields for each observational class a belief state covering all the states in that class, and hence a plan for every belief state. ■

The above example shows how the exponential number of state sets (corresponding to the Cartesian product of the observational classes) considered by Rintanen [2002] is represented only implicitly. The algorithm by Rintanen [2002] explicitly generates the state sets, the number of which in many cases is very high. With the new representation the computational complexity is shifted from the size of the representation to the time it takes to find a combination of belief states having a useful preimage. This shift is useful for two reasons. First, much of the space complexity (and the time complexity it implies) is traded to time complexity only: the state sets are not represented explicitly (except in the unobservable special case.) Second, the succinct representation allows much better control on which belief states to produce, and although finding one new belief state and plan still takes worst-case exponential time, this may be performed by clever algorithms and be further sped up by heuristics.

Next we formalize the framework in detail.

Definition 4 (Belief space) Let P = (C1, . . . , Cn) be a partition of the set of all states. Then a belief space is an n-tuple 〈G1, . . . ,Gn〉 where Gi ⊆ 2Ci for all i ∈ {1, . . . , n} and B ̸⊂ B′ for all i ∈ {1, . . . , n} and {B, B′ } ⊆ Gi.

Notice that in each component of a belief space we only have set-inclusion maximal belief states. The simplest belief spaces are obtained from sets B of states as B(B) = 〈{C1 ∩ B}, . . . , {Cn ∩ B}〉. A belief space is extended as follows.

Definition 5 (Extension) Let P = (C1, . . . , Cn) be the partition of all states, G = 〈G1, . . . , Gn〉 a belief space, and T a set of states. Define G⊕T as 〈G1 ⋓(T ∩C1), . . . , Gn ⋓(T ∩ Cn)〉 where the operation ⋓ adds the latter set of states to the former set of sets of states and eliminates sets that are not setinclusion maximal, defined as U ⋓ V = {R ∈ U ∪ {V }|R ̸⊂ K for all K ∈ U ∪ {V }}.

A belief space G = 〈G1, . . . ,Gn〉 represents the set of sets of states flat(G) = {B1 ∪ · · · ∪ Bn|Bi ∈ Gi for all i ∈ {1, . . . , n}} and its cardinality is |G1| · |G2| · . . . · |Gn|.

4 Complexity of Basic Operations

The basic operations on belief spaces needed in planning algorithms are testing the membership of a set of states in a belief space, and finding a set of states whose preimage with respect to an action is not contained in the belief space. Next we analyze the complexity of these operations.

Theorem 6 For belief spaces G and state sets B, testing whether there is B′ ∈ flat(G) such that B ⊆ B′ , and computing G⊕B takes polynomial time.

Proof: Idea: A linear number of set-inclusion tests suffices. □

Our algorithm for extending belief spaces by computing the preimage of a set of states (Lemma 8) uses exhaustive search and runs in worst-case exponential time. This asymptotic worst-case complexity is very likely the best possible because the problem is NP-hard. Our proof for this fact is a reduction from SAT: represent each clause as the set of literals that are not in it, and then a satisfying assignment is a set of literals that is not included in any of the sets, corresponding to the same question about belief spaces.

Theorem 7 Testing if for belief space G there is R ∈ flat(G) such that preimgo (R) ̸⊆ R′ for all R′ ∈ flat(G) is NPcomplete. This holds even for deterministic actions o.

Proof: Membership is easy: For G = 〈G1, . . . ,Gn〉 choose nondeterministically Ri ∈ Gi for every i ∈ {1, . . . , n}, compute R = preimgo (R1∪· · ·∪Rn), and verify that R∩Ci ̸⊆ B for some i ∈ {1, . . . , n} and all B ∈ Gi. Each of these steps takes only polynomial time.

Let T = {c1, . . . , cm} be a set of clauses over propositions A = {a1, . . . , ak}. We define a belief space based on states {a1, . . . , ak, ˆa1, . . . , ˆak, z1, . . . , zk, ˆ z1, . . . , ˆ zk}. The states ˆa represent negative literals. Define

We claim that T is satisfiable if and only if there is B ∈ flat(G) such that preimgo (B) ̸⊆ B′ for all B′ ∈ flat(G).

Assume T is satisfiable, that is, there is M such that M |= T. Define M ′ = {zi|ai ∈ A,M |= ai} ∪ {ˆ zi|ai ∈ A,M ̸|= ai}. Now M ′ ⊆ B for some B ∈ flat(G) because from each class only one of {zi} or {ˆ zi} is taken. Let M ′′ = preimgo (M ′ ) = {ai ∈ A|M |= ai} ∪ {ˆai|ai ∈ A, M ̸|= ai}. We show that M ′′ ̸⊆ B for all B ∈ flat(G). Take any i ∈ {1, . . . ,m}. Because M |= ci, there is aj ∈ ci ∩ A such that M |= aj (or ¬aj ∈ ci, for which the proof goes similarly.) Now zj ∈M ′ , and therefore aj ∈M ′′ . Also, aj ̸∈ c′j . As there is such an aj (or ¬aj) for every i ∈ {1, . . . ,m}, M ′′ is not a subset of any c′i , and hence M ′′ ̸⊆ B for all B ∈ flat(G).

Assume there is B ∈ flat(G) such that D = preimgo (B) ̸⊆ B′ for all B′ ∈ flat(G). Now D is a subset of A∪ {ˆa|a ∈ A} with at most one of ai and ˆai for any i ∈ {1, . . . , k}. Define a model M such that for all a ∈ A, M |= a if and only if a ∈ D. We show that M |= T. Take any i ∈ {1, . . . ,m} (corresponding to a clause.) As D ̸⊆ B for all B ∈ flat(G), D ̸⊆ c′i . Hence there is aj or ˆaj in D\c′i . Consider the case with aj (ˆaj goes similarly.) As aj ̸∈ c′i , aj ∈ ci. By definition of M, M |= aj and hence M |= ci. As this holds for all i ∈ {1, . . . ,m}, M |= T . □

5 Planning Algorithms

Based on the problem representation in the preceding section, we devise a planning algorithm that repeatedly identifies new belief states (and associated plans) until a plan covering the initial states is found. The algorithm in Figure 2 tests for plan existence; further book-keeping is needed for outputting a plan. The size of the plan is proportional to the number of iterations the algorithm performs, and outputting the plan takes polynomial time in the size of the plan. The algorithm uses the subprocedure findnew (Figure 1) for extending the belief space (this is the NP-hard subproblem from Theorem 7). Our implementation of the subprocedure orders sets f1, . . . , fm by cardinality in a decreasing order: bigger belief states are tried first. We also use a simple pruning technique for deterministic actions o: If preimgo (fi) ⊆ preimgo (fj) for some i and j such that i > j, then we may ignore fi.

PROCEDURE findnew(o,A,F ,H); IF F = 〈〉 AND preimgo (A) ̸⊆ B for all B ∈ flat(H) THEN RETURN A; IF F = 〈〉 THEN RETURN ∅; F is 〈{f1, . . . , fm}, F2, . . . , Fk〉 for some k ≥ 1; FOR i := 1 TOmDO B := findnew(o,A ∪ fi,〈F2, . . . , Fk〉,H); IF B ̸= ∅ THEN RETURN B; END; RETURN ∅

PROCEDURE plan(I ,O,G); H := B(G); progress := true; WHILE progress and I ̸⊆ I ′ for all I ′ ∈ flat(H) DO progress := false; FOR EACH o ∈ O DO B := findnew(o,∅,H,H); IF B ̸= ∅ THEN BEGIN H := H ⊕ preimgo (B); progress := true; END; END; END; IF I ⊆ I ′ for some I ′ ∈ flat(H) THEN RETURN true ELSE RETURN false;

Lemma 8 Let H be a belief space and o an action. The procedure call findnew(o,∅,F,H) returns a set B′ of states such that B′ = preimgo (B) for some B ∈ flat(F) and B′ ̸⊆ B′′ for all B′′ ∈ flat(H), and if no such belief state exists it returns ∅.

Proof: Sketch: The procedure goes through the elements 〈B1, . . . ,Bn〉 of F1 × · · · × Fn and tests whether preimgo (B1 ∪ · · · ∪Bn) is in H. The sets B1 ∪ · · · ∪Bn are the elements of flat(F). The traversal through F1 × · · · × Fn is by generating a search tree with elements of F1 as children of the root node, elements of F2 as children of every child of the root node, and so on, and testing whether the preimage is in H. The second parameter of the procedure represents the state set constructed so far from the belief space, the third parameter is the remaining belief space, and the last parameter is the belief space that is to be extended, that is, the new belief state may not belong to it. □

The correctness proof of the procedure plan consists of the following lemma and theorems. The first lemma simply says that extending a belief space H is monotonic in the sense that the members of flat(H) can only become bigger.

Lemma 9 Assume T is any set of states and B ∈ flat(H). Then there is B′ ∈ flat(H ⊕ T ) so that B ⊆ B′ .

The second lemma says that if we have belief states in different observational classes such that each is included in a belief state of a belief space H, then there is a set in flat(H) that includes all these belief states.

Lemma 10 Let B1, . . . , Bn be sets of states so that for every i ∈ {1, . . . , n} there is B′i ∈ flat(H) such that Bi ⊆ B′i , and there is no observational class C such that for some {i, j} ⊆ {1, . . . , n} both i ̸= j and Bi ∩C ̸= ∅ and Bj ∩C ̸= ∅. Then there is B′ ∈ flat(H) such that B1 ∪ · · · ∪ Bn ⊆ B′ .

The proof of the next theorem shows how the algorithm is capable of finding any plan by constructing it bottom up starting from the leaf nodes. The construction is based on first assigning a belief state to each node in the plan, and then showing that the algorithm reaches that belief state from the goal states by repeated computation of preimages.

Theorem 11 Whenever there exists a finite acyclic plan for a problem instance, the algorithm in Figure 2 returns true.

Proof: Assume there is a plan 〈N, b, l〉 for a problem instance 〈S, I,O,G, P〉. Label all nodes of the plan as follows. The root node b is labeled with I, that is, Z(b) = I. When all parent nodes of a node n have a label, we assign a label to n. Let l(n1) = 〈o1, n〉, . . . , l(nm) = 〈om, n〉 for action nodes n1, . . . , nm that have n as the child node, and let l(n′1 ) = {〈C1, n〉, . . .}, . . . , l(n′k ) = {〈Ck, n〉, . . .} for all observation nodes n′1 , . . . , n′k with n as one of the children. Then Z(n) = imgo1 (Z(n1))∪· · ·∪imgom (Z(nm))∪(Z(n′1 )∩C1)∪· · ·∪ (Z(n′k )∩Ck). If the above labeling does not assign anything to a node n, then assign Z(n) = ∅. Each node is labeled with those states that are possible in that node on some execution.

We show that if plans for Z(n1), . . . ,Z(nk) exist, where n1, . . . , nk are children of a node n in a possible plan, then the algorithm determines that a plan for Z(n) exists as well.

Induction hypothesis: For each plan node n such that all paths to a terminal node have length i or less, its label B = Z(n) is a subset of some B′ ∈ flat(H) where H is the value of the program variable H after the while loop exits and H could not be extended further.

Base case i = 0: Terminal nodes of the plan are labeled with subsets of G. By Lemma 9, there is G′ such that G ⊆ G′ and G′ ∈ flat(H) because initially H = B(G) and thereafter it was repeatedly extended.

Inductive case i ≥ 1: Let n be a plan node. By the induction hypothesis for all children n′ of n, Z(n′ ) ⊆ B for some B ∈ flat(H).

If n is an observation node with children n1, . . . , nk and respective observations C1, . . . ,Ck, then Z(n) ∩ C1, . . ., Z(n) ∩ Ck all occupy disjoint observational classes and superset of Z(n) ∩ Ci for every i ∈ {1, . . . , k} is in flat(H). Hence by Lemma 10 Z(n) ⊆ B for some B ∈ flat(H).

If n is an action node with action o and child node n′ , then imgo (Z(n)) ⊆ Z(n′ ), and by the induction hypothesis Z(n′ ) ⊆ B′ for some B′ ∈ flat(H). We have to show that Z(n) ⊆ B′′ for some B′′ ∈ flat(H). Assume that there is no such B′′ . But now by Lemma 8 findnew(o,∅,H,H) would return B′′′ such that preimgo (B′′′ ) ̸⊆ B for all B ∈ flat(H), and the while loop could not have exited with H, contrary to our assumption about H. □

Theorem 12 Let Π = 〈S, I, O, G, P 〉 be a problem instance. If plan(I,O,G) returns true, then Π has a solution plan.

Proof: Let H0,H1, . . . be the sequence of belief spaces H produced by the algorithm. We show that for all i ≥ 0, for every B ∈ flat(Hi) there is a plan that reaches G.

Induction hypothesis: Hi contains only such state sets B ∈ flat(Hi) for which a plan reaching G exists.

Base case i = 0: H0 = B(G), and the only state set in H0 is G. The empty plan reaches G from G.

Inductive case i ≥ 1: Hi+1 is obtained as Hi⊕preimgo (B) where B = findnew(o,∅,Hi,Hi).

Because by Lemma 8 B ∈ flat(Hi), by induction hypothesis there is a plan π for B. The plan that executes o followed by π reaches G from preimgo (B).

Let B be any member of flat(Hi+1). We show that for B there is a plan for reaching G. The plan for B starts by a branch 2 . We show that for every possible observation, corresponding to one observational class, there is a plan that reaches G. Let Cj be the jth observational class. When observing Cj, the current state is in Bj = B ∩ Cj. Now for Bj there is B′j ∈ Hi+1,j with Bj ⊆ B′j where Hi+1,j is the jth component of Hi+1. Now by induction hypothesis there is a plan for B′j if B′j ∈ Hi,j, and if B′j ∈ Hi+1,j\Hi,j, then for the branch corresponding to Cj we use the plan for preimgo (B), as B′j must be preimgo (B) ∩ Cj . □

Until now we have used only one partition of the state space to observational classes. However, it is relatively straightforward to generalize the above definitions and algorithms to the case in which several partitions are used, each for a different set of actions. This means that the possible observations depend on the action that has last been taken.

6 Experimentation with an Implementation

We have implemented the algorithm from the previous section and call the resulting planning system BBSP. The only heuristic is the one described in the preceding sections: findnew chooses bigger belief states first. The implementation is based on representing sets of states and actions as BDDs [Burch et al., 1994]. There is a small improvement in the belief space representation with BDDs: all components of a belief space consisting of one belief state only are represented by one BDD.

We carried out a comparison to the MBP planner [Bertoli et al., 2001] which uses forward-search together with some heuristics for restricting branching. MBP starts search from the initial states, and proceeds forward by taking actions, leading to another set of states, or by using observations to split the current state set to several smaller ones. Different choices of actions and observations induce a search tree.

2 Some branches might not be needed, and if the intersection of B with only one observational class is non-empty the plan could start with an action node instead of a degenerate observation node.

Some of the MBP runtimes given by Bertoli et al. [2001] are much better than given by us in this paper (specifically on the medical and ring problems) because the branching heuristic used by Bertoli et al. works well on their formulations of the benchmarks: branch only on one observable state variable if possible. We used a slightly different formulation where one many-valued observation is replaced by a small number of Boolean observations.

Runtimes of the planners are given in Table 1. The runs were on a 360 MHz Sun Sparcstation under Solaris. The problem instances are the same as in [Rintanen, 2002] where MBP was shown in almost all cases to be faster than GPT [Bonet and Geffner, 2000] and much faster than the YK¨A planner [Rintanen, 2002] on most of the problems except the blocks worlds problems with full or almost full observability. BTCS is the bomb-in-the-toilet problem with sensing. In the medical problems patients are cured by performing tests and medicating. The emptyroom problems are about navigating from an unknown location to the center of the room. The ring problems are about closing and locking all the windows of a building consisting of a cycle of rooms. BW is the blocks world with increasing number of blocks with the goal to arrange them into one stack from any initial configuration under different degrees of observability: fo is full observability, pfo is with the on relation observable, and po is partial observability (clear and ontable are observable). The problems are solvable under partial observability because moving a block only requires that it is clear and a move action is applicable no matter where the block is.

The rightmost column gives the number of iterations BBSP needs for finding a plan. MBP runtimes in some cases grow faster because it performs more search. This is most obvious in some of the problems with more observations as the number of possible ways of branching becomes astronomical. In our algorithm, the dynamic programming character of plan generation better avoids this explosion in the number of belief states to be considered.

In forward search there is an inherent conflict between A) keeping the size of plans and search trees down by not branching on all possible observations and B) branching enough to be able to find a plan. In MBP a number of heuristics is used for controlling branching, and for these benchmarks the heuristics in most cases work very well. For backward plan construction no similar conflict exists, and plan construction by a form of dynamic programming leads to effective reuse of already constructed belief states and plans, and there is no separate problem of deciding how to branch.

7 Conclusions and FutureWork

We have presented a novel framework for non-probabilistic conditional planning with partial observability, proposed a backward search algorithm for finding plans, and shown that the basic backup step of the algorithm is NP-hard. We have also demonstrated how an efficient implementation of the backup step leads to competitive planning.

For future work we propose considering the problem of finding plans with quality guarantees, for example, plans with optimal execution length, as well as planning under more general infinite-horizon executions. Also, the use of more sophisticated heuristics for driving the planning algorithm should be considered, for example the ones proposed by Rintanen [2004b] generalized to partially observable problems.