Simple and Fast Strong Cyclic Planning for Fully-Observable Nondeterministic Planning Problems

1 Introduction

Planning is the problem of generating a plan of actions that lead us from an initial state to a goal state. While the problem of deterministic planning has been extensively investigated, the same is not true for planning in nondeterministic domains [Levesque, 2005; Kissmann & Edelkamp, 2009], where the outcomes of an action are uncertain. These nondeterministic actions contribute to the exponential growth in the search space and hence the difficulty of nondeterministic planning. This difficulty remains even in fully-observable nondeterministic (FOND) planning, where the states of the world are fully observable [Kuter et al., 2008].

We address an important yet under-investigated class of planning problems: FOND planning problems with strong cyclic solutions. The notion of strong cyclic solutions was first introduced by Cimatti et al. [2003], who, for the purpose of addressing nondeterministic planning problems, present a three-way categorization of planning solutions: weak planning solutions have a chance to achieve the goal; strong planning solutions are guaranteed to achieve the goal; and strong cyclic planning solutions have a possibility to terminate and if they terminate, then they are guaranteed to achieve the goal.

Strong cyclic planning problems have been reported hard

Vincent Ng, Farokh B. Bastani, and I-Ling Yen

Computer Science Department University of Texas at Dallas

vince@hlt.utdallas.edu,{bastani, ilyen}@utdallas.edu

to solve [Levesque, 2005]. In fact, we can get a better sense of how difficult these problems are by observing the performance of state-of-the-art planners on the FOND benchmark problems from the International Planning Competition 2008 (IPC2008): none of the participating planners can solve more than ten of the 30 problems in the Blocksworld domain [Bryce & Buffet, 2008b].

As mentioned above, a major challenge in strong cyclic planning involves dealing with a very large state space. To circumvent the state space explosion problem, a planner may plan along the directions that allow the goal to be reached quickly in a limited state space involving only the relevant states. However, an interesting but challenging problem arises: how would one know which states and search directions are relevant before the search for a solution has even begun [Magnusson & Doherty, 2008]?

To address this question, we need a basic strong cyclic planner to start with. Consequently, we first implemented an idea motivated by NDP [Kuter et al., 2008]: we iteratively expand a graph that only includes states reachable from the initial state until one solves (i.e., establishes a path to the goal from) each of its non-goal leaf states. We show for the first time that an NDP-motivated algorithm outperforms state-of-the-art planners such as MBP [Cimatti et al., 2003] and Gamer [Kissmann & Edelkamp, 2009]. 1 In particular, this "Basic" algorithm can solve all of the IPC2008 FOND problems in the Blocksworld domain. In other words, we are proposing extensions to a state-of-the-art planner.

Next, as it is common to encounter states that have been previously solved in the course of strong cyclic planning, we enhance the Basic algorithm with the capability to avoid re-exploring a solved state. Note that the idea of "state reuse" is not new: MattmŸller et al. [2010] have already implemented this idea in their solve-labeling procedure. What is new, however, is (1) we show that state reuse can be implemented with little overhead, in contrast to MattmŸller et al.'s planner, where state reuse is implemented with substantial overhead; and (2) the little overhead incurred in our implementation allows us to examine the benefits of state reuse in strong cyclic planning, specifically by determining the extent to which the efficiency of the Basic algorithm is improved via state reuse, in contrast to MattmŸller et al., who did not evaluate the benefits of state reuse. Our results suggest that state reuse can improve our state-of-the-art Basic algorithm. In contrast, even with state reuse, MattmŸller et al.'s planner cannot solve all the Blocksworld problems.

1 NDP is not publicly available, so we cannot verify whether it also outperforms MBP and Gamer.

Finally, we address the aforementioned challenge by proposing a novel heuristic, goal alternative. This heuristic aims to improve planning efficiency by heuristically identifying an alternative goal that is typically closer to a state to be solved than the overall planning goal and hence can be reached more quickly. Incorporating goal alternative into our planner brings it to the next level of performance.

