Incremental Heuristic Search for Planning with Temporally Extended Goals and Uncontrollable Events

1 Introduction

Many real-life systems, such as a power grid, a network of water pipes, or the machinery inside a factory, need to be configured such that their subsequent functioning, called the nominal behaviour, is the desired one. The problem can be formalized as an extended planning model, which handles both temporal logic goals and events, transitions that are not under the control of a planning agent. Configuration steps are represented as actions under the control of the planning agent. As soon as a configuration process completes, the system starts to function on its own (nominal behaviour). Transitions Andr´e A. Cir´e Institute of Computing University of Campinas Brazil during the nominal behaviour are modelled as uncontrollable events. The nominal behaviour is a non-deterministic process. If several events are applicable in a state, only one of them, selected at random, will occur. The planning task is to configure a system in such a way that every possible evolution (event sequence) in the nominal behaviour is consistent with a goal formula expressed in temporal logic.

∗We thank the annonymous reviewers for their feedback.

†NICTA is funded through the Australian government's baking Australia's ability initiative.

Despite its importance, the problem of reconfiguring a system to achieve a desired subsequent nominal behaviour has received little attention in the AI literature. In addressing this need, this paper presents the following main contributions.

We introduce an incremental planning algorithm based on goal decomposition, and a search-guiding heuristic that estimates the relevance of an action with respect to a goal. The relevance heuristic is fast to compute at runtime, as all the needed information can be obtained in a pre-processing step. Even though our heuristic might seem somewhat simpler than current heuristics used in classical planning, it has the advantage that it works for temporally extended goals. Adapting other heuristics from reachability goals to temporally extended goals that model the nominal behaviour is by no means a trivial task.

The incremental algorithm and the relevance heuristic are not limited to planning with temporal goals and uncontrollable events. However, in this work we restrict our attention to this planning model. Further application ideas are briefly discussed in the future work section. Our enhancements are implemented on top of an existing solver for planning with temporal goals and uncontrollable events. The basic solver is already fast, as it contains an online learning step that helps guide the planning and avoid potentially expensive (modelchecking) searches. See a brief overview in Section 3. In experiments, the enhancements presented in this paper further improve the solver speed by a convincing margin.

2 RelatedWork

The area of configuration relates to composing pre-defined parameterisable components in order to satisfy a set of constraints and some desired requirements [Mittal and Frayman, 1989; Sabin and Weigel, 1998]. AI approaches have been established as central technologies to the configuration paradigm, as they provide the appropriate formalism and efficient reasoning methods for coping with large configuration systems and complex component interactions. A distinctive feature of our work is that we consider the future evolution of the system as part of the task objective.

Planners such as TLPLAN [Bacchus and Kabanza, 2000] use temporal logic to represent search control knowledge. More recently, temporal logic has been used to express hard and soft constraints (preferences) in a plan. Examples of systems that implement this paradigms are SGPLAN [Hsu et al., 2006], MIPS [Edelkamp et al., 2006] and HPLAN-P [Baier et al., 2007]. Temporal logic has been integrated in reactive planning, where actions must respond to event occurrences (e.g., [Barbeau et al., 1998]). Differently from these contributions, the temporal information in our configuration problem refers only to transitions in the future nominal behaviour, not to actions controllable by the planning agent. Moreover, there is no goal state to reach in reactive planning, while our model has a clear notion of a goal state.

The incremental search algorithm can be seen as a generalization of planning with goal agendas [Koehler, 1998]. Goal agendas require completeness conditions that often cannot be satisfied in practice. For this reason, one of the most popular goal agenda implementations, integrated in the FF planning system [Hoffmann and Nebel, 2001], gives up on completeness. In contrast, our approach is complete, as it allows backtracking from one subproblem to another in case a (local) solution was not found.

Our incremental planning approach fits into the broader area of factored planning. The idea in factored planning is to explore loose planning domain interactions in a divide-andconquer fashion, aiming at improving the search efficiency. Recent approaches, such as [Amir and Engelhardt, 2003; Kelareva et al., 2007], are based on a representation of the subdomains into a tree-like structure that captures the interactions among them. Brafman and Domshlak [2008] formalize the concept of coupling in a multi-agent planning system, and introduce a problem decomposition method based on a partitioning of the set of actions. In contrast, we focus on an iterative decomposition of the temporally extended goal.

