Domain-Independent, Automatic Partitioning for Probabilistic Planning

1 Introduction

AI researchers typically formulate planning under uncertainty problems using a Markov Decision Process (MDP) [Bresina et al., 2002; Aberdeen et al., 2004]. Popular algorithms to solve MDPs, like value iteration (VI), RTDP, LAO*, etc., are all based on dynamic programming [Bellman, 1957; Barto et al., 1995; Hansen and Zilberstein, 2001]. While effective in small settings, all these algorithms have memory requirements polynomial in the size of the (reachable) state space, which is exponential in the number of domain features. This greatly constrains the size of the problems that can be solved, making existing techniques practically useless for real planning problems.

Recent progress for scaling up dynamic programming has exploited external memory to alleviate this memory bottleneck. EMVI [Edelkamp et al., 2007] associates values with edges instead of nodes. Using a clever sorting routine it ensures that all the backups of a VI can be accomplished by a scan on two contiguous files from the disk. EMVI is a theoretically clever algorithm, but was outperformed in practice by PEMVI [Dai et al., 2008]. PEMVI divides the states into blocks and performs (one or more) backups on all states in a block before moving onto the next ones. All information required for backing blocks is stored on the disk and is transferred on demand in a piecemeal fashion. This simple idea was very effective in practice and significantly outperformed EMVI, but, with one caveat - PEMVI required a human to specify the partitioning of the state space. Human specified partitioning is a far cry from the vision of automated planning.

In this paper, we develop and implement automatic partitioning on top of PEMVI. We first build a theory of XOR groups [Edelkamp and Helmert, 1999] and construct necessary and sufficient conditions for a set of fluents to be a valid XOR group. We use static domain analysis to identify XOR groups present in the domain and search over a partition space created by these XOR groups yielding a suitable partition. We evaluate three criteria (viz. coherence, locality and balance) for this search, and conclude that a combination of two yields the best results. We also observe that our automatic partitioning engine constructs better partitions than the manual partitioning constructed in our previous work [Dai et al., 2008], due to which we are able to solve problems larger than ones that were previously reported. We release a fully automated, domain-independent, optimal MDP solver that is able to solve many large problems across domains from the international planning competition 2006 [ipc, 2006].

2 Background

A Markov decision process is defined as a four-tuple 〈S, A, T, C〉, where S is the state space, A represents the set of all applicable actions, T is the transition matrix describing the domain dynamics, and C denotes the cost of actions. A probabilistic planning problem is typically described by a factored MDP, which specifies F - the set of domain features. The state space S can be calculated as the set of value assignments to the features in F.

The agent executes its actions in discrete time steps called stages. At each stage, the system is in one distinct state s. The agent can pick from any action a ∈ A, incurring a cost of C(s, a). The action takes the system to a new state s′ stochastically, with probability Ta(s′ |s).

The horizon of an MDP is the number of stages for which costs are accumulated. We are interested in a special set of MDPs called stochastic shortest path problems. The horizon is indefinite and the costs are accumulated with no discount. There are a set of sink goal states G ⊆ S, reaching which terminates the execution. To solve the MDP we need to find an optimal policy (S → A), a probabilistic execution plan that reaches a goal state with the minimum expected cost. We evaluate a policy π by a value function. Any optimal policy must satisfy the following system of Bellman equations:

The optimal policy, thus, is extracted from the value function:π∗

2.1 Dynamic Programming

Most popular MDP algorithms are based on dynamic programming. Its usefulness was first proved by a simple yet powerful algorithm named value iteration [Bellman, 1957]. Value iteration first initializes the value function arbitrarily. Then, the values are updated using an operator called Bellman backup to create successively better approximations. Value iteration stops updating when the value function converges.

Value iteration (and other modern algorithms like LAO*, labeled RTDP, etc.) converges to the optimal value function in time polynomial in the size of the states [Littman et al., 1995], but the model of an MDP (transition and value function) must be present in the memory before computation is applicable. This constraint prohibits these algorithms from solving problems whose models do not fit in the memory. This precludes most real world problems, since they are too large to be optimally solvable.