The rest of the paper is organized as follows. Section 2 defines nondeterministic planning. In Section 3, we present our NDP-motivated Basic algorithm for generating strong cyclic plans. Section 4 introduces two extensions to the Basic algorithm. We present evaluation results in Section 5, discuss related work in Section 6, and conclude in Section 7.

2 Nondeterministic Planning

We introduce the definitions and notation in nondeterministic planning that we will rely on in the rest of this paper.

Definition 1. A nondeterministic planning domain is a 4-tuple ∆ = (P, S, A, Β), where P is a finite set of propositions; S ∧ 2 P is a finite set of states in the system; A is a finite set of actions; and Β : S ⋅ Aτ 2 S is the state-transition function.

Definition 2. A planning problem is a triple ∇s0, g, ∆⎜, where s0 is the initial state, g is the goal condition, and ∆ is the planning domain.

Definition 3. Given a planning problem ∇s0, g, ∆⎜ with ∆ = (P, S, A, Β), a policy is a function Μ : SΜ τA, where SΜ ∧ S is the set of states to which an action has been assigned. In other words, #s ∨SΜ : &a ∨A such that (s, a) ∨Μ. Given a state s ∨ SΜ, the applicable action in the solution is Μ(s). Therefore, Μ defines how to act under a specific state. We use SΜ(s) to denote the set of states reachable from s using Μ.

Definition 4 (taken from the rules of IPC2008 [Bryce & Buffet, 2008a]). A policy Μ is closed with respect to s iff SΜ(s) ∧ SΜ . Μ is proper with respect to s iff the goal state can be reached using Μ from all sζ ∨ SΜ(s). Μ is a valid solution to the non-deterministic problem iff Μ is closed and proper with respect to the initial state s0.

3 Basic Strong Cyclic Algorithm

In this section, we describe our NDP-motivated Basic strong cyclic algorithm and illustrate how it works via an example.

3.1 Algorithm

Our Basic strong cyclic algorithm takes as input a planning problem, ∇s0, g, ∆⎜, and outputs a policy Μ that is a valid solution to the given problem. It starts with an empty Μ and iteratively augments it with state-action pairs.

Before we describe the algorithm, it helps to realize that Μ defines (and hence can be equivalently represented as) a digraph GΜ = {VΜ , EΜ}, where VΜ = SΜ ⇒ {Β(s, Μ(s)) | s ∨ SΜ} is the set of nodes in GΜ and EΜ = {(s, sζ) | s ∨ SΜ and sζ ∨ Β(s,

Μ(s))} is the set of edges. Note that there are two types of nodes in VΜ : leaves and non-leaves. SΜ are the non-leaves, since according to Definition 3, an action has been assigned to each state in SΜ; on the other hand, {Β(s, Μ(s)) | s ∨ SΜ} subsumes the set of leaves of GΜ. Assume that GΜ(s0) represents a sub-graph of GΜ rooted at s0. Since the algorithm starts with an empty Μ, GΜ(s0) initially contains only the initial state s0. Informally, this Basic algorithm aims to augment Μ (or, equivalently, expand GΜ) so that each node in GΜ(s0) is solved (i.e., there are no non-goal leaf nodes).

Figure 1 outlines the Basic strong cyclic algorithm, which is similar in spirit to NDP [Kuter et al., 2008], but otherwise differs in various implementation details. As mentioned before, the algorithm takes as input a planning problem ∇s0, g, ∆⎜ and initializes Μ to be an empty policy (line 1). L stores the set of non-goal leaf states in GΜ(s0) (line 3), which initially contains only the initial state s0. If L is empty (line 4), the algorithm terminates and returns a solution. Note that this solution, Μ, is closed and proper (i.e., there are no non-goal leaf states and all the non-goal states can reach the goal along some paths) and is therefore a valid solution to the given planning problem. If L is not empty, a non-goal leaf state s is arbitrarily selected from L (line 5), and a SEARCH process (line 6) is created to obtain a path from state s to the overall planning goal g, which represents a weak plan. According to Kuter et al. [2008], this weak plan can be converted into an equivalent policy Μζ. In fact, the conversion is straightforward, since the path returned by SEARCH is a sequence that alternates between states and actions. Hence, if a path is found, the state-action pairs can be directly obtained from the path and incorporated into Μ (line 11).

