Investigating domain independent heuristics in a timeline-based planner

Abstract

Taking inspiration from both Constraint Programming (CP) and Logic Programming (LP), the ILOC domain-independent planning system is a timeline-based planner that allows to model both planning and scheduling problems according to a uniform schema. This paper presents a complete description of the planner and describes two domain independent heuristics aiming at improving the planner ability to solve classical planning problems. An experimental evaluation demonstrates the ILOC strength in solving temporally expressive problems and its improved ability to address the causal reasoning capability which is a dominant feature of classical planning. Furthermore the experimentation produces some observations for new directions to synthesize effective general purpose solving abilities.

Keywords

Heuristics timelines planning

1 Introduction

Timeline-based planning is an approach to temporal planning introduced in [29]. It consists of synthesizing temporal functions that describe the variation over time of a set of domain dynamic features to achieve temporally extended goals (see also [35] for an introduction and [11] for a recent formalization). Most of the current timeline-based planners, like Europa [25], ASPEN [9], IxTeT [23] and APSI-TRF [7, 22], are defined as complex software environments suitable for deploying planning applications. Such architectures are, typically, inherently quite inefficient and, therefore, rely on a careful engineering phase of the domain model, possibly supported by the definition of domain-dependent heuristics. With few exceptions (e.g., [3]), the search control in those planners has always remained significantly under explored.

Mostly based on the notion of partial order planning [38], timeline-based planners have usually neglected advantages from classical planning triggered from the use of both GraphPlan and modern heuristic search [4 , 24]. Indeed, the different branching schema does not seem to allow effective pruning mechanisms during search hence dead-ends are discovered too late and, as a consequence, the size of the search tree is likely to explode. Similar to most Partial Order Causal Link (POCL) planners, timeline-based planners tend to reason about the sole elements in the current partial plan [37], mostly relying on temporal reasoning aspects, while overlooking possible subsequent plan refinements. On the contrary, when building and using the planning graph GraphPlan reasons, in a limited way, on all the possible plans underlying a domain model specification, hence producing a wider view of the problem to be solved (the same holds for heuristic search approaches based on [5] and derivatives).

To directly cope with such pitfalls, we have developed a new framework, called ILOC 1 , able to solve both planning and scheduling problems in a uniform schema. In [16] we described its resolution algorithm and endowed it with basic (static and dynamic) heuristics. The initial heuristic followed the general principle of simplifying the initial problem, solving the simplified problem, and then using the solution to guide the search in the initial, more complex, problem. In a first stage, only a simple form of causal relations was left and all the other types of constraints from the problem were removed, resulting in a heuristic which, despite allowed us to greatly improve the performance of the reasoner, ended up being too uninformed.

This work is a consolidated version of a subsequent work [17] where some of the “removed” constraints (in particular, the disjunctions) have been reintroduced in the heuristic, thus enriching its informativeness and allowing improved performances of the resolution algorithm, particularly on those domains in which performances were worse.

The current paper follows the path paved by those previous works [16, 17]. It describes in more detail the composing elements of ILOC, robustifies several of the previous descriptions and also corrects some oversights. By the end of the paper, we suggest possible paths to follow which we believe might straighten the planner till to reach performances which are at least comparable with other state-of-the-art planners.

The paper is organized as follows. Section 2 introduces the basic principles underlying the ILOC system, while Sections 3 and 4 detail the different heuristics that are currently explored. Section 5 shows how the system reasons about timelines while Section 6 compares the planner with others on some relevant planning domains. Finally, Section 7 presents a discussion on timeline-based heuristics in other planners, while Section 8 elaborates on the limitations emerging from our experience and identifies some directions for future work. Some conclusions end the paper.

2 ILOC: An integrated logic and constraint reasoner

In building our planner we have first created a reasoner based on first-order logic and constraint programming, then we have endowed such reasoner with some domain independent heuristics to improve the performance of the resolution process and, as a third step, we have introduced features to create a timeline-based planner. It is worth observing that the resulting planner is quite different with respect to the pre-existing purely constraint-based implementations – see later discussion in Section 7.

The basic core of the ILOC architecture provides an object-oriented virtual environment for the definition of objects and constraints among them. Similarly to most object oriented environments, every object in the ILOC environment is an instance of a specific type. ILOC distinguishes among primitive types (i.e., booleans, integers, reals, enums and strings) and user defined complex types (e.g., robots, trucks, locations, etc.) endowed with their member variables (variables associated to a specific object of either primitive or complex type), constructors (a special type of subroutine called to create an instance of the complex type) and methods (subroutines associated with an object of a complex type). Defining a navigation problem, for example, might require the definition of a Location complex type having two numeric member variables x and y representing the coordinates of each Location instance. In the following, we will address objects and their member variables using a dot notation (e.g., given a Location instance l, its x-coordinate will be expressed as l.x). Finally, we do allow multiple inheritance among types. Specifically, types can inherit characteristics and features from more than one parent type.

Once objects are defined, ILOC allows the definition of constraints among them. For example, in case a robot r should always be more East of a location l, the ILOC user could assert a constraint such 〚l.x < r.x〛. ILOC considers constraints as logic propositions (in constraint based literature such constraints are typically called reified constraints) and, as such, it allows the possibility for negating them (e.g., ¬ 〚l.x ≤ 5〛), for expressing conjunctions (e.g., 〚l.x ≤ 10〛 ∧ 〚l.x ≥ 5〛), disjunctions (e.g., 〚l.x ≤ 5〛 lor 〚l.x ≥ 10〛) and logic implications (e.g., 〚l.x ≥ 10〛 → 〚l.y ≥ 10〛). In order for a solution to be valid, such constraints must always be consistent among themselves therefore, whenever an inconsistency is detected (e.g., 〚l.x ≤ 10〛 ∧ 〚l.x ≥ 15〛), the system will return a failure or, as we will see soon, if within the search space, will perform a backtracking step.

In addition, it is possible to impose constraints on existentially quantified variables (e.g., ∃l ∈ Locations : l.x ≥ 10) as well as universally quantified variables (e.g., ∀l ∈ Locations : l.x ≤ 100). By combining logical quantifier and object oriented features, ILOC allows to manage, in one shot, all the instances of a given complex type. Specifically, in case of existentially quantified variables, the system will introduce a new enumerative variable, whose initial domain (i.e., its initial allowed values) will contain all the instances of the type of the variable, and whose value, once assigned, will identify the object on which the constraint is enforced (e.g., in the above example, the new variable will be the location l such that l.x ≥ 10). Universally quantified variables are, clearly, much easier to be managed since they do not require any variable to be added and the constraint (e.g., l.x ≤ 100 in the above example) is simply enforced on all instances of the type of the variable.

A rather straightforward method for managing this kind of problems is to translate them into a Satisfiability Modulo Theories (SMT) problem (see, for example, [33]). SMT is the problem of deciding the satisfiability of a formula with respect to some theory. In particular, the theories we are interested in are those of Linear Arithmetic (LA) and Nonlinear Arithmetic (NLA) over both Reals and Integers. Since SMT checks the satisfiability of a formula over a theory, SMT solvers support natively reified constraints, therefore we can easily express any combination of numerical constraints. Furthermore, SMT solvers are generally endowed of incremental features, providing support for the addition and the retraction of variables and constraints through a stack. Such features, we will see soon, are essential for allowing our solver to backtrack and thus for guaranteeing a complete search during the resolution phase. There are several available SMT solvers having different performances and capabilities (e.g., linear vs non-linear mathematical constraints). Since ILOC is written in Java the only available choices are, to the best of our knowledge, the SMTInterpol [10], the MathSAT 5 [12] and the Z3 [18] solvers 2 . It is worth highlighting the fact that we have chosen to use SMT technology mostly for their incremental features. Indeed, any incremental constraint based solver would have been equivalent. Since the translation is straightforward, it will not be described here.

