Introducing Preferences in Planning as Satisfiability

Planning as Satisfiability is one of the most well-known and effective techniques for classical planning: satplan has been the winning system in the deterministic track for optimal planners in the 4th International Planning Competition (IPC) and a cowinner in the 5th IPC. Given a planning problem Π and a makespan n, the approach based on satisfiability (a.k.a. SAT-based) simply works by (i) constructing a SAT formula Π n and (ii) checking Ðn for satisfiability: if there is a model for Π n then we have found a plan, otherwise n is increased. The approach guarantees that the makespan is optimal, i.e. minimum. In this article we extend the Planning as Satisfiability approach in order to handle preferences and satplan in order to solve problems with simple preferences. This allows, e.g. to take into consideration ‘plan quality’ issues other than makespan, like number of actions and ‘soft’ goals. The basic idea is to explore the search space of possible plans in accordance with the given partially ordered preferences.We first prove that, at fixed makespan, our approach returns an ‘optimal’ plan, if any. Then, considering both classical planning problems and problems coming from IPC-5, we show that satplan extended in order to deal with preferences: (i) returns optimal plans that are often of considerable better quality, i.e. with fewer actions or with a better plan metric on soft goals, than satplan; and (ii) is overall competitive, in terms of plan quality, with sgplan, the winning system in the ‘SimplePreferences’ category of the IPC-5. Notably, such results are often obtained without sacrificing efficiency.

Related papers:

title: Planning as Satisfiability
abstract: SATPLAN04 is a updated version of the planning as satisfiability approach originally proposed in (Kautz & Selman 1992; 1996) using hand-generated translations, and implemented for PDDL input in the blackbox system (Kautz & Selman 1999). Like blackbox, SATPLAN04 accepts the STRIPS subset of PDDL and finds solutions with minimal parallel length: that is, many (non-interferring) actions may occur in parallel at each time step, and the total number of time steps in guaranteed to be as small as possible. Also like blackbox, SATPLAN works by:

title: Unifying SAT-based and Graph-based Planning
abstract: The Blackbox planning system unifies the planning as satisfiability framework (Kautz and Selman 1992, 1996) with the plan graph approach to STRIPS planning (Blum and Furst 1995). We show that STRIPS problems can be directly translated into SAT and efficiently solved using new randomized systematic solvers. For certain computationally challenging benchmark problems this unified approach outperforms both SATPLAN and Graphplan alone. We also demonstrate that polynomialtime SAT simplification algorithms applied to the encoded problem instances are a powerful complement to the "mutex" propagation algorithm that works directly on the plan graph.

title: A Heuristic Search Approach to Planning with Temporally Extended Preferences
abstract: In this paper we propose a suite of techniques for planning with temporally extended preferences (TEPs). To this end, we propose a method for compiling TEP planning problems into simpler domains containing only final-state (simple) preferences and metric functions. With this simplified problem in hand, we propose a variety of heuristic functions for planning with final-state preferences, together with an incremental best-first planning algorithm. A key feature of the planning algorithm is its ability to prune the search space. We identify conditions under which our planning algorithm will generate optimal plans. We implemented our algorithm as an extension to the TLPLAN planning system and report on extensive testing performed to evaluate the effectiveness of our heuristics and algorithm. Our planner, HPLAN-P, competed in the 5th International Planning Competition, achieving distinguished performance in the qualitative preferences track.

title: The Deterministic Part of IPC-4: An Overview
abstract: We provide an overview of the organization and results of the deterministic part of the 4th International Planning Competition, i.e., of the part concerned with evaluating systems doing deterministic planning. IPC-4 attracted even more competing systems than its already large predecessors, and the competition event was revised in several important respects. After giving an introduction to the IPC, we briefly explain the main differences between the deterministic part of IPC-4 and its predecessors. We then introduce formally the language used, called PDDL2.2 that extends PDDL2.1 by derived predicates and timed initial literals. We list the competing systems and overview the results of the competition. The entire set of data is far too large to be presented in full. We provide a detailed summary; the complete data is available in an online appendix. We explain how we awarded the competition prizes.

title: Long-distance mutual exclusion for planning
abstract: Mutual exclusion (mutex) is a powerful mechanism for search space pruning in planning. However, a serious limitation of mutex is that it cannot specify constraints relating actions and facts across different time steps. In this paper, we propose a new class of mutual exclusions that significantly generalizes mutex and can be efficiently computed. The proposed long-distance mutual exclusion (londex) can capture constraints over actions and facts not only at the same time step but also across multiple steps. As a generalization, londex is much stronger than mutex, and provides a general and effective tool for developing efficient planners. We propose two levels of londex. The first level, londex"1, is derived from individual domain transition graphs (DTGs), and the second level, londex"m, is derived from multiple DTGs by taking into account the interactions among them. Londex constraints provide stronger pruning power but also require a large amount of memory. To address the memory problem, we further develop a virtual realization mechanism in which only a small proportion of londex constraints are dynamically generated as needed during the search. This scheme can save a huge amount of memory without sacrificing the pruning power of londex. For evaluation purposes, we incorporate londex into SATPlan04 and SATPlan06, two efficient SAT-based planners. Our experimental results show that londex"m can significantly improve over londex"1 since the former exploits causal dependencies among DTGs. Our experimental results for various planning domains also show significant advantages of using londex constraints for reducing planning time.

title: Long-Distance Mutual Exclusion for Propositional Planning
abstract: The use of mutual exclusion (mutex) has led to significant advances in propositional planning. However, previous mutex can only detect pairs of actions or facts that cannot be arranged at the same time step. In this paper, we introduce a new class of constraints that significantly generalizes mutex and can be efficiently computed. The proposed long-distance mutual exclusion (londex) can capture constraints over actions and facts not only at the same time step but also across multiple steps. Londex provides a powerful and general approach for improving planning efficiency. As an application, we have integrated londex into SATPLAN04, a leading optimal planner. Experimental results show that londex can effectively prune the search space and reduce the planning time. The resulting planner, MaxPlan, has won the First Place Award in the Optimal Track of the 5th International Planning Competition.