2.2 External-Memory Dynamic Programming

Recently, researchers have developed external memory algorithms that use disk to store the large MDP models. External memory value iteration (EMVI) [Edelkamp et al., 2007] is the first such MDP algorithm. It associates values with edges instead of nodes. Using a clever sorting routine it ensures that all the backups of a VI can be accomplished by a scan on two contiguous files from the disk. EMVI is able to solve larger problems than classical dynamic programming, albeit, somewhat slowly.

Partitioned external memory value iteration (PEMVI) [Dai et al., 2008] is a much faster external memory algorithm. It first partitions the state space into non-overlapping partition blocks, and then iteratively backs up states per block till convergence. PEMVI is able to make efficient use of I/O by backing up a state more than once per I/O iteration, so it converges faster than EMVI by a magnitude. However, PEMVI assumes a given valid partition, i.e., one in which each partition block can be backed up in memory. In this work, the partitions are designed with human input by applying the manually chosen XOR constraints in a domain dependent way. Specifying a partition of the state space is added burden on the domain designer and takes away from the vision of AI planning. In this paper, we focus on generating the partitions automatically making the overall planner completely automated and capable of solving large problems using additional storage in the external memory.

2.3 State Abstraction in Deterministic Domains

Edelkamp & Helmert [1999] use automatically-constructed domain invariants to produce a compact encoding 1 of the problem. These invariants were used by Zhou & Hansen [2006] as XOR groups to define state abstractions for structured duplicate detection in external-memory search algorithms. Zhou & Hansen also defined the locality heuristic as a criterion for choosing a suitable state abstraction. This paper generalizes the notion of XOR groups, adapts them to probabilistic domains, and investigates additional partitioning heuristics, which are more relevant to probabilistic domains.

3 A Theory of XORGroups

While there is an exponential number of ways to partition the state space, we focus on structurally meaningful partitions, which can be represented compactly. We use the key notion of XOR groups developed by Zhou and Hansen, but, generalize it as follows: A set of formulae forms an XOR group if exactly one formula in the set is true in any state reachable from the start state. For example, for any formula ϕ, the set {ϕ, ¬ϕ} represents an XOR group. For another example consider the Explosive-Blocksworld domain with two block constants, b1 and b2. The fact that either a block (say b1) is clear or else it must have another block on it can be represented as an XOR group: {clear(b1), on(b1, b1), on(b2, b1)}. Sometimes it is clearer to think of an XOR group as a logical formula. We can write this XOR group logically as clear(b1) ⊕ on(b1, b1) ⊕ on(b2, b1). It is easy to see that an XOR group compactly represents a partition of the state space, where each partition block contains all the states satisfying a single formula (exclusive disjunct) in the group.

Our definition of an XOR-group is more general than the original one by Zhou and Hansen - they only allowed positive literals in an XOR group. On the other hand we accept any complex formula in our definition of XOR-groups.

In order to achieve a compact representation, it is convenient to specify XOR groups using first-order logic. This is facilitated by introducing some syntactic sugar, an exclusive quantifier ∃1, to the logic. Intuitively, ∃1x ϕ(x) means that there exists exactly one constant that satisfies ϕ(x), that is, exclusively quantified is represented as ∃1x. With this notation, a large XOR group can be represented by a short logical formula. For example, if there were many blocks in the domain, then the XOR group shown previously would get quite long, but this notation allows a compact specification:

Note that this group is specific to the specific block, b1, but there is a similar group for b2: {clear(b2), on(b1, b2), on(b2, b2)}. These two XOR

1 Encoding here refers to converting the PDDL description of the domain to an explicit state representation.

groups can be represented, by adding a new, universally quantified, variable b′ :

If we ground this formula (assuming a universe of two blocks), we get a formula, whose conjuncts corresponds to an XOR group each.

(clear(b1) ⊕ on(b1, b1) ⊕ on(b2, b1)) ∧ (clear(b2) ⊕ on(b1, b2) ⊕ on(b2, b2))