2.1 Rules and requirements

Although this basic core allows the definition of quite complex problems, some of the problems we are interested are excluded from the possibility of being modeled with this formalism. In order to overcome these limitations, we need something more powerful. Something that, roughly speaking, is able to “decide” the number of involved variables, together with their value. For this purpose, we have chosen to extend the above formalism by allowing many-sorted first-order Horn clauses 3 , i.e., clauses with at most one positive literal, called the head of the clause, and any number of negative literals, forming the body of the clause. For example, we could use a predicate such as FirstQuadrant, with a Location l argument, within the clause FirstQuadrant (Location l) ⇐ 〚l.x ≥ 0〛 ∧ 〚l.y ≥ 0〛, for describing locations in the first quadrant of a Cartesian coordinate system. Furthermore, we do not allow constraints in the head of a clause but we slightly relax the “positive” literals in the body by allowing constraints to appear in any logical combination (i.e., we could rewrite the above example as FirstQuadrant (Location l) ⇐ ¬ 〚l.x < 0〛 ∧ ¬ 〚l.y < 0〛). We exploit this implication-based syntax by analogy with logic programming. By exploiting De Morgan’s laws 4 , it should not be a problem, for the reader, to recognize the equivalence with the clausal form.

A consequence of what we have seen is that ILOC planning problems can be described by a collection of clauses. There are two types of clauses: rules and requirements. A rule is of the form Head ⇐ Body. While the head of the rules is limited to predicates, a rule’s body consists of a set of calls to predicates (either facts or goals, in the latter case we talk about sub-goals) and a set of constraints, the latter, in any logical combination. We consider rules having the same head as disjunctive. Clauses with an empty head are called requirements and can be calls to predicates (either facts or goals) or constraints, the latter, in any logical combination. Example of requirements are FirstQuadrant (Location l), 〚l.x ≥ 5〛 and 〚l.y ≥ 5〛, through which we are asking the planner to find a location l, among those which are in the first quadrant, having both coordinates greater than or equal to 5. Clearly, we can share the same syntax to define both the bodies of the rules and the collection of requirements.

The distinction between rules and requirements allows us to make a comparison with classical planning theory. Specifically, the set of rules represents what, in classical planning, is typically called domain theory (or, interchangeably, domain model) while the set of requirements represents what, in classical planning, is typically called a problem. Furthermore, in common classical planning languages, it is customary to define types within domain models and their instances (i.e., the objects) within planning problems. A detailed description of the input language is out of the scope of this document. However, it is worth noting that a complete problem is described by (i) the definition of the types, (ii) the rules, (iii) the type instances and (iv) the requirements. As regards the solution, this is completely described by a set of requirements in which any call to a predicate is a fact (i.e., there are no goals in a solution).

It is worth highlighting that, contrary to what happens in common logic programming, we do allow variables in fact atoms. This allows us to easily model pure scheduling problems and, furthermore, to easily model classical planning causality (we will see an example later on). However, a consequence of this is that, unlike logic programming, we cannot use capitalization to distinguish between facts and goals. We need, therefore, to explicitly annotate atoms in order to distinguish them (i.e., goal : FirstQuadrant (Location l) is a goal while fact : FirstQuadrant (Location l) is a fact). Finally, we consider atomic formulas as objects (and predicates as types) within our object oriented environment and, as such, they have an identifier which can be used, by means of the dot notation, to address their arguments and to use them within constraints. Therefore, given a predicate as At (Location l) representing, for example, the position of a robot, we might define a problem as, for example, fact:at0 : At (), goal:at1 : At () and at0 . l ! = at1 . l (notice the identifiers at0 and at1 for the atoms and their use within constraints). Each time a new atomic formula object is created, a new existentially quantified variable is added for each of the arguments of its predicate. For example, when creating the fact fact:at0 : At (), a new object variable, whose allowed values are all the instances of Location, is created and associated to the fact at0.

2.2 The resolution algorithm

From an operational point of view, ILOC uses an adaptation of the resolution principle [32] for first-order logic, extended for managing constraints in the more general scheme usually known as constraint logic programming (CLP) [1]. Starting from the initial set of objects (we recall that both facts and goals are objects) and constraints, as described by the initial requirements, the reasoner maintains an agenda of the current (sub)goals. Incrementally, the system chooses (sub)goals from the agenda and, by exploiting rules, adds facts and constraints into the working memory.

Figure 1 shows a general description of the ILOC reasoning engine. Specifically, the system maintains a set of rules (i.e., the domain theory). A working memory maintains information about the current objects and the current constraints among such objects. An agenda maintains information about all the goals to be solved. Finally, an inference engine has the dual role of solving all the goals of the agenda while maintaining consistent all the constraints among the objects.

Initially, the working memory contains all the requirements. For each goal $P (t_{1}^{g}, \dots, t_{i}^{g})$ in the agenda, in general, a branch in the search space is created. Resolution, at first, will try to unify goals with compatible facts already present in the working memory, if any, creating a single branch for all the eligible candidates. Specifically, given the existing facts $P (t_{1}^{1}, \dots, t_{i}^{1}), \dots, P (t_{1}^{j}, \dots, t_{i}^{j})$ , having the same predicate of the goal, the formula $〚 t_{1}^{g} = t_{1}^{1} \land \dots \land t_{i}^{g} = t_{i}^{1} 〛 \dots 〚 t_{1}^{g} = t_{1}^{j} \land \dots \land t_{i}^{g} = t_{i}^{j} 〛$ (we will say, in short, p_g ≡ p₁lor … lorp_j) is added to the working memory and the goal is removed from the agenda. In addition, a branch is also created for each of the rules whose head unifies with the chosen goal and, whenever such a branch is chosen by the resolution algorithm, the body of the corresponding rule is added to the working memory possibly generating further facts, goals and constraints to be managed. Also in this case, since the chosen goal has been solved, it is removed from the agenda however, contrary to the unification case, this goal is now considered as a new fact within the working memory.

The final aim of the resolution process is, therefore, to remove all the goals from the agenda. At the end of the resolution process, from a logical point of view, all the goals might be seen as a consequence of the application of a rule. Intuitively, the purpose of unification is to avoid considering those goals whose (any) rule has already been applied. Needless to say that all the constraints among all the objects of the working memory must be satisfied.

Summarizing, the basic operations for refining the working memory π toward a final solution are the following:

Find all the (sub)goals of π (i.e., the agenda).

Select one such (sub)goals.

Find ways to resolve it (i.e., find all the possible unifications and all the rules which might be applied).

Choose a resolver for the (sub)goal (i.e., either unify with an existing fact or choose a compatible rule).

Refine π according to the chosen resolver.

The process follows an A* search strategy that aims at minimizing the number of goals in the agenda, proceeding until there are no more goals into the agenda and while all the constraints in the working memory are consistent. As briefly mentioned earlier, whenever the constraints become inconsistent the system performs a backtracking step.

Figure 2 shows how this process is applied to the simple problem depicted. We have shortened goal in g for space reasons and used a color schema for distinguishing facts from goals (i.e., orange circles represent goals and green circles represent facts). Furthermore, we have used different variable names to further highlight the differences between the rules space and the working memory. At the beginning, the two goals a₀ and b₀ need to be resolved, so, for example, the former is chosen. Since unification with already existing facts is not possible (there is no fact yet in the current working memory), the first rule is applied, resulting in the addition of sub-goal goal:b : B (y) and constraint 〚x < b.x〛. At this point, goal b₀ is chosen. Again, unification is not possible so the second rule is applied, resulting in the addition of constraint 〚x < 10〛. Last goal to be solved is subgoal b. Since unification is now possible, we create a branch in the search space creating two nodes (i.e., Node 1 and Node 2) and in the former we unify formulas b and b₀ (by adding the constraint 〚v = y〛) while in the latter we apply the second rule a second time. It is worth noting that by selecting b₀ at the first step, although with different paths, we would have got the same two final nodes. In addition, since the first two steps do not require choices, there is no need for creating a branching and the resolution can continue “inside” Node 0. Finally, both the resulting nodes represent a solution for our starting problem (i.e., no goals in the agenda and consistent constraints) and thus the resolution process can terminate. Clearly, the presence of additional (sub)goals would have required further unifications and/or rules applications.

