Jussi Rintanen

AAAI Conference 2024 Conference Paper

Optimizing the Optimization of Planning Domains by Automatic Action Schema Splitting

• Mojtaba Elahi
• Jussi Rintanen

Most planners are based on grounding, that is, generating all instances of a parameterized action during a preprocessing phase. For some problems the number of ground actions is too high, causing a performance bottleneck. Building upon an existing approach, we present an enhanced method to split action schemas automatically during the grounding phase, to reduce the number of ground actions. First, we propose to exploit the structural knowledge of the problems to have a more informative dependency graph. Then, we suggest a better objective function to define and choose the best split. Finally, we present a more effective search to find it. We experimentally measure the impact of each of these improvements, and show that our approach significantly outperforms the state of the art.

ECAI Conference 2024 Conference Paper

Symmetry-Breaking Constraints for Directed Graphs

• Jussi Rintanen
• Masood Feyzbakhsh Rankooh

Finding a graph with given properties occurs as a sub-problem of many important problems in A. I. and other areas of computer science. Main approaches to solving such problems include automated reasoning and constraint satisfaction methods. These can often be substantially sped up by considering only a subset of graphs for each equivalence class of isomorphic graphs, motivating the use of symmetry-breaking constraints for graphs. We present a symmetry-breaking constraint for directed graphs, generalizing earlier works that have presented such constraints for undirected graphs without loops, and experimentally demonstrate their effectiveness.

ICAPS Conference 2024 Conference Paper

Termination Properties of Transition Rules for Indirect Effects

• Mojtaba Elahi
• Saurabh Fadnis
• Jussi Rintanen

Indirect effects of agent's actions have traditionally been formalized as condition-effect rules that always fire whenever applicable, after each action taken by the agent. In this work, we investigate a core problem of indirect effects, the possibility of arbitrarily or infinitely long sequences of rule firings. Specifically we investigate the termination of rule firings, as well as their confluence, that is, the uniqueness of the state that is ultimately reached. Both problems turn out to be PSPACE-complete. After this, we devise practically interesting syntactic and structural restrictions that guarantee polynomial-time termination and confluence tests. Finally, in the context of planning languages that support indirect effects, we propose new implementation technologies.

JELIA Conference 2023 Conference Paper

Planning with Partial Observability by SAT

• Saurabh Fadnis
• Jussi Rintanen

Abstract Geffner & Geffner (2018) have shown that finding plans by reduction to SAT is not limited to classical planning, but is competitive also for fully observable non-deterministic planning. This work extends these ideas to planning with partial observability. Specifically, we handle partial observability by requiring that during the execution of a plan, the same actions have to be taken in all indistinguishable circumstances. We demonstrate that encoding this condition directly leads to far better scalability than an explicit encoding of observations-to-actions mapping, for high numbers of observations.

ICAPS Conference 2022 Conference Paper

Efficient Computation and Informative Estimation of h+ by Integer and Linear Programming

• Masood Feyzbakhsh Rankooh
• Jussi Rintanen

We investigate modeling cost optimal delete-free STRIPS Planning by Integer/Linear Programming (IP/LP). We introduce two IP models and their LP relaxations based on a recently formulated representation of relaxed plans, named causal relaxed plan representation. The new models are produced by enforcing acyclicity in so-called causal relation graphs using vertex elimination and time labeling methods. We empirically show that while the vertex elimination based method outperforms the time labeling based method and all previously introduced domain independent methods for computing the exact values of h+, the time labeling based LP model is faster to solve compared to its vertex elimination based alternative, making it more suitable for using as heuristic function for optimal planning. We also theoretically analyze the admissible heuristic functions obtained by solving our LP models, and prove that the vertex elimination based heuristic is at least as informative as the time labeling based heuristic. Moreover, our empirical analysis shows that our vertex elimination based heuristic, which is a novel admissible estimation of h+, often has information complementary to that of the LM-cut heuristic.

AAAI Conference 2022 Conference Paper

Efficient Encoding of Cost Optimal Delete-Free Planning as SAT

• Masood Feyzbakhsh Rankooh
• Jussi Rintanen

We introduce a novel method for encoding cost optimal delete-free STRIPS Planning as SAT. Our method is based on representing relaxed plans as partial functions from the set of propositions to the set of actions. This function can map any proposition to a unique action that adds the proposition during execution of the relaxed plan. We show that a relaxed plan can be produced by maintaining acyclicity in the graph of all causal relations among propositions, represented by the mentioned partial function. We also show that by efficient encoding of action cost propagation and enforcing a series of upper bounds on the total costs of the output plan, an optimal plan can effectively be produced for a given delete-free STRIPS problem. Our empirical results indicate that this method is quite competitive with the state of the art, demonstrating a better coverage compared to that of competing methods on standard STRIPS planning benchmark problems.