Procedure Basic_Strong_Cyclic (∇s0, g, ∆⎜) 1. Μσ 2. loop 3. Lσ{all non-goal leaf states in GΜ(s0)} 4. if EMPTY(L) then RETURNSOL(Μ) ; endif 5. arbitrarily choose s ∨L; 6. Μζ = SEARCH(s, g, ∆); 7. if Μζ = FAILURE then 8. if s = s0 then return FAILURE; endif 9. BACKTRACK(s, Μ, GΜ(s0), ∆); 10. else 11. ΜσΜ ⇒ {(s, a) ∨Μζ| s ∠SΜ(s0)} ; 12. endif 13. endloop

However, if SEARCH fails to find a path from s to the goal, then s is a dead-end (line 7), and any paths leading to state s will be futile. In particular, if s is the initial state, then it is not possible to establish a path from the initial state to the goal state and hence there is no solution to the given planning problem (line 8). On the other hand, if s is not the initial state, we use the BACKTRACK procedure (line 9) to prune all the paths in GΜ(s0) that lead to s. Formally, #sζ ∨ SΜ(s0), a ∨ A such that s ∨Β(sζ, a), BACKTRACK will update: ΜσΜ 2 {(sζ, a)}, LσL ⇒ { sζ}, and make action a inapplicable at sζ in ∆. Therefore, the non-goal leaf set L in line 3 is dynamic in the planning process. This Basic strong cyclic algorithm is sound and complete if the SEARCH procedure is sound and complete [Kuter et al., 2008]. In our implementation of this Basic algorithm, we use FF [Hoffmann & Nebel, 2001] to find a weak plan in SEARCH.

Two implementation details deserve mention. First, while we describe the Basic algorithm in terms of how GΜ is expanded, GΜ is only a conceptual structure: all we need to keep track of are Μ and L, not GΜ. Second, deterministic actions will be preferred to nondeterministic actions if both types of actions are available to expand the current state.

3.2 An Illustrative Example

To better understand this Basic algorithm, we apply it to generate a strong cyclic plan for the following problem from the Beam domain [Cimatti et al., 2003], which is shown in Figure 2. Recall that in Beam, the goal is to have the agent move from the beginning (down0) to the end (upn) of the beam. There are three actions: Jump, Climb, and Moveback. The action Jump is nondeterministic: if the agent is at upi-1, it may successfully jump to upi or fall to downi. If it falls, it has to move all the way back to the leftmost down position (down0) via the Moveback action, after which the Climb action will bring it to up0. Here, Moveback and Climb are deterministic.

When applying the basic algorithm to this problem, L is initialized to {down0}, since the initial state is the only non-goal leaf state (line 3). Next, the algorithm selects {down0} from L (line 5), and uses SEARCH to find a weak plan wp from down0 to the goal upn (line 6), where wp = Climb(down0, up0); Jump(up0, up1); Jump(up1, up2); …; Jump(upn-1, upn). The corresponding policy Μζ = {(down0, Climb(down0, up0)), (up0, Jump(up0, up1)), …, (upn-1, Jump(upn-1, upn))} (line 6) is then merged with Μ (line 11).

Then, the algorithm proceeds to the next iteration. It begins by updating L (line 3). At this point, L = {down1, down2, …, downn}. For each non-goal leaf state downi in L, the Basic algorithm will generate a weak plan in the form of Moveback(downi, downi-1); …; Moveback(down1, down0); Climb(down0, up0); Jump(up0, up1); …; Jump (upn-1, upn). Note that many states (e.g., down0, up0, etc.) are repeatedly explored.

4 Two Extensions to the Basic Algorithm

4.1 Goal-Alternative Heuristic

Recall that the Basic algorithm needs to solve every non-goal leaf node by establishing a path from the node to the goal. For many planning problems, the goal can be far away from a non-goal leaf node. As a result, computing the heuristic distance between the two nodes needed for heuristic search could be costly, thus causing planning to be inefficient. Our first extension to the Basic algorithm, the goal alternative heuristic, aims to improve planning efficiency by identifying an alternative goal that is closer to a non-goal leaf node than the overall goal, so that a path can be established between the leaf node and this alternative goal more quickly.