We define a set of formulae F balanced under an action a if in each of its probabilistic outcomes, a's effects either (i) do not change the truth value of any formula in F or (ii) make exactly one of the formulae in F true, while making another (previously true) formula in F false.

Necessary and Sufficient Conditions: A set of grounded formulae F forms a XOR group if and only if F satisfies the following two conditions:

1. Exactly one ϕ ∈ F is satisfied in the initial state.
2. For every ground action a that is executable in the reachable part of the state space, F is balanced under a.

These constraints help us efficiently evaluate whether a candidate set of formulae is indeed an XOR group or not.

4 Algorithm

Our planning system contains several pieces, shown in Figure 1. First, it performs static analysis of the domain and identifies the various XOR groups present in it. The externalmemory reachability analysis detects irrelevant parts of the state space. Additionally, it samples a subset of the reachable space, which facilitates the next phase (searching for a partition) by estimating the sizes of various partitions. Then it searches in the space of partitions, represented using the XOR groups, to construct a valid partition. Next, the encoding module scans the reachable state space and computes a much more compact string representation for each state based on the XOR groups. It also prepares the data structures necessary for PEMVI, such as distributing all states into disk files, one for each partition block, etc. Finally we apply PEMVI over this encoding of states and the chosen partition.

4.1 Domain Analysis

Our original definition of XOR groups is very general, but, searching over such a general space of formulae may not be practical, so we add two constraints in our search for XOR groups: 1) All formulae in an XOR group must be literals (instead of a general Boolean formula). 2) all terms in a

Algorithm 1 Xorify(P)

• 1: Input: P = 〈p1, p2, . . . , pk〉 (a list of predicates)
• 2: // compute candidate XORs
• 3: XF ← ∅
• 4: A← {aij}|i=1..k where aij is j th argument of pi
• 5: C ← set of all possible type-sensitive equivalence relations of A (Algo 2)
• 6: for all equivalence relations c ∈ C do
• 7: ϕ ← XOR of all predicates in P such that two arguments are represented by the same variable name iff they lie in the same equivalence class ∈ c
• 8: add ϕ to XF

9: 10: for all ϕ ∈ XF do 11: AA← set of all arguments in ϕ 12: open← {emptyset} 13: while open is not empty do 14: delete the first set, E, from open 15: if (∀x∈Ex)(∃1y∈AA-E y)[ϕ] is an XOR formula then 16: output (∀x∈Ex)(∃1y∈AA-E y)[ϕ] 17: goto line 10 18: for all a ∈ AA - E do 19: E ′ ← E ∪ {a} 20: if E ′ /∈ open then 21: append E ′ at the end of open

