We explore a deductive approach to planning. We have developed a Theorem Proving Lifted Heuristic (TPLH) planner that searches for a plan in a tree of situations using the A* search algorithm. It is controlled by a delete relaxation-based domain independent heuristic. First, we compare a baseline version of TPLH with Fast Downward (FD) and Best First Width Search (BFWS) planners over several standard benchmarks. Since our implementation is not optimized, TPLH is slower than FD and BFWS. But it explores fewer states, sometimes it computes shorter plans, and this results in a comparable IPC scores for several domains. Next, we consider another version of TPLH that discards previously visited states, and that can do greedy search and/or use two priority queues. We determine experimentally the best configuration of the second version of TPLH that outperforms the baseline version. The IPC scores based on plan length and the number of visits are used as metrics for comparison. Thus, we show that the study of deductive lifted heuristic planning is a productive research direction.
provides heuristic control over resolution, but in [
We start with a review of SC, then we explain how our TPLH planner can be developed
from the first principles as a search over the situation tree. To facilitate an implementation, our
TPLH planner is implemented in PROLOG under the usual CWA and DCA. A more general
implementation is left to future work. We present an experimental comparison of the baseline
version of TPLH with the recent version of FastDownward (FD) planner [
We assume that the readers are familiar with PDDL [
The situation calculus (SC) is a logical approach to representation and reasoning about actions
and their effects. It was introduced in [25, 26] to capture common sense reasoning about the
actions and events that can change properties of the world and mental states of the agents. SC was
refined by Reiter [ 33, 35] who introduced the Basic Action Theory (BAT). Unlike the notion of
state that is common in model-based planning, SC relies on situation, namely a sequence of actions,
which is a concise symbolic representation and a convenient proxy for the state in the cases when
all actions are deterministic [
The basic action theory (BAT) is the conjunction of the following classes of axioms:
= Σ ∧ ∧ ∧ ∧ 0 . We use examples from the BlocksWorld (BW) domain [
ap is a set of action precondition axioms of the form ∀∀¯. ((¯), ) ↔ Π(¯, ), where (, ) is a special predicate meaning that an action is possible in situation , Π(¯, ) is a formula uniform in , and is an n-ary action function. In most planning benchmarks, the formula Π is simply a conjunction of fluent literals and possibly negations of equality. We consider a version of BW, where there are three actions: move-b-to-b(, , ), move a block from a block to another block , move-b-to-t(, ), move a block from a block to the table, move-t-to-b(, ), move a block from the table to a block . (move-b-to-b(,,), ) ↔ (,) ∧ (,) ∧ (, , ) ∧ ̸= . (move-b-to-t(, ), ) ↔ (, ) ∧ (, , ). (move-t-to-b(, ), ) ↔ (, ) ∧ (, ) ∧ (, ).
Let ss be a set of the successor state axioms (SSA):
(¯, (,)) ↔ + (¯, ,) ∨ (¯, ) ∧ ¬ − (¯, ,), where ¯ is a tuple of object arguments of the fluent , and each of the ’s is a disjunction of uniform formulas [∃¯]. = (¯) ∧ (¯, ¯, ),where (¯) is an action with a tuple ¯ of object arguments, (¯, ¯, ) is a context condition, and ¯ ⊆ ¯ are optional object arguments. It may be that ¯ ⊂ ¯.
If ¯ in an action function (¯) does not include any variables, then there is no optional ∃¯ quantifier. If not all variables from ¯ are included in ¯, then it is said that (¯) has a global effect, since the fluent has at least one ∀-quantified object argument not included in ¯. Therefore, experiences changes beyond the objects explicitly named in (¯). For example, if a truck drives from one location to another, and driving action does not mention any boxes loaded on the truck, then the location of all loaded boxes change. When the tuple of action arguments ¯ contains all fluent arguments ¯, and possibly contains ¯, we say that the action (¯) has a local effect. A BAT is called a local-effect BAT if all of its actions have only local effects. In a local-effect action theory, each action can change values of fluents only for objects explicitly named as arguments of the action. In our implementation, we focus on a simple class of local-effect BAT, where SSAs have no context conditions. However, since [27], it is common to consider a broader class of SSAs with conditional effects that depend on contexts (¯, ¯, ). Often, contexts are quantifier-free formulas, and then SSA is called essentially quantifier-free . In BW, we consider fluents (, ), meaning block has no blocks on top of it in situation , (, , ), meaning block is on block in situation , (, ), meaning block is on the table in situation . The following SSAs are local-effect (with implicit ∀, ∀, ∀, ∀): (, (, )) ↔∃,( = move-b-to-b(,,))∨∃( = move-b-to-t(,))∨ (, ) ∧ ¬∃, ( = move-b-to-b(, , )) ∧ ¬∃( = move-t-to-b(, )), (, , (, )) ↔∃( = move-b-to-b(, , ))∨∃( = move-t-to-b(, )∨ (, , ) ∧ ¬∃( = move-b-to-b(, , )) ∧ ¬∃( = move-b-to-t(, )), (, (, )) ↔ ∃( = move-b-to-t(, ))∨
(, ) ∧ ¬∃( = move-t-to-b(, )).
Note that each SSA mentions which actions have a (positive) add-effect (i.e., make the lfuent true in the resulting situation), and which actions have a (negative) delete-effect (i.e., make the fluent false in the resulting situation). Heuristics based on the so-called delete relaxation can ignore those parts of the SSA which are related to delete effects.
is a finite set of unique name axioms (UNA) for actions and named objects. For example, move-b-to-b(, , ) ̸= move-b-to-t(, ), move-b-to-t(, ) = move-b-to-b(′, ′) → = ′ ∧ = ′, and other similar axioms.
0 is a set of FO formulas whose only situation term is 0. It specifies the values of fluents in the initial state. It describes all the (static) facts that are not changeable by actions. Also, it includes domain closure for actions such as ∀. ∃, , ( = move-b-to-b(, , )) ∨ ∃, ( = move-b-to-t(, )) ∨
∃, ( = move-t-to-b(, )).
In particular, it may include axioms for domain specific constraints (state axioms), e.g., ∀∀((, , 0) → ¬(, , 0))∧ ∀∀∀((, , 0) ∧ (, , 0) → = )∧ ∀∀∀((, , 0) ∧ (, , 0) → = ).
Notice we did not include any state constraint (axioms uniform in ) into BAT, e.g.,
As stated in [35], they are entailed from the similar sentences about 0 for any situation that includes only consecutively possible actions.
Finally, the foundational axioms Σ are generalization of axioms for a single successor function
(see Section 3.1 in [
= ( ⊏ ′ ∨ = ′), ∀. (︀ (0) ∧ ∀∀( () → ((, ))) )︀
→ ∀( ()).
The last SO axiom limits the sort situation to the smallest set containing 0 that is closed under the application of to an action and a situation.
These axioms say that the set of situations is really a tree; there are no cycles, and no merging. These foundational axioms Σ are domain independent. Since situations are finite sequences of actions, they can be implemented as lists in PROLOG, e.g., 0 is like the empty list [ ], and (, ) adds an action at the front of a list representing , i.e. [ | ]. Therefore, in PROLOG, all situation terms satisfy the foundational axioms [35]. Appendix 2 includes BW implemented in Prolog.
It is often convenient to consider only executable (legal) situations: these are action histories in which it is actually possible to perform the actions one after the other.
< ′ = ⊏ ′∧∀∀* ( ⊏ (, * ) ⊑ ′ → (, * )) where < ′ means that is an initial sub-sequence of ′ and all intermediate actions are possible. Subsequently, we use the following abbreviations: ≤ ′ = ( < ′) ∨ = ′. Also, () = 0 ≤ . [35] formulates Theorem 1. (([ 1, · · · , ], 0)) ↔ ( 1, 0) ∧ ⋀︀
=2 ( , ([ 1, · · · , − 1], 0)).
Theorem 2. [28] A basic action theory = Σ ∧ ∧ ∧ ∧ 0 is satisfiable iff ∧ 0 is satisfiable.
Theorem 2 states that no SO axioms Σ are needed to check for satisfiability of BAT . This result is the key to tractability of , since ∧ 0 are sentences in FOL.
There are two main reasoning mechanisms in SC. One of them relies on the regression operator [39, 33] that reduces reasoning about a query formula uniform in a given situation to reasoning about regression of the formula wrt 0 . Another mechanism called progression [17] is responsible for reasoning forward, where after each action , the initial theory 0 is updated to a new theory . In this paper, we focus on simplified progression in a local effect BAT [ 22], where SSAs are essentially quantifier free, as defined before.
The Domain Closure Assumption (DCA) for objects [30, 32] means that the domain of interest
is finite, the names of all objects in 0 are explicitly given as a set of constants 1, 2, . . . , ,
and for any object variable it holds that ∀( = 1 ∨ = 2 ∨ . . . ∨ = ). According to
the Closed World Assumption (CWA), an initial theory 0 is conjunction of ground fluents, and
all fluents not mentioned in 0 are assumed by default to be false [31, 32]. According to an
opposite Open World Assumption (OWA), an initial theory 0 can have a more general form,
e.g., it can be in a + form [
As proved in Theorem 4.1 in [32], in the case of a database augmented with the axioms of equality, the queries that include only ∃-quantifiers over object variables can be answered without the DCA. Similar results can be proved for a 0 in a + form, assuming there are no object function symbols other than constants. From this fact, the above mentioned results, and the results from [21], it follows that in the case of a BAT where 0 is in a + form, the context conditions in SSAs are essentially quantifier free, where the preconditions Π(¯, ) in ap include only ∃-quantifiers over object variables, the goal formula includes only ∃-quantifiers over object variables, and all sets of axioms use only a bounded number of variables, the lengthbounded planning problem can be solved without DCA over the object variables (and without CWA). In the next section, we formulate the (bounded) planning problem for BATs and show a planner can be developed from the first principles.
Let () be a goal formula that is uniform in and has no other free variables. Let ℎ() be a number of actions in situation , i.e., ℎ(([ 1, · · · , ], 0)) = and ℎ(0) = 0. Following [35], the bounded planning problem can be formulated in SC as |= ∃. ℎ() ≤ ∧ () ∧ (), (1) where ≥ 0 is an upper bound. From the Theorem 1, definition of (), the foundational axioms Σ, it follows that this can be equivalently reformulated for > 2 as |= (0) ∨ ∃1(︀ (1, 0) ∧ ((1, 0)))︀ ∨ ∃1∃2(︀ 0 < ([1, 2], 0)∧ ︀( (([1, 2], 0)) ∨
∃(([1, 2], 0) ≤ ∧ ℎ() ≤ ∧ ()) )︀ )︀ This simply means that if there exists a situation term that solves the planning problem (1), then either it is 0, or for some action 1 that is possible in 0, it is (1, 0), or for some actions 1 and 2 that are consecutively possible from 0, either (([1, 2], 0)) holds, or there exists situation that is executable from ([1, 2], 0) such that its total length is less than or equal to and the formula () holds in . Suppose that a BAT has different action functions 1(¯1), . . . , (¯). Then, according to the DCA for actions, the formulas =1 ∃¯ ︀( ((¯), 0))︀ ∃ ((, 0)) and ∃∃′ ((′, (, 0))) are equivalent to ⋁︀ and ⋁︀ =1∃¯ ︀( ( (¯ ),((¯), 0)))︀ . Thus,
=1∃¯ ⋁︀ Theorem 3. A ground situation term ([ 1,· · · , ], 0), ≤ is a solution to problem (1) iff for some sequence (1, · · · , ) of action indices, 1 ≤ ≤ , there are ground substitutions for action arguments that unify 1 (¯1 ) with 1,. . . , (¯ ) with , and for these substitutions both ∃¯ · · · ∃ ¯1 (︀ ([1 (¯1 ),· · · , (¯ )], 0)︀) and the formula ∃¯ · · ·∃ ¯1 0≤ ([1(¯1 ),· · · , (¯ )],0) are entailed from a BAT .
This theorem is the first key observation that helps design a lifted planner based on SC. The planner has to search over executable sequences of actions on a situation tree. Note that the state space and states themselves remain implicit, since situations serve as symbolic proxies to states. (For a given situation, state is a set of fluents that are true in this situation in a model of ). Whenever a sequence of ground actions determined by a search results in a situation ([ 1, · · · , ], 0)), to find the next action the planner must check among the actions 1(¯1), . . . , (¯) for which of the values of their object arguments these actions are possible in ([ 1, · · · , ], 0)). Since this computation is done at run-time, but not before the planner starts searching for actions, the SC-based planner is naturally lifted, no extra efforts are required.
According the above discussion, if is large, then the right hand side of (1) expands into the long disjunction of formulas, and it is not clear in what order the deductive planner has to search over these formulas. The second key observation is that an efficient deductive planner needs control that helps select for each situation the most promising next possible action to execute. This control can be provided by a search algorithm that relies on a domain independent heuristic.
Our SC-based TPLH planner is implemented in PROLOG following the two key observations mentioned in the previous section. The planner is driven by theorem proving that is controlled by a version of A* search for a shortest sequence of actions that satisfies (1). The distinctive feature of TPLH is that it does forward search over the situation tree from 0. Since each search node is a unique situation, the previously visited nodes cannot be reached again. Moreover, frontier nodes cannot be reached along different paths, since each situation represents a unique path. However, different situations can represent the same state, where same fluents are true. Therefore, we consider two versions of our planner. In this section and in 5.2, we discuss the baseline version that keeps no records of what situations have been already visited. In Section 5.3, we consider another version that checks each visited state to ensure it has not been visited before. More specifically, the list of actions corresponding to each visited state is stored in a hash table. When search visits a new situation, we progress it to compute its state, then compute a hash value of this state and check whether the value maps to a hash table slot occupied by any of the previously visited situations. Upon encountering a collision, the state represented by a previous situation in the hash table is recomputed to verify whether it is equivalent to the current state. If so, the shortest situation is preserved, the longer situation is discarded, and then search continues. In both versions, for simplicity, the cost of every action is 1, and the cost of a path to a node is simply the length of the situation representing that node. This search terminates as soon as it finds a ground situation that satisfies a goal (). In Algorithm 1, a plan is a situation that is represented as a list of actions from 0, while 0 is represented as the empty list.
The main advantage of this design is that the frontier stored in a priority queue consists of
situations and their -values1 computed as the sum of situation length and a heuristic estimate.
Therefore, situations serve as convenient symbolic proxies for states. As usual, a state
corresponding to situation is a set of fluents that are true in . However, in hard-to-ground domains, each
state can be very large, and storing all intermediate states can exhaust all memory. This issue
was demonstrated on realistic domains such as Organic Synthesis [24]. Moreover, in the case of
planning in physical space and real time, the state space is infinite, but a deductive planner can
still search (without ad-hoc discretizations of space and time) over finite sequences of actions
according to semantics in [
In Algorithm 1, the sub-procedure InitialState(0 ) on Line 5 takes the initial theory as its
input, and computes the initial state under the usual DCA and CWA. (Note this is a limitation of
the current implementation, but not of the TPLH approach in general). We store this initial state
in a specialized data structure that facilitates computing progression efficiently. On Line 7,
the algorithm extracts the next most promising situation from the frontier. Then, on Line 8, it
computes progression of the initial state using the actions mentioned in . On Line 9, there
is a check for whether the goal formula is satisfied in the current state . If it is, then is
returned as a plan. If not, then on Line 12, the algorithm finds all actions that are possible from the
current state using the precondition axioms. In fact, the sub-procedure
is using preconditions to ground all action functions from the given BAT in the current state.
Since actions are grounded at run-time, TPLH is a lifted planner by design. If there are no
actions possible from , then the algorithm proceeds to the next situation from the frontier.
Otherwise, for each possible ground action , it constructs the next situation = (, ),
and if its length does not exceed the upper bound , it computes the positive integer number
on Line 21 as − ℎ(). This bound is provided as an input to the heuristic function
(, , , , ) that does limited look-ahead up to depth from to evaluate situation .
On Line 24, and its -value . are inserted into the frontier, and then search continues
until the algorithm finds a plan, or it explores all situations with at most actions. The for-loop,
Lines 16-24, makes sure that all possible successors of are constructed, evaluated and inserted
into the frontier. This is important to guarantee completeness of Algorithm 1.
1This is a term from the area of heuristic search, see [
Algorithm 1: * search over situation tree to find a plan Input: (, ) - a BAT and a goal formula G Input: - Heuristic function Input: - Upper-bound on plan length Output: that satisfies (1) ◁ Plan is the list of actions in
◁ Initialize PQ ◁ Initialize state ◁ Current state ◁ Found a plan ◁ No actions are possible in ◁ is next situation
◁ Next state ◁ exceeds upper bound
◁ is depth bound ◁ No plan for bound
The bound ≥ 0 makes sure that search will always terminate in a finite domain, since there are finitely many ground situations with length less than or equal to , and in the worst case, all of them will be explored. However, due to this upper bound, search may terminate prematurely, i.e., without reaching a goal state, if the shortest plan includes more than action. Consequently, this planner is complete only if the bound is greater than or equal to the length of a shortest plan. Obviously, the planner is sound thanks to Lines 8 and 9.
Note that (, ) computes afresh the current state from the given initial state and the list of actions in . If the computed state does not satisfy a goal formula, it is not Algorithm 2: GraphPlan heuristic with delete relaxation Input: (, ) - BAT and a goal formula Input: ≥ 1 - Look-ahead bound for the heuristic algorithm Input: , - The current situation and its length Input: - The current state Output: Score - A heuristic estimate for the given situation preserved after computing the heuristic value of . Only successor situations are retained in the frontier, but not their corresponding states. This is an important contribution of the TPLH approach. The previous planning algorithms usually retained states, but not situations in their frontiers; see [38] for a detailed discussion. In the TPLH approach, the initial state remains in memory, but all other intermediate states are recomputed from on demand. Therefore, TPLH trades speed for memory. Since the memory footprint of TPLH is smaller than it would be for alternative implementations, our approach is suitable for planning in hard to ground domains.
Computing the heuristic function is done in two stages, using the usual delete relaxation. First, a planning graph is built from the current state, layer-by-layer until all goal literals are satisfied. Best supporting actions are then found for the goal literals, going backwards through the graph; see Algorithm 2.
The planning graph is initialized to the current situation and state. At each step in building the planning graph, all possible actions for the current state are found, and then filtered so that only those actions with one or more new (positive) add effects not in the current state are kept. The state is updated using relaxed progression to incorporate their new add effects. These ‘relevant actions’, their new add effects and the updated state are inserted into the next layer of the planning graph, and the process is repeated.
Once all goal literals are satisfied, the most recent layer of the planning graph is examined. For each of the new add effects in this layer belonging to the set of goal literals, all relevant actions from the layer which achieve the effect are selected. These are referred to as the ‘supporting actions’ for the goal literal. For each supporting action, a ‘reachability’ score is recursively computed using its preconditions as the new goal literals. The easiest action whose preconditions have the lowest reachability is considered the ‘best supporting action’. Thus, our reachability score represents the estimated cost of achieving a set of literals. If all literals are satisfied in the initial layer of the planning graph , then the set’s reachability is 0. Otherwise, its reachability is equal to the reachability of the remaining goals and preconditions for the set of the easiest actions, plus the number of best support actions. The details are summarized in Algorithm 3. This heuristic is not admissible, but our experiments show it is informative in several applications. ArgMin {. over } ◁ This is different from FF
◁ Find the easiest action from with minimum estimate ∪ .
∪
To evaluate our implementation experimentally, we run our planner on several STRIPS benchmarks, where preconditions of actions are conjunctions of fluents (though they can include negations of equality between variables or constants), the SSAs have no context conditions, and the goal formula is a conjunction of ground fluents.
Tests were run separately using the TPLH, FD, and BFWS planners. TPLH and FD used the A* algorithm to prioritize shorter plan lengths, whereas BFWS used a default greedy search algorithm based on a width heuristic [18, 19, 20]. Both TPLH and FD did eager search with FF heuristic. All testing was done on a desktop with an Intel(R) Core(TM) i7-3770 CPU running at 3.40GHz. Tests measured total time spent, plan length, and number of states (situations) visited. Comparisons are made based on International Planning Competition (IPC) scores for satisficing planning that are extensivly discussed in [23]. As defined there, each participating planner gets a score per planning task “expressed as = * / , where is the total cost of the best solution found by planner for instance , and * is the lowest total cost found so far by any planner for the same problem, that is, * = {}" [23]. Since unsolved problems are scored as 0, coverage is taken into account by the score function. As you can see, the highest possible score per instance is 1. Usually, the score is based on the total cost, i.e., the sum of the costs of all individual actions in a plan, the IPC score can be adapted to other metrics as well. In our research we conside both the IPS score based on plan length (since TPLH assigns cost 1 to each action), and on the number of situations or states visited, where situation is visited when TPLH evaluates whether it is a goal state. The TPLH planner, domain files and problem instances have been loaded, compiled and run within ECLiPSe Constraint Logic Programming System, Version 7.0 #63 (x86_64_linux), released on April 24, 2022. In comparison, the FD and BFWS were compiled into executable files.
Testing was done over randomly generated problems for 8 different popular domains that represent well the variety of planning problems from the IPC competitions. These domains were Barman (BR), BlocksWorld (BW), ChildSnack (CS), Depot (D), FreeCell (FC), Grippers (GR), Logistics (L), and Miconic (M). In addition, testing was also done on 10 pre-existing problems belonging to the PipesWorld (PW) domain. All domains are in STRIPS, extended to include negated equalities and object typing. For simplicity, the Barman domain was modified to remove action costs.
Roughly 100 problems with varying numbers of objects were generated for each of the specified domains, using publicly available PDDL generators. All PDDL domains and generated instances ifles were automatically translated from PDDL to PROLOG using our program that constructs a hash table based representation of an initial theory. The TPLH planner was run over every problem using a 15 minute time-out limit, and a 512M MB stack size limit, i.e., much less than typical memory cutoffs 6 GB. Problems for which the planner timed out were discarded, as were problems with 0-step solutions (i.e., where the initial state satisfied the goal state). The number of kept instances for each domain is shown in parentheses after the domain name in Table 1. The remaining instances are not trivial for several domains that we checked, i.e., when we run TPLH on them without heuristic (ℎ set to 0), it could not solve most of them within the allocated time and memory bounds. The TPLH planner was given the upper bound = 100 for all planning instances that usually had short solutions, e.g., 20 steps or less. Miconic was the only domain where some of the computed plans were longer than 20 steps. Recall is used to guarantee completeness of TPLH, but it had little effect in this set of experiments. Namely, when we tried different values = {50, 75, 100, 125, 150} over some domains, the total time varied within 1%, but plan length and the number of situations visited by TPLH did not change at all.
Before TPLH could be tested on a domain, the domain file was converted from PDDL to a BAT implemented in PROLOG, and initial state hash tables were built for each individual problem. More specifically, we implemented initial state as a list of fluent names, where each lfuent is represented by a hash table which stores all instances which are true in the initial state . Hashing fluent arguments allows for efficient access and updating of state information to facilitate progression planning. Translating domains files themselves took very little time (under 0.1 seconds in all cases), and this cost was further amortized by the fact that it only needed to be done once, regardless of how many problems were tested. Building initial state hash tables however could take a non-negligible amount of time. This time was consistent across all problems belonging to a domain, and ranged from approximately 1.5 seconds per problem (for BlocksWorld) to nearly 10 seconds per problem (for Barman). The inefficiency here is tied to the current implementation of the script used, and is not inherent to the task of creating the hash tables themselves. Preprocessing time for each problem was added to the time spent by the planner itself to get the total time to solve a problem. (Performance of TPLH on easy instances was much better when preprocessing was factored out.)
In terms of CPU time, as expected, TPLH was much slower than FD and BFWS. More specifically, TPLH was on average about 102 times slower than FD. In BW, Grippers, Miconic and PipesWorld, TPLH was on average 103 times slower than BFWS, and on other domains TPLH was about 104 times slower than BFWS. TPLH timed out on several instances, but both FD and BFWS solved all the instances within allocated time and memory. Note that the number of objects in the generated instances was relatively small. The slow performance of TPLH was not surprising, but it is interesting to compare TLPH with FD and BFWS in terms of IPC scores. We do this in the next sub-sections, starting with a baseline version of TPLH, and then we proceed to more optimized versions of TPLH.
In this sub-section, we discuss only a baseline version of TPLH which does not check whether the current situation corresponds to a state that was previously visited. When testing the problems using TPLH, the number of situations visited was recorded, as was the length of the produced plan and the total time taken. A situation was considered as having been visited upon checking whether it satisfied a goal state. Thus, the minimum number of situations visited by TPLH is one greater than the length of the produced plan. The same data was gathered when testing using the FD and BFWS planners, with the distinction that the number of states visited by each planner was recorded, rather than situations. In this section, we consider only a mini-competition between a baseline TPLH, FD, and BFWS. We compare the IPC scores for plan length and the number of situations visited for TPLH to FD and BFWS, see Table 1. In the second column, we include for each domain the object counts used to generate the random instances.
Domain BR (100) BW (95) CS (100) D (76) FC (95) GR (98) L (119) M (93) PW (6) #Obj 11-31 8-11 9-17 8-21 21-37 10-27 9-32 17-40 26-44
TPLH was competetive with FD when evaluating plan length across every domain; it matched FD in four of the domains, and outperformed it for problems belonging to the Depot domain. In addition, it only fell short in the BlocksWorld domain due to the fact that it failed to complete three problems within the allotted time. When comparing to BFWS, TPLH outperformed it for plan length across all nine domains. This is not surprising, since TPLH does A* search, but BFWS does greedy search guided by novelty, and this leads to increased exploration as explained in [19].
When using IPC scores based on the number of situations/states visited, TPLH greatly outperformed FD, and scored better than BFWS in seven of the nine domains, but was beaten in the ChildSnack and PipesWorld domains. A few inherent aspects of the ChildSnack domain lead to the heuristic performing poorly wrt BFWS. Firstly, plans in this domain are highly ’interleavable’; i.e. there are several permutations of the same actions which are all valid solutions. Secondly, ChildSnack problems have relatively few goal atoms, which are all achieved by the last few actions of an optimal plan. Third, no heuristic is perfect. As the heuristic is domain-independent, it is natural that there will be some domains where it excels, and some where it struggles. Apparently, the width-based heuristic in BFWS is better on this domain. Notice that in ChildSnack TPLH performs much better than FD (with a FF heuristic) in terms of the situations/states visited.
It is important to realize our heuristic is more informative than the implementation of FF used
by the FD planner. In Algorithm 3, see Lines 10-14, when we evaluate support actions
which achieve one of the fluents in , the cost of achieving the preconditions of each
action is recursively estimated, and then the action with the lowest such cost is selected on Line
14. The cost is the number of the best supporting actions, see Line 21. This is in contrast to the
FF heuristic, which does one top-down loop over the layers and selects the minimum difficulty
supporting action for each fluent, see Figure (2) and Section 4.2.2 in [
The heuristic used by TPLH performed remarkably well on certain problems, only ever visiting situations which were a subsequence of the final plan. In the FreeCell domain for example, this was true of every problem tested. This is likely due to the nature of the Planning Graph data structure and the process used for finding best supporting actions. When evaluating actions which 1 0.86
1 0.97 0.91 0.96 1 1 0.83 achieve the goal state for the relaxed problem, the cost of achieving the preconditions of each action is recursively computed, and the action with the lowest such cost is selected. This means that for highly sequential problems, where a specific chain of actions is necessary to allow a sub-goal to be achieved (e.g. in FreeCell, cards must be placed on the foundation pile in sequential order), the heuristic can identify situations which allow for shorter causal chains. As long as a given move completes a step in this chain, TPLH recognizes the resulting situation as more promising than the previous one, and pursues it. When the causal chain is complete for the final goal, the problem is solved.
TPLH was also competetive with FD and BFWS when comparing on a problem-by-problem basis. Refer to Table 2 for % of problems across each domain for which TPLH performed at least as well as its competitors on plan length (left column) and situations visited (right column).
Measuring the ratio of the length of the plan produced to the number of situations visited by TPLH, we can evaluate the performance of our heuristic across each of the nine domains tested. We used a cutoff value of ≥ 0.75 to identify the percentage of problems that the heuristic guided effectively, see Table 3. As previously discussed, the heuristic was able to effectively guide 100% of problems in the FreeCell domain. It also performed well on the BlocksWorld domain (45%) and the Depot domain (54%). At the lowest end, none of the problems from the Barman domain met this threshold ≥ 0.75.
The recursive nature of finding the best supporting actions necessitates a lot of redundant computations. The current non-optimized implementation of the heuristic spends the vast majority (upwards of 95%) of total TPLH time. This is part of the reason why TPLH is orders of magnitude slower than FD and BFWS. Moreover, finding new possible actions inside heuristic takes time. More specifically, we found that Lines 5 and 6 consume significant time in Algorithm 2, due to the fact that they must recompute all actions which were possible in previous layers of the planning graph in addition to those new to the current layer. Computing only those new relevant actions which were not previously possible is non-trivial; this is future work. 5.3. Extensions to the Baseline Version of TPLH This section will compare the performance of our TPLH planner with and without various extensions we have implemented, in order to examine trends across different domains and determine an optimal configuration. All tests were performed over the same set of problems from the previous subsections, using the same hardware, memory, and timeout limits. Table 4 contains IPC scores for each of the tested configurations of TPLH, along with FD and BFWS, across all problems for each domain. Note that in this section we computed IPC scores not only for FD and BFWS, but also for all different configurations and extensions of TPLH. Therefore, the data in Tables 4 and 5 are not directly comparable with the data in Table 1. We postpone our discussion of these tables to the end of this section.
The most important extension we have added to the baseline version of TPLH is the ability to detect and filter out repeated states while exploring different action sequences in the situation tree. For example, two different sequences of actions in the Gripper domain can pick up two balls in a different order and move them from one room to another so that the state resulting from these two sequences is exactly the same. The baseline TPLH discussed in the previous Section 5.2 did not have this check. Now, we can record all visited situations in a hash table. When the search algorithm takes a new situation, we compute the state it represents, compute from the state its hash function to check whether the corresponding hash table slot is occupied or not by any of the previously visited situations, and if yes, then verify whether their states are actually the same or not. If their states are the same, we pursue only the shorter situation and discard the longer. Otherwise, we insert a new visited situation in the hash table slot. Notice we still only store situation in memory, and recompute the corresponding states on demand.
In the sequel, when we directly compare two configurations of the TPLH planner, only those problems solved by both configurations were included while calculating average performances across different criteria.
With filtering enabled, the A * planner was able to find plans more quickly across every domain except for ChildSnack, where the large number of situations visited led to a greater number of hash collisions, and FreeCell, where the strong performance of the heuristic we used meant that repeated states were never encountered. The most marked improvements effected by filtering were found in the Depot, Grippers, and Logistics domains. Unsurprisingly, filtering duplicate states also resulted in fewer states being visited across almost every domain. Table 6 contains full information on the effects of filtering for each domain. (The bold font shows the best performance.)
Filtering of repeated states also allowed for the use of a greedy search strategy, as repeated action sequences cycling through states with the same heuristic value can be avoided. Table 7 contains a breakdown of its performance relative to the A* search method with filtering. The greedy search strategy was able to achieve a substantial improvement in solving time over the A* strategy across almost every domain. This is due to it visiting fewer overall situations, meaning that the greedy strategy shows a smaller overall improvement across domains where the heuristic guides the search more effectively, such as FreeCell and Miconic.
In addition, we implemented a second queue in the frontier, to hold “useful" situations reached
via helpful/preferred actions. These are defined recursively as actions which achieve a goal fluent,
or actions which achieve a ground fluent which is a precondition for a previously found preferred
action [
Domain B (100) BW (93) CS (100) D (76) FC (95) G (98) L (119) M (93) PW (6)
Finally, we would like to sumamrize the results reported in the Tables 4 and 5. IPC scores for plan length and situations visited can be best compared according to the search strategy used. Consider the Table 4 and note that TPLH with an A* search strategy was competitive with FD for plan length in the A* -U and A* -1 configurations, falling approximately one point short of it. Notably however, TPLH was unable to solve three of the problems within the BlocksWorld domain within the time/memory limits, and the A* -2 configuration could not solve an additional twenty problems from the ChildSnack domain. If these instances were removed from the comparison pool, then we could say that TPLH slightly outscores FD, meaning that TPLH actually finds shorter solutions on a problem-by-problem basis. Now, focusing on the Table 5, note that the G-2 configuration scores very similarly to BFWS despite solving two fewer problems overall. When considering the number of states/situations visited, TPLH greatly outshines FD and BFWS regardless of the search strategy being used. Therefore, we can conclude from these experimental results that deductive planning is a productive research direction.
We have developed a sound and complete lifted planner based on theorem proving in the situation calculus. It searches for a plan in a tree of situations, but not in a state space, and therefore it has minimal memory footprint. It was tested using a heuristic inspired by FF. To the best of our knowledge, TPLH is the first deductive planner based on SC with a domain independent heuristic. The readers can find a detailed discussion of the previous work on deductive planning in [38].
It is easy to consider arbitrary action costs within TPLH. It is possible to develop a deductive planner that works not only with context-free domains, but also with more general BATs, where SSAs have context conditions. The bound is not essential to the design of TPLH. It can be easily removed, but then TPLH will lose completeness guarantees over finite domains with DCA.
In future, we would like to develop lifted versions of several heuristics. In particular, the current implementation of the Plan Graph based heuristics that is described in this paper grounds both fluents and actions at run-time and builds a large data structure, but this is inefficient and consumes more memory as the number of objects grow. However, one can implement a lifted version of the same heuristic that can be more suitable to planning in the hard-to-ground domains. We noted that deductive planning in SC leads naturally to lifted planning with action schemas at run time. However, in this paper we do not compare our planner with other recent lifted single-model planners. This study remains an interesting and important future research direction.
Since we ground actions at run-time by evaluating their preconditions, and this is one of the computational bottlenecks, in particular, in the hard-to-ground domains with complex preconditions as in [24, 29], we need a better algorithm for finding possible actions. This is work in progress. It is important for research in deductive planning.
In the case of incomplete 0 (no CWA), and a local effect BAT, one would need a more sophisticated algorithm for progression. In addition, we would like to develop an implementation that does not rely on DCA for objects, e.g., an implementation for the planning problems where the actions can create or destroy objects. This is doable within our deductive approach to planning.
Thanks to the Natural Sciences and Engineering Research Council of Canada for partial funding of this research and to the reviewers of the preliminary version of this paper for useful comments. Appendix 1: The Blocks World in PDDL Appendix 2: The Blocks World in PROLOG
/* Precondition axioms */ poss(move-b-to-b(X,Y,Z),S):- clear(X,S),clear(Z,S), on(X,Y,S),not X=Z. poss(move-b-to-t(X,Y),S) :- clear(X,S), on(X,Y,S). poss(move-t-to-b(X,Z),S) :- ontable(X,S), clear(X,S), clear(Z,S).
/* Succesor state axioms */ on(X,Y, [move-b-to-b(X,Z,Y) | S]). on(X,Y, [move-t-to-b(X,Y) | S]). on(X,Y, [A | S]) :- on(X,Y,S), not A=move-b-to-b(X,Y,Z),
not A=move-b-to-t(X,Y). ontable(X, [move-b-to-t(X,Y) | S]). ontable(X, [A | S]) :- ontable(X,S), not A=move-t-to-b(X,Y). clear(X, [move-b-to-b(Y,X,Z) | S]). clear(X, [move-b-to-t(Y,X) | S]). clear(X, [A | S]) :- clear(X,S), not A=move-b-to-b(Y,Z,X)), not A=move-t-to-b(Y,X). [16] Fangzhen Lin. Situation calculus. In Handbook of Knowledge Representation, volume 3 of
Foundations of Artificial Intelligence , pages 649–669. Elsevier, 2008. [17] Fangzhen Lin and Raymond Reiter. How to Progress a Database. Artificial Intelligence , 92:131–167, 1997. [18] Nir Lipovetzky and Hector Geffner. Width-based algorithms for classical planning: New results. In 21st European Conference on AI, ECAI-2014, pages 1059–1060, 2014. [19] Nir Lipovetzky and Hector Geffner. Best-first width search: Exploration and exploitation in classical planning. In 31st AAAI-2017, pages 3590–3596, 2017. [20] Lipovetzky and Geffner. Best First Width Search Planner, Github repository. https://github.
com/nirlipo/BFWS-public, 2022. Accessed: 2022-11-17. [21] Yongmei Liu. Tractable Reasoning in Incomplete First-Order Knowledge Bases. PhD thesis, Department of Computer Science, University of Toronto, 2005. [22] Yongmei Liu and Gerhard Lakemeyer. On First-Order Definability and Computability of Progression for Local-Effect Actions and Beyond. In 21st IJCAI-2009, pages 860–866, 2009. [23] Carlos Linares López, Sergio Jiménez Celorrio, and Angel García Olaya. The deterministic part of the seventh international planning competition. Artif. Intell., 223:82–119, 2015. [24] Arman Masoumi, Megan Antoniazzi, and Mikhail Soutchanski. Modeling Organic Chemistry and Planning Organic Synthesis. In Global Conference on AI, GCAI-2015, Georgia, volume 36 of EPiC Series in Computing, pages 176–195. EasyChair, 2015. [25] John McCarthy. Situations, actions and causal laws. Technical Report Memo 2, Stanford University AI Laboratory, Stanford, CA, 1963. Reprinted in Marvin Minsky, editor, Semantic Information Processing, MIT Press, 1968. [26] John McCarthy and Patrick Hayes. Some Philosophical Problems from the Standpoint of Artificial Intelligence. In B. Meltzer and D. Michie, editors, Machine Intelligence, volume 4, pages 463–502. Edinburgh Univ. Press, 1969. [27] Edwin P. D. Pednault. ADL and the State-Transition Model of Action. J. of Logic and
Comput., 4(5):467–512, 1994. [28] Fiora Pirri and Ray Reiter. Some contributions to the metatheory of the situation calculus.
Journal of the ACM (JACM), 46(3):325–361, 1999. [29] Hadi Qovaizi. Efficient Lifted Planning with Regression-Based Heuristics, Master Thesis.
Technical report, TMU, Toronto Metropolitan (formerly Ryerson) University, Department of Computer Science, Dec 2019. [30] Raymond Reiter. An Approach to Deductive Question-Answering. BBN Technical Report 3649 (Accession Number : ADA046550), Bolt Beranek and Newman, Inc., 1977. [31] Raymond Reiter. On Closed World Data Bases. In Logic and Data Bases, pages 55–76.
Plenum, 1978. [32] Raymond Reiter. Equality and Domain Closure in First-Order Databases. J. ACM, 27(2):235– 249, 1980. [33] Raymond Reiter. The Frame Problem in the Situation Calculus: A Simple Solution (sometimes) and a Completeness Result for Goal Regression. In V. Lifschitz, editor, AI and Mathematical Theory of Computation: Papers in Honor of John McCarthy, pages 359–380, San Diego, 1991. Academic Press. [34] Raymond Reiter. Proving Properties of States in the Situation Calculus. Artif. Intell., 64(2):337–351, 1993. [35] Raymond Reiter. Knowledge in Action. Logical Foundations for Specifying and Implementing Dynamical Systems. MIT, http://cognet.mit.edu/book/knowledge-action, 2001. [36] Silvia Richter and Matthias Westphal. The LAMA planner: Guiding cost-based anytime planning with landmarks. J. Artif. Intell. Res., 39:127–177, 2010. [37] Mikhail Soutchanski. Planning as Heuristic Controlled Reasoning in the Situation Calculus.
PROLOG source code, TMU (formerly Ryerson), Dep. of Computer Science, https://www. cs.torontomu.ca/~mes/, Toronto, Canada, July 2017. [38] Mikhail Soutchanski and Ryan Young. Planning as theorem proving with heuristics. CoRR, https:// doi.org/ 10.48550/ arXiv.2303.13638, 2023. [39] R. Waldinger. Achieving Several Goals Simultaneously. In Machine Intelligence, volume 8, pages 94–136, Edinburgh, Scotland, 1977. Ellis Horwood.