Before describing the heuristic, let us motivate it using an example. Recall from the beam example that the states down1 and up1 are both generated by the nondeterministic action Jump(up0, up1). One effect of this action is the state up1, which is included in the weak plan produced by SEARCH and is called the intended effect [Kuter, 2004]. The other effect, down1, is not included in the weak plan and is called a failed effect. In the Basic algorithm, every failed effect of a nondeterministic action is inserted into L (and therefore needs to be solved at some point). We call the heuristic of setting the intended effect as the goal when searching for a weak plan for a failed effect goal alternative.

More formally, when given the planning problem ∇s, g, ∆⎜ for some s ∨L, instead of searching for g directly, a SEARCH algorithm that exploits the goal alternative heuristic will first try to search for , the intended effect of the nondeterministic action that produces s. If a weak plan (path) is found, then the SEARCH is done. Otherwise, the SEARCH will be restarted to search for the original goal g. A special case deserves mention, though. During the first iteration of the algorithm when s0 (the initial state) is the only non-goal leaf node, s0 does not have an intended effect. Consequently, SEARCH will directly search for the goal g when given the planning problem ∇s0, g, ∆⎜.

Correctness. It is easy to determine the correctness of goal alternative for SEARCH(s, g, ∆). By definition, an intended effect must be included in some path wp to the goal g, while the failed effect s is ignored in path wp. Since we have already found a path from to g, if we can find a path from s to , then the path from s to can be the solution to ∇s, g, ∆⎜. Thus, much effort is saved by avoiding repeating the search from to g. However, if no path can be found from s to , then we will resort to establishing a path from s to g.

Rationale and completeness. An intended effect and its corresponding failed effects are generated from the same nondeterministic action. Heuristically, the distance between a failed effect and the intended effect is shorter than that between a failed effect and the overall planning goal.

Since goal alternative is a heuristic, there are situations where the true distance to the intended effect is longer than that to the overall planning goal or no paths exist at all to the intended effect. In practice, however, the goal alternative heuristic works well on most of the benchmark problems.

4.2 State Reuse

Our second extension aims to enhance the Basic algorithm with the capability to avoid re-exploring a solved state. Specifically, during the SEARCH for a weak plan (line 6), if we encounter a solved state, the search stops. Since this extension can be incorporated easily into the Basic algorithm, there is almost no overhead in employing state reuse.

To see how state reuse helps improve planning efficiency, consider again our running example. Assume without loss of generality that L = {down1, down2, …, downn} and that the states are selected from L in the same order as they are listed (i.e., downi is selected before downi+1). If the Basic algorithm also adopts the goal alternative heuristic, it will initiate SEARCH(down1, up1, ∆); otherwise, it will initiate SEARCH(down1, upn, ∆). Note that both searches will result in the same weak plan that consists of the single action Moveback(down1, down0), since down0 is a solved state and hence the search stops. By the same token, for downi where 1, SEARCH will generate the weak plan consisting of only one action, Moveback(downi, downi-1). Note that the effectiveness of the state reuse extension depends slightly on the order in which the states are selected from L. For instance, if downi+1 is selected before downi, then downi cannot be reused for downi+1, even though downi can reuse the states generated by the search for downi+1. In our implementation of the state reuse extension, L is a queue, which allows the states to be chosen in the order in which they are inserted. Performance-wise, however, we found that this first-in-first-out ordering of the states offers only marginal benefits over a random ordering of the states.

5 Evaluation

In this section, we evaluate our planner, FIP (Fast Incremental Planner), which consists of the Basic algorithm augmented with the state reuse extension and the goal alternative heuristic. As baseline systems, we employ two state-of-the-art planners for strong cyclic FOND planning problems: MBP and Gamer (the winner of the FOND track at IPC2008). To gauge the usefulness of our two extensions, we also report the performance of the Basic algorithm. All problem instances belong to the benchmark domains of the IPC2008 FOND track (i.e., Blocksworld [bw], Forest, Faults, and First-responders [f-r]). Our experiments were conducted on a PC with an Intel Pentium-4 3GHz processor and 1 GB of memory. The operating system is Linux. We set the cutoff time to 1,200 seconds to prevent a planner from running indefinitely.