first-order XOR formula must either be universally quantified or exclusively quantified (i.e., they can't be constants). In theory, these assumptions may result in missing some XOR groups, but, our experiments demonstrate that our method yields useful XOR groups for all planning benchmarks. Similar results were reported in [Zhou and Hansen, 2006].

We identify XOR groups by performing static domain analysis - first finding first-order XOR formulae and later grounding them to construct the final set. In the process we use a new term: We say a set of literals, P, is fully balanced (balanced for short) if it is balanced under all ground actions. This is faster to check than the necessary XOR conditions which quantify over executable actions. A balanced set of literals is minimal if no proper subset is also balanced. We denote the set of arguments of a predicate p by args(p).

Finding First-Order XOR Groups: At the highest level, our algorithm searches through syntactic XOR formulae in first-order logic and looks for candidates that satisfy the XOR conditions of the previous section. Suppose we want to construct an XOR formula such that each literal corresponds to a predicate from the list P. Note that each predicate ∈ P may be in its positive or negated form and two predicates ∈ P may be the same 2 . Such a P is the input to the Algorithm 1.

Algorithm 1 first computes all possible variable bindings (Lines 3-8). For example, suppose P = 〈clear(·), on(·, ·)〉. Then the three arguments in P could be bound to the same variable name: clear(x)⊕on(x, x); all different variable names: clear(x)⊕on(y, z) or the two intermediate cases. All such cases will lead to different final XOR formulae. To compute this we consider all possible type-sensitive equivalence relations for the set of arguments and assign the same variable name if two arguments lie in the same equivalence class

2 This is necessary in searching for XOR groups of the form ∀b[clear(b) ⊕ ¬clear(b)]

Algorithm 2 Compute Type-Sensitive Equivalence Relation

1: Input: A (a set of arguments) k (the number of types) 2: distribute arguments by type into sets A1, . . . ,Ak. 3: for each type ti do 4: Ri ←EquivReln(Ai) 5: return the Cartesian product of R1, . . . ,Rk 6: 7: Function EquivReln(B) 8: if B = emptyset then 9: return a singleton that contains emptyset 10: else 11: x ← last element in B 12: R←EquivReln(B -{x}) 13: Rnew ← emptyset 14: for every relation R ∈ R do 15: for every equivalence class D ∈ R do 16: Dnew ← D ∪ {x} 17: add ((R ∪ {Dnew}) - D) to Rnew 18: add R ∪ {{x}} to Rnew 19: return Rnew

(line 7). We define a type-sensitive equivalence relations of a set of arguments A to be a set of non-empty, non-overlapping subsets of arguments whose union is A, with the constraint that elements in one equivalence class must have the same type. For example, if A = {b1, b2, c1, c2} (two blocks and two colors) then type sensitive equivalence relation of A is {{b1, b2}, {c1, c2}}, {{b1}, {b2}, {c1, c2}}, {{b1, b2}, {c1}, {c2}}, {{b1}, {b2}, {c1}, {c2}}. Algorithm 2 outlines a method to compute this set.

Given this candidate XOR formula, ϕ, whose variables are not quantified so far, we wish to find a set, E, from all arguments of ϕ, such that 1) when all arguments in E are universally quantified and all arguments in args(ϕ) - E are exclusively quantified, a correct XOR group results; and 2) no proper subset of E meets condition 1. For all E that meet condition 1 we say E xorifies φ. We call a set that meets both condition 1 and 2 a minimal xorifier.

To find this set of arguments we perform a breadth-first search over all subsets of args(ϕ), starting from the empty set (lines 12-21 in Algo 1). Expanding a node adds another argument to the current node. The goal is a minimal set E that xorifies ϕ. Running this algorithm on different P yields several first order XOR formulae. Finally, we ground these to get the concrete XOR groups.

As an illustration, consider a modified ExplosiveBlocksworld, where blocks are colored. Consider a world with two pigment constants, red and blue, and an initial state, which specifies that initially b1 and b2 are red and blue respectively. The only action to modify a block's color is paint:

(:action paint :parameters (?b - block ?c ?nc - pigment) :precondition (color ?b ?c) :effect (and (color ?b ?nc) (not (color ?b ?c))))

To find the minimal set using just the predicate color(b, c) we start the search with E = ∅ (line 12). ∅ does not xorify color, since the XOR formula ∃1b∃1c [color(b, c)] does not hold, because, both blocks have some color in the initial state. The algorithm then looks for sets of size 1. Consider E = {c}, or equivalently an XOR group ∀c∃1b [color(b, c)]. This means there exists exactly one block of each color. Although the initial state satisfies this condition, the paint action may violate it. So it does not xorify color. But E = {b} xorifies color, since it means every block must have exactly one color. This minimal xorifier leads to two ground xor groups: color(b1, red) ⊕ color(b1, blue) and color(b2, red) ⊕ color(b2, blue).

Our algorithm for computing XOR groups has marked differences from the previous version by Edelkamp & Helmert. We call their version EH algorithm. In particular, EH algorithm (1) did not handle any XOR formulae with negated predicates, and (2) required exactly one argument in the whole formula to be exclusively quantified, hence they cannot infer properties like ∀x[loves(x, x) ⊕ depressed(x)], or ∀pkg∃1truck∃1city[on(pkg, truck) ⊕ in(pkg, city)]. We implemented an extension of algorithm that additionally finds simple negated XOR groups like ∀b[clear(b) ⊕ ¬clear(b)].

4.2 External-Memory Reachability Analysis