Partitioning an initial pool of actions into relevant and irrelevant actions is a typical preprocessing step implemented in most modern planning systems. The goal is to reduce the search effort by ignoring actions that are either provably or heuristically ruled out as irrelevant to the problem at hand. Our relevance heuristic extends this idea to get a finer distinction between relevant actions. Actions are assigned relevance scores that are useful to heuristically guide a search.

3 Background

The formal planning problem we address has been introduced in previous work [Cir´e and Botea, 2008]. We briefly reproduce the definition. A planning task is a structure 〈S, s0, ϕ, γ, A, E〉 with S a finite state space, s0 ∈ S an initial state, and ϕ a temporal logic formula that describes the goal. The function γ : S × (A ∪ E) → S models deterministic transitions in the state space. The transitions are partitioned into a set of actions A (i.e., transitions under the control of the planner), and a set of uncontrollable events E that define the nominal behavior of a system. As in STRIPS planning, each transition a has a set of preconditions pre(a), a set of add effects add(a) and a set of delete effects del(a).

The state (sub)space P(s) generated from a given state s by applying only actions is called the planning space of s. Likewise, the (sub)spaceM(s) generated from s by applying only events is called the model checking space of s.

The planning task is to find a finite sequence of actions that can be applied to s0 and that reaches a goal state. A state is a goal state if it satisfies ϕ. By definition, a state q ∈ S satisfies a temporal logic formula φ iff every event sequence that originates in q (i.e., is applicable to q) satisfies φ.

We add our contributions on top of an existing solver [Cir´e and Botea, 2008], which we'll call CB in the rest of this paper. A brief description and analysis of CB are necessary for a better understanding of the remaining sections. CB performs a global search in P(s0), the planning space of the initial state s0. To check whether a state s ∈ P(s0) is a goal, a model checking search is performed inM(s). If all event sequences that originate in s are consistent with ϕ, then s is a goal state. Otherwise, an online learning step analyzes event sequences where ϕ does not hold. A condition c is extracted that holds in s and explains the failure of ϕ along such an event sequence. All states where c holds are guaranteed not be goal states. All conditions c are disjunctively combined into the global learned information I.

A main benefit of using I is the ability to eliminate unnecessary model checking searches. There is no need to run a model checking search in a state s where I holds, as s is guaranteed not to be a goal state. As a second benefit, I can guide the global search in the planning space. ¬I can be seen as a weak form of a reachability goal, which indicates what states to avoid instead of indicating what states to reach. An additional complication raises from the fact that I evolves in time, and therefore different states could be evaluated using different reachability goals ¬I. For such reasons, ¬I is not used not to compute heuristic estimates of the distance to a goal state. It is used only to partition the planning space into helpful states and rescue states [Hoffmann and Nebel, 2001; Vidal, 2004], a process that we call helpful partitioning. As a result, the savings achieved in the global search appear to be more limited than the savings in the model checking component. Our contributions, outlined in the following sections, address this limitation.

4 Incremental Planning

The search in the planning space is decomposed into a series of subproblems. Assume the global goal is expressed as a conjunction of subformulas ϕ = ϕ1∧ϕ2 · · ·∧ϕn. A subproblem is created for each subgoal φk = ϕ1 ∧ · · · ∧ ϕk. That is, the algorithm tries to achieve the first subgoal, then achieve the first two subgoals and so on. For each k ∈ {1 . . . n}, the corresponding subproblem is a local search Sk that starts from a state that satisfies φk-1 and seeks a state that satisfies φk. (Assume φ0 = true.) A state that satisfies φk is called a local goal state for Sk. A local search Sk can be interrupted, when searching in other subproblems becomes necessary, and possibly resumed later. An interruption is performed to either advance to the next subproblem or to backtrack to the previous subproblem. The search performed in a subproblem between two consecutive interruptions is called a search round. All searches share a global closed list and a global transposition table for duplicate detection. Each subproblemSk has its own open list Ok. An open list Ok is ordered using the helpful partitioning as a main criterion and the relevance heuristic value as a tie-breaker.

Figure 1 illustrates how incremental search works. A search round for S1 is launched from s0 to seek a state where ϕ1 is satisfied. As soon as a local goal state s1g is found, S1 is interrupted. Its open list is not discarded, since this search might be resumed in the future, as shown later in this example. A search round for S2 is launched from s1g to seek a state where φ2 = ϕ1 ∧ ϕ2 is satisfied. In our example, assume that, during this search round, S2 explores the entire subtree of s1g without finding a local goal state. Note that this is equivalent to the O2 open list becoming empty. As no local goal state was found in the most recent search round, the algorithm backtracks to S1 and resumes it to seek another state that satisfies ϕ1. As soon as a new local goal state q1 g is found, it is added to O2 and S2 is resumed. Since the previous search round in S2 ended up with an empty open list, the new search round is rooted in q1 g . The process continues in this fashion until either a search round in Sn finds a solution (global success) or S1 ends up with an empty open list (no global solution). The steps of the incremental search algorithm are outlined more formally in Algorithm 1. See the explanatory comments and the previous example to follow the pseudocode more easily.