5.1 Results

Table 1 shows the problem coverage (i.e., the number of problems for which a strong cyclic plan was found) of four planners: MBP, Gamer, the Basic algorithm, and FIP. 2 As we can see, FIP and Basic have the same problem coverage, which is substantially higher than that of the two baselines. FIP and Basic also solve more problems than LAO* with PDB [MattmŸller et al., 2010], which can solve only 94 problems. For the notoriously difficult blocksworld benchmark problems [Bryce & Buffet, 2008b; MattmŸller et al., 2010], no existing planners can solve more than ten problems in this domain. In contrast, FIP and Basic can solve all of the 30 problems efficiently. As Basic is a state-of-the-art planner, any improvements of FIP over Basic shown below can be interpreted as improvements over the state of the art.

2 We use the original implementations of MBP and Gamer to obtain the results for these two planners. We downloaded MBP from http://mbp.fbk.eu/download/mbp_1.01.tar.gz, and obtained Gamer directly from its authors.

Table 2 includes a subset of the benchmark problems that are hard to solve, i.e., at least one planner took 15 seconds to search for a solution or at least one planner timed out on that particular problem. To ensure a fair comparison of the planners, the preprocessing time (e.g., reachability analysis) and the plan output time are excluded. In other words, we only compared the pure search time needed to find a solution. The left half of Table 2 compares the performance of the four planners. Each planner is evaluated in terms of (1) the search time (expressed in seconds) needed to solve a problem (see the columns marked 't'); and (2) the plan size (expressed in terms of the number of state-action pairs in the solution policy; see the columns marked 's'). Note that "---" indicates that the corresponding planner did not return a solution within the time limit. In terms of planning time, FIP is on average 3844 times faster than Gamer. While Basic performs better than MBP and Gamer, FIP is 8.2 times faster than Basic on average. Importantly, as the complexity of the benchmark problems increases, FIP can be more than 100 times faster than Basic. In terms of solution size, FIP's plans are 2.8 times smaller than Gamer's and 3.4 times smaller than Basic's on average. Overall, FIP's results on these benchmark problems are very impressive.

5.2 Contributions Made by the Two Extensions

To measure the contributions of our two extensions to FIP's performance, we conducted ablation experiments, where we ran two versions of FIP. Each version contains exactly one of the two extensions to the Basic algorithm. Specifically, FIP-GA-only extends Basic with only goal alternative, whereas FIP-SR-only extends Basic with only state reuse. Results of these two ablation experiments are shown in the two rightmost columns of Table 2.

First, we determine the extent to which state reuse reduces planning time and solution size. Comparing Basic and FIP-SR-only, we see that on average, the addition of state reuse allows FIP-SR-only to run 1.4 times faster than Basic, but it does not allow FIP-SR-only to generate significantly smaller plans than those of Basic. Comparing FIP and FIP-GA-only, we see that the absence of state reuse causes FIP-GA-only to run 1.2 times slower than FIP, but again FIP-GA-only's solutions have almost the same size as those of FIP. Hence, these results suggest that while state reuse plays an important role in improving planning efficiency, it does not contribute significantly to generating compact solutions.

Second, we determine the extent to which goal alternative reduces planning time and solution size. Comparing Basic and FIP-GA-only, we see that the addition of goal alternative allows FIP-GA-only to run 7.5 times faster than Basic and generate plans that are 3.4 times smaller than those of Basic. Comparing FIP and FIP-SR-only, we can see that in the absence of goal alternative, FIP-SR-only runs 8 times slower than FIP and generates solutions that are 3.4 times larger than FIP's. Therefore, these results substantiate the claim that goal alternative contributes to both faster planning time and smaller solution size.