Often the state space reachable from the start state and the state space expressed by the PPDDL description are of extremely varied sizes. For example, the Blocksworld problems have orders of magnitude more unreachable states than reachable ones, because the PPDDL description allows for several blocks on top of a block, whereas the semantics of the domain given the typical initial states does not. We perform reachability analysis to focus computation only on the relevant subset of the states. Since the state spaces can be huge we implement an external memory version, which is a layered BFS that uses delayed duplicate detection [Korf, 2003]. Our optimizations enable the search algorithm to switch automatically between the in-memory (when a search frontier can fit in the memory) algorithm, and the external-memory version.

Sampling: Additionally, we build a random subset of the reachable state space by sampling each state with a uniform probability x. This subset helps us in estimating the sizes of partition blocks and its transitions in the next phase.

4.3 Search for Partitions

Recall that a valid partition is one in which partition blocks can be backed up in memory. In this phase we search for a valid partition by successively applying the XOR groups computed by domain analysis.

Choosing a good partition is vital for PEMVI algorithm, since it can massively save on the computation time, as well as memory requirements. In our previous work, we proposed two desirable heuristics that can be used to assess the quality of a partition - locality and coherence [Dai et al., 2008]. Coherence favors a partition whose total percentage of intrablock state transitions is the greatest among all transitions, and therefore optimizes the information flow to achieve faster convergence. Locality prefers a partition that has the lower number of successor blocks, so it makes loading successor blocks less I/O costly. In this paper we define a new heuristic, balance, which prioritizes a partition that shrinks the memory requirement of PEMVI most significantly, thus it can help reach a valid partition as early as possible.

However, evaluating these heuristics requires computing these criteria, e.g., percentage of intra-block transitions, for the reachable space, an endeavor too ambitious to undertake. We exploit our sampled state space to make this tractable. With the (unknown) partition block size l, the size of the sampled space in that block follows a Binomial distribution(l, x) under some reasonable assumptions. If sampling generates a subspace of size r, then l follows a negative binomial distribution(r, x), with mean μ = r/x and standard deviation σ = √r(1 -x)/x. This distribution, according to the central limit theorem [Rice, 2001], is approximately Normal. The size l has a very slight probability (≈ 0.1%) of being greater than μ + 3σ. We use this number to be the upper bound while estimating l. We estimate the number of transitions into a block and other criteria in a similar fashion.

Given a heuristic (any of these above), ideally, we will enumerate all partitions and evaluate them based on the heuristic value to get the best partition. Unfortunately, if there are n XOR groups in the domain, the total number of possible partitions is 2n . Moreover, evaluating a partition, even though made feasible by the use of sampled state space, is still quite time-consuming (see Section 5 for details). For this reason, we trade off optimality for time and use greedy search by picking the XOR group that has the best heuristic estimate at each partitioning step. In the experiments section we empirically compare these three heuristics and develop a strategy to maximize the algorithm performance.

Sometimes the partitioning process itself exhausts the available memory. The block transition table is a table that represents the successor block relations between all partition blocks. In our implementation, we represent the table as an adjacency list, and store it in memory. When the algorithm generates too many partition blocks then the block transition table overflows and we terminate the algorithm with failure.

4.4 Encoding

