We study the problem of finding cost-optimal solutions to planning problems that feature qualitative state trajectory constraints expressed in PDDL3. These constraints are properties that every plan must satisfy and can be seen as a fragment of LTL over finite traces. The state-of-the-art system for handling PDDL3 problems is a compilation-based approach. Such a compilation has been tested only using a satisficing planner, while the case where we require the planner to find optimal solutions is scarcely studied; with this paper, we want to fill this gap. We propose an experimental analysis that involves TCORE, the current state-of-the-art compilation approach to handle qualitative PDDL3 constraints, and two compilation approaches supporting arbitrary LTL formulas. We evaluate each system using two optimal planners, and we analyze the results using diferent metrics to explain the behavior of the considered approaches. Our analysis confirms the result previously obtained with a suboptimal planner; that is, in the optimal setting TCORE outperforms all other compilations over our benchmark domains.
The aim of this paper is to study the behavior of diferent state-of-the-art systems for handling
trajectory constraints in the context of finding optimal solutions. In particular, we focus
on planning problems that feature qualitative constraints defined by the PDDL3 language
[
We borrow standard notions and notations from propositional logic and the work by Gerevini
et al. [
A classical planning problem is a tuple Π = ⟨ , , , ⟩ where is a set of atoms, ⊆ is the initial state, is a propositional formula over , and is a set of actions. An action ∈ is a pair ⟨Pre(), Ef ()⟩ , where Pre() is a formula over expressing the preconditions of , and Ef () is a set of conditional efects, each of which is a pair ▷ where: is a formula and is a set of literals, both over . With − and + we indicate the partition of featuring only negative and positive literals, respectively. A state is a subset of , with the meaning that if ∈ , then is true in , and if ∉ , is false in . An action is applicable in if ⊧ Pre() , and the application of an action in yields the state ′ = ( ⧵ ⋃ −) ∪ ⋃ +. We indicate ▷∈ Ef () ▷∈ Ef () with ⊧ with ⊧ with ′ = [] the state resulting from applying action in , and assume conflicting efects ( and ¬ ) are only yield by conditional efects having their conditions mutually exclusive in .
A plan for a problem Π = ⟨ , , , ⟩ is a sequence of actions ⟨ 0, 1, ..., −1 ⟩ in Π; plan
is valid for Π if there exists a sequence of states (state trajectory) ⟨ 0, 1, ..., ⟩ such that 0 = ,
∀ ∈ [0, … , − 1] we have that ⊧ Pre( ) and +1 = [ ], and ⊧ . The cost of a plan ( ) , is
given by the sum of the cost () of each action in . A plan is said to be optimal if no plan
′ with ( ′) < ( ) exists. PDDL3 state-trajectory constraints are a class of temporal formulae
over trajectory of states, and they involve necessary conditions that the state trajectory of
a valid plan must satisfy. In this work, we consider planning tasks with constraints that in
PDDL3 are called “qualitative” [
A PDDL3 planning problem is a tuple ⟨Π, ⟩ where Π is a classical planning problem and is a set of trajectory constraints; the valid plans of ⟨Π, ⟩ are all valid plans of Π whose state trajectories satisfy all constraints in .
This section briefly describes how TCORE translates a PDDL3 problem into an equivalent planning problem without constraints. TCORE identifies two classes of constraints: invariant trajectory constraints (ITCs) and landmark trajectory constraints (LTCs). Intuitively, ITCs can be checked along any plan prefix and if they are violated, there is no way the planner can ever re-establish them; they are invariant conditions that must be maintained over the state trajectory of the plan. LTCs are constraints that require certain conditions true at some state over the state trajectory of the plan. TCORE works by extending the action preconditions and conditional efects in order to (i) block the violation of ITCs during planning, and (ii) keep track of the truth of relevant (w.r.t. trajectory constraints) formulae in the states generated by the plan prefix. This is achieved by making use of the efect regression operator , and by introducing a set of monitoring atoms. The efect regression is a formula manipulation technique: given a propositional formula and an action , (, ) is a propositional formula such that, for any state , ⊧ (, ) if [] ⊧ . The regression makes it possible to identify what actual influence the action has over the trajectory constraint of interest. Monitoring atoms serve the purpose of collecting relevant facts on the plan state trajectory and asserting their truth/falsity. The ITCs are: A , AO , SB, . For each AO and SB, , TCORE adds the fresh predicates and to record whether and have ever held. The LTCs are: ST and SA, . For each LTC, the compilation adds a predicate ℎ . Such a predicate is meant to record whether the constraint is already satisfied or not according to the current plan prefix.
Algorithm 1 describes the full compilation. As a very first step, TCORE creates the necessary atoms (line 3) and sets up the initial state so as to reflect the current status of the trajectory constraints; in particular, the algorithm captures if a LTC is already achieved in , or if a formula ( or ) that is necessary for the evaluation of an ITC is already true in . Then TCORE checks whether any ITC is already unsatisfied; if so, the problem is unsolvable.
After the initialization phase, the algorithm iterates over all actions and constraints to modify each original action model (preconditions and efects) by considering the interactions between the constraints and the action model. If the constraint is an ITC, the algorithm determines, by regression, a condition such that, if holds in the state where the action is applied, the execution of such an action will violate the constraint. For example, in the case of A , models whether the action makes formula false (line 10). The regressed condition is negated and then conjoined with the precondition of the action. In this way, if the action will violate the constraint in a given state, such an action is deemed inapplicable by the planner. In the case of ITCs, conditional efects are added to keep track of whether relevant formulae have ever held in the state trajectory of the plan prefix. For instance, SB, requires to deal with the truth of : if an action makes true, then the action must make true too. In this way, the compilation prevents applying an action when it makes true and has not held before in current plan state trajectory (lines 14–17).
For each LTC ∈ , the algorithm yields a formula that is true only in those states where the action achieves the targeted formula expressed in . Note here the slightly diferent treatment ′ = ′ ∧ ℎ 28 return Classical Planning Problem ⟨ ∪ ′, ′, ∪ ′, ∧ ′⟩ for the two types of LTCs. While ST only requires to be true, for SA, the compilation needs to signal the necessity of only when becomes satisfied; this is done by introducing two conditional efects (lines 21 and 22) afecting the additional goal ℎ of ′ (line 27). Also observe that can become true multiple times, and each state satisfying needs to be followed by a state such that is true again; this state can also be the same state in which holds, as prescribed by the semantics of PDDL3.
Note that Algorithm 1 can add irrelevant preconditions and conditional efects that can easily be omitted by looking at whether regression leaves a formula unaltered. E.g., for A , if = (¬, ) = ¬ , there is no need to extend Pre() with ¬ = at line 17. Such optimizations are implemented but omitted here for clarity and compactness.
As trajectory constraints are monitored along the entire plan, and regression through efects provides suficient conditions for ensuring that no ITC is violated by an action and no LTC remains unsatisfied at the plan end, it is easy to see that the compiled problem always finds a solution that conforms with the trajectory constraints of the problem. Moreover, since the exploited regression establishes necessary conditions too, the existence of a solution in the compiled problem implies that the original problem is solvable.
Our experimental analysis studies the behavior of TCORE and two state-of-the-art compilation
approaches dealing with LTL constraints in the context of finding optimal solutions. Specifically,
we considered the exponential compilation by Baier and McIlraith [
The performance of each system is evaluated in terms of the number of solved instances
(coverage), the time spent to find a solution (computed as the compilation time plus planning
time), the number of nodes expanded by ∗(ℎ ), and dimension of the compiled problems. All
experiments were performed on a Xeon Gold 6140M 2.3 GHz, with time and memory limits of
1800s and 8GB, respectively. We tested the systems using the benchmark by Bonassi et al. [
Domain for instances compiled by each system. EXP and POLY work on the lifted representation of a planning task, while TCORE has to instantiate the planning problem before performing the actual compilation. For the sake of a fair comparison, the averages reported in Table 1 were calculated by grounding the instances resulting from the two LTL systems using the FastDownward translator.
We can observe that the tasks compiled by TCORE contain on average less efects and less
lfuents compared to the instances compiled with EXP/POLY. This is due to the fact that EXP and
POLY are capable of handling arbitrary nested LTL formulas (unsupported by PDDL3); to deal
with such expressive power, these two compilations rely on automata theory to compile the
LTL formulas away. Integrating the resulting automatons into the domain model requires many
additional fluents and efects as shown by Table 1. On the other hand, TCORE is tailored at
handling PDDL3 qualitative constraints and this allows for a more eficient compilation. Indeed,
TCORE introduces up to one fluent for each trajectory constraint (zero in the case of an always)
and takes advantage of the regression computation to minimize the number of additional efects.
Coverage. Table 2 shows an overall picture of the coverage achieved by each system across
all domains. TCORE achieves the highest coverage in four out of five domains, solving a
total of 277 instances. Remarkable are the performances in R o v e r and O p e n s t a c k ; TCORE
solves 95% and 98% of the instances in these domains, respectively. The performances of TCORE
(a)
(c)
(b)
(d)
with an optimal planner are close to those of TCORE with a satisficing planner: in the same
instances, TCORE with LAMA [
As expected, TCORE cannot solve many problems, achieving roughly half the coverage of TCORE . We attribute this behavior to the fact that ∗ with ℎ is less sophisticated compared to SYM-K. Interestingly, though, ∗ with ℎ is more efective at solving instances compiled with EXP and POLY; with both compilations, such a system outperforms SYM-K in all domains. We believe that this is due to the fact that SYM-K does not scale well when problems have many atoms and efects, and this is the case for the instances compiled through EXP and POLY, as shown in Table 1.
Coverage-wise, Bonassi et al. [
Analogously to the results presented by Bonassi et al. [
CPU time analysis. Figure 2a reports how systems increase their coverage over time. TCORE surpasses EXP right from the start, and achieves 90% of its maximum coverage after 333 seconds. TCORE increases its coverage at a slower rate, achieving 90% of its maximum coverage in about 474 seconds. Diferently, ∗ with ℎ is faster than SYM-K with EXP, as EXP dominates EXP .
Figures 2c and 2d show a pairwise comparison of the runtimes of TCORE with the runtimes of EXP, while Figure 2b compares TCORE with EXP in terms of expanded nodes. Most of the PDDL3 instances are solved generally faster than the instances compiled with EXP. From Figure 2b, we can observe that TCORE expands less nodes than EXP , and this indicates that the ℎ heuristic is more informed when tasks are compiled with TCORE; the EXP compilation introduces axioms, a feature that seems to be not fully supported by the heuristic. There is an exception for a small set of S t o r a g e problems; in such instances EXP performs more eficiently than TCORE regardless of the planner. We attribute this to the fact that TCORE has to spend time to ground the instances before performing the actual compilation, while EXP directly works on the first-order representation.
We have presented an experimental analysis that compares three diferent compilation-based
systems to handle PDDL3 qualitative constraints with optimal planners. Results shows that
TCORE remains the state-of-the-art approach to handle the considered class of problems.
Recently, Bonassi et al. [
We thank the anonymous reviewers for their helpful comments. This work has been partially supported by EU-H2020 projects AIPlan4EU (No. 101016442) and TAILOR (No. 952215), and by MUR PRIN-2020 project RIPER (No. 20203FFYLK).