Next, we examine how well goal alternative performs on different domains. Blocksworld and Faults are the domains where goal alternative demonstrates substantial benefits. On the other hand, the role played by goal alternative in First-responders is comparatively less significant. To see the reason, note that most of the nondeterministic actions in this domain can generate one of two possible effects: (1) Β(s, a) = sζ and sζ ♦ s, i.e., moving to another state sζ; or (2) Β(s, a) = s, i.e., remaining in the current state. However, for the failed effect of remaining in the current state (i.e., case 2), there is no need to initiate a search for it because the current state s has already been associated with the nondeterministic action a, i.e., (s, a) ∨ Μ. As a result, the first weak plan generated, which is a plan from s0 to g, is almost the final solution as most of the failed effects generated by the nondeterministic actions are already solved. Finally, using goal alternative is slightly harmful for Forest, where planning time was even a little faster when goal alternative was not used (see FIP-SR-only). However, the time difference between using and not using goal alternative is fairly minor. Hence, even when goal alternative provides the wrong direction to the search, the overhead of failing to find a path to the intended effect and resorting to the original planning goal is low.

On average, FIP-GA-only runs more than 5 times faster and creates plans that are 3.4 times smaller than FIP-SR-only. These results provide suggestive evidence that goal alternative plays a more crucial role than state reuse in improving planning efficiency and reducing plan size.

3 MBP outputs too much information to enable easy counting of the number of meaningful state-action pairs.

6 Related Work

MBP [Cimatti et al., 2003] and Gamer [Kissmann & Edelkamp, 2009] are widely considered as the best known planners that are able to deal with strong cyclic planning. MBP formulates planning as model-checking. It is built upon Binary Decision Diagrams (BDDs), which allow a compact representation and can therefore explore a large state space. It starts with a universal policy UniΜ that contains all the possible state-action pairs, and iteratively eliminates from UniΜ the state-action pairs leading to states not covered by UniΜ and state-action pairs that are dead-ends. After the iterative process terminates, if the initial state is defined in the final policy, then a plan is found. The inherent weakness of MBP is that it has to deal with a very large state space and therefore its execution time grows exponentially with the problem size [Kuter & Nau, 2004]. Gamer is also based on BDDs. It transforms a nondeterministic planning problem into a two-player turn-taking game so that tools can be applied to infer a minimized state encoding, which results in smaller BDDs than MBP. As a result, Gamer is more efficient and has better scalability than MBP. However, both MBP and Gamer use uninformed symbolic regression search, which may negatively impact planning efficiency.

NDP [Kuter et al., 2008] uses classical AI planners to solve nondeterministic problems without requiring internal modifications to the classical planners. It calls a classical planner to find a weak plan for each non-goal leaf node to the goal. It does not maintain the intermediate search results and, hence, unlike FIP, it cannot avoid exploring the same states repeatedly, resulting in wasted efforts.

MattmŸller et al. [2010] use LAO* [Hansen & Zilberstein, 2001], an informed explicit state search algorithm on an AND/OR graph, in combination with pattern database heuristics [Edelkamp, 2001] to generate strong cyclic solutions. LAO* explicitly constructs a graph during planning, but maintaining this graph incurs much overhead because determining whether a state is solved and checking whether a solution is found are very expensive operations. More specifically, the solve labeling procedure in MattmŸller et al. [2010] is a nested fixed point computation, in which an outer loop and two inner nested loops compute a set of nodes backwardly reachable from the goal. As a result, this method does not scale very well.

7 Conclusions

We have examined an important class of nondeterministic planning problems: FOND problems with strong cyclic solutions. Our work makes two contributions to planning research. First, we showed how the state reuse extension can help avoid re-exploring a solved state with little overhead and evaluated for the first time the benefits of state reuse for strong cyclic FOND planning problems. Second, we propose a novel heuristic, goal alternative, which aims to improve planning efficiency by heuristically identifying an alternative goal that is typically closer to the current state and can therefore be expected to be reached more quickly. Experimental results on the benchmark domains of the IPC2008 FOND track show that our planner, FIP, significantly outperforms state-of-the-art planners in terms of problem coverage, CPU time, and solution size. These results suggest that our two extensions to the Basic algorithm are both very effective.