Based on our set of XOR groups we can encode the state space into a compact representation. For ease of illustration we describe the case when all domain features are Boolean. In such a case a naive encoding will use a bit-string whose length equals the number of the features. To reduce this further we can define a single multi-valued feature for an XOR group of k literals and the total number of bits needed for that feature will be log2 k and we will save on k - log2 k bits. In our encoding algorithm, we define these features greedily for each XOR group and remove all the participating ground predicates. We continue this process until all XOR groups are exhausted. We are left with a set of multi-valued features that we newly defined and some Boolean features (for the original ground predicates that didn't participate in any XOR group). We use this representation for a compact encoding of a state.

5 Experiments

We address the following questions: (1) How do the different heuristics (viz. locality, coherence and balance) compare with each other? (2) Does our general algorithm for finding XOR groups produce better XOR groups compare to EH algorithm? Does our algorithm scale? (3) How does the quality of automatically-generated partitions compare to those that are manually generated? (4) Does automatic partitioning

Algorithm 3 Search for Partition

1: input: S (state space), R (the set of XOR groups) 2: // Ptn means a partition, bk means a partition block 3: Ptn← {bk|bk = S} 4: backtrack ← false 5: d ← 0 6: while Ptn is not valid do 7: if backtrack = false then 8: pick a greedy r ∈ R using coherence heuristic 9: d ← d + 1 10: else 11: pick a greedy r ∈ R using balance heuristic 12: modify Ptn by partitioning Ptn using r 13: if block transition table overflows then 14: backtrack ← true 15: if d ≥ 0 then 16: d ← d - 1 17: backtrack to partition depth d AND goto 6 18: else 19: return fail

• 20: return Ptn

scale to large problems in IPC domains? (5) Does the use of simple-negated XOR groups benefit the partitioning process?

We implemented our automatic partitioning algorithms and PEMVI using C++. We evaluated our planner using an Intel(R) Core(TM)2 CPU processor with 2GB RAM and a 60GB SATA II (300MB/s) hard disk.

Comparing Heuristics: We first performed control experiments in order to determine which of locality, coherence and balance is the best heuristic. Using a suite of six problems from three domains, we ran PEMVI with partitions generated by following each heuristic's guidance. We measured overall running time (partition generation + policy construction) with a cut-off of 10 hours. Figure 2 shows the time taken on a log scale. Apart from the smallest problem, coherence outperformed the other heuristics, which often failed to generate partitions that could solve the problem within the time limit.

Moreover, when we tested on even larger ExplosiveBlocksworld problems, we observed that none of the heuristics enabled PEMVI to generate a solution within 10 hours. However, balance seemed to get closest in the sense that it was able to generate a valid partition (just not one that could be solved within the limit). In contrast, the other heuristics exhausted memory while just trying to find a valid heuristic.

These and other observations suggest a hybrid strategy. We partition greedily using the coherence heuristic, until either we find a valid partition or we reach a state where further partitioning will cause overflow of the block transition table. In this latter case we backtrack, trying the balance heuristic at the previous decision points. We use this hybrid scheme in all further experiments (Algorithm 3).

Comparing domain analysis algorithms: We now compare the performance of our new algorithm for finding XOR formulae (Algorithm 1) with the EH algorithm. For all the problems that we tried, both algorithm ran very fast (finished in less than 1 second). As expected, the new algorithm consistently found a superset of XOR formulae. Table 1 shows that our algorithm finds additional XOR formulae in 50% of the domains. With the new set of XOR formulae, PEMVI managed to solve Zeno p5 in 23% of the time, with 53% of memory compared to using the smaller set of XOR formulae found by the EH algorithm.

Quality of Automatic Partitioning: We now compare the partition generated by our algorithm with the Explosive Blocksworld partition devised manually in our previous work [Dai et al., 2008]. That partition recursively applied a grounding of the ∃1b [clear(b′ )⊕on(b, b′ )] XOR group, using a new block b′ at each level.

In contrast, automatic partitioning starts by picking the same XOR group, but at the next level it picks a group that differentiates different locations of b′ , namely ∃1b [holding(b′ ) ⊕ on(b′ , b)] (whether b′ is in hand, or on top of another block). By considering these two related XOR groups as a pair, the resulting partition gets a better performance, as we show below.

We compare the two partition schemes by averaging over four 7-block Explosive Blocksworld problems, whose average number of reachable states is 9,649,979. Table 2 compares the performance of the two partitioning approaches, which each found a valid partition at level 2 on every problem. We observe that on average automatic partitioning solves problems slightly faster (5.5%) and with slight less memory (6.4%). When tested on even larger (8- and 9-block) problems, manual partitioning failed completely, overflowing its block transition table. In contrast, automatic partitioning solved these problems handily (Table 3).

Scalability: We evaluated our system on problems from 8 domains from IPC-06 [ipc, 2006]. Since problems in Drive and Unrolled-Drive are extremely small, we do not report those results. Table 3 lists some of the large problems solved by our algorithm. 3 For each problem, we also report the size of its reachable state space, time spent performing reachability and partitioning, I/O time and CPU time consumed by PEMVI, as well as the planner's peak memory usage. As an external memory algorithm, the convergence of PEMVI on these problems is relatively fast (usually within a couple of hours). This shows the great power of our automated techniques in solving large probabilistic planning problems.

3 The ones with * are not original IPC problems

Simple-Negated XOR Groups: We also find that very few XOR groups are present in some domains. For them we decided to use simple-negated XOR groups, of the form {l, ¬l}, where l is a grounded literal. This modification especially helps in Blocksworld and Tireworld, since they have very few XOR groups with complex structure.

Results show that, for the four Tireworld problems we tried, using simple-negated XOR groups lead to faster convergence (average 50.0% speedup, but most useful on small problems). For the Blocksworld domain, failure to consider simple-negated groups does not slow convergence on small problems (e.g., 5-blocks). However, on larger problems (e.g. 6-blocks and larger), we were unable to find a solution without using simple-negated groups. We conclude that simplenegated groups is very important in generating a partition, especially when the non-trivial XOR groups are too sparse. So, overall their use makes the algorithm more robust to a wide variety of domains.

6 RelatedWork

Automatic partitioning in logically-specified planning domains was introduced by Zhou and Hansen [2006]. They use a partition to reduce the size of the states that are checked for finding duplicate states during systematic, external-memory searches. Static partitioning over non-logical probabilistic domains was used by Wingate and Seppi [2005]. They manually form a partition and solve each partition block iteratively, in order to expedite classical dynamic programming.

Our idea of automatic partitioning is related to variable resolution [Moore and Atkeson, 1995; Dean et al., 1997; Munos and Moore, 2000; 2002]. Variable resolution tries to automatically and dynamically group similar states as an abstract state, solves the abstract MDP, and uses the solution to the abstract MDP as an approximation. However, we aim to solve the original MDP optimally, and thus our approach differs from them in a fundamental way. Our emphasis is on creating a partition that minimizes the total time (I/O + backup) for optimal policy construction whereas they aim at partitions that achieves better approximation. However, dynamic partitioning is not I/O efficient, and does not guarantee that the abstract MDP fits in the memory.

7 Limitations and FutureWork

PEMVI can be very sensitive to the quality of partition. For instance, consider Figure 3, in which s1 and s2 form a cycle with probability 0.9. Dynamic programming may need many iterations of backups for computing the correct values for both states. If s1 and s2 end up in two different partition blocks, this translates into a large number of I/O iterations, which can be very costly! Note that if the two states are in the same block it is not a problem, since PEMVI already performs multiple backups within a block in each I/O iteration. In our experiments, we found that cycles of this type are pervasive especially in Explosive-Blocksworld problems. In practice, our automatic partitioning algorithm sometimes falls into traps and finds a partition that cannot be solved. In the future, we plan to resolve this issue by exploring dynamic repartitioning. If one partition fails, i.e., is taking a long time to converge, we can detect the cycles responsible for slow convergence and generate a new valid partition in which the states on those cycles are assigned to the same partition block.

8 Conclusions

This paper makes several contributions. First, we demonstrate the practicality of automatically partitioning probabilistic planning problems by implementing a completely autonomous, domain-independent MDP solver, which can optimally handle as yet unsolved problems in several IPC-06 domains.

Second, our algorithm uses a novel approach for generating XOR groups, which generalizes those of [Edelkamp and Helmert, 1999; Zhou and Hansen, 2006].

Third, we propose a new heuristic, balance, for guiding the search for partitions and introduce a sampling method for its efficient computation.

Finally, we present several experiments: comparing three partitioning heuristics, comparing our algorithm to compute XOR groups with previous work, showing that automatic partitioning can beat manual methods, and demonstrating the utility of simple-negated groups.

Acknowledgments

This work was supported by Office of Naval Research grant N00014-06-1-0147 and the WRF / TJ Cable Professorship. We thank the three anonymous reviewers and Andrey Kolobov for their suggestions on improving the paper.