title: MaxPlan : Optimal Planning by Decomposed Satisfiability andBackward Reduction
abstract: Planning as satisfiability is one of the best approaches to optimal planning. In addition to being effective and efficient on many planning domains, this approach is general, in that a generic method for satisfiability (SAT) can be used. As a result, it is able to take advantage of the general research devoted to SAT. Nevertheless, the potential of this approach has not been fully exploited. In the MaxPlan planner, we develop an efficient SAT solving algorithm that effectively exploits the structure of planning applications and decomposes the original SAT problem into a series of much simpler SAT subproblems. The decomposed SAT approach has been shown to be significantly more efficient than the previous approach which uses a generic SAT solver as a black-box without exploiting the problem structure. Several other novel techniques, including backward level reduction, accumulative learning of clauses, and searchspace pruning based on multi-valued domain formulation, are also developed to further improve the search efficiency for both satisfiability solving and unsatisfiability proving.

title: An Extensible SAT-solver
abstract: In this article, we present a small, complete, and efficient SAT-solver in the style of conflict-driven learning, as exemplified by Chaff. We aim to give sufficient details about implementation to enable the reader to construct his or her own solver in a very short time.This will allow users of SAT-solvers to make domain specific extensions or adaptions of current state-of-the-art SAT-techniques, to meet the needs of a particular application area. The presented solver is designed with this in mind, and includes among other things a mechanism for adding arbitrary boolean constraints. It also supports solving a series of related SAT-problems efficiently by an incremental SAT-interface.

title: A machine program for theorem-proving
abstract: The programming of a proof procedure is discussed in connection with trial runs and possible improvements.

title: Planning with Goal Preferences and Constraints
abstract: In classical planning, the planner is given a concrete goal; it returns a plan for it or a failure message. In the latter case, the user can either quit or modify the goal. For many applications, it is more convenient to let the user provide a more elaborate specification consisting of constraints and preferences over possible goal states. Then, let the system discover a plan for the most desirable among the feasible goal states. To materialize such an approach we require a formalism for specifying preferences and constraints over goals and an algorithm for solving the resulting constrained optimization problem. In this work we motivate the need for planning with preferences and constraints, suggest a rich, yet intuitive formalism for representing goal preferences in the context of a deterministic action model, discuss some of its properties, propose an efficient algorithm for planning with preferences and constraints based on this formalism, and provide extensive experimental analysis in an interesting new domain of configuration planning.

title: CP-nets: A Tool for Representing and Reasoning withConditional Ceteris Paribus Preference Statements
abstract: Information about user preferences plays a key role in automated decision making. In many domains it is desirable to assess such preferences in a qualitative rather than quantitative way. In this paper, we propose a qualitative graphical representation of preferences that reflects conditional dependence and independence of preference statements under a ceteris paribus (all else being equal) interpretation. Such a representation is often compact and arguably quite natural in many circumstances. We provide a formal semantics for this model, and describe how the structure of the network can be exploited in several inference tasks, such as determining whether one outcome dominates (is preferred to) another, ordering a set outcomes according to the preference relation, and constructing the best outcome subject to available evidence.

title: Using the Davis and Putnam Procedure for an Efficient Computation of Preferred Models
abstract: Some famous problems (ATMS inference, Closed World Reasoning (CWR) for instance) can be replaced by a problem of preferred model computation. We thus propose a preference relation between models based on a preference relation between literals and an \eecient" algorithm to compute the associated preferred models of a theory. Then, we apply this algorithm to ATMS inference and problems of CWR. Sub-problems like subsumption and label computation 7]]8] are thus implicitly solved.

title: Solving Optimization Problems with DLL
abstract: Propositional satisfiability (SAT) is a success story in Computer Science and Artificial Intelligence: SAT solvers are currently used to solve problems in many different application domains, including planning and formal verification. The main reason for this success is that modern SAT solvers can successfully deal with problems having millions of variables. All these solvers are based on the Davis-Logemann-Loveland procedure (DLL). DLL is a decision procedure: Given a formula φ, it returns whether φ is satisfiable or not. Further, DLL can be easily modified in order to return an assignment satisfying φ, assuming one exists. However, in many cases it is not enough to compute a satisfying assignment: Indeed, the returned assignment has also to be “optimal” in some sense, e.g., it has to minimize/maximize a given objective function. 
 
In this paper we show that DLL can be very easily adapted in order to solve optimization problems like MAX-SAT and MIN-ONE. In particular these problems are solved by simply imposing an ordering on a set of literals, to be followed while branching. Other popular problems, like DISTANCE-SAT and WEIGHTED-MAX-SAT, can be solved in a similar way. We implemented these ideas in ZCHAFF and the experimental analysis show that the resulting system is competitive with respect to other state-of-the-art systems.

title: Unrestricted vs restricted cut in a tableau method for Boolean circuits
abstract: AbstractThis paper studies the relative efficiency of variations of a tableau method for Boolean circuit satisfiability checking. The considered method is a nonclausal generalisation of the Davis–Putnam–Logemann–Loveland (DPLL) procedure to Boolean circuits. The variations are obtained by restricting the use of the cut (splitting) rule in several natural ways. It is shown that the more restricted variations cannot polynomially simulate the less restricted ones. For each pair of methods T, T′, an infinite family 
$\{\mathcal{C}_{n}\}$ 
of circuits is devised for which T has polynomial size proofs while in T′ the minimal proofs are of exponential size w.r.t. n, implying exponential separation of T and T′ w.r.t. n. The results also apply to DPLL for formulas in conjunctive normal form obtained from Boolean circuits by using Tseitin’s translation. Thus DPLL with the considered cut restrictions, such as allowing splitting only on the variables corresponding to the input gates, cannot polynomially simulate DPLL with unrestricted splitting.

title: STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving
abstract: We describe a new problem solver called STRIPS that attempts to find a sequence of operators in a space of world models to transform a given initial world model into a model in which a given goal formula can be proven to be true. STRIPS represents a world model as an arbi trary collection of first-order predicate calculus formulas and is designed to work with models consisting of large numbers of formulas. It employs a resolution theorem prover to answer (juestions of particular models and uses means-ends analysis to guide it to the desired goal-satisfying model.

title: Choosing Objectives in Over-Subscription Planning
abstract: Many NASA planning problems are over-subscription problems – that is, there are a large number of possible goals of differing value, and the planning system must choose a subset that can be accomplished within the limited time and resources available. Examples include planning for telescopes like Hubble, SIRTF, and SOFIA; scheduling for the Deep Space Network; and planning science experiments for a Mars rover. Unfortunately, existing planning systems are not designed to deal with problems like this – they expect a well-defined conjunctive goal and terminate in failure unless the entire goal can be achieved. In this paper we develop techniques for over-subscription problems that assist a classical planner in choosing which goals to achieve, and the order in which to achieve them. These techniques use plan graph cost-estimation techniques to construct an orienteering problem, which is then used to provide heuristic advice on the goals and goal order that should be considered by a planner.

title: Effective Approaches for Partial Satisfaction (Over-Subscription) Planning
abstract: In many real world planning scenarios, agents often do not have enough resources to achieve all of their goals. Consequently, they are forced to find plans that satisfy only a subset of the goals. Solving such partial satisfaction planning (PSP) problems poses several challenges, including an increased emphasis on modeling and handling plan quality (in terms of action costs and goal utilities). Despite the ubiquity of such PSP problems, very little attention has been paid to them in the planning community. In this paper, we start by describing a spectrum of PSP problems and focus on one of the more general PSP problems, termed PSP NET BENEFIT. We develop three techniques, (i) one based on integer programming, called OptiPlan, (ii) the second based on regression planning with reachability heuristics, called AltAltps, and (iii) the third based on anytime heuristic search for a forward state-space heuristic planner, called Sapaps. Our empirical studies with these planners show that the heuristic planners generate plans that are comparable to the quality of plans generated by OptiPlan, while incurring only a small fraction of the cost.

title: Combining the Expressivity of UCPOP with the Efficiency of Graphplan
abstract: There has been a great deal of recent work on new approaches to efficiently generating plans in systems such as Graphplan and SATplan. However, these systems only provide an impoverished representation language compared to other planners, such as UCPOP, ADL, or Prodigy. This makes it difficult to represent planning problems using these new planners. This paper addresses this problem by providing a completely automated set of transformations for converting a UCPOP domain representation into a Graphplan representation. The set of transformations extends the Graphplan representation language to include disjunctions, negations, universal quantification, conditional effects, and axioms. We tested the resulting planner on the 18 test domains and 41 problems that come with the UCPOP 4.0 distribution. Graphplan with the new preprocessor is able to solve every problem in the test set and on the hard problems (i.e., those that require more than one second of CPU time) it can solve them significantly faster than UCPOP. While UCPOP was unable to solve 7 of the test problems within a search limit of 100,000 nodes (which requires 414 to 980 CPU seconds), Graphplan with the preprocessor solved them all in under 15 CPU seconds (including the preprocessing time).

title: Efficient CNF Encoding of Boolean Cardinality Constraints
abstract: In this paper, we address the encoding into CNF clauses of Boolean cardinality constraints that arise in many practical applications. The proposed encoding is efficient with respect to unit propagation, which is implemented in almost all complete CNF satisfiability solvers. We prove the practical efficiency of this encoding on some problems arising in discrete tomography that involve many cardinality constraints. This encoding is also used together with a trivial variable elimination in order to re-encode parity learning benchmarks so that a simple Davis and Putnam procedure can solve them.

title: Satisfiability Planning with Constraints on the Number of Actions
abstract: We investigate satisfiability planning with restrictions on the number of actions in a plan. Earlier work has considered encodings of sequential plans for which a plan with the minimal number of time steps also has the minimum number of actions, and parallel (partially ordered) plans in which the number of actions may be much higher than the number of time steps. For a given problem instance finding a parallel plan may be much faster than finding a corresponding sequential plan but there is also the possibility that the parallel plan contains unnecessary actions. 
 
Our work attempts to combine the advantages of parallel and sequential plans by efficiently finding parallel plans with as few actions as possible. We propose techniques for encoding parallel plans with constraints on the number of actions. Then we give algorithms for finding a plan that is optimal with respect to a given number of steps and an anytime algorithm for successively finding better and better plans. We show that as long as guaranteed optimality is not required, our encodings for parallel plans are often much more efficient in finding plans of good quality than a sequential encoding.

title: Planning with Qualitative Temporal Preferences
abstract: In this paper, we address the problem of specifying and generating preferred plans using rich, qualitative user preferences. We propose a logical language for specifying non-Markovian preferences over the evolution of states and actions associated with a plan. The semantics for our first-order preference language is defined in the situation calculus. Unlike other recent temporal preference languages, our preferences are qualitative rather than just ordinal, affording greater expressivity and less incomparability. We propose an approach to computing preferred plans via bounded best-first search in a forward-chaining planner. Key components of our approach are the exploitation of progression to efficiently evaluate levels of preference satisfaction over partial plans, and development of an admissible evaluation function that establishes the optimality of best-first search. We have implemented our planner PPLAN and evaluated it experimentally. Our preference language and planning approach is amenable to integration with several existing planners, and beyond planning, can be used to support arbitrary dynamical reasoning tasks involving preferences.

title: A framework for compiling preferences in logic programs
abstract: We introduce a methodology and framework for expressing general preference information in logic programming under the answer set semantics. An ordered logic program is an extended logic program in which rules are named by unique terms, and in which preferences among rules are given by a set of atoms of form s [pr ] t where s and t are names. An ordered logic program is transformed into a second, regular, extended logic program wherein the preferences are respected, in that the answer sets obtained in the transformed program correspond with the preferred answer sets of the original program. Our approach allows the specification of dynamic orderings, in which preferences can appear arbitrarily within a program. Static orderings (in which preferences are external to a logic program) are a trivial restriction of the general dynamic case. First, we develop a specific approach to reasoning with preferences, wherein the preference ordering specifies the order in which rules are to be applied. We then demonstrate the wide range of applicability of our framework by showing how other approaches, among them that of Brewka and Eiter, can be captured within our framework. Since the result of each of these transformations is an extended logic program, we can make use of existing implementations, such as dlv and smodels. To this end, we have developed a publicly available compiler as a front-end for these programming systems.

title: Clause Form Conversions for Boolean Circuits
abstract: The Boolean circuits is well established as a data structure for building propositional encodings of problems in preparation for satisfiability solving. The standard method for converting Boolean circuits to clause form (naming every vertex) has a number of shortcomings. 
 
In this paper we give a projection of several well-known clause form conversions to a simplified form of Boolean circuit. We introduce a new conversion which we show is equivalent to that of Boy de la Tour in certain circumstances and is hence optimal in the number of clauses that it produces. We extend the algorithm to cover reduced Boolean circuits, a data structure used by the model checker NuSMV. 
 
We present experimental results for this and other conversion procedures on BMC problems demonstrating its superiority, and conclude that the CNF conversion has a significant role in reducing the overall solving time.

title: A Structure-Preserving Clause Form Translation
abstract: Most resolution theorem provers convert a theorem into clause form before attempting to find a proof. The conventional translation of a first-order formula into clause form often obscures the structure of the formula, and may increase the length of the formula by an exponential amount in the worst case. We present a non-standard clause form translation that preserves more of the structure of the formula than the conventional translation. This new translation also avoids the exponential increase in size which may occur with the standard translation. We show how this idea may be combined with the idea of replacing predicates by their definitions before converting to clause form. We give a method of lock resolution which is appropriate for the non-standard clause form translation, and which has yielded a spectacular reduction in search space and time for one example. These techniques should increase the attractiveness of resolution theorem provers for program verification applications, since the theorems that arise in program verification are often simple but tedious for humans to prove.

title: A Heuristic Search Approach to Planning with Temporally Extended Preferences
abstract: In this paper we propose a suite of techniques for planning with temporally extended preferences (TEPs). To this end, we propose a method for compiling TEP planning problems into simpler domains containing only final-state (simple) preferences and metric functions. With this simplified problem in hand, we propose a variety of heuristic functions for planning with final-state preferences, together with an incremental best-first planning algorithm. A key feature of the planning algorithm is its ability to prune the search space. We identify conditions under which our planning algorithm will generate optimal plans. We implemented our algorithm as an extension to the TLPLAN planning system and report on extensive testing performed to evaluate the effectiveness of our heuristics and algorithm. Our planner, HPLAN-P, competed in the 5th International Planning Competition, achieving distinguished performance in the qualitative preferences track.

title: Constraint Partitioning for Solving Planning Problems with Trajectory Constraints and Goal Preferences
abstract: The PDDL3 specifications include soft goals and trajectory constraints for distinguishing highquality plans among the many feasible plans in a solution space. To reduce the complexity of solving a large PDDL3 planning problem, constraint partitioning can be used to decompose its constraints into subproblems of much lower complexity. However, constraint locality due to soft goals and trajectory constraints cannot be effectively exploited by existing subgoal-partitioning techniques developed for solving PDDL2.2 problems. In this paper, we present an improved partition-andresolve strategy for supporting the new features in PDDL3. We evaluate techniques for resolving violated global constraints, optimizing goal preferences, and achieving subgoals in a multivalued representation. Empirical results on the 5th International Planning Competition (IPC5) benchmarks show that our approach is effective and significantly outperforms other competing planners.

title: Plan Constraints and Preferences in PDDL3
abstract: We propose an extension to the PDDL language, called PDDL3.0, that aims at a better characterization of plan quality by allowing the user to express strong and soft constraints about the structure of the desired plans, as well as strong and soft problem goals. PDDL3.0 was the reference language of the 5th International Planning competition (IPC-5). This paper contains most of the document about PDDL3.0 that was discussed by the Consulting Committee of IPC-5, and then distributed to the IPC-5 competitors.  The notion of plan quality in automated planning is a practically very important issue. In many real-world planning domains, we have to address problems with a large set of solutions, or with a set of goals that cannot all be achieved. In these problems, it is important to generate plans of good or optimal quality achieving all problem goals (if possible) or some subset of them. In the previous International planning competitions, the plan generation CPU-time played a central role in the evaluation of the competing planners. In the fifth International planning competition (IPC-5), while considering the CPUtime, we would like to give greater emphasis to the importance of plan quality. The versions of PDDL used in the previous two competitions (PDDL2.1 and PDDL2.2) allow us to express some criteria for plan quality, such as the number of plan actions or parallel steps, and relatively complex plan metrics involving plan makespan and numerical quantities. These are powerful and expressive in domains that include metric fluents, but plan quality can still only be measured by plan size in the case of propositional planning. We believe that these criteria are insufficient, and we propose to extend PDDL with new constructs increasing its expressive power about the plan quality specification. The proposed extended language allows us to express strong and soft constraints on plan trajectories (i.e. constraints over possible actions in the plan and intermediate states reached by the plan), as well as strong and soft problem goals (i.e. goals that must be achieved in any valid plan, and goals that we desire to achieve, but that do not have to be necessarily achieved). Strong constraints and goals must be satisfied by any valid plan, while soft constraints and goals express desired constraints and goals, some of which may be more preferred than others. Informally, in planning with soft constraints and goals, the best quality plan should satisfy “as much as possible” the soft constraints and goals according to the specified preference relation distinguishing alternative feasible plans (satisfying all strong constraints and goals). While soft constraints have been extensively studied in the CSP literature, only very recently has the planning community started to investigate them (Brafman & Chernyavsky 2005; Briel et al. 2004; Delgrande, Schaub, & Tompits 2005; Miguel, Jarvis, & Shen 2001; Smith 2004; Son & Pontelli 2004), and we believe that they deserve more research efforts. The following are some informal examples of plan trajectory constraints and soft goals. Additional formal examples will be given in the next section. Examples in a blocksworld domain: a fragile block can never have something above it, or it can have at most one block on it; we would like that the blocks forming the same tower always have the same colour; in some state of the plan, all blocks should be on the table. Examples in a transportation domain: we would like that every airplane is used (instead of using only a few airplanes, because it is better to distribute the workload among the available resources and limit heavy usage); whenever a ship is ready at a port to load the containers it has to transport, all such containers should be ready at that port; we would like that at the end of the plan all trucks are clean and at their source location; we would like no truck to visit any destination more than once. When we have soft constraints and goals, it can be useful to give different priorities to them, and this should be taken into account in the plan quality evaluation. While there is more than one way to specify the importance of a soft constraint or goal, as a first attempt to tackle this issue, for IPC5 we have chosen a simple quantitative approach: each soft constraint and goal is associated with a numerical weight representing the cost of its violation in a plan (and hence also its relative importance with respect the other specified soft constraints and goals). Weighted soft constraints and goals are part of the plan metric expression, and the best quality plans are those optimising such an expression (more details are given in the next sections). Using this approach we can express that certain plans are more preferred than others. Some examples are (other formalised examples are given in the next sections):1 I prefer a plan where every airplane is used, rather than a plan using 100 units of fuel less, which could be expressed by weighting a failure to use all the planes by a number 100 times bigger than the weight associated with the fuel use in the plan metric; I prefer a plan where each city is visited at most once, rather than a plan with a shorter makespan, which could be expressed by using constraint violation costs penalising a failure to visit each city at most once very heavily; I prefer a plan where at the end each truck is at its start location, rather than a plan where every city is visited by at most one truck, which could be expressed by using goal costs penalising a goal failure of having every truck at its start location more heavily than a failure of having in the plan every city visited by at most one truck. We also observe that the rich additional expressive power we propose to add for goal specifications allows the expression of constraints that are actually derivable necessary properties of optimal plans. By adding them as goal conditions, we have a way to express constraints that we know will lead to the planner finding optimal plans. Similarly, one can express constraints that prevent a planner from exploring parts of the plan space that are known to lead to inefficient performance. In the next sections, we outline some extensions to PDDL2.2 that we propose for IPC-5. We call the extended language PDDL3.0. It should be noted that this is a preliminary version of the extended language, and that a more detailed description will be prepared in the future. Moreover, given that the proposed extensions are relatively new in the planning community, and that the teams participating in IPC-5 will have limited time to develop their systems, we impose some simplifying restrictions to make the language more accessible. State Trajectory Constraints Syntax and Intended Meaning State trajectory constraints assert conditions that must be met by the entire sequence of states visited during the execution of a plan. They are expressed through temporal modal operators over first order formulae involving state predicates. We recognise that there would be value in also allowing propositions asserting the occurrence of action instances in a plan, rather than simply describing properties of the states visited during execution of the plan, but we choose to restrict ourselves to state predicates in this extension of the language. The use of the extensions described here imply a new requirements flag, :constraints. The basic modal operators we propose to use in IPC-5 are: always, sometime, at-most-once, and atend (for goal state conditions). We use a special default assumption that unadorned conditions in the goal specification are automatically taken to be “at end” conditions. This assumption The benchmark domains and problems of IPC-5 contain many additional examples; some samples of them are described in (Gerevini & Long 2006). is made in order to preserve the standard meaning for existing goal specifications, despite the fact that in a standard semantics for an LTL formula an unadorned proposition would be interpreted according to the current state. We add within which can be used to express deadlines. In addition, rather than allowing arbitrary nesting of modal operators, we introduce some specific operators that offer some limited nesting. We have sometime-before, sometime-after, always-within. Other modalities could be added, but we believe that these are sufficiently powerful for an initial level of the sublanguage modelling constraints. It should be noted that, by combining these modalities with timed initial literals (defined in PDDL2.2), we can express further goal constraints. In particular, one can specify the interval of time when a goal should hold, or the lower bound on the time when it should hold. Since these are interesting and useful constraints, we introduce two modal operators as “syntactic sugar” of the basic language: hold-during and hold-after. Trajectory constraints are specified in the planning problem file in a new field, called :constraints that will usually appear after the goal. In addition, we allow constraints to be specified in the action domain file on the grounds that some constraints might be seen as safety conditions, or operating conditions, that are not physical limitations, but are nevertheless constraints that must always be respected in any valid plan for the domain (say legal constraints or operating procedures that must be respected). This also uses a section labelled (:constraints ...). The interpretation of (:constraints ...) in the conjunction of a domain and a problem file is that it is equivalent to having all the constraints added to the goals. The use of trajectory constraints (in the domain file or in the goal specification) implies the need for the :constraints flag in the :requirements list. Note that no temporal modal operator is allowed in preconditions of actions. That is, all action preconditions are with respect to a state (or time interval, in the case of overall action c

title: Anytime heuristic search for partial satisfaction planning
abstract: We present a heuristic search approach to solve partial satisfaction planning (PSP) problems. In these problems, goals are modeled as soft constraints with utility values, and actions have costs. Goal utility represents the value of each goal to the user and action cost represents the total resource cost (e.g., time, fuel cost) needed to execute each action. The objective is to find the plan that maximizes the trade-off between the total achieved utility and the total incurred cost; we call this problem PSP Net Benefit. Previous approaches to solving this problem heuristically convert PSP Net Benefit into STRIPS planning with action cost by pre-selecting a subset of goals. In contrast, we provide a novel anytime search algorithm that handles soft goals directly. Our new search algorithm has an anytime property that keeps returning better quality solutions until the termination criteria are met. We have implemented this search algorithm, along with relaxed plan heuristics adapted to PSP Net Benefit problems, in a forward state-space planner called Sapa^P^S. An adaptation of Sapa^P^S, called Yochan^P^S, received a ''distinguished performance'' award in the ''simple preferences'' track of the 5th International Planning Competition.

title: Introducing Variable Importance Tradeoffs into CP-Nets
abstract: The ability to make decisions and to assess potential courses of action is a comer-stone of many AI applications, and usually this requires explicit information about the decision-maker's preferences. In many applications, preference elicitation is a serious bottleneck. The user either does not have the time, the knowledge, or the expert support required to specify complex multi-attribute utility functions. In such cases, a method that is based on intuitive, yet expressive, preference statements is required. In this paper we suggest the use of TCP-nets, an enhancement of CP-nets, as a tool for representing, and reasoning about qualitative preference statements. We present and motivate this framework, define its semantics, and show how it can be used to perform constrained optimization.

title: Act, and the Rest Will Follow: Exploiting Determinism in Planning as Satisfiability
abstract: In this paper we focus on Planning as Satisfiability (SAT). We build from the simple consideration that the values of fiuents at a certain time point derive deterministically from the initial situation and the sequence of actions performed till that point. Thus, the choice of actions to perform is the only source of nondeterminism. This is a rather trivial consideration, but which has important positive consequences if implemented in current planners via SAT. In fact, it produces a dramatic size reduction of the space of the truth assignments searched in by the SAT decider used to solve the final SAT problem. To justify this claim, we repeat many of the experiments reported in (Ernst, Millstein, & Weld 1997), and show that the CPU time requested to solve a problem can go down up to 4 orders of magnitude.

title: Translating Pseudo-Boolean Constraints into SAT
abstract: In this paper, we describe and evaluate three dieren t techniques for translating pseudoboolean constraints (linear constraints over boolean variables) into clauses that can be handled by a standard SAT-solver. We show that by applying a proper mix of translation techniques, a SAT-solver can perform on a par with the best existing native pseudo-boolean solvers. This is particularly valuable in those cases where the constraint problem of interest is naturally expressed as a SAT problem, except for a handful of constraints. Translating those constraints to get a pure clausal problem will take full advantage of the latest improvements in SAT research. A particularly interesting result of this work is the eciency of sorting networks to express pseudo-boolean constraints. Although tangential to this presentation, the result gives a suggestion as to how synthesis tools may be modied to produce arithmetic circuits more suitable for SAT based reasoning.

title: The First Evaluation of Pseudo-Boolean Solvers (PB'05)
abstract: The rst evaluation of pseudo-Boolean solvers was organized as a subtrack of the SAT 2005 competition. The rst goal of this event is to take a snapshot of the current state of the art in the eld of pseudo-Boolean constraints. The second goal is to stimulate the research eorts in this eld and contribute to the creation of better technologies. This paper details the organization and the results of this event.

title: The Complexity of Optimal Planning and a More Efficient Method for Finding Solutions
abstract: We present a faster method of solving optimal planning problems and show that our solution performs up to an order of magnitude faster than Satplan on a variety of problems from the IPC-5 benchmarks. Satplan makes several calls to a SAT solver, discarding learned information with each call. Our planner uses a single call to a SAT solver, eliminating this problem. 
 
We explain our technique by describing a new theoretical framework which allows us to prove that a single call to a SAT solver is sufficient to solve every problem in Δ2. (This does not imply that NP is equal to Δ2; only that SAT solvers' capabilities are greater than previously realized.) We also prove that optimal planning is FΘ2 Complete when the plan length is bounded by a polynomial; optimal planning is thus harder than SAT even in the presence of such a bound. Despite the relative complexities, the Δ2 capability of DPLL and the fact that Θ2 ⊆ Δ2 show that a single satisfiability call can solve optimal planning problems in the presence of a polynomial bound on plan length.

title: HTN Planning with Preferences
abstract: In this paper we address the problem of generating preferred plans by combining the procedural control knowledge specified by Hierarchical Task Networks (HTNs) with rich user preferences. To this end, we extend the popular Planning Domain Definition Language, PDDL3, to support specification of simple and temporally extended preferences over HTN constructs. To compute preferred HTN plans, we propose a branch-and-bound algorithm, together with a set of heuristics that, leveraging HTN structure, measure progress towards satisfaction of preferences. Our preference-based planner, HTNPLAN-P, is implemented as an extension of the SHOP2 planner. We compared our planner with SGPlan5 and HPLAN-P- the top performers in the 2006 International Planning Competition preference tracks. HTNPLAN-P generated plans that in all but a few cases equalled or exceeded the quality of plans returned by HPLAN-P and SGPlan5. While our implementation builds on SHOP2, the language and techniques proposed here are relevant to a broad range of HTN planners.

title: Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP
abstract: The idea of synthesizing bounded length plans by compiling planning problems into a combinatorial substrate, and solving the resulting encodings has become quite popular in recent years. Most work to-date has however concentrated on compilation to satisfiability (SAT) theories and integer linear programming (ILP). In this paper we will show that CSP is a better substrate for the compilation approach, compared to both SAT and ILP. We describe GP-CSP, a system that does planning by automatically converting Graphplan's planning graph into a CSP encoding and solving it using standard CSP solvers. Our comprehensive empirical evaluation of GP-CSP demonstrates that it is superior to both the Blackbox system, which compiles planning graphs into SAT encodings, and an ILP-based planner in a wide range of planning domains. Our results show that CSP encodings outperform SAT encodings in terms of both space and time requirements in various problems. The space reduction is particularly important as it makes GP-CSP less susceptible to the memory blow-up associated with SAT compilation methods. The paper also discusses various techniques in setting up the CSP encodings, planning specific improvements to CSP solvers, and strategies for variable and value selection heuristics for solving the CSP encodings of different types of planning problems.

title: On Graphical Modeling of Preference and Importance
abstract: In recent years, CP-nets have emerged as a useful tool for supporting preference elicitation, reasoning, and representation. CP-nets capture and support reasoning with qualitative conditional preference statements, statements that are relatively natural for users to express. In this paper, we extend the CP-nets formalism to handle another class of very natural qualitative statements one often uses in expressing preferences in daily life - statements of relative importance of attributes. The resulting formalism, TCP-nets, maintains the spirit of CP-nets, in that it remains focused on using only simple and natural preference statements, uses the ceteris paribus semantics, and utilizes a graphical representation of this information to reason about its consistency and to perform, possibly constrained, optimization using it. The extra expressiveness it provides allows us to better model tradeoffs users would like to make, more faithfully representing their preferences.

title: Planning as Satisfiability with Preferences
abstract: Planning as Satisfiability is one of the most well-known and effective technique for classical planning: SATPLAN has been the winning system in the deterministic track for optimal planners in the 4th International Planning Competition (IPC) and a co-winner in the 5th IPC. 
 
In this paper we extend the Planning as Satisfiability approach in order to handle preferences and SATPLAN in order to solve problems with simple preferences. The resulting system, SATPLAN(P) is competitive with SGPLAN, the winning system in the category "simple preferences" at the last IPC. Further, we show that SATPLAN(P) performances are (almost) always comparable to those of SATPLAN when solving the same problems without preferences: in other words, introducing simple preferences in SATPLAN does not affect its performances. This latter result is due both to the particular mechanism we use in order to incorporate preferences in SAT-PLAN and to the relative low number of soft goals (each corresponding to a simple preference) usually present in planning problems. Indeed, if we consider the issue of determining minimal plans (corresponding to problems with thousands of preferences) the performances of SATPLAN(P) are comparable to those of SATPLAN in many cases, but can be significantly worse when the number of preferences is very high compared to the total number of variables in the problem. Our analysis is conducted considering both qualitative and quantitative preferences, different reductions from quantitative to qualitative ones, and most of the propositional planning domains from the IPCs and that SATPLAN can handle.

title: SHOP2: An HTN Planning System
abstract: The SHOP2 planning system received one of the awards for distinguished performance in the 2002 International Planning Competition. This paper describes the features of SHOP2 which enabled it to excel in the competition, especially those aspects of SHOP2 that deal with temporal and metric planning domains.

title: The Metric FF Planning System Translating Ignoring Delete Lists to Numeric State Variables
abstract: Planning with numeric state variables has been a challenge for many years and was a part of the rd International Planning Competition IPC Currently one of the most popular and successful algorithmic techniques in STRIPS planning is to guide search by a heuristic function where the heuristic is based on relaxing the planning task by ignoring the delete lists of the available actions We present a natural extension of ignoring delete lists to numeric state variables preserving the relevant theoretical properties of the STRIPS relaxation under the condition that the numeric task at hand is monotonic We then identify a subset of the numeric IPC competition language linear tasks where monotonicity can be achieved by pre processing Based on that we extend the algorithms used in the heuristic planning system FF to linear tasks The resulting system Metric FF is according to the IPC results which we discuss one of the two currently most e cient numeric planners

title: Partial Satisfaction (Over-Subscription) Planning as Heuristic Search
abstract: Many planning problems can be characterized as over-subscription problems in that goals have different utilities, actions have different costs and the planning system must choose a subset that will provide the greatest net benefit. This type of problems can not be solved by existing planning systems, where goals are assumed to have uniform utility, and the planner can terminate only when all of the goals are achieved. Existing methods for such problems use greedy approaches, which pre-select a subset of goals based on their estimated utility, and solve for those goals. Unfortunately, greedy methods, while efficient, can produce plans of arbitrarily low quality. In this paper, we introduce a more sophisticated heuristic search framework for over-subscription planning problems. In our framework, top-level goals are treated as soft-constraints and the search is guided by a relaxed-plan based heuristic that estimates the most beneficial set of goals from a given state. We implement this search framework in the context of Sapa, a forward state-space planner. We provide preliminary empirical results that demonstrate the effectiveness of our approach in comparison to a greedy approach.

title: Planning for Temporally Extended Goals as Propositional Satisfiability
abstract: Planning for temporally extended goals (TEGs) expressed as formulae of Linear-time Temporal Logic (LTL) is a proper generalization of classical planning, not only allowing to specify properties of a goal state but of the whole plan execution. Additionally, LTL formulae can be used to represent domain-specific control knowledge to speed up planning. In this paper we extend SATbased planning for LTL goals (akin to bounded LTL model-checking in verification) to partially ordered plans, thus significantly increasing planning efficiency compared to purely sequential SAT planning. We consider a very relaxed notion of partial ordering and show how planning for LTL goals (without the next-time operator) can be translated into a SAT problem and solved very efficiently. The results extend the practical applicability of SATbased planning to a wider class of planning problems. In addition, they could be applied to solving problems in bounded LTL model-checking more efficiently.

title: Classical negation in logic programs and disjunctive databases
abstract: An important limitation of traditional logic programming as a knowledge representation tool, in comparison with classical logic, is that logic programming does not allow us to deal directly with incomplete information. In order to overcome this limitation, we extend the class of general logic programs by including classical negation, in addition to negation-as-failure. The semantics of such extended programs is based on the method of stable models. The concept of a disjunctive database can be extended in a similar way. We show that some facts of commonsense knowledge can be represented by logic programs and disjunctive databases more easily when classical negation is available. Computationally, classical negation can be eliminated from extended programs by a simple preprocessor. Extended programs are identical to a special case of default theories in the sense of Reiter.

title: REFERRED A NSWER S ETS FOR E XTENDED L OGIC P ROGRAMS
abstract: In this paper, we address the issue of how Gelfond and Lifschitz’s answer set semantics for extended logic programs can be suitably modified to handle prioritized programs. In such programs an ordering on the program rules is used to express preferences. We show how this ordering can be used to define preferred answer sets and thus to increase the set of consequences of a program. We define a strong and a weak notion of preferred answer sets. The first takes preferences more seriously, while the second guarantees the existence of a preferred answer set for programs possessing at least one answer set. Adding priorities to rules is not new, and has been explored in different contexts. However, we show that many approaches to priority handling, most of which are inherited from closely related formalisms like default logic, are not suitable and fail on intuitive examples. Our approach, which obeys abstract, general principles that any approach to prioritized knowledge representation should satisfy, handles them in the expected way. Moreover, we investigate the complexity of our approach. It appears that strong preference on answer sets does not add on the complexity of the principal reasoning tasks, and weak preference leads only to a mild increase in complexity. 1Universität Leipzig, Institut für Informatik, Abteilung Intelligente Systeme,Augustusplatz 9/10, D-04109 Leipzig, Germany.  brewka@informatik.uni-leipzig.de 2Institut für Informatik, Universität Gießen, Arndtstraße 2, D-35392 Gießen, Germany.  eiter@informatik.uni-giessen.de A short and partial version of this paper will appear in the Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning (KR ’98), Trento, Italy, June 2–4, 1998.

title: Loosely Coupled Formulations for Automated Planning: An Integer Programming Perspective
abstract: We represent planning as a set of loosely coupled network flow problems, where each network corresponds to one of the state variables in the planning domain. The network nodes correspond to the state variable values and the network arcs correspond to the value transitions. The planning problem is to find a path (a sequence of actions) in each network such that, when merged, they constitute a feasible plan. In this paper we present a number of integer programming formulations that model these loosely coupled networks with varying degrees of flexibility. Since merging may introduce exponentially many ordering constraints we implement a so-called branch-and-cut algorithm, in which these constraints are dynamically generated and added to the formulation when needed. Our results are very promising, they improve upon previous planning as integer programming approaches and lay the foundation for integer programming approaches for cost optimal planning.

title: Optiplan: Unifying IP-based and Graph-based Planning
abstract: The Optiplan planning system is the first integer programming-based planner that successfully participated in the international planning competition. This engineering note describes the architecture of Optiplan and provides the integer programming formulation that enabled it to perform reasonably well in the competition. We also touch upon some recent developments that make integer programming encodings significantly more competitive.

title: Plan-A : A Cost Optimal Planner Based on SAT-Constrained Optimization ∗
abstract: Planning as satisfiability, represented by SATPlan, can find plans with the shortest makespan for classical planning. However, it has been deemed a limitation of SAT-based approaches for delivering optimality regarding metrics other than the makespan. Our Plan-A solver uses the SAT-based framework to find plans with minimal total action costs. The idea is to optimally solve SAT instances based on certain optimality metrics. Bounding and pruning techniques are proposed and integrated with the standard DPLL algorithm to reduce the search cost.

title: Heuristics for Planning with Action Costs Revisited
abstract: We introduce a simple variation of the additive heuristic used in the HSP planner that combines the benefits of the original additive heuristic, namely its mathematical formulation and its ability to handle non-uniform action costs, with the benefits of the relaxed planning graph heuristic used in FF, namely its compatibility with the highly effective enforced hill climbing search along with its ability to identify helpful actions. We implement a planner similar to FF except that it uses relaxed plans obtained from the additive heuristic rather than those obtained from the relaxed planning graph. We then evaluate the resulting planner in problems where action costs are not uniform and plans with smaller overall cost (as opposed to length) are preferred, where it is shown to compare well with cost-sensitive planners such as SGPlan, Sapa, and LPG. We also consider a further variation of the additive heuristic, where symbolic labels representing action sets are propagated rather than numbers, and show that this scheme can be further developed to construct heuristics that can take delete-information into account.

title: Optimal Symbolic Planning with Action Costs and Preferences
abstract: This paper studies the solving of finite-domain action planning problems with discrete action costs and soft constraints. For sequential optimal planning, a symbolic perimeter database heuristic is addressed in a bucket implementation of A*. For computing net-benefits, we propose symbolic branch-and-bound search together with some search refinements. The net-benefit we optimize is the total benefit of satisfying the goals, minus the total action cost to achieve them. This results in an objective function to be minimized that is a linear expression over the violation of the preferences added to the action cost total.