AAAI Conference 2022 Conference Paper

Propositional Encodings of Acyclicity and Reachability by Using Vertex Elimination

• Masood Feyzbakhsh Rankooh
• Jussi Rintanen

We introduce novel methods for encoding acyclicity and st-reachability constraints for propositional formulas with underlying directed graphs, based on vertex elimination graphs, which makes them suitable for cases where the underlying graph has a low directed elimination width. In contrast to solvers with ad hoc constraint propagators for graph constraints such as GraphSAT, our methods encode these constraints as standard propositional clauses, making them directly applicable with any SAT solver. An empirical study demonstrates that our methods do often outperform both earlier encodings of these constraints as well as GraphSAT especially when underlying graphs have a low directed elimination width.

ICAPS Conference 2018 Conference Paper

Planning for Partial Observability by SAT and Graph Constraints

• Binda Pandey
• Jussi Rintanen

Chatterjee et al. have recently shown the utility of SAT in solving a class of planning problems with partial observability. A core component of their logical formulation of planning is constraints expressing s-t-reachability in directed graphs. In this work, we show that the scalability of the approach can be dramatically improved by using dedicated graph constraints, and that a far broader class of important planning problems can be expressed in terms of s-t-reachability and acyclicity constraints.

AAAI Conference 2017 Conference Paper

Schematic Invariants by Reduction to Ground Invariants

• Jussi Rintanen

Computation of invariants, which are approximate reachability information for state-space search problems such as AI planning, has been considered to be more scalable when using a schematic representation of actions/events rather than an instantiated/ground representation. A disadvantage of schematic algorithms, however, is their complexity, which also leads to high runtimes when the number of schematic events/actions is high. We propose algorithms that reduce the problem of finding schematic invariants to solving a smaller ground problem.

IJCAI Conference 2017 Conference Paper

Temporal Planning with Clock-Based SMT Encodings

• Jussi Rintanen

We propose more scalable encodings of temporal planning in SMT. The first contribution is practical clock-based encodings of resources and effect delays. Existing encodings of effect delays (Shin and Davis, 2015) have a quadratic size, due to the necessity to determine the time differences between steps for a linear number of steps. Clocks improve this to linear. The second contribution is a new relaxed scheme for steps. Existing schemes require a step for every time point with discontinuous change. This is relaxed, improving scalability.

AAAI Conference 2015 Conference Paper

Discretization of Temporal Models with Application to Planning with SMT

• Jussi Rintanen

The problem of planning or discrete control for timed system has earlier been solved with various constraint-based solution methods, including Constraint Programming, SAT solvers, SAT modulo Theories solvers, and Mixed Integer-Linear Programming. In this work we investigate the encoding of time in such constraint-based representations. A main issue with existing encodings is the necessity to allow arbitrary interleavings of concurrent actions’ starting and ending times. The complex combinatorics of this can lead to poor scalability of leading search methods. We show how real or rational time in temporal models can in many practically important cases be replaced by integer time, and how this leads to far simpler encodings of planning as constraints. We demonstrate that the simplified encodings substantially improve the scalability of constraint-based planning.

AAAI Conference 2015 Conference Paper

Impact of Modeling Languages on the Theory and Practice in Planning Research

• Jussi Rintanen

We propose revisions to the research agenda in Automated Planning. The proposal is based on a review of the role of the Planning Domain Definition Language (PDDL) in the activities of the AI planning community and the impact of PDDL on parts of its research agenda. We specifically show how specific properties of PDDL have impacted research on planning, by putting emphasis on certain research topics and complicating others. We argue that the development of more advanced modeling languages would be – analogously to the impact PDDL has had – a low overhead and smooth route for the ICAPS community shift its research focus to increasingly promising and relevant research topics.

IJCAI Conference 2015 Conference Paper

Models of Action Concurrency in Temporal Planning

• Jussi Rintanen

Models of temporal planning are complex, due to the possibility of multiple concurrent and mutually interacting actions. This work compares two modeling languages, one with a PDDL-style action exclusion mechanism, and another with an explicit notion of resources, and investigates their implications on constraint-based search. The first mechanism forces temporal gaps in action schedules and have a high performance penalty. The second mechanism avoids the gaps, with dramatically improved performance.

ECAI Conference 2014 Conference Paper

Answer Set Programming as SAT modulo Acyclicity

• Martin Gebser
• Tomi Janhunen
• Jussi Rintanen