Algorithm 2 describes a search round in a subproblem. At line 2, it enumerates candidate goal states, states that could possibly satisfy the local temporal goal φk. Notice that a local search is allowed to temporarily destroy the previous goal φk-1, but in such a case it must re-achieve it in order to satisfy the stronger goal φk. Processing a candidate goal state (lines 5-11) is similar to how CB processes states in its global search. As outlined in Section 3, a model checking search is run to test whether the candidate goal state at hand is a (local) goal state indeed (line 7). The model checking search is safely skipped when possible (lines 5-6). If a model checking search returns a failure, a new online learning step is triggered

Algorithm 1 Incremental planning.

1: I ← false {initialize learned info (global variable)} 2: k ← 1 {index of the subproblem at hand} 3: s0 →O1 {initialize open list of first subproblem} 4: s10 ← s0 {root of search in first subproblem is s0} 5: while true do 6: (skg , πk ) ← SearchRoundInSubproblem(k) {return both final state and plan} 7: if πk = nil then 8: k ← k - 1 {backtrack to previous subproblem} 9: if k = 0 then 10: return no global solution 11: else 12: if k = n then 13: return π1 ; π2 ; . . . ; πn {global success} 14: else 15: skg → Ok+1 16: sk+1 0 ← skg {root of new search round is skg } 17: k ← k + 1 {move on to next subproblem}

(line 11).

To enumerate candidate goal states (line 2), the planning space P(sk0 ) is explored, where sk0 , the current local root, is set as shown in Algorithm 1, lines 4 and 16. The exploration is guided with both helpful partitioning and a new relevance heuristic, described in detail in Section 5. As in CB, helpful states have higher priority, and a rescue state is explored only when no helpful states are currently contained in the open list. This is similar to using a heuristic that can take only two possible values (one value for helpful states and another, lower-priority value for rescue states). A major limitation of helpful partitioning is that it cannot distinguish further between states that belong to the same partition. For example, all helpful states look equally good to the helpful partitioning heuristic. For this reason, CB performs blind search as long as the set of helpful states in the open list is not empty. We address this by adding a secondary ordering criterion, given by the relevance heuristic. The relevance heuristic can take many possible values, and therefore states can potentially be ordered much more precisely.

Algorithm 2 SearchRoundInSubproblem.

• 1: while true do 2: (skg , πk ) ← GetNextCandidateGoalState() {πk is the action sequence from sk0 to skg } 3: if no state skg is found then 4: return (nil, nil) {no solution} 5: if skg |= I then 6: continue {no need for a costly mod. check. round} 7: ModelChecking(skg) {check if skg satisfies φk} 8: if model checking succeeds then 9: return (skg , πk ) 10: else 11: I ← I ∨ ExtractInfo() {learning}

As the closed list, the transposition table, and the learned information I are global, the effort spent in a search round can be reduced using data acquired in previous search rounds. When expanding a state, successors that have been visited before, either in the current or in a different local search are skipped. This ensures that, despite running multiple searches in the global planning space, a state does not have to be expanded more than once.

A global I allows to eliminate more model checking searches. The global information I decomposes as I = I1 ∨ I2 ∨ . . . In, where Ik is the information learned while searching in the k-th subproblem, using φk as a local goal. States s where Ik holds are guaranteed not to satisfy φk. If the learned information were used only locally, then I would be replaced with Ik at line 5 of Algorithm 2. As I is weaker than Ik, the test at line 5 will succeed more often when I is used, skipping more model checking searches. As argued below, this choice has no negative effect on the completeness.

The incremental algorithm is sound and complete. The soundness is obvious, as a global success is reported only when a state that satisfies φn = ϕ1 ∧ · · · ∧ ϕn = ϕ is found. To better emphasize the completeness, we point out that the incremental algorithm can be seen as a global search algorithm, except for two main differences: (1) there are multiple open lists; and (2) when processing a state, the goal test is performed for a goal formula ψ that can be weaker than the global goal ϕ (i.e., ϕ = ψ ∧ α, with α an arbitrary formula). We discuss each of these differences in turn.