3 The ALLREACHABLE heuristic

Since all the goals must be solved sooner or later, there is almost no difference among which goal is solved first. Selecting the “right” goal, however, impacts heavily with the efficiency of the resolution algorithm. In order to overcome this obstacle we can take advantage of some heuristics. It is worth to highlight the fact that, in general, for solving our problem, two heuristics are needed. Specifically, we need an heuristic for selecting the right goal to be solved in the current node of the search space and an heuristic for selecting the next node of the search space from the fringe. This is similar to what happens in Constraint Satisfaction Problems (CSP) in which a variable selection heuristic, for selecting the next variable, is flanked by a value selection heuristic, for assigning a value to the selected variable. Given the similarity with CSPs, we also refer to our approach with the term Meta-CSP.

As a first attempt (see [16] for further details) in producing our heuristics we have created a data structure, called static causal graph (since it does not change during the resolution process), aimed at producing some kind of information which might be used to guide the search process. Our graph has a node for each of the predicates that appear in our rules and, for every rule, an edge from the head of the rule to each of the predicates that appear in the body of the same rule. The main idea was to create a simple data structure (keeping GraphPlan as a reference) that would have taken into consideration something more than the sole objects in the current working memory. Such a data structure would have allowed us to reason, in a limited way, about all possible plans, producing a wider view of the problem to be solved.

Initially, we considered the estimated cost for solving a goal (i.e., the estimated cost of our equivalent of variable selection heuristic) as the number of reachable nodes from the node relative to the predicate associated to the goal. We called such a strategy “All Reachable - Goal Selection Heuristic” (ALLREACHABLE). The idea behind the ALLREACHABLE strategy is to evaluate goals by considering a kind of worst case scenario where none of the formulas unify. Figure 3 shows the static causal graph resulting from the rules of Fig. 2. As an example, the cost for solving an A goal, according to ALLREACHABLE, is 1 (since the sole node B is reachable from node A) while the cost for solving an E goal is 4 (since all the nodes F, G, H and I are reachable from node E). Clearly, this graph and, consequently, the costs for each of their nodes, solely depends on the rules, therefore, our heuristic is problem independent and thus can be built once and for ever at the beginning of the solving process (hence the name static), allowing constant-time cost retrieval.

At first, we did not consider at all the possible disjunctions (resulting from rules having the same head) of the domain theory, nor the arguments of the predicates nor the constraints among the objects. In order to mitigate this oversight, we selected nodes from the fringe of the search space according to another heuristic (i.e., the estimated cost of our equivalent of value selection heuristic). By considering the resolution process as an optimization problem, the first choice was to choose the node having the least unresolved (sub)goals. Better than nothing, such a strategy did not appear smart enough since it completely ignored the kind of involved (sub)goals. A slightly better strategy consists in reusing the idea behind ALLREACHABLE by considering the distance of a node from the solution of the problem as the sum of the costs for solving all its goals. We called such a strategy “All Reachable - Node Selection Heuristic”. The estimated cost for managing Node 0 of Fig. 2, for example, is now equal to the estimated cost for solving goal the goal a₀ (i.e., 1) plus the estimated cost for solving goal b₀ (i.e., 0). It is worth noting that both the presented strategies for selecting the next goal and the next node, are not admissible heuristics since they can easily overestimate the cost for solving a goal (e.g., by neglecting some unification), therefore the A* search strategy does not guarantee to find an “optimal” solution in terms of minimum number of steps.

To sum up, when choosing the next goal to be solved, we choose the goal having the minimum estimated cost, when choosing the next node to be solved, we choose the node having the minimum estimated distance from the solution. The fact that the ALLREACHABLE heuristic was too uninformative did not even allow us to see that the first heuristic (i.e., choosing the goal having the minimum estimated cost) was clearly a mistake, violating the basic principle of solving the most difficult problems first.

4 The MINREACH heuristic

A slight improvement to our heuristic is constituted by the addition of disjunctions into the static causal graph by means of two special nodes representing conjunctions (AND nodes) and disjunctions (OR nodes). Figure 4 shows the improved static causal graph generated from the example in Fig. 2. The cost for solving a goal is now evaluated as the minimum number of reachable nodes starting from the node associated to the goal predicate. The general idea here was the following: whenever the resolution algorithm finds a disjunction, the application of the rule that would lead to the minimum number (notice that we are persevering in the above mistake!) of formulas should be chosen. We call such a strategy MINREACH. As an example, the cost for solving a G () goal is now reduced from 3 to 1 since all the nodes F, H and I are reachable from node E, yet introducing a sole formula I () (second rule associated to predicate G) is probably preferable than introducing both formulas F () and H () (first rule associated to predicate G), and far more preferable than introducing all the three formulas F (), H () and I () as expected by heuristic ALLREACHABLE.

One might argue that by introducing disjunctions into the static causal graph we increase the complexity of the evaluation from polynomial to exponential. However, just as for the ALLREACHABLE heuristic, this graph and, consequently, the costs for each of their nodes, solely depend from the rules, therefore, our heuristic is independent from the requirements (notice that we are neglecting some precious information!) and thus can be built once and for all at the beginning of the solving process, allowing constant-time cost retrieval. Nevertheless, the problem can easily be encoded into a MIN-ONE SAT problem (i.e., given a propositional formula, if it is satisfiable, find the variable assignment that contains the minimal number of positive literals) and let a SAT-solver (e.g., Sat4j [26]) solve it for us. The encoding is trivial:

a boolean variable is associated to each predicate and to each AND node;

for each arc 〈s, t〉, going from source node with boolean variable s to target node with boolean variable t, a clause (¬ s, t) is added;

for each arc 〈s, OR〉, going from source node with boolean variable s to an OR target node, we consider the variables b₁, …, b_n associated to all the n nodes directly reachable from the OR node and a clause (¬ s, b₀, …, b_n) is added.

Each predicate can now be evaluated as follows: we assume a unit clause containing the variable associated to the predicate we want to evaluate, solve the resulting MIN-ONE SAT problem, count the number of positive literals associated to predicates and subtract 1, since we don’t count the starting node. As an example, the resulting MIN-ONE SAT problem associated to predicate G of Fig. 4 is the following (we use lowercase names for the associated boolean variables): $\begin{matrix} (g) (\neg a, b) (\neg c, d) (\neg e, f) (\neg e, g) \\ (\neg g, and, i) (\neg and, f) (\neg and, h) \end{matrix}$ resulting in the sole g and i positive literals and, consequently, in an estimated cost of 1.

Similar to what we did for the ALLREACHABLE heuristic, we exploit the MINREACH heuristic both for goal selection and for node selection. It is worth to note that, in case of a classical planning problem, having as possible atoms the sole nodes of our static causal graph, our MINREACH heuristic is analogous to the well known h_max heuristic [5]. Another way of looking at our MINREACH heuristic, indeed, is to consider the h_max heuristic on a classical planning problem in which we are not taking into account the arguments of the predicates nor the parameters of the actions.

5 Timeline-based planning and ILOC

As we will see in this section, the logic-based formalism introduced in the previous sections is powerful enough to represent timelines. Furthermore, the proposed heuristics are not strictly limited to the timeline-based planning problems. The search space of a timeline-based planner, however, has typically partially specified plans as nodes and plan refinement operations as arcs. A partially specified plan maintains causal and temporal relations among timely scoped formulas (usually called tokens) and, therefore, is really similar to the working memory of the ILOC reasoner. Plan refinement operations are intended to further complete a partial solution, i.e., to achieve an open goal or to remove some possible inconsistency. In this section, we will extend the resolution algorithm for managing such inconsistencies.

A possible approach to the modeling of timeline-based planning problems is to endow the predicates described in the previous sections with numerical arguments in order to represent timely scoped atomic formulas 5 . Such atoms represent the assertion of a certain fact within a given time interval. For example, the formula At (r, l, s, e, d) might be used for representing the presence of a robot r in the location l from time s (for start) to time e (for end) for a duration d. This expedient, however, is not enough to detect all the inconsistencies. We need some specialized algorithms which understand the proper semantic of such numerical arguments recognizing them as temporal information. Unfortunately, such algorithms are dependent on the specific kind of timeline. One possibility which we have pursued is to exploit the complex types of the ILOC reasoner. In particular, we have defined some specific complex types, whose instances will be called timelines, which, according to their implementation, add further “implicit” constraints (e.g., ordering constraints) among the arguments of the atoms. This will also result in a slight adaptation of the resolution procedure in order to check the consistency for every object in the working memory so as to make explicit, by invoking the above mentioned specialized procedures, these implicit constraints.

Unlike most of the timeline-based planners which consider timelines as a sort of “containers” for the atomic formulas, we simply add a parameter, having the same type as the timeline, to the predicates and call such a parameter scope. The type of our scope variables will be a “distinguisher” for triggering further reasoning required by the specific timeline. Furthermore, the resulting scope variables are, to all effects, variables and, therefore, could be subject to constraints. In the following we will describe some of these timelines, commonly used in timeline-based planning, providing some intuition of their specialized algorithms.

State variables They are used to describe the “state” of a dynamical system as, for example, the position of a specific object at a given time or a simple manufacturing tool that might be operating or not. The semantics of a state variable (and thus the implicit constraints we need to make explicit) is simply that, for each time instant $t \in 𝕋$ , the timeline can assume only one value. Figure 5(a) represents an example of state variable with three atomic formulas (parameter types are omitted for sake of space). The example shows a robot r₀, a state variable of type Robot, which might be At a given location or might be Going to another location. We thus have the two predicates At (sc, l, s, e, d) and Going (sc, l, s, e, d) each having a parameter sc of type Robot describing the scope of the formulas and parameters l, s, e and d respectively for the location, the start, the end and the duration. The planner will take care of adding the proper constraints for avoiding the temporal overlapping of the incompatible states (i.e., all the formulas which have the same scope and do not unify) or for “moving” the states on other instances of type Robot (i.e., choosing another value, for example r₁, for the scope of the formula).

Resources They are entities characterized by a resource level $L : T \to R$ , representing the amount of available resource at any given time, and by a resource capacity $C \in R$ , representing the physical limit of the available resource. We can identify several types of resources depending on how the resource level can be increased or decreased in time. A consumable resource is a resource whose level is increased or decreased by some activities in the system. An example of consumable resource is a reservoir which is produced when a plan activity “fills” it (i.e., a tank refueling task) as well as consumed if a plan activity “empties” it (i.e., driving a car uses gas). Consumable resources have two predefined rules, each having an empty body, and a predicate Produce (sc, id, a, s, e, d) (Consume (sc, id, a, s, e, d)) as head, so as to represent a resource production (consumption) on the consumable resource sc of amount a from time s to time e with duration d (we use an id parameter to prevent unification among these formulas). In addition, the consumable resource complex type has four member variables representing the initial and the final amount of the resource, the min and the max value for the resource level. Quite popular in the scheduling literature, reusable resources are similar to consumable resources where productions and consumptions go in tandem at the start and at the end of the activities. Reusable resources can be used for modelling, for example, the number of programmers employed on a given project for a given time interval. Reusable resources have one predefined rule having an empty body and a predicate Use (sc, id, a, s, e, d) as head so as to represent an instantaneous production of resource sc of amount a at time s and an instantaneous consumption of the same resource sc of the same amount a at time e. In addition, the reusable resource type has a member variable for representing the capacity of the resource. Figure 5(b) and (c) represent, respectively, an example of consumable resource and an example of reusable resource with some associated formulas.

Enhancements to the reasoner By introducing these complex types, we require the reasoner to add further constraints so as to avoid object inconsistencies (e.g., different states overlapping for some state variable; resource levels $L$ exceeding resource capacity $C$ or going lower than min, etc.). We chose to refine our resolution process by introducing a step for detecting such inconsistencies and for adding required constraints which would remove them. The resulting basic operations for refining the working memory π toward a final solution are thus the following:

Find the (sub)goals of π.

Select one such (sub)goals.

Find ways to resolve it.

Choose a resolver for the (sub)goals.

Refine π according to that resolver.

Check for any object inconsistency and remove it.

Similar to [8], we use a lazy approach for detecting inconsistencies. Namely, we let the underlying SMT solver to extract a solution given the current constraints and, in case some inconsistency is detected we add further constraints so as to remove the inconsistency. A simple example should clarify the idea. Let us suppose in a given working memory there are two formulas describing a state variable sv_k having two overlapping states s_i and s_j, we solve the inconsistency by adding the constraint 〚s_i . start ≥ s_j . end〛 lor 〚s_j . start ≥ s_i . end〛 lor 〚s_i . scope ≠ s_j . scope〛 preventing further overlapping of these states on the same state variable. The core idea for solving resource inconsistencies follows a very similar schema.

6 Planner evaluation

To assess the value of our heuristics, we have endowed ILOC with the proposed MINREACH (MR) and ALLREACHABLE (AR) heuristics and tried to compare the resulting system with different planners on different benchmarking problems. Specifically, we have selected three planners that are interesting for their features and compared them with ILOC : VHPOP [34] shares with our planner the partial ordering approach, OPTIC [2] and COLIN (see [13]) are both based on a classic FF-style forward chaining search [24]. All the tests have been executed with default configurations for every planner. It is worth to say that, although VHPOP is slightly dated, both OPTIC and COLIN are quite recent works.

The problems We start the comparison by solving the Blocks World domain, a workhorse for the planning community. As known, in this domain a set of cubes (blocks) are initially placed on a table. The goal is to build one or more vertical stacks of blocks. The catch is that only one block may be moved at a time: it may either be placed on the table or placed atop another block. Because of this, any blocks that are, at a given time, under another block cannot be moved. We used the 4-operator version of the classic Blocks World domain, as found on the International Planning Competition (IPC) website 6 , as a starting point. Furthermore, we use a simpler variant of the general problem (usually called Tower) in which, at the initial state, all the blocks are on the table and whose goal is to stack all the blocks on a single tower. Specifically, for each block, we defined a state variable for representing what is on top of the block (i.e., either another block or the value “Clear”) and a state variable for representing if the block is on the table or not. An additional state variable has been defined for modeling the robotic arm supporting values that represent either the arm holding a block or the value “Empty”. Finally, we defined an “Agent” complex type for modeling the agents’ actions. Rules have been defined so as to have an atomic formula for each effect of the PDDL actions as head and an atomic formula for the actions as body (modeled as a subgoal), aside from rules having an atomic formula for each PDDL action as head and an atomic formula for their preconditions (modeled as subgoals) and effects (modeled as facts) as body. By modeling the effects of the actions through facts we avoid the introduction of further subgoals into the agenda when applying the rule associated to the action. Temporal constraints have been conveniently added for guaranteeing that preconditions precede actions and effects follow actions.

We have also checked our system with two other problems, namely the Temporal Machine Shop [15] and the Cooking Carbonara domain [27]. Both these problems are temporally expressive (see [14]) since they require concurrency for being solved. Domain models and instances have been taken from the TLP-GP planner website 7 .

The Temporal Machine Shop problem is the only temporally expressive problem of the IPC and, up to now, in the various editions of the competition, it is solved by the sole ITSAT planner (see [31]). The problem models a baking ceramic domain in which ceramics can be baked while a kiln is firing. Different ceramic types require a different baking time. While a kiln can fire for at most 20 minutes at a time (and then it must be made ready again), baking a ceramic takes, in general, less time, therefore we can save costs by baking them altogether. Additionally, similar to [31], we have slightly complicated the domain by considering the possibility for ceramics to be assembled, so as to produce different structures which should be baked again to obtain the final product. Specifically, for each kiln we defined a state variable for distinguishing either the kiln is “Ready” or “on Fire”. In addition, each kiln has associated a reusable resource for representing its capacity. For each ceramic piece we defined a state variable for representing either the piece is “Baking” (with an additional parameter for representing the kiln in which is baking), or the piece is “Baked”, or the piece is “Treating”, or the piece is “Treated”. Similarly, for each ceramic structure we defined a state variable for representing either the structure is “Assembling”, or the structure is “Assembled”, or the structure is “Baking” (with an additional parameter for representing the kiln in which it is baking), or the structure is “Baked”. Rules force these values to appear in time, in each state variable, in the intuitive manner (i.e., in the order in which these values have just been introduced). The interesting aspect, however, is that ceramic structures can bake concurrently with ceramic pieces both while (hence the temporal expressiveness) the kiln is firing.

The Cooking Carbonara domain represents another temporally expressive problem in which the aim is the preparation of a meal, as well as its consumption by respecting constraints of warmth. Problems cooking-carbonara-n allow to plan the preparation of n dishes of pasta. The concurrency of actions is required to obtain the goal because it is necessary that the electrical plates work in a way that water and oil are hot enough to cook pasta and bacon cubes. It is also necessary to perform this baking in parallel to serve a dish that is still hot during its consumption. Specifically, for each plate we defined a reusable resource for representing its (unary) capacity. For each pot we defined a state variable for distinguishing either the pot is “Boiling” (with an additional parameter for representing the plate on which is boiling) or the pot is “Hot”. For each pan we defined a state variable for distinguishing either the pan is “Boiling” (with an additional parameter for representing the plate on which is boiling) or the pan is “Hot”. Each portion of spaghetti has associated a state variable for distinguishing either the portion is “Cooking” (with an additional parameter for representing the pot in which is cooking) or the portion has been “Cooked”. For each bacon portion we defined a state variable for distinguishing either the bacon is “Cooking” (with an additional parameter for representing the pan in which is cooking) or the bacon has been “Cooked”. Each egg has associated a state variable for distinguishing either the egg is “Being beaten” or the egg has been “Beaten”. Finally, for each carbonara portion we defined a state variable for distinguishing either the portion is “Cooking” (with an additional parameter for representing the plate on which should be cooked), or the portion has been “Cooked”, or someone is “Eating” the portion or the portion has been “Eaten”. Again, rules force values to appear in time, in each state variable, in the intuitive manner (i.e., in the order in which these values have just been introduced). Furthermore, carbonara portions should be cooking after spaghetti, bacon and eggs have been correctly prepared, hence requiring spaghetti to be “Cooking” while the water in pots is “Hot” as well as bacon to be “Cooking” while the oil in pans is “Hot”. Finally, cooking carbonara portions, boiling water in pots and oil in pans should be performed while plates are available.

Results and discussion Starting from the blocks world (the problem where causal reasoning is paramount), we can see, Fig. 6, that despite the introduction of our heuristics, planners endowed with “classical heuristics” still perform significantly better than our approach. Thanks to the MINREACH heuristic, however, we were able to boost the system performance appreciably, allowing us to find solutions up to, approximately, one third of the time it was required before. Such partial results for ILOC should not come as a surprise since its current heuristics, as already said, neglect much of the precious information like the initial working memory, the constraints among objects and the constraints defined within rules. Not considering such information is, probably, the explanation for the performance gap still existing between ILOC and COLIN or OPTIC – both planners coming from a longer history about causal reasoning.

Experimental results on the other domains (Figs. 7 and 8) show that ILOC performs competitively with respect to COLIN and OPTIC. It is worth observing that the heuristics neither guarantee a substantial improvement nor their overhead produces a significant worsening (performance remains almost unchanged). This is explained by the fact that the temporal/resource reasoning features of ILOC are not much affected by the causal heuristics. Furthermore, even though COLIN performs better than ILOC, it is not able to solve problems with more than 50 ceramics since it runs out of memory (we used the default configuration for the planner). This aspect is much more evident in the Cooking Carbonara domain which, since it does not contain a maximum duration for plate firing, can be easily reduced to a basic scheduling problem and, as such, more classical planners suffer more in scaling.

A separate discussion it is worth doing concerns the expressiveness of ILOC. All the competing planners use the PDDL2.1 language (see [21]) for modeling their planning problems and, in general, it is quite cumbersome to impose temporal constraints among plain PDDL actions. In the Cooking Carbonara domain, for example, it is important that the cooking happens before the eating but eating should not start too late to avoid that food becomes cold. In [27] a PDDL extension is proposed to overcome this issue and to model properly the domain, however, none of the available planners supports this extension and thus they have been evaluated in a simplified domain in which the warmth constraint decays and dishes can be served anytime after they have been cooked. It is worth noting how this constraint is naturally captured in the ILOC modelling language by creating a rule having as head an action and as body a second action in conjunction with a constraint among the temporal parameters of the two actions.

Managing execution uncertainty We now address a different perspective for evaluating ILOC features. When tackling with plans, indeed, a key aspect to consider is that they have to be executed and, when executed, failures are not uncommon. When dealing with dynamic environments, further constraints might become available at execution time requiring the adaptation of the plan to some real needs or, in some cases, a complete replanning step. Since replanning is often an expensive task, requiring solving a PSPACE problem, generating flexible plans that might be slightly adapted at execution time is highly desirable.

Consider, for example, a simple logistic company having a fleet of two trucks (see Fig. 9). The two tasks t₀ and t₁ are scheduled for Truck 1 respectively from 10:00 to 12:00 and from 13:30 to 15:30. Although task t₀ can be slightly postponed, we have a further constraint asserting it must end strictly before 17:00. However, in order to avoid penalties with its customer, task t₁ must be executed exactly at the scheduled time. Now suppose that at 9:55 our logistic company discovers that Truck 1 has some problem at the engine. Since estimated repair time is one hour, we could temporally adapt the plan for starting t₀ at 11:00 (we achieve this by adding the constraint 〚t₀ . start > =11〛). This kind of temporal adaptation is quite common for any planning and execution environment (see, for example, [30] and [6]) up to be considered mandatory. Now imagine at 10:55 we discover that repair time was underestimated and a further hour is required. By moving t₀’s start time at 12:00 we would interfere with task t₁, scheduled for time 13:30. Clearly, given these constraints, a replanning phase would assign task t₀ to Truck 2. However, by exploiting the scope parameter introduced earlier, we can adapt the plan by reassigning task t₀ and thus avoiding a possibly time consuming replanning phase. We recall that the scope parameter is indeed a variable, and therefore we can let the reasoner choose a value for it according to involved constraints. In other words, similar to what happens for temporal adaptation, we can perform also more complex forms of adaptation, including this kind of “causal” adaptation. It could be argued that such an adaptation could be expensive as well and, indeed, it is exponential in the worst case. Nevertheless, the underlying constraint solver allows efficient constraint propagation, making the adaptation process negligible, with respect to a complete replanning process, on the simple problems that we have used for testing this kind of flexibility.

7 About timeline-based planning heuristics

Despite some performance issues on some specific domains, thanks to the expressive representation capabilities of the ILOC framework we can represent and reason on a significant amount of domains. A consequence of our logic based approach, as we have seen, is that ILOC differs significantly from other timeline-based planners. In contrast to APSI-TRF or to the formalization described in [11], for example, we maintain a clear distinction between state variables and state machines. The reason for this choice is that state machines, if needed, can be modeled by means of rules. On the contrary, modeling undecided behaviors for a state machine might be cumbersome. Furthermore, our logic based formalism allows to model resources in a way which is more close to how they are managed in scheduling literature.

Similarly to Europa, we allow the possibility to define facts within rules. Although it might seem unsuitable, from a formal point of view, this possibility allows, among other things, a more efficiently modeling of classical planning causality. In classical planning, indeed, the effects of the actions are supported by the actions themselves and, once the actions have been introduced into the plan, there is no need for justifying their effects. The translation we have used in our experiments, for example, represents the effects of the actions through facts. If we deprive of the possibility of defining facts within rules we should justify the effects either by unifying them with some other fact or by applying another rule. The latter case would, clearly, further degrade performance.

The performance aspect, however, remains still open. Despite the formalization would remain valid, some of our latest studies are gradually leading us to reconsider the concepts at the core of the framework. The main learned lesson, indeed, is that reasoning about the sole elements within the current partial plan might not be sufficient for producing adequately informative heuristics. Although in a limited way, GraphPlan and other planners based on heuristic search allow to reason, at once, about all possible plans (all the plans achievable unfolding the domain theory). In developing the ALLREACHABLE and the MINREACH heuristics we tried to reproduce these capabilities. The representation of such possible plans within our heuristics, however, is currently too weak, leading to too uninformed search strategies. The above heuristics completely ignore the constraints within the rules’ bodies, solely relying on the pure causality relations among predicates. Similarly, objects and constraints coming from the requirements and, therefore, initially appearing in the working memory, are neglected as well. All this information is directly available from the domain theory and from the initial problem.

Reasoning about the sole elements within the current partial plan also appears in other similar planners including APSI-TRF and Europa. Worth mentioning is the CHIMP planner [36] that shares with ILOC both the expressiveness and the Meta-CSP approach. The meta-Constraints used in CHIMP are not much different from our “timelines”. Through the use of the scope variable and the introduction of a new complex type, as described above, ILOC could carry out some specific path planning reasoning, going beyond the type of reasoning strictly related to timelines. However, although the CHIMP heuristics are not extensively detailed, they supposedly rely on (i) giving priority on unifications, (ii) preferring nodes with a lower number of subtasks to expand and (iii) binding preconditions to fluents with a later starting time. All of them, apparently, rely on the sole elements within the current partial plan and are likely to overlook possible subsequent plan refinements.

Some ILOC features are also shared with the FAPE [20] planner. Similarly to CHIMP, FAPE combines the expressiveness of the timeline-based approach with the decomposition of HTN methods. In this regard, it is worth noticing how task decomposition can be easily obtained by means of our first-order based rules. As stated by the authors, the FAPE motivation is not efficient planning per se, but the tight integration of acting and temporal planning with task decomposition. Although efficiency is not the main objective, we believe that FAPE could possibly benefit from some of the ideas pursued in this paper.

In the next section we will discuss some of the reasons for the blindness of the heuristics. We will then try to provide some guidelines which might lead, in future works, to bridge the performance gap between classical and timeline-based planning.

8 Directions for further work

Finding the right balance between the informativeness and the computational complexity of an heuristic is not an easy task. In any case the current level of informativeness is not satisfactory and should be increased. A first refinement step for the future might be to consider the initial state of the working memory. Consider again the graph in Fig. 4. Now suppose two facts F () and H () are initially present in the working memory. We might imagine that eligible subgoals, coming from the application of the rules, will eventually unify with the above facts. We might consider such information for enhancing the informativeness of the heuristic by pruning, in general, the causal graph. In such a circumstance, indeed, the cost for solving a G () goal is now further reduced from 1 to 0. Indeed, despite they are two, we might consider the atoms F () and H () preferable, since they will be unified, compared to the sole formula I ().

Indeed, it is possible to do more. Consider again the graph in Fig. 4. The two edges incoming into node F represent the unification of two atoms having predicate F. Now suppose predicate F has some argument as, for example, an integer i. Suppose, also, that the body of the rule, having E as head, contains a constraint 〚i > 0〛, while the body of the rule, having G as head, contains, in addition to F, a constraint 〚i < 0〛. Clearly, the two atoms will never unify. Now, despite the initial state, the preferable choice for the disjunction associated to predicate G () goes back to being the sole formula I (). Furthermore, similar constraints might also be present in the initial state of the working memory.

Neglecting this information seems a valid reason for not scaling well, especially on causally biased domains. It is less clear how to consider this information within the heuristics and, therefore, how to overcome our performance issues. If we want to consider more information within our heuristic, a possible path to follow might be to replace predicates directly with atoms in our causal graph. Unfortunately, this transition is not as straightforward as it might seem. We will provide, in the next sections, some insights on how it can be achieved.

8.1 The constrained causal graph

In order to replace predicates with atoms, we should create a data structure which (i) does not propagate constraints in case of disjunctions (we recall that such disjunctions represent branches in the search tree), yet (ii) powerful enough to propagate constraints that allow us to recognize ineligible unifications.

The first of our problems can be easily solved through simple arc-consistency techniques (see, for example, [19]). Roughly speaking, a variable of a Constraint Satisfaction Problem (CSP) is said to be arc-consistent with another one if each of its admissible values is consistent with some admissible value of the second variable. Specifically, a variable x_i is arc-consistent with another variable x_j if, for every value a in the domain of x_i there exists a value b in the domain of x_j such that (a, b) satisfies any binary constraint between x_i and x_j. We might use bound consistency to represent numeric variables domains and, whenever possible (i.e., in case of linear constraints), we will apply incremental Gauss-Jordan elimination [28]. Now, what happens if constraints are not binary? Arc-consistency is not powerful enough to propagate such constraints. However, since we do not want too much propagation, what might seem a limitation of this local consistency technique turns out to be, actually, a strength.

Concerning the second issue, similarly to the InPlan variables of CPT [37], for each atomic formula p, we might create an enumerative variable state (p)∈ { Inactive, Active, Unified } indicating the state of the atom p. Specifically, an atom p might be inactive, in which case it is not considered within the current working memory, might be active, in which case it is considered within the current working memory, or might be unified with an already active formula. The trick is to constraint these variables among themselves, together with the reified constraints coming from rules, in order to represent, in a limited way, the causality of the different plans emerging both from the rules and from the initial working memory. To check whether a formula p is not unifiable with a fact f it would be enough to check if the constraints state (p) ={ Unified }, state (f) ={ Active } and p ≡ f would make the problem inconsistent.

We call this arc-consistency based network, representing both constraints and causal relations, constrained causal graph. We would build such a graph incrementally, starting from the initial working memory. In analogy with classical planning, we might call action both the application of a rule and a unification of a goal with a fact. We might create a boolean variable a_i for each of the actions that will be added to our graph. In addition, we might introduce a fictitious action, with an associated boolean variable a₀, whose application would represent the resolution of the whole planning problem which, in this light, would become the problem of creating the preconditions for the application of this action. In the following we will use a_i to refer both to the boolean variable and to the associated action.

It is worth noticing that these actions, in most of the cases, would be really similar to the classical planning actions. Indeed, we would try to benefit as much as possible from this analogy. In case of the application of a rule, for example, we might consider a classical action having as preconditions the body of the rule and as effect the achievement of the goal having the same predicate as the head of the rule. Similarly, in case of the unification, we might consider a classical action having as preconditions the fact with which the goal is unifying, together with the unification constraint and as effect, again, the achievement of the goal having the same predicate as the head of the rule. Finally, the fictitious action a₀ might be considered as a classical action having as preconditions the initial requirements and as effect the solution of the planning problem. Since we want our problem to be solved, we would force variable a₀ to be equal to true.

In building our graph, we would have different behaviors for actions representing rule applications and actions representing unifications. For each actions a_i, representing the application of a rule, we would force the validity of the constraints in the preconditions of a_i to be equal to the variable a_i 8 . To this purpose, we recall we have reified constraints. For each fact p_j in the preconditions of action a_i we would add the constraints a_i ⇔ state (p_j) = Active and ¬a_i ⇔ state (p_j) = Inactive. For each goal p_j in the preconditions of action a_i, considering A (p_j) the set of actions a_k that achieve p_j, we would add the constraint a_i ⇔ ExactlyOne (A (p_j)). Now, for each action a_k in A (p_j) representing an application of a rule, we would add the constraints a_k ⇔ state (p_j) = Active and ¬a_k ⇔ state (p_j) = Inactive. Similarly, for each action a_k in A (p_j) representing a unification with an atom p_u, we would add the constraints a_k ⇔ state (p_j) = Unified ∧ state (p_u) = Active ∧ p_j ≡ p_u and ¬a_k ⇔ state (p_j) = Inactive.

Similarly to our agenda, we would maintain a queue of goals to be solved and we will add new actions backwards until either there would be no goals or every goal, individually, could be achieved by means of an unification action. In other words, a goal which might be achieved through an unification action would be considered solved and all the subgoals within preconditions of the other actions for achieving the goal, at first, would not be considered for further expanding the graph.

It is worth to spend some more words about the latter case. Specifically, it should be noted that, in general, the fact that two goals, individually, might unify, for example, with the same fact, does not necessarily imply that, together, the two goals will actually unify. In general, it depends from the involved constraints. Furthermore, the addition of constraints during the construction of the constrained causal graph might invalidate previous unifications. In these cases, we should be able to consider again some of the subgoals initially excluded from the agenda in order to subsequently refine the graph. However, we would not consider, at first, these cases, and might use the graph for generating a heuristic which would tell us when and how to refine the graph. Whenever we find a goal which might unify with an eligible fact we would create a backtracking point, we would force the state of the fact to be Active, we would force the state of the goal to be Unified, we would check that the unification constraints propagate and, in so, we would consider the goal as solved. In any case we would restore the state of the arc-consistency network as it was before the creation of the backtracking point.

Another way to describe our actions is to consider them as the actions that the planner needs to perform in order to produce a valid plan. Although our action might take into account temporal aspects in their preconditions, they are to all effects impulsive actions like those of classical planning. In this light, we are interested in finding a sequential plan whose execution, by the planner, would lead to the generation of our desired plan.

Finally, it is worth highlighting some similarities of our causal graph with the classical GraphPlan. Specifically, unlike classical planning, we do allow numerical variables (e.g., temporal variables) as predicate arguments. This fact precludes us the opportunity to represent extensively all the atoms of the state space which is, in general, infinite. On the other hand, according to our formalism, we do not allow atoms to appear as negated 9 . This aspect naturally matches with the well-known delete relaxation classical heuristic according to which negated atoms are ignored.

8.2 Using the constrained causal graph

The main aim of the constrained causal graph is to extract some values for an heuristic. Given the analogy with classical planning actions, the core idea is to use classical planning heuristics on the domain model represented by our actions. Specifically, we would use the constrained causal graph to extract a heuristic which is very similar to the h_max heuristic described in [5]. Specifically, the cost of achieving a set of atoms C would be approximated by the cost of achieving the most costly atom in the set. We give a formal recursive description of this heuristic:

$\begin{matrix} h_{\max} (C) \\ = {\begin{matrix} 0 & if C unifies, else \\ \min_{a \in A (p)} [1 + h_{\max} (pre (a))] & if C = {p}, else \\ \max_{f \in C} h_{\max} ({p}) & if | C | > 1 \end{matrix} \end{matrix}$

where f is an atom and A (f) is the set of actions for achieving the atom f. Roughly speaking, we would consider unifying goals as having cost zero. If different actions would achieve a goal, we would choose the less expensive action, however, the cost of an action would be given by the cost of the most expensive of its preconditions.

We might use this heuristic to guide the overall search process which, at this stage, might be seen as a simple search problem within the same constrained causal graph. We would have built a constraint satisfaction problem which would represent a solution for our reasoning problem. At the beginning, we would check the consistency of all the objects (e.g., the timelines) which might add further constraints to the graph. Then, we would choose the atom p having the highesth_max (p) value and would remove the value Inactive from its state. Also, we would choose the action a_k, among the set of actions A (p) achieving the goal p, having the lowest value for h_max (pre (a_k)) and would force its value to true.

Unfortunately, since the constrained causal graph structure would bring with itself an high level semantic from which the heuristics for the resolution of the constraint satisfaction problem (i.e., the whole reasoning problem) would be deduced, there is no hope, in any available constraint propagator, that such a behavior would emerge from its already existing heuristics. We have already tried this approach with standard solvers with not satisfactory results, therefore, a drawback of our situation is that we should discard available constraint based solvers in favor of solutions built from scratch.

9 Conclusions

This paper has introduced the ILOC planner and two domain-independent heuristics (i.e., the ALLREACHABLE heuristic and the MINREACH heuristic) that improve the planner performance with respect to those of a previous work. The problem relaxation introduced for the computation of the first heuristic is too strong, resulting in a too uninformed heuristic. With the second heuristic we started in the direction of coping with previous oversimplification and reintroducing some of the neglected parts. In particular by introducing disjunctions we obtain a heuristic that improves the performance of the resolution algorithm, especially on those domains in which the performance was weaker.

The ILOC planner has comparable (or even better) performance than the other planners on those domains in which temporal reasoning constitutes the main reasoning requirements (i.e., temporally expressive domains). For this reason, we are focusing now on those domains in which the temporal aspects are negligible compared to the causal ones. Performance on the class of problems not very suited for the timeline-based approach have been improved. The current results on these domains, however, are not enough competitive with those of mainstream planners. For this reason, we have analyzed the proposed heuristics and provided some hints which might help, in a future work, to bridge the performance gap between classical and timeline-based planning.

One final comment is worth being done: although applicable to any logic based problem, the proposed heuristics have been tested on classical planning problems. The reason for such a choice is twofold: (a) we are pursuing the idea of a domain-independent planner able to solve efficiently the wider spectrum of planning problems; (b) the planning community has plenty of benchmarking problems. Despite such abundance of problems, most of them do not take into account the temporal aspects of reality. We believe, however, that these problems might constitute a springboard for addressing more complex domains.

Footnotes

Source code and some example domains are available at

While SMTInterpol provides a pure Java implementation, MathSAT and Z3 provide Java wrappers to their native API. We have not found other SMT solvers that provide, directly or indirectly, a Java API.

This means, in general, sacrificing decidability.

De Morgan’s laws allow the expression of conjunctions and disjunctions in terms of each other via negation. Specifically, given two terms a and b, we have that ¬ (a ∧ b) = ¬ alor ¬ b and that ¬ (alorb) = ¬ a ∧ ¬ b.

Partial order and timeline-based planners commonly call such atoms “tokens”.

A more efficient implementation would use the same variable a_i when building the constraints.

If needed, negations might be represented by adding a boolean argument to predicates representing the polarity of the atoms.

Acknowledgments

Authors work is partially funded by the Ambient Assisted Living Joint Program under the SpONSOR project (AAL-2013-6-118).

References

Apt

K.R.

and Wallace

M.G.

, Constraint Logic Programming Using ECLiPSe. Cambridge University Press, New York, NY, USA, (2007).

Benton

, Coles

Amanda

, and Coles

Andrew

. Temporal Planning with Preferences and Time-Dependent Continuous Costs. In Twenty-Second International Conference on Automated Planning and Scheduling, (2012).

Bernardini

and Smith

D.E.

, Developing Domain- Independent Search Control for EUROPA2. In Proceedings of the Workshop on Heuristics for Domain-independent Planning at ICAPS-07, (2007).

Blum

and Furst

M.L.

, Fast Planning Through Planning Graph Analysis. In IJCAI, Morgan Kaufmann, (1995), 1636–1642.

Bonet

and Geffner

, Planning as heuristic search, Artificial Intelligence129(1-2) (2001), 5–33.

Cashmore

, Fox

, Larkworthy

, Long

and Magazzeni

, AUV Mission Control via Temporal Planning. In 2014 IEEE International Conference on Robotics and Automation, ICRA, (2014), 6535–6541.

Cesta

, Cortellessa

, Fratini

and Oddi

, Developing an End-to-End Planning Application from a Timeline Representation Framework. In IAAI-09. Proceedings of the 21st Innovative Applications of Artificial Intelligence Conference, Pasadena, CA, USA, (2009).

Cesta

, Oddi

and Smith

S.F.

, A constraint-based method for project scheduling with time windows, Journal of Heuristics8(1) (2002), 109–136.

Chien

, Tran

, Rabideau

, Schaffer

S.R.

, Mandl

and Frye

, Timeline-Based Space Operations Scheduling with External Constraints. In ICAPS-10. Proc. of the 20th Int. Conf. on Automated Planning and Scheduling, (2010).

10.

Christ

, Hoenicke

and Nutz

, SMTInterpol: An Interpolating SMT Solver. In Model Checking Software - 19th International Workshop, SPIN 2012, Oxford, UK, July 23-24, Proceedings, (2012), 248–254.

11.

Mayer

M.C.

, Orlandini

and Umbrico

, Planning and execution with flexible timelines: a formal account, Acta Informatica (2015), 1–32.

12.

Cimatti

, Griggio

, Schaafsma

and Sebastiani

, The MathSAT5 SMT Solver. In Piterman

Nir

and Smolka

Scott

, editors, Proceedings of TACAS, 7795 of LNCS. Springer, (2013).

13.

Coles

A.J.

, Coles

A.I.

, Fox

and Long

, COLIN: Planning with continuous linear numeric change, Journal of Artificial Intelligence Research44 (2012), 1–96.

14.

Cushing

, Kambhampati

, Mausam and Weld

D.S.

, When is Temporal Planning Really Temporal? In Proceedings of the 20th International Joint Conference on Artifical Intelligence, IJCAI’07, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc, (2007), 1852–1859.

15.

Cushing

, Weld

D.S.

, Kambhampati

, Mausam

and Talamadupula

, Evaluating temporal planning domains. In Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling, ICAPS 2007, Providence, Rhode Island, USA, September 22-26, AAAI, (2007), 105–112.

16.

De Benedictis

and Cesta

, Integrating Logic and Constraint Reasoning in a Timeline-based Planner. In AI*IA 2015 - XIVth International Conference of the Italian Association for Artificial Intelligence, (2015).

17.

De Benedictis

and Cesta

, New Heuristics for Timeline-Based Planning. In Proceedings of the 6th Italian Workshop on Planning and Scheduling A workshop of the XIV International Conference of the Italian Association for Artificial Intelligence (AI*IA 2015), Ferrara, Italy, September 22 2015, (2015), 33–48.

18.

De Moura

and Bjørner

, Z3: An Efficient SMT Solver. In Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS’08/ ETAPS’08, Berlin, Heidelberg, Springer-Verlag, (2008), 337–340.

19.

Dechter

, Constraint Processing. Morgan Kaufmann Publishers Inc., (2003).

20.

Dvorak

, Bit-Monnot

, Ingrand

and Ghallab

, Plan-Space Hierarchical Planning with the Action Notation Modeling Language. In IEEE International Conference on Tools with Artificial Intelligence (ICTAI), Limassol, Cyprus, (2014).

21.

Fox

and Long

, PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains, Journal of Artificial Intelligence Research20 (2003), 61–124.

22.

Fratini

, Pecora

and Cesta

, Unifying planning and scheduling as timelines in a component-based perspective, Archives of Control Sciences18(2) (2008), 231–271.

23.

Ghallab

and Laruelle

, Representation and Control in IxTeT, a Temporal Planner. In AIPS-94. Proceedings of the 2nd Int Conf on AI Planning and Scheduling, (1994), 61–67.

24.

Hoffman

, FF: The fast-forward planning system, AI Magazine22(3) (2001), 57–62.

25.

Jonsson

A.K.

, Morris

P.H.

, Muscettola

, Rajan

and Smith

, Planning in Interplanetary Space: Theory and Practice. In AIPS-00. Proceedings of the Fifth Int Conf on AI Planning and Scheduling, (2000).

26.

Le Berre

and Parrain

, The Sat4j library, release 2.2, JSAT7(2-3) (2010), 59–56.

27.

Maris

and Régnier

, TLP-GP: A planificateur pour la résolution de problèmes temporellements expressifs, Revue d’ Intelligence Artificielle24(4) (2010), 445–464.

28.

Marriott

and Stuckey

P.J.

, Programming with Constraints: An Introduction. MIT Press, 1998.

29.

Muscettola

, HSTS: Integrating Planning and Scheduling. In Zweben

and Fox

M.S.

, editor, Intelligent Scheduling. Morgan Kauffmann, (1994).

30.

, Rajan

and McGann

, A Systematic Agent Framework for Situated Autonomous Systems. In AAMAS, IFAAMAS, (2010), 583–590.

31.

Rankooh

M.F.

, Mahjoob

and Ghassem-Sani

, Using Satisfiability for Non-optimal Temporal Planning. In Logics in Artificial Intelligence - 13th European Conference, JELIA 2012, Toulouse, France, September 26-28, 2012. Proceedings, (2012), 176–188.

32.

Robinson

J.A.

, A machine-oriented logic based on the resolution principle, Journal of the Association for Computing Machinery12(1) (1965), 23–41.

33.

Sebastiani

, Lazy satisability modulo theories, JSAT3 (2007), 141–224.

34.

Simmons

and Younes

, VHPOP: Versatile Heuristic Partial Order Planner. CoRR, (2011).

35.

Smith

D.E.

, Frank

and Jónsson

A.K.

, Bridging the Gap Between Planning and Scheduling. Knowledge Engineering Review, (2000).

36.

Stock

, Mansouri

, Pecora

and Hertzberg

, Hierarchical hybrid planning in a mobile service robot. In Hölldobler

Steffen

, Krötzsch

Markus

, Peñaloza

Rafael

, and Rudolph

Sebastian

, editors, KI: Advances in Artificial Intelligence: 38th Annual German Conference on AI, Dresden, Germany, September 21-25, Proceedings, Cham, Springer International Publishing. (2015), 309–315.

37.

Vidal

and Geffner

, Branching and pruning: An optimal temporal POCL planner based on constraint programming, Artificial Intelligence170(3) (2006), 298–335.

38.

Weld

D.S.

, An introduction to least commitment planning, AI Magazine15(4) (1994), 27–61.