Answer set programming (ASP) is a declarative programming paradigm for solving search problems arising in knowledge-intensive domains. One viable way to implement the computation of answer sets corresponding to problem solutions is to recast a logic program as a Boolean satisfiability (SAT) problem and to use existing SAT solver technology for the actual search. Such mappings can be obtained by augmenting Clark's completion with constraints guaranteeing the strong justifiability of answer sets. To this end, we consider an extension of SAT by graphs subject to an acyclicity constraint, called SAT modulo acyclicity. We devise a linear embedding of logic programs and study the performance of answer set computation with SAT modulo acyclicity solvers.

JELIA Conference 2014 Conference Paper

Constraint-Based Algorithm for Computing Temporal Invariants

• Jussi Rintanen

Abstract Automatically identified invariants are an important part of reductions of state-space reachability problems to SAT and related formalisms as a method of pruning the search space. No general algorithms for computing temporal invariants have been proposed before. Earlier algorithms restrict to unconditional actions and at-most-one invariants. We propose a powerful inductive algorithm for computing invariants for timed systems, showing that a wide range of timed modeling languages can be handled uniformly. The algorithm reduces the computation of timed invariants to a sequence of temporal logic consistency tests.

JELIA Conference 2014 Conference Paper

SAT Modulo Graphs: Acyclicity

• Martin Gebser
• Tomi Janhunen
• Jussi Rintanen

Abstract Acyclicity is a recurring property of solutions to many important combinatorial problems. In this work we study embeddings of specialized acyclicity constraints in the satisfiability problem of the classical propositional logic (SAT). We propose an embedding of directed graphs in SAT, with arcs labelled with propositional variables, and an extended SAT problem in which all clauses have to be satisfied and the subgraph consisting of arcs labelled true is acyclic. We devise a constraint propagator for the acyclicity constraint and show how it can be incorporated in off-the-shelf SAT solvers. We show that all existing encodings of acyclicity constraints in SAT are either prohibitively large or do not sanction all inferences made by the constraint propagator. Our experiments demonstrate the advantages of our solver over other approaches for handling acyclicity.

KR Conference 2014 Short Paper

Systematic Declarative Encodings of Tree-Like Properties

• Martin Gebser
• Tomi Janhunen
• Jussi Rintanen

IJCAI Conference 2013 Conference Paper

Computing Upper Bounds on Lengths of Transition Sequences

• Jussi Rintanen
• Charles Orgill Gretton

We describe an approach to computing upper bounds on the lengths of solutions to reachability problems in transition systems. It is based on a decomposition of state-variable dependency graphs (causal graphs). Our approach is able to find practical upper bounds in a number of planning benchmarks. Computing the bounds is computationally cheap in practice, and in a number of benchmarks our algorithm runs in polynomial time in the number of actions and propositional variables that characterize the problem.

NeurIPS Conference 2013 Conference Paper

Learning Chordal Markov Networks by Constraint Satisfaction

• Jukka Corander
• Tomi Janhunen
• Jussi Rintanen
• Henrik Nyman
• Johan Pensar

We investigate the problem of learning the structure of a Markov network from data. It is shown that the structure of such networks can be described in terms of constraints which enables the use of existing solver technology with optimization capabilities to compute optimal networks starting from initial scores computed from the data. To achieve efficient encodings, we develop a novel characterization of Markov network structure using a balancing condition on the separators between cliques forming the network. The resulting translations into propositional satisfiability and its extensions such as maximum satisfiability, satisfiability modulo theories, and answer set programming, enable us to prove the optimality of networks which have been previously found by stochastic search.

ICAPS Conference 2013 Conference Paper

Scheduling with Contingent Resources and Tasks

• Jussi Rintanen

Finding optimal schedules for the most commonly considered classes of scheduling problems is NP-complete. Best algorithms scale up to very large scheduling problems when optimality is not required and good solution quality suffices. These problems have perfect information in the sense that the resource availability, set of tasks, task duration, and other important facts, are fully known at the time of constructing a schedule. However, the assumption of perfect information is rarely satisfied, and real-world scheduling faces several forms of uncertainty, most notably with respect to durations and availability of resources. The effective handling of uncertainty is a major issue in applying scheduling in new areas. In this work, we investigate the properties of a number of classes of problems of contingent scheduling, in which assignments of resources to tasks depend on resource availability and other facts that are only known fully during execution, and hence the off-line construction of one fixed schedule is insufficient. We show that contingent scheduling in most general cases is most likely outside the complexity class NP, and resides, depending on the assumptions, in PSPACE, Sigma-p-2 or Pi-p-2. The results prove that standard constraint-satisfaction and SAT frameworks are in general not straightforwardly applicable to contingent scheduling.

ECAI Conference 2012 Conference Paper

Complexity of Conditional Planning under Partial Observability and Infinite Executions

• Jussi Rintanen

The computational properties of many classes of conditional and contingent planning are well known. The main division in the field is between probabilistic planning (typically infinite or unbounded executions, reward rather than goal-based, and focus on expected costs or rewards) and non-probabilistic planning (ignoring probabilities, focus on plans that reach goal states.) In this work, we address the middle ground between these problems: planning with infinite executions and designated goal states. We address worst case rather than expected costs measures for the problem we consider. We analyze the structure of the plans for two possible goal-based specifications such plans may have to satisfy, maintaining a goal property indefinitely as well as visiting a goal state infinitely often, and establish their complexity under different observability assumptions.

ECAI Conference 2012 Conference Paper

Engineering Efficient Planners with SAT

• Jussi Rintanen

Planning with SAT has long been viewed as a main approach to AI planning. In comparison to other approaches, its high memory requirements have been considered to be a main obstacle to its scalability to large planning problems. Better implementation technology, especially addressing the memory use, together with a shift of understanding about SAT-based planning during the past ten years, enables planners that radically differ from those from the late 1990s. We discuss a SAT-based planning system that implements modern versions of virtually all components of first planners that used SAT, focusing on the new implementation technology for a compact clause representation that is both simpler and more effective than ones proposed earlier. Specifically, the decreased memory requirements enable the use of top-level solution strategies that lift the performance of SAT-based planning to the same level with other search methods.

AIJ Journal 2012 Journal Article

Planning as satisfiability: Heuristics

• Jussi Rintanen

Reduction to SAT is a very successful approach to solving hard combinatorial problems in Artificial Intelligence and computer science in general. Most commonly, problem instances reduced to SAT are solved with a general-purpose SAT solver. Although there is the obvious possibility of improving the SAT solving process with application-specific heuristics, this has rarely been done successfully. In this work we propose a planning-specific variable selection strategy for SAT solving. The strategy is based on generic principles about properties of plans, and its performance with standard planning benchmarks often substantially improves on generic variable selection heuristics, such as VSIDS, and often lifts it to the same level with other search methods such as explicit state-space search with heuristic search algorithms.

ICAPS Conference 2011 Conference Paper

Heuristics for Planning with SAT and Expressive Action Definitions

• Jussi Rintanen

We present the first effective SAT heuristics for planning with expressive planning languages such as ADL. Recently, SAT heuristics for STRIPS planning have been introduced. In this work we show that the basic ideas in the heuristic can be generalized to actions with conditional effects but without disjunction, and that disjunction requires a more fundamental analysis of the STRIPS heuristic, which, despite complications, will still lead to a natural heuristic which can be implemented efficiently. The experimental analysis shows substantial and systematic improvements over the state of the art in planning with SAT with ADL.

IJCAI Conference 2011 Conference Paper

Planning with SAT, Admissible Heuristics and A*

• Jussi Rintanen

We study the relationship between optimal planning algorithms, in the form of (iterative deepening) A* with (forward) state-space search, and the reduction of the problem to SAT. Our results establish a strict dominance relation between the two approaches: any iterative deepening A* search can be efficiently simulated in the SAT framework, assuming that the heuristic has been encoded in the SAT problem, but the opposite is not possible as A* and IDA* searches sometimes take exponentially longer.

AAAI Conference 2011 Conference Paper

Planning with Specialized SAT Solvers

• Jussi Rintanen

Logic, and declarative representation of knowledge in general, have long been a preferred framework for problem solving in AI. However, specific subareas of AI have been eager to abandon general-purpose knowledge representation in favor of methods that seem to address their computational core problems better. In planning, for example, state-space search has in the last several years been preferred to logic-based methods such as SAT. In our recent work, we have demonstrated that the observed performance differences between SAT and specialized state-space search methods largely go back to the difference between a blind (or at least planningagnostic) and a planning-specific search method. If SAT search methods are given even simple heuristics which make the search goal-directed, the efficiency differences disappear.

ECAI Conference 2008 Conference Paper

A New Approach to Planning in Networks

• Jussi Rintanen

Control of networks like those for transportation, power distribution, communication to name a few, provides challenges to planning and scheduling. Many problems can be defined in terms of a basic state space model, but more general problems require an expressive language for talking about the topology and connectivity of the system, which are outside the scope of standard planning languages. In this work we introduce a general framework for defining planning languages for networked systems, with capability to express properties of connectivity and topology of such systems.

KR Conference 2008 Conference Paper

Planning Graphs and Propositional Clause-Learning

• Jussi Rintanen

The planning graph of Blum and Furst is one of the frequently used tools in planning. It is a data structure which can be visualized as a bipartite graph with state variables and actions as nodes and which approximates (upper bound) the set of reachable states with a given number of sets of simultaneous actions. We show that the contents of planning graphs follow from two more general notions: extended clause learning restricted to 2-literal clauses and the representation of parallel plans consisting of STRIPS actions in the classical propositional logic. This is the first time planning graphs have been given an explanation in terms of the inference methods used in SAT solvers. The work helps in bridging the gap between specialized algorithms devised for planning and general-purpose algorithms for automated reasoning.

ECAI Conference 2008 Conference Paper

Regression for Classical and Nondeterministic Planning

• Jussi Rintanen

Many forms of reasoning about actions and planning can be reduced to regression, the computation of the weakest precondition a state has to satisfy to guarantee the satisfaction of another condition in the successor state. In this work we formalize a general syntactic regression operation for ground PDDL operators, show its correctness, and define a composition operation based on regression. As applications we present a very simple yet powerful algorithm for computing invariants, as well as a generalization of the hnheuristic of Haslum and Geffner to PDDL.

IJCAI Conference 2007 Conference Paper

• Sarah Hickmott
• Jussi Rintanen
• Sylvie Thi
• eacute; baux
• Lang White

The factored state representation and concurrency semantics of Petri nets are closely related to those of concurrent planning domains, yet planning and Petri net analysis have developed independently, with minimal and usually unconvincing attempts at cross-fertilisation. In this paper, we investigate and exploit the relationship between the two areas, focusing on Petri net unfolding, which is an attractive reachability analysis method as it naturally enables the recognition and separate resolution of independent subproblems. On the one hand, based on unfolding, we develop a new forward search method for cost-optimal partial-order planning which can be exponentially more efficient than state space search. On the other hand, inspired by well-known planning heuristics, we investigate the automatic generation of heuristics to guide unfolding, resulting in a more efficient, directed reachability analysis tool for Petri nets.

IJCAI Conference 2007 Conference Paper

• Robert Mattm
• uuml; ller
• Jussi Rintanen

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 SAT-based 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 SAT-based planning to a wider class of planning problems. In addition, they could be applied to solving problems in bounded LTL model-checking more efficiently.

IJCAI Conference 2007 Conference Paper

• Jussi Rintanen
• Alban Grastien

We show how testing whether a system is diagnosable can be reduced to the satisfiability problem and how satisfiability algorithms yield a very efficient approach to testing diagnosability. Diagnosability is the question whether it is always possible to know whether a given system has exhibited a failure behavior. This is a basic question that underlies diagnosis, and it is also closely related to more general questions about the possibility to know given facts about system behavior. The work combines the twin plant construct of Jiang et al. , which is the basis of diagnosability testing of systems with an enumerative representation, and SAT-based techniques to AI planning which form a very promising approach to finding paths in very large transition graphs.

IJCAI Conference 2007 Conference Paper

• Jussi Rintanen

Reasoning about the knowledge of an agent is an important problem in many areas of AI. For example in diagnosis a basic question about a system is whether it is possible to diagnose it, that is, whether it is always possible to know whether a faulty behavior has occurred. In this paper we investigate the complexity of this diagnosability problem and the size of automata that perform diagnosis. There are algorithms for testing diagnosability in polynomial time in the number of states in the system. For succinct system representations, which may be exponentially smaller than the state space of the system, the diagnosability problem is consequently in EXPTIME. We show that this upper bound is not tight and that the decision problem is in fact PSPACE-complete. On-line diagnosis can be carried out by diagnosers which are automata that recognize faulty behavior. We show that diagnosers in the worst case have a size that is exponential in the number of states, both for explicit and succinct system representations. This is a consequence of the diagnoser having to maintain beliefs about the state of the system.

AAAI Conference 2007 Conference Paper

Asymptotically Optimal Encodings of Conformant Planning in QBF

• Jussi Rintanen

The world is unpredictable, and acting intelligently requires anticipating possible consequences of actions that are taken. Assuming that the actions and the world are deterministic, planning can be represented in the classical propositional logic. Introducing nondeterminism (but not probabilities) or several initial states increases the complexity of the planning problem and requires the use of quantified Boolean formulae (QBF). The currently leading logic-based approaches to conditional planning use explicitly or implicitly a QBF with the prefix ∃∀∃. We present formalizations of the planning problem as QBF which have an asymptotically optimal linear size and the optimal number of quantifier alternations in the prefix: ∃∀ and ∀∃. This is in accordance with the fact that the planning problem (under the restriction to polynomial size plans) is on the second level of the polynomial hierarchy, not on the third.

ICAPS Conference 2007 Conference Paper

Complexity of Concurrent Temporal Planning

• Jussi Rintanen

We consider the problem of temporal planning in which a given goal is reached by taking a number of actions which may temporally overlap and interfere, and the interference may be essential for reaching the goals. We formalize a general temporal planning problem, show that its plan existence problem is EXPSPACE-complete, and give conditions under which it is reducible to classical planning and is therefore only PSPACE-complete. Our results are the first to show that temporal planning can be computationally more complex than classical planning. They also show how and why a very large and important fragment of temporal PDDL is reducible to classical planning.

AAAI Conference 2007 Conference Paper

Diagnosis of Discrete-Event Systems Using Satisfiability Algorithms

• Grastien Alban
• Jussi Rintanen

The diagnosis of a discrete-event system is the problem of computing possible behaviors of the system given observations of the actual behavior, and testing whether the behaviors are normal or faulty. We show how the diagnosis problems can be translated into the propositional satisfiability problem (SAT) and solved by algorithms for SAT. Our experiments demonstrate that current SAT algorithms can solve much bigger diagnosis problems than traditional diagnosis algorithms can.

ECAI Conference 2006 Conference Paper

Compact Representation of Sets of Binary Constraints

• Jussi Rintanen

We address the problem of representing big sets of binary constraints compactly. Binary constraints in the form of 2-literal clauses are ubiquitous in propositional formulae that represent real-world problems ranging from model-checking problems in computer-aided verification to AI planning problems. Current satisfiability and constraint solvers are applicable to very big problems, and in some cases the physical size of the problem representations prevents solving the problems, not their computational difficulty. Our work is motivated by this observation. We propose graph-theoretic techniques based on cliques and bicliques for compactly representing big sets of binary constraints that have the form of 2-literal clauses. An n, m biclique in a graph associated with the constraints can be very compactly represented with only n+m binary constraints and one auxiliary variable. Cliques in the graph are associated with at-most-one constraints, and can be represented with a logarithmic number of binary constraints. The clique representation turns out to be a special case of the biclique representation. We demonstrate the effectiveness of the biclique representation in making the representation of big planning problems practical.

AIJ Journal 2006 Journal Article

Planning as satisfiability: parallel plans and algorithms for plan search

• Jussi Rintanen
• Keijo Heljanko
• Ilkka Niemelä

We address two aspects of constructing plans efficiently by means of satisfiability testing: efficient encoding of the problem of existence of plans of a given number t of time points in the propositional logic and strategies for finding plans, given these formulae for different values of t. For the first problem we consider three semantics for plans with parallel operator application in order to make the search for plans more efficient. The standard semantics requires that parallel operators are independent and can therefore be executed in any order. We consider a more relaxed definition of parallel plans which was first proposed by Dimopoulos et al. , as well as a normal form for parallel plans that requires every operator to be executed as early as possible. We formalize the semantics of parallel plans emerging in this setting and present translations of these semantics into the propositional logic. The sizes of the translations are asymptotically optimal. Each of the semantics is constructed in such a way that there is a plan following the semantics exactly when there is a sequential plan, and moreover, the existence of a parallel plan implies the existence of a sequential plan with as many operators as in the parallel one. For the second problem we consider strategies based on testing the satisfiability of several formulae representing plans of n time steps for several values of n concurrently by several processes. We show that big efficiency gains can be obtained in comparison to the standard strategy of sequentially testing the satisfiability of formulae for an increasing number of time steps.

ECAI Conference 2006 Conference Paper

Unified Definition of Heuristics for Classical Planning

• Jussi Rintanen

In many types of planning algorithms distance heuristics play an important role. Most of the earlier works restrict to STRIPS operators, and their application to a more general language with disjunctivity and conditional effects first requires an exponential size reduction to STRIPS operators. I present direct formalizations of a number of distance heuristics for a general operator description language in a uniform way, avoiding the exponentiality inherent in earlier reductive approaches. The formalizations use formulae to represent the conditions under which operators have given effects. The exponentiality shows up in satisfiability tests with these formulae, but would appear to be a minor issue because of the small size of the formulae.

ICAPS Conference 2005 Conference Paper

Satisfiability Planning with Constraints on the Number of Actions

• Markus Büttner
• Jussi Rintanen

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.

ICAPS Conference 2004 Conference Paper

Complexity of Planning with Partial Observability

• Jussi Rintanen

We show that for conditional planning with partial observability the problem of testing existence of plans with success probability 1 is 2-EXP-complete. This result completes the complexity picture for non-probabilistic propositional planning. We also give new proofs for the EXP-hardness of conditional planning with full observability and the EXPSPACEhardness of conditional planning without observability. The proofs demonstrate how lack of full observability allows the encoding of exponential space Turing machines in the planning problem, and how the necessity to have branching in plans corresponds to the move to a complexity class defined in terms of alternation from the corresponding deterministic complexity class. Lack of full observability necessitates the use of beliefs states, the number of which is exponential in the number of states, and alternation corresponds to the choices a branching plan can make.

AAAI Conference 2004 Conference Paper

Distance Estimates for Planning in the Discrete Belief Space

• Jussi Rintanen

We present a general framework for studying heuristics for planning in the belief space. Earlier work has focused on giving implementations of heuristics that work well on benchmarks, without studying them at a more analytical level. Existing heuristics have evaluated belief states in terms of their cardinality or have used distance heuristics directly based on the distances in the underlying state space. Neither of these types of heuristics is very widely applicable: often goal belief state is not approached through a sequence of belief states with a decreasing cardinality, and distances in the state space ignore the main implications of partial observability. To remedy these problems we present a family of admissible, increasingly accurate distance heuristics for planning in the belief space, parameterized by an integer n. We show that the family of heuristics is theoretically robust: it includes the simplest heuristic based on the state space as a special case and as a limit the exact distances in the belief space.

ECAI Conference 2004 Conference Paper

Evaluation Strategies for Planning as Satisfiability

• Jussi Rintanen

JELIA Conference 2004 Conference Paper

Parallel Encodings of Classical Planning as Satisfiability

• Jussi Rintanen
• Keijo Heljanko
• Ilkka Niemelä

Abstract We consider a number of semantics for plans with parallel operator application. The standard semantics used most often in earlier work requires that parallel operators are independent and can therefore be executed in any order. We consider a more relaxed definition of parallel plans, first proposed by Dimopoulos et al. , as well as normal forms for parallel plans that require every operator to be executed as early as possible. We formalize the semantics of parallel plans emerging in this setting, and propose effective translations of these semantics into the propositional logic. And finally we show that one of the semantics yields an approach to classical planning that is sometimes much more efficient than the existing SAT-based planners.

KR Conference 2004 Conference Paper

Phase transitions in classical planning: an experimental study

• Jussi Rintanen

Phase transitions in the solubility of problem instances are known in many types of computational problems relevant for artificial intelligence, most notably for the satisfiability problem of the classical propositional logic. However, phase transitions in classical planning have received far less attention. Bylander has investigated phase transitions theoretically as well as experimentally by using simplified planning algorithms, and shown that most of the soluble problems can be solved by a naive hill-climbing algorithm. Because of the simplicity of his algorithms he did not investigate hard problems on the phase transition region. In this paper, we address exactly this problem. We introduce two new models of problem instances, one eliminating the most trivially insoluble instances from Bylander’s model, and the other restricting the class of problem instances further. Then we perform experiments on the behavior of different types of planning algorithms on hard problems from the phase transition region, showing that a planner based on general-purpose satisfiability algorithms outperforms two planners based on heuristic local search.

ICAPS Conference 2004 Conference Paper

Phase Transitions in Classical Planning: An Experimental Study

• Jussi Rintanen

Phase transitions in the solubility of problem instances are known in many types of computational problems relevant for artificial intelligence, most notably for the satisfiability problem of the classical propositional logic. However, phase transitions in classical planning have received far less attention. Bylander has investigated phase transitions theoretically as well as experimentally by using simplified planning algorithms, and shown that most of the soluble problems can be solved by a naïve hill-climbing algorithm. Because of the simplicity of his algorithms he did not investigate hard problems on the phase transition region. In this paper, we address exactly this problem. We introduce two new models of problem instances, one eliminating the most trivially insoluble instances from Bylander’s model, and the other restricting the class of problem instances further. Then we perform experiments on the behavior of different types of planning algorithms on hard problems from the phase transition region, showing that a planner based on general-purpose satisfiability algorithms outperforms two planners based on heuristic local search.

ICAPS Conference 2003 Conference Paper

Expressive Equivalence of Formalisms for Planning with Sensing

• Jussi Rintanen

There have been several proposals for expressing planning problems with different forms of uncertainty, including nondeterminism and partial observability. In this paper we investigate two questions. First, the restriction to certain normal forms of operators, for example, restricting to operators in which nondeterministic choice must be outside conditional effects, or vice versa. We show that some such restrictions lead to an exponentially less succinct representation of problem instances. Second, we consider the problem of reducing certain features of formalisms for planning problem to other, more basic features. We show that compound observations can be reduced to atomic observations, sensing uncertainty can be reduced to effect uncertainty, dependence of observations on the operator last applied (special sensing actions) can be reduced to the case in which same observations are always possible. We show that these reductions are possible without significantly affecting quantitative properties of problem instances. One reduction doubles plan length, and the others do not affect plan length and only increase problem instance size slightly.

ICAPS Conference 2003 Conference Paper

Symmetry Reduction for SAT Representations of Transition Systems

• Jussi Rintanen

Symmetries are inherent in systems that consist of several interchangeable objects or components. When reasoning about such systems, big computational savings can be obtained if the presence of symmetries is recognized. In earlier work, symmetries in constraint satisfaction problems have been handled by introducing symmetry-breaking constraints. In reasoning about transition systems, notably in model-checking and reachability analysis in computer-aided verification, symmetries have been handled by symmetry reduction algorithms that eliminate redundant search caused by symmetries. In this work, we investigate symmetry handling in a problem in the intersection of these two areas: handling symmetries in representations of transition systems in the propositional logic. The problem shows up in representations of AI planning as a satisfiability problem, and in recent approaches to model-checking that represent transition systems as propositional formulae. Symmetry-breaking constraints can be added to the propositional logic representation of transition sequences for removing all the symmetry at one point of time, but removing symmetry from the whole transition sequence is much more difficult, and has not been addressed in earlier work. We present a solution to the problem.

ICAPS Conference 2002 Conference Paper

Backward Plan Construction for Planning with Partial Observability

• Jussi Rintanen

We present algorithms for partially observable planning that iteratively compute belief states with an increasing distance to the goal states. The algorithms handle nondeterministic operators, but restrict to problem instances with a finite upper bound on execution length, that is plans without loops. We discuss an implementation of the algorithms which uses binary decision diagrams for representing belief states. It turns out that generation of new belief states from existing ones, corresponding to the use of conditional branches in the plans, can very naturally be represented as standard operations on binary decision diagrams. We also give a preliminary experimental evaluation of the algorithms.

LPAR Conference 2001 Conference Paper

Partial Implicit Unfolding in the Davis-Putnam Procedure for Quantified Boolean Formulae

• Jussi Rintanen

Abstract Quantified Boolean formulae offer a means of representing many propositional formula exponentially more compactly than propositional logic. Recent work on automating reasoning with QBF has concentrated on extending the Davis-Putnam procedure to handle QBF. Although the resulting procedures make it possible to evaluate QBF that could not be efficiently reduced to propositional logic (requiring worst-case exponential space), its efficiency often lags much behind the reductive approach when the reduction is possible. We attribute this inefficiency to the fact that many of the unit resolution steps possible in the reduced (propositional logic) formula are not performed in the corresponding QBF. To combine the conciseness of the QBF representation and the stronger inferences available in the unquantified representation, we introduce a stronger propagation algorithm for QBF which could be seen as partially unfolding the universal quantification. The algorithm runs in worst-case exponential time, like the reduction of QBF to propositional logic, but needs only polynomial space. By restricting the algorithm the exponential behavior can be avoided while still preserving many of the useful inferences.

AAAI Conference 2000 Conference Paper

An Iterative Algorithm for Synthesizing Invariants

• Jussi Rintanen

We present a general algorithm for synthesizing state invariants that speed up automated planners and have other applications in reasoning about change. Invariants are facts that hold in all states that are reachable from an initial state by the application of a number of operators. In contrast to earlier work, we recognize the fact that establishing an invariant may require considering other invariants, and this in turn seems to require viewing synthesis of invariants as fixpoint computation. Also, the algorithm is not inherently restricted to invariants of particular syntactic forms.

ECAI Conference 2000 Conference Paper

Incorporation of Temporal Logic Control into Plan Operators

• Jussi Rintanen

IJCAI Conference 1999 Conference Paper

Improvements to the Evaluation of Quantified Boolean Formulae

• Jussi Rintanen

We present a theorem-prover for quantified Boolean formulae and evaluate it on random quantified formulae and formulae that represent problems from automated planning. Even though the notion of quantified Boolean formula is theoretically important, automated reasoning with QBF has not been thoroughly investigated. Universal quantifiers are needed in representing many computational problems that cannot be easily translated to the propositional logic and solved by satisfiability algorithms. Therefore efficient reasoning with QBF is important. The Davis-Putnam procedure can be extended to evaluate quantified Boolean formulae. A straightforward algorithm of this kind is not very efficient. We identify universal quantifiers as the main area where improvements to the basic algorithm can be made. We present a number of techniques for reducing the amount of search that is needed, and evaluate their effectiveness by running the algorithm on a collection of formulae obtained from planning and generated randomly. For the structured problems we consider, the techniques lead to a dramatic speed-up.

AIJ Journal 1998 Journal Article

Lexicographic priorities in default logic

• Jussi Rintanen

Resolving conflicts between default rules is a major subtask in performing default reasoning. A declarative way of controlling the resolution of conflicts is to assign priorities to default rules, and to prevent conflict resolution in ways that violate the priorities. This work extends Reiter's default logic with a priority mechanism that is based on lexicographic comparison. Given a default theory and a partial ordering on the defaults, the preferred extensions are the lexicographically best extensions. We discuss alternative ways of using lexicographic comparison, and investigate their properties and relations between them. The applicability of the priority mechanism to inheritance reasoning is investigated by presenting two translations from inheritance networks to prioritized default theories, and relating them to inheritance theories presented earlier by Gelfond and Przymusinska and by Brewka.