The concatenation of the local open lists can be seen as a global open list where pop and push operations can be performed at arbitrary, yet well-specified locations. For example, when searching in the k-th subproblem, only the portion corresponding to Ok allows insertion and extraction operations. Clearly, such a global open list affects the direction in which the planning space is explored, but has no impact on the algorithm completeness.

The goal test for each visited state s is performed at lines 5 and 7-8 in Algorithm 2. If s is ruled out as a local goal at line 5 (case 1), it means that s |= I, which is equivalent to s |= I1 ∨ I2 ∨ . . . In and, further, to (∃j) : s |= Ij. The last expression implies that s does not satisfy φj. Since ϕ = φj ∧ ϕj+1 ∧ . . . ϕn, we obtain that s does not satisfy ϕ. If s is ruled out as a local goal at lines 7-8 (case 2), we obtain that s does not satisfy φk and, following a similar argument as above, s does not satisfy ϕ. In either case, a state ruled out as a (local) goal is guaranteed not to satisfy the global goal ϕ. Therefore, we never miss out solutions and the completeness is not affected.

5 Relevance Heuristic

Besides considering only a part of the global goal, a subproblem keeps the search focused by using a heuristic measure of how relevant actions are to the subproblem at hand. Informally, this relevance heuristic gives priority to actions that guide the search towards either local goal states (exploitation) or non-goal states where learning new information can be successful (exploration). The latter scenario is useful to discover information that would speed up the rest of the solving process. The sooner such information is learned, the greater the potential savings are.

Given a subproblem, all actions are assigned numerical values as a measure of their relevance. As illustrated later in this section, smaller values correspond to more relevant actions. As no actions are ruled out as totally irrelevant, the algorithm completeness is not affected. An action can have a different relevance to two different subproblems. However, the relevance of an action to a given subproblem is fixed from one search round to another. Therefore, the relevance can be obtained in a pre-processing step.

When computing the relevance, the only subproblemspecific information given as an input parameter is a temporal formula ψ. See details about how ψ is selected for each subproblem later in this section. The relevance is computed with an iterative, Dijkstra-like procedure called RC. RC maintains a list of atoms L that is initialized to A(ψ), the set of atoms in ψ, and gets extended with action and event preconditions. Initially, each action (or event) a has its relevance value rψ(a) set to ∞. At a given iteration i, zero or more transitions (actions and events) a have their relevance rψ(a) set to i and have their preconditions added to L. For this to happen, a transition a must satisfy both following conditions: (1) rψ(a) = ∞ and (2) add(a) ∩ L ̸= ∅ or del(a)∩L1 ̸= ∅. L1 is the subset of L that contains the atoms in ψ and the preconditions of the events marked as relevant so far: L1 = A(ψ) ∪ {p|(∃e ∈ E) : rψ(e) < ∞ ∧ p ∈ pre(e)}. The process stops at an iteration iM where a fixpoint is reached. All actions a with rψ(a) = ∞ get assigned a relevance value of iM + 1.

By definition, we say that an action a impacts the formula ψ if (add(a)∪del(a))∩L1 ̸= ∅. This means that a can either change the truth value of some atoms in ψ, or it can affect the preconditions of an event sequence that can change the truth value of some atoms in ψ.

In a local search round, relevant actions set the grounds to apply actions that are even more relevant, up to the point where a relevant action impacts the formula ψ. This strategy, that guides the search towards making changes that impact the formula ψ, is more desirable than searching in an area where the changes in the current state have no relevance to the goal at hand. One main advantage is that a state where ψ holds is more likely to be achieved. Furthermore, the changes in the current state produced by actions that impact ψ can trigger more activations of the learning procedure and hence end up in having more comprehensive information available.

For the subproblemSk, the input parameter ψ given to RC is set to ϕk instead of the entire subgoal φk = φk-1 ∧ϕk . We have made this choice based of the following observations. Since φk-1 is satisfied by searching in the previous subproblems, the current search round should focus on achieving ϕk without temporarily breaking φk-1, unless this is necessary. In addition, computing the relevance with respect to a smaller formula keeps a search more focused due to the following monotonicity property. Consider two temporal formulas ψ1 and ψ2 with A(ψ1) ⊆ A(ψ2). For a given relevance value v, let Aψ(v) be the set of all actions whose relevance with respect to ψ is v. Then it can easily be shown that ⋃i≤v Aψ1 (i) ⊆ ⋃i≤v Aψ2 (i). In other words, using a smaller formula tends to build a smaller pool of actions that have a higher priority, focusing the search more effectively.

6 Experimental Results

We have implemented the incremental algorithm and the relevance heuristic in Java 1.6, on top of the CB solver [Cir´e and Botea, 2008]. The domain [Cir´e and Botea, 2008] used in experiments is available online at http://abotea.rise. anu.edu.au/factory-benchmark/. An instance has machines and repositories, as in a factory. Planning actions add and remove connections between machines and repositories, and clean machines after having used certain raw products. Uncontrollable events include the automatic transfer of raw material from repositories to machines, and the creation of final products by combining specific raw materials. The nominal behaviour (LTL goal) states that certain raw materials must never mix (otherwise the machine would break down) and that certain finite products must eventually be produced. There are 350 instances, with the number of actions and events ranging each from 50 to 150. The temporal formula size ranges from 5 to 15 conjunctive clauses. As we didn't study goal ordering heuristics yet, sub-goals are considered in the order they appear in the input file.

The experiments are peformed on an Intel 3.2 GHz machine, with 4 GB RAM. The time is set to 30 minutes for each instance. The planner stops as soon as the first solution is found or the problem is proven to have no solution. The experiments focus on a few directions. First, we compare the CB solver with the enhanced solver. Then, we analyze how each of our two main enhancements contribute to the performance. Finally, the effect on the solution quality is evaluated.

To save room, we will focus only on instances where a solution exists. For the remaining ones, there is no significant difference in performance among the planners. This is expected to happen, since the numbers of visited nodes in planning are necessarily the same for all solvers in such instances.

Figure 2 compares the original CB and the enhanced solver (CB+I+R). In very easy problems, both solvers are fast. Except for some easy problems, CB is almost never faster. As problems grow, the speed difference tends to increase, and CB+I+R rarely needs more than 10 seconds to solve a problem in this set. The largest improvement over CB exceeds two orders of magnitude. This gain in performance is a result of both visiting fewer states in the planning space, as shown in Figure 3, and performing fewer model checking rounds.

Next we analyze the speed-up gain contributed by each of the two enhancements individually. Figure 4 presents a time comparison between global search (CB) and incremental search (CB+I). Each data point corresponds to a problem instance. The x-coordinate is the time required by CB, whereas the y-coordinate corresponds to CB+I. If a data point is below the diagonal, then CB+I is faster in that instance. Most data points fall below the diagonal. The only cases when CB is faster correspond to relatively easy instances.

To illustrate the impact of the relevance heuristic, Figure 5 presents a comparison between global search (CB) and global search enhanced with the relevance heuristic (CB+R). Similarly to the behaviour of the incremental algorithm (Figure 4), the relevance heuristic significantly speeds up the solver in many cases. Most instances that are challenging for CB become quite easy with the heuristic in use.

Plan length is improved with a simple post-processing step. Even though plans are generated as a totally ordered sequence, they can be generalized to a partial ordering, with many possible total orderings. Our procedure attempts to rearrange a plan into a sequence that contains cycles (state repetitions). The action sequence between two identical states is removed. The process continues as long as possible.

Figure 6 summarizes the differences in plan length between CB and the three enhanced versions (CB+R, CB+I, CB+I+R). Given an enahced solver version Y , the percentage distance for an instance is computed as (sY - sCB)/sCB ∗ 100, where sX is the plan length obtained by planner X after postprocessing. Even though the impact on plan length varies in both directions, the enhanced planner versions tends to produce longer plans than CB. In two thirds of the cases, the percentage distance stays within the [-50, 50] range. Cases where it exceeds 100% (i.e., enhanced-planner solutions are more than double in length) are rare. We leave a better study of plan quality as future work.

7 Conclusion and Future Work

The problem of re-configuring a system, such that it subsequently functions as desired, can be formalized as a planning problem with temporal goals and uncontrollable events. This paper introduces an incremental search algorithm and a heuristic based on action relevance, two generally applicable planning enhancements. We apply these to planning with temporal goals and uncontrollable events. An existing planner designed for this model, that can achieve an impressive speed-up due to an online learning method, is used as a benchmark in experiments. Our enhancements further improve the speed considerably.

In the future, we plan to add goal ordering heuristics to the incremental search approach, aiming at further speed-up and better solution quality. The incremental algorithm and the relevance heuristic can easily be adapted to classical planning. We plan to use them in combination with existing heuristics, e.g., by using the relevance heuristic as a secondary ordering criterion, to break ties in the main heuristic.