Arrow Research search

Author name cluster

Álvaro Torralba

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

49 papers
2 author rows

Possible papers

49

AAAI Conference 2026 Conference Paper

Dominance Pruning and Heuristics in Optimal Adversarial Non-Deterministic Planning

  • Rasmus G. Tollund
  • Álvaro Torralba

In many planning problems there are non-deterministic actions for which the outcome cannot be fully controlled by the planning agent. For critical tasks, we need to find a strategy that achieves the goal within a predictable time-frame and/or cost. Thus, we consider an adversarial planning setting and compute optimal policies that optimize the worst-case cost to reach the goal. In this work, we introduce domain-independent optimal heuristic search algorithms for this adversarial setting. To guide the search, we show how to leverage classical planning heuristics by applying single-outcome determinization. We also generalize dominance techniques, that analyse when a state is as good as another, to the non-deterministic setting and apply them to prune the search space. Our experimental analysis shows that both methods greatly help to compute optimal policies across multiple domains.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Not Everything Is Permitted: Constrained Cartesian Abstractions for Optimal Classical Planning

  • Martín Pozo
  • Álvaro Torralba
  • Carlos Linares López

Cartesian abstractions can flexibly approximate planning tasks to generate admissible heuristic functions. Constrained abstractions use state constraints, such as mutexes, to eliminate parts of the abstraction that cannot belong to solutions for the original problem. While this has been successfully applied to simple forms of abstraction, no previous work has explored how to do this for Cartesian abstractions. We introduce constrained Cartesian abstractions, which leverage state constraints in multiple ways: to prune spurious transitions and to simplify or even remove abstract states. Moreover, we also use disambiguation to better guide the counterexample-guided process used to generate the abstractions. Our experimental results show that the resulting constrained Cartesian abstractions induce more informed heuristics than their non-constrained counterpart.

PDF Details DOI

ECAI Conference 2025 Conference Paper

Conditional Dominance Analysis for Classical Planning

  • Anna Wilhelm
  • Álvaro Torralba

Dominance analysis methods compare pairs of states in a planning task to prove that one is at least as close to the goal as other. Existing methods compute fact-dominance relations, which identify facts that are at least as good as others in any situation. However, this is only possible when a fact is at least as good as another in every single possible context. We introduce a new notion of conditional dominance, which can identify that a fact dominates another under certain conditions. We extend previous methods to compute dominance by taking into account a set of “contexts” in order to find maximal dominance relations. We propose several strategies to find relevant contexts automatically and show that even with one single condition, one can achieve significant pruning in certain domains.

Details

AIJ Journal 2024 Journal Article

Boosting optimal symbolic planning: Operator-potential heuristics

  • Daniel Fišer
  • Álvaro Torralba
  • Jörg Hoffmann

Heuristic search guides the exploration of states via heuristic functions h estimating remaining cost. Symbolic search instead replaces the exploration of individual states with that of state sets, compactly represented using binary decision diagrams (BDDs). In cost-optimal planning, heuristic explicit search performs best overall, but symbolic search performs best in many individual domains, so both approaches together constitute the state of the art. Yet combinations of the two have so far not been an unqualified success, because (i) h must be applicable to sets of states rather than individual ones, and (ii) the different state partitioning induced by h may be detrimental for BDD size. Many competitive heuristic functions in planning do not qualify for (i), and it has been shown that even extremely informed heuristics can deteriorate search performance due to (ii). Here we show how to achieve (i) for a state-of-the-art family of heuristic functions, namely potential heuristics. These assign a fixed potential value to each state-variable/value pair, ensuring by LP constraints that the sum over these values, for any state, yields an admissible and consistent heuristic function. Our key observation is that we can express potential heuristics through fixed potential values for operators instead, capturing the change of heuristic value induced by each operator. These reformulated heuristics satisfy (i) because we can express the heuristic value change as part of the BDD transition relation in symbolic search steps. We run exhaustive experiments on IPC benchmarks, evaluating several different instantiations of potential heuristics in forward, backward, and bi-directional symbolic search. Our operator-potential heuristics turn out to be highly beneficial, in particular they hardly ever suffer from (ii). Our best configurations soundly beat previous optimal symbolic planning algorithms, bringing them on par with the state of the art in optimal heuristic explicit search planning in overall performance.

Details DOI

ICAPS Conference 2024 Conference Paper

Computing Planning Centroids and Minimum Covering States Using Symbolic Bidirectional Search

  • Alberto Pozanco
  • Álvaro Torralba
  • Daniel Borrajo

In some scenarios, planning agents might be interested in reaching states that keep certain relationships with respect to a set of goals. Recently, two of these types of states were proposed: centroids, which minimize the average distance to the goals; and minimum covering states, which minimize the maximum distance to the goals. Previous approaches compute these states by searching forward either in the original or a reformulated task. In this paper, we propose several algorithms that use symbolic bidirectional search to efficiently compute centroids and minimum covering states. Experimental results in existing and novel benchmarks show that our algorithms scale much better than previous approaches, establishing a new state-of-the-art technique for this problem.

Details

ECAI Conference 2024 Conference Paper

Gotta Catch 'Em All! Sequence Flaws in CEGAR for Classical Planning

  • Martín Pozo
  • Álvaro Torralba
  • Carlos Linares López

Counterexample-Guided Abstraction Refinement (CEGAR) is a prominent technique to generate Cartesian abstractions for guiding search in cost-optimal planning. The core idea is to iteratively refine the abstraction, by finding a flaw in the current optimal abstract plan. Previous works find only a single flaw, by executing the abstract plan in the concrete state space and stopping when such execution cannot be continued. We show, however, that many flaws can be identified on a single plan. To that end, we introduce sequence flaws, which execute the plan in a Cartesian relaxation of the task to characterize issues beyond the first flaw found along its execution. This greatly increases the flexibility of CEGAR regarding how to refine the abstraction. Our experiments show that a high number of sequence flaws exist in most abstract plans across existing benchmarks. We observe that the selected flaw has a high impact on the resulting heuristic, opening new research opportunities for better selection strategies.

Details

ECAI Conference 2024 Conference Paper

Merge-and-Shrink Heuristics for SSPs with Prune Transformations

  • Thorsten Klößner
  • Álvaro Torralba
  • Marcel Steinmetz
  • Silvan Sievers

The merge-and-shrink framework is a powerful tool for constructing state-of-the-art admissible heuristics in classical planning. Recent work has begun generalizing the complex theory behind this framework to probabilistic planning in forms of stochastic shortest-path problems (SSPs). There however remain two important gaps. Firstly, although the previous work makes substantial efforts, the probabilistic merge-and-shrink theory is still incomplete, lacking in particular prune transformations, i. e. , transformations discarding uninteresting states, effectively reducing the size of the abstraction without losing relevant information. Secondly, an actual implementation and experimental evaluation of the merge-and-shrink framework for SSPs is so far missing. Here, we round off the previous work by contributing both a theoretical analysis of prune transformations, as well as an empirical evaluation of merge-and-shrink heuristics. Our results show that merge-and-shrink heuristics outperform previous single abstraction heuristics, but do not quite reach the performance of state-of-the-art additive combinations of such heuristics yet.

Details

ICAPS Conference 2024 Conference Paper

Optimal Infinite Temporal Planning: Cyclic Plans for Priced Timed Automata

  • Rasmus G. Tollund
  • Nicklas S. Johansen
  • Kristian Ø. Nielsen
  • Álvaro Torralba
  • Kim G. Larsen

Many applications require infinite plans ---i. e. an infinite sequence of actions--- in order to carry out some given process indefinitely. In addition, it is desirable to guarantee optimality. In this paper, we address this problem in the setting of doubly-priced timed automata, where we show how to efficiently compute ratio-optimal cycles for optimal infinite plans. For efficient computation, we present symbolic λ-deduction (S-λD), an any-time algorithm that uses a symbolic representation (priced zones) to search the state-space with a compact representation of the time constraints. Our approach guarantees termination while arriving at an optimal solution. Our experimental evaluation shows that S-λD outperforms the alternative of searching in the concrete state space; is very robust with respect to fine-grained temporal constraints; and has a very good anytime behaviour.

Details

ICAPS Conference 2023 Conference Paper

A Theory of Merge-and-Shrink for Stochastic Shortest Path Problems

  • Thorsten Klößner
  • Álvaro Torralba
  • Marcel Steinmetz
  • Silvan Sievers

The merge-and-shrink framework is a powerful tool to construct state space abstractions based on factored representations. One of its core applications in classical planning is the construction of admissible abstraction heuristics. In this paper, we develop a compositional theory of merge-and-shrink in the context of probabilistic planning, focusing on stochastic shortest path problems (SSPs). As the basis for this development, we contribute a novel factored state space model for SSPs. We show how general transformations, including abstractions, can be formulated on this model to derive admissible and/or perfect heuristics. To formalize the merge-and-shrink framework for SSPs, we transfer the fundamental merge-and-shrink transformations from the classical setting: shrinking, merging, and label reduction. We analyze the formal properties of these transformations in detail and show how the conditions under which shrinking and label reduction lead to perfect heuristics can be extended to the SSP setting.

Details

ICAPS Conference 2023 Conference Paper

Automatic Metamorphic Test Oracles for Action-Policy Testing

  • Jan Eisenhut
  • Álvaro Torralba
  • Maria Christakis
  • Jörg Hoffmann 0001

Testing is a promising way to gain trust in learned action policies π. Prior work on action-policy testing in AI planning formalized bugs as states t where π is sub-optimal with respect to a given testing objective. Deciding whether or not t is a bug is as hard as (optimal) planning itself. How can we design test oracles able to recognize some states t to be bugs efficiently? Recent work introduced metamorphic oracles which compare policy behavior on state pairs (s, t) where t is easier to solve; if π performs worse on t than on s, we know that t is a bug. Here, we show how to automatically design such oracles in classical planning, based on simulation relations between states. We introduce two oracle families of this kind: first, morphing query states t to obtain suitable s; second, maintaining and comparing upper bounds on h* across the states encountered during testing. Our experiments on ASNet policies show that these oracles can find bugs much more quickly than the existing alternatives, which are search-based; and that the combination of our oracles with search-based ones almost consistently dominates all other oracles.

Details

ICAPS Conference 2023 Conference Paper

Efficient Evaluation of Large Abstractions for Decoupled Search: Merge-and-Shrink and Symbolic Pattern Databases

  • Daniel Gnad 0001
  • Silvan Sievers
  • Álvaro Torralba

Abstraction heuristics are a state-of-the-art technique to solve classical planning problems optimally. A common approach is to precompute many small abstractions and combine them admissibly using cost partitioning. Recent work has shown that this approach does not work out well when using such heuristics for decoupled state space search, where search nodes represent potentially large sets of states. This is due to the fact that admissibly combining the estimates of several heuristics without sacrificing accuracy is NP-hard for decoupled states. In this work we propose to use a single large abstraction instead. We focus on merge-and-shrink and symbolic pattern database heuristics, which are designed to produce such abstractions. For these heuristics, we prove that the evaluation of decoupled states is NP-hard in general, but we also identify conditions under which it is polynomial. We introduce algorithms for both the general and the polynomial case. Our experimental evaluation shows that single large abstraction heuristics lead to strong performance when the heuristic evaluation is polynomial.

Details

SoCS Conference 2022 Conference Paper

Additive Pattern Databases for Decoupled Search

  • Silvan Sievers
  • Daniel Gnad 0001
  • Álvaro Torralba

Abstraction heuristics are the state of the art in optimal classical planning as heuristic search. Despite their success for explicit-state search, though, abstraction heuristics are not available for decoupled state-space search, an orthogonal reduction technique that can lead to exponential savings by decomposing planning tasks. In this paper, we show how to compute pattern database (PDB) heuristics for decoupled states. The main challenge lies in how to additively employ multiple patterns, which is crucial for strong search guidance of the heuristics. We show that in the general case, for arbitrary collections of PDBs, computing the heuristic for a decoupled state is exponential in the number of leaf components of decoupled search. We derive several variants of decoupled PDB heuristics that allow to additively combine PDBs avoiding this blow-up and evaluate them empirically.

Details

ICAPS Conference 2022 Conference Paper

Beyond Stars - Generalized Topologies for Decoupled Search

  • Daniel Gnad 0001
  • Álvaro Torralba
  • Daniel Fiser

Decoupled search decomposes a classical planning task by partitioning its variables such that the dependencies between the resulting factors form a star topology. In this topology, a single center factor can interact arbitrarily with a set of leaf factors. The leaves, however, can interact with each other only indirectly via the center. In this work, we generalize this structural requirement and allow arbitrary topologies. The components must not overlap, i. e. , each state variable is assigned to exactly one factor, but the interaction between factors is not restricted. We show how this generalization is connected to star topologies, which implies the correctness of decoupled search with this novel type of decomposition. We introduce factoring methods that automatically identify these topologies on a given planning task. Empirically, the generalized factorings lead to increased applicability of decoupled search on standard IPC benchmarks, as well as to superior performance compared to known factoring methods.

Details

AAAI Conference 2022 Conference Paper

Homomorphisms of Lifted Planning Tasks: The Case for Delete-Free Relaxation Heuristics

  • Rostislav Horčík
  • Daniel Fišer
  • Álvaro Torralba

Classical planning tasks are modelled in PDDL which is a schematic language based on first-order logic. Most of the current planners turn this lifted representation into a propositional one via a grounding process. However, grounding may cause an exponential blowup. Therefore it is important to investigate methods for searching for plans on the lifted level. To build a lifted state-based planner, it is necessary to invent lifted heuristics. We introduce maps between PDDL tasks preserving plans allowing us to transform a PDDL task into a smaller one. We propose a novel method for computing lifted (admissible) delete-free relaxed heuristics via grounding of the smaller task and computing the (admissible) delete-free relaxed heuristics there. This allows us to transfer the knowledge about relaxed heuristics from the grounded level to the lifted level.

PDF Details

AAAI Conference 2022 Conference Paper

Operator-Potential Heuristics for Symbolic Search

  • Daniel Fišer
  • Álvaro Torralba
  • Jörg Hoffmann

Symbolic search, using Binary Decision Diagrams (BDDs) to represent sets of states, is a competitive approach to optimal planning. Yet heuristic search in this context remains challenging. The many advances on admissible planning heuristics are not directly applicable, as they evaluate one state at a time. Indeed, progress using heuristic functions in symbolic search has been limited and even very informed heuristics have been shown to be detrimental. Here we show how this connection can be made stronger for LP-based potential heuristics. Our key observation is that, for this family of heuristic functions, the change of heuristic value induced by each operator can be precomputed. This facilitates their smooth integration into symbolic search. Our experiments show that this can pay off significantly: we establish a new state of the art in optimal symbolic planning.

PDF Details

ICAPS Conference 2022 Conference Paper

Operator-Potentials in Symbolic Search: From Forward to Bi-directional Search

  • Daniel Fiser
  • Álvaro Torralba
  • Jörg Hoffmann 0001

Symbolic search using binary decision diagrams is a state-of-the-art technique for cost-optimal planning. Heuristic search in this context has been problematic as even a very informative heuristic can be detrimental in case it induces difficult-to-represent state partitionings. It was recently shown that operator-potential heuristics can address this issue in forward search by computing a numeric potential for each operator corresponding to the change of the heuristic value induced by that operator. Forward search is, however, not the best known variant of symbolic search. Here we investigate the integration with backward and bi-directional search instead. We prove that forward search (distance-to-goal) operator-potential heuristics can be turned into backward search (distance-to-initial-state) heuristics elegantly in this context, by summing the backward search path operator-potentials with the initial state goal-distance estimate. We run exhaustive experiments on IPC benchmarks, showing that significant performance improvements can be obtained over symbolic forward search and other state-of-the-art techniques.

Details

ICAPS Conference 2022 Conference Paper

Optimal Mixed Strategies for Cost-Adversarial Planning Games

  • Rostislav Horcík
  • Álvaro Torralba
  • Pavel Rytír
  • Lukás Chrpa
  • Stefan Edelkamp

This paper shows that domain-independent tools from classical planning can be used to model and solve a broad class of game-theoretic problems we call Cost-Adversarial Planning Games (CAPGs). We define CAPGs as 2-player normal-form games specified by a planning task and a finite collection of cost functions. The first player (a planning agent) strives to solve a planning task optimally but has limited knowledge about its action costs. The second player (an adversary agent) controls the actual action costs. Even though CAPGs need not be zero-sum, every CAPG has an associated zero-sum game whose Nash equilibrium provides the optimal randomized strategy for the planning agent in the original CAPG. We show how to find the Nash equilibrium of the associated zero-sum game using a cost-optimal planner via the Double Oracle algorithm. To demonstrate the expressivity of CAPGs, we formalize a patrolling security game and several IPC domains as CAPGs.

Details

ICAPS Conference 2022 Conference Paper

Pattern Selection Strategies for Pattern Databases in Probabilistic Planning

  • Thorsten Klößner
  • Marcel Steinmetz
  • Álvaro Torralba
  • Jörg Hoffmann 0001

Recently, pattern databases have been extended to probabilistic planning, to derive heuristics for the objectives of goal probability maximization and expected cost minimization. While this approach yields both theoretical and practical advantages over techniques relying on determinization, the problem of selecting the patterns in the first place has only been scantily addressed as yet, through a method that systematically enumerates patterns up to a fixed size. Here we close this gap, extending pattern generation techniques known from classical planning to the probabilistic case. We consider hill-climbing as well as counter-example guided abstraction refinement (CEGAR) approaches, and show how they need to be adapted to obtain desired properties such as convergence to the perfect value function in the limit. Our experiments show substantial improvements over systematic pattern generation and the previous state of the art.

Details

PRL Workshop 2022 Workshop Paper

Scaling up ML-based Black-box Planning with Partial STRIPS Models

  • Matias Greco
  • Álvaro Torralba
  • Jorge A. Baier
  • Hector Palacios

A popular approach for sequential decision-making is to perform simulator-based search guided with Machine Learning (ML) methods like policy learning. On the other hand, modelrelaxation heuristics can guide the search effectively if a full declarative model is available. In this work, we consider how a practitioner can improve ML-based black-box planning on settings where a complete symbolic model is not available. We show that specifying an incomplete STRIPS model that describes only part of the problem enables the use of relaxation heuristics. Our findings on several planning domains suggest that this is an effective way to improve ML-based black-box planning beyond collecting more data or tuning ML architectures.

PDF Details

ICAPS Conference 2021 Conference Paper

Automatic Instance Generation for Classical Planning

  • Álvaro Torralba
  • Jendrik Seipp
  • Silvan Sievers

The benchmarks from previous International Planning Competitions (IPCs) are the de-facto standard for evaluating planning algorithms. The IPC set is both a collection of planning domains and a selection of instances from these domains. Most of the domains come with a parameterized generator that generates new instances for a given set of parameter values. Due to the steady progress of planning research some of the instances that were generated for past IPCs are inadequate for evaluating current planners. To alleviate this problem, we introduce Autoscale, an automatic tool that selects instances for a given domain. Autoscale takes into account constraints from the domain designer as well as the performance of current planners to generate an instance set of appropriate difficulty, while avoiding too much bias with respect to the considered planners. We show that the resulting benchmark set is superior to the IPC set and has the potential of improving empirical evaluation of planning research.

Details

AAAI Conference 2021 Conference Paper

Faster Stackelberg Planning via Symbolic Search and Information Sharing

  • Álvaro Torralba
  • Patrick Speicher
  • Robert Künnemann
  • Marcel Steinmetz
  • Jörg Hoffmann

Stackelberg planning is a recent framework where a leader and a follower each choose a plan in the same planning task, the leader’s objective being to maximize plan cost for the follower. This formulation naturally captures security-related (leader=defender, follower=attacker) as well as robustnessrelated (leader=adversarial event, follower=agent) scenarios. Solving Stackelberg planning tasks requires solving many related planning tasks at the follower level (in the worst case, one for every possible leader plan). Here we introduce new methods to tackle this source of complexity, through sharing information across follower tasks. Our evaluation shows that these methods can significantly reduce both the time needed to solve follower tasks and the number of follower tasks that need to be solved in the first place.

PDF Details

AAAI Conference 2021 Conference Paper

On the Optimal Efficiency of A* with Dominance Pruning

  • Álvaro Torralba

A well known result is that, given a consistent heuristic and no other source of information, A∗ does expand a minimal number of nodes up to tie-breaking. We extend this analysis for A∗ with dominance pruning, which exploits a dominance relation to eliminate some nodes during the search. We show that the expansion order of A∗ is not necessarily optimally efficient when considering dominance pruning with arbitrary dominance relations, but it remains optimally efficient under certain restrictions for the heuristic and dominance relation.

PDF Details

ICAPS Conference 2021 Conference Paper

Pattern Databases for Goal-Probability Maximization in Probabilistic Planning

  • Thorsten Klößner
  • Jörg Hoffmann 0001
  • Marcel Steinmetz
  • Álvaro Torralba

Heuristic search algorithms for goal-probability maximization (MaxProb) have been known since a decade. Yet prior work on heuristic functions for MaxProb relies on determinization, not actually taking the probabilities into account. Here we begin to fix this, by introducing MaxProb pattern databases (PDB). We show that, for the special case of PDBs in contrast to more general abstractions, abstract transitions have a unique probability so that the abstract planning task is still an MDP. The resulting heuristic functions are admissible, i. e. , they upper-bound the real goal probability. We identify conditions allowing to admissibly multiply heuristic values across several PDBs. Our experiments show that even non-probabilistic PDB heuristics often outperform previous MaxProb heuristics, and that our new probabilistic PDBs can in turn yield significant performance gains over non-probabilistic ones.

Details

SoCS Conference 2020 Conference Paper

Applying Monte-Carlo Tree Search in HTN Planning

  • Julia Wichlacz
  • Daniel Höller
  • Álvaro Torralba
  • Jörg Hoffmann 0001

Search methods are useful in hierarchical task network (HTN) planning to make performance less dependent on the domain knowledge provided, and to minimize plan costs. Here we investigate Monte-Carlo tree search (MCTS) as a new algorithmic alternative in HTN planning. We implement combinations of MCTS with heuristic search in PANDA. We furthermore investigate MCTS in JSHOP, to address lifted (non-grounded) planning, leveraging the fact that, in contrast to other search methods, MCTS does not require a grounded task representation. Our new methods yield coverage performance on par with the state of the art, but in addition can effectively minimize plan cost over time.

Details

IJCAI Conference 2020 Conference Paper

Plan-Space Explanation via Plan-Property Dependencies: Faster Algorithms & More Powerful Properties

  • Rebecca Eifler
  • Marcel Steinmetz
  • Álvaro Torralba
  • Jörg Hoffmann

Justifying a plan to a user requires answering questions about the space of possible plans. Recent work introduced a framework for doing so via plan-property dependencies, where plan properties p are Boolean functions on plans, and p entails q if all plans that satisfy p also satisfy q. We extend this work in two ways. First, we introduce new algorithms for computing plan-property dependencies, leveraging symbolic search and devising pruning methods for this purpose. Second, while the properties p were previously limited to goal facts and so-called action-set (AS) properties, here we extend them to LTL. Our new algorithms vastly outperform the previous ones, and our methods for LTL cause little overhead on AS properties.

PDF Details DOI

ICAPS Conference 2019 Conference Paper

Bridging the Gap between Abstractions and Critical-Path Heuristics via Hypergraphs

  • Marcel Steinmetz
  • Álvaro Torralba

Abstractions and critical-path heuristics are among the most important families of admissible heuristics in classical planning. In this paper, we present a new family of heuristics, which we name hyperabstractions, given by the combination of the principal ideas underlying abstractions and critical-path heuristics. Hyperabstractions approximate goal distances through a mapping from states to sets of abstract states. The abstract transition behavior forms a relation between abstract states and sets of abstract states, and is formally represented via the notion of hypergraphs. We show that both abstractions and critical-path heuristics can naturally be expressed as members of this family. Moreover, we devise a method to construct hyperabstractions, using either a set of abstractions or a critical-path heuristic as a seed, in a way that guarantees that the resulting distance estimations dominate those of the input heuristics, sometimes even strictly. By finding suitable cost partitionings for hyperabstraction heuristics, this dominance result is preserved even in comparison to the additive combination of the input heuristics. Our experiments indicate the potential of this new class of heuristics, opening a wide range of future research topics.

Details

SoCS Conference 2019 Conference Paper

Interleaving Search and Heuristic Improvement

  • Santiago Franco
  • Álvaro Torralba

Abstraction heuristics are a leading approach for deriving admissible estimates in cost-optimal planning. However, a drawback with respect to other families of heuristics is that they require a preprocessing phase for choosing the abstraction, computing the abstract distances, and/or suitable cost-partitionings. Typically, this is performed in advance by a fixed amount of time, even though some instances could be solved much faster with little or no preprocessing. We interleave the computation of abstraction heuristics with search, avoiding a long precomputation phase and allowing information from the search to be used for guiding the abstraction selection. To evaluate our ideas, we implement them on a planner that uses a single symbolic PDB. Our results show that delaying the preprocessing is not harmful in general even when an important amount of preprocessing is required to obtain good performance.

Details

AAAI Conference 2019 Conference Paper

Learning How to Ground a Plan – Partial Grounding in Classical Planning

  • Daniel Gnad
  • Álvaro Torralba
  • Martín Domínguez
  • Carlos Areces
  • Facundo Bustos

Current classical planners are very successful in finding (nonoptimal) plans, even for large planning instances. To do so, most planners rely on a preprocessing stage that computes a grounded representation of the task. Whenever the grounded task is too big to be generated (i. e. , whenever this preprocess fails) the instance cannot even be tackled by the actual planner. To address this issue, we introduce a partial grounding approach that grounds only a projection of the task, when complete grounding is not feasible. We propose a guiding mechanism that, for a given domain, identifies the parts of a task that are relevant to find a plan by using off-the-shelf machine learning methods. Our empirical evaluation attests that the approach is capable of solving planning instances that are too big to be fully grounded.

PDF Details

IJCAI Conference 2019 Conference Paper

Merge-and-Shrink Task Reformulation for Classical Planning

  • Álvaro Torralba
  • Silvan Sievers

The performance of domain-independent planning systems heavily depends on how the planning task has been modeled. This makes task reformulation an important tool to get rid of unnecessary complexity and increase the robustness of planners with respect to the model chosen by the user. In this paper, we represent tasks as factored transition systems (FTS), and use the merge-and-shrink (M&S) framework for task reformulation for optimal and satisficing planning. We prove that the flexibility of the underlying representation makes the M&S reformulation methods more powerful than the counterparts based on the more popular finite-domain representation. We adapt delete-relaxation and M&S heuristics to work on the FTS representation and evaluate the impact of our reformulation.

PDF Details

AAAI Conference 2019 Conference Paper

Operator Mutexes and Symmetries for Simplifying Planning Tasks

  • Daniel Fišer
  • Álvaro Torralba
  • Alexander Shleyfman

Simplifying classical planning tasks by removing operators while preserving at least one optimal solution can significantly enhance the performance of planners. In this paper, we introduce the notion of operator mutex, which is a set of operators that cannot all be part of the same (strongly) optimal plan. We propose four different methods for inference of operator mutexes and experimentally verify that they can be found in a sizable number of planning tasks. We show how operator mutexes can be used in combination with structural symmetries to safely remove operators from the planning task.

PDF Details

ICAPS Conference 2019 Conference Paper

Symbolic Planning with Axioms

  • David Speck 0001
  • Florian Geißer
  • Robert Mattmüller
  • Álvaro Torralba

Axioms are an extension for classical planning models that allow for modeling complex preconditions and goals exponentially more compactly. Although axioms were introduced in planning more than a decade ago, modern planning techniques rarely support axioms, especially in cost-optimal planning. Symbolic search is a popular and competitive optimal planning technique based on the manipulation of sets of states. In this work, we extend symbolic search algorithms to support axioms natively. We analyze different ways of encoding derived variables and axiom rules to evaluate them in a symbolic representation. We prove that all encodings are sound and complete, and empirically show that the presented approach outperforms the previous state of the art in costoptimal classical planning with axioms.

Details

IJCAI Conference 2018 Conference Paper

Completeness-Preserving Dominance Techniques for Satisficing Planning

  • Álvaro Torralba

Dominance pruning methods have recently been introduced for optimal planning. They compare states based on their goal distance to prune those that can be proven to be worse than others. In this paper, we introduce dominance techniques for satisficing planning. We extend the definition of dominance, showing that being closer to the goal is not a prerequisite for dominance in the satisficing setting. We develop a new method to automatically find dominance relations in which a state dominates another if it has achieved more serializable sub-goals. We take advantage of dominance relations in different ways; while in optimal planning their usage focused on dominance pruning and action selection, we also use it to guide enforced hill-climbing search, resulting in a complete algorithm.

PDF Details

AIJ Journal 2018 Journal Article

Symbolic perimeter abstraction heuristics for cost-optimal planning

  • Álvaro Torralba
  • Carlos Linares López
  • Daniel Borrajo

In the context of heuristic search within automated planning, abstraction heuristics map the problem into an abstract instance and use the optimal solution cost in the abstract state space as an estimate for the real solution cost. Their flexibility in choosing different abstract mappings makes abstractions a powerful tool to obtain domain-independent heuristics. Different types of abstraction heuristics exist depending on how the mapping is defined, like Pattern Databases (PDBs) or Merge-and-Shrink (M&S). In this paper, we consider two variants of PDBs, symbolic and perimeter PDBs, combining them to take advantage of their synergy. Symbolic PDBs use decision diagrams in order to efficiently traverse the abstract state space. Perimeter PDBs derive more informed estimates by first constructing a perimeter around the goal and then using it to initialize the abstract search. We generalize this idea by considering a hierarchy of abstractions. Our algorithm starts by constructing a symbolic perimeter around the goal and, whenever continuing the search becomes unfeasible, it switches to a more abstracted state space. By delaying the use of an abstraction, the algorithm derives heuristics as informed as possible. Moreover, we prove that M&S abstractions with a linear merge strategy can be efficiently represented as decision diagrams, enabling the use of symbolic search with M&S abstractions as well as with PDBs. Our experimental evaluation shows that symbolic perimeter abstractions are competitive with other state-of-the-art heuristics.

Details DOI

AIJ Journal 2017 Journal Article

Efficient symbolic search for cost-optimal planning

  • Álvaro Torralba
  • Vidal Alcázar
  • Peter Kissmann
  • Stefan Edelkamp

In cost-optimal planning we aim to find a sequence of operators that achieve a set of goals with minimum cost. Symbolic search with Binary Decision Diagrams (BDDs) performs efficient state space exploration in terms of time and memory. This is crucial in optimal settings, in which large parts of the state space must be explored in order to prove optimality. However, the development of accurate heuristics for explicit-state search in recent years have left symbolic search techniques in a secondary place. In this article we propose two orthogonal improvements for symbolic search planning. On the one hand, we analyze and compare different methods for image computation in order to efficiently perform the successor generation on symbolic search. Image computation is the main bottleneck of symbolic search algorithms so an efficient computation is paramount for efficient symbolic search planning. On the other hand, we study how to use state-invariant constraints to prune states in symbolic search. This is essential in regression search but it is yet to be exploited in symbolic search planners. Experiments with symbolic bidirectional uniform-cost search and symbolic A ⁎ search with PDBs show remarkable performance improvements on most IPC benchmark domains. Overall, with the help of our improvements, symbolic bidirectional search outperforms explicit-state search with state-of-the-art heuristics such as LM-cut across many different domains.

Details DOI

IJCAI Conference 2017 Conference Paper

From Qualitative to Quantitative Dominance Pruning for Optimal Planning

  • Álvaro Torralba

Dominance relations compare states to determine whether one is at least as good as another in terms of their goal distance. We generalize these qualitative yes/no relations to functions that measure by how much a state is better than another. This allows us to distinguish cases where the state is strictly closer to the goal. Moreover, we may obtain a bound on the difference in goal distance between two states even if there is no qualitative dominance. We analyze the multiple advantages that quantitative dominance has, like discovering coarser dominance relations, or trading dominance by g-value. Moreover, quantitative dominance can also be used to prove that an action starts an optimal plan from a given state. We introduce a novel action selection pruning that uses this to prune any other successor. Results show that quantitative dominance pruning greatly reduces the search space, significantly increasing the planners' performance.

PDF Details

IJCAI Conference 2017 Conference Paper

On Creating Complementary Pattern Databases

  • Santiago Franco
  • Álvaro Torralba
  • Levi H. S. Lelis
  • Mike Barley

A pattern database (PDB) for a planning task is a heuristic function in the form of a lookup table that contains optimal solution costs of a simplified version of the task. In this paper we introduce a method that sequentially creates multiple PDBs which are later combined into a single heuristic function. At a given iteration, our method uses estimates of the A* running time to create a PDB that complements the strengths of the PDBs created in previous iterations. We evaluate our algorithm using explicit and symbolic PDBs. Our results show that the heuristics produced by our approach are able to outperform existing schemes, and that our method is able to create PDBs that complement the strengths of other existing heuristics such as a symbolic perimeter heuristic.

PDF Details

SoCS Conference 2017 Conference Paper

Symbolic Leaf Representation in Decoupled Search

  • Daniel Gnad 0001
  • Álvaro Torralba
  • Jörg Hoffmann 0001

Star-Topology Decoupled Search has recently been introduced in classical planning. It splits the planning task into a set of components whose dependencies take a star structure, where one center component interacts with possibly many leaf components. Here we address a weakness of decoupled search, namely large leaf components, whose state space is enumerated explicitly. We propose a symbolic representation of the leaf state spaces via decision diagrams, which can be dramatically smaller, and also more runtime efficient. We further introduce a symbolic version of the LM-cut heuristic, that nicely connects to our new leaf representation. We show empirically that the symbolic representation indeed pays off when the leaf components are large.

Details

ICAPS Conference 2017 Conference Paper

Symmetry Breaking in Star-Topology Decoupled Search

  • Daniel Gnad 0001
  • Álvaro Torralba
  • Alexander Shleyfman
  • Jörg Hoffmann 0001

Symmetry breaking is a well-known method for search reduction. It identifies state-space symmetries prior to search, and prunes symmetric states during search. A recent proposal, star-topology decoupled search, is to search not in the state space, but in a factored version thereof, which avoids the multiplication of states across leaf components in an underlying star-topology structure. We show that, despite the much more complex structure of search states -- so-called decoupled states -- symmetry breaking can be brought to bear in this framework as well. Starting from the notion of structural symmetries over states, we identify a sub-class of such symmetries suitable for star-topology decoupled search, and we show how symmetries from that sub-class induce symmetry relations over decoupled states. We accordingly extend the routines required for search pruning and solution reconstruction. The resulting combined method can be exponentially better than both its components in theory, and this synergetic advantage is also manifested in practice: empirically, our method reliably inherits the best of its base components, and often outperforms them both.

Details

ICAPS Conference 2016 Conference Paper

Practical Undoability Checking via Contingent Planning

  • Jeanette Daum
  • Álvaro Torralba
  • Jörg Hoffmann 0001
  • Patrik Haslum
  • Ingo Weber

We consider a general concept of undoability, asking whether a given action can always be undone, no matter which state it is applied to. This generalizes previous concepts of invertibility, and is relevant for search as well as applications. Naïve undoability checking requires to enumerate all states an action is applicable to. Extending and operationalizing prior work in this direction, we introduce a compilation into contingent planning, replacing such enumeration by standard techniques handling large belief states. We furthermore introduce compilations for checking whether one can always get back to an at-least-as-good state, as well as for determining partial undoability, i. e. , undoability on a subset of states an action is applicable to. Our experiments on IPC benchmarks and in a cloud management application show that contingent planners are often effective at solving this kind of problem, hence providing a practical means for undoability checking.

Details

ICAPS Conference 2015 Conference Paper

A Reminder about the Importance of Computing and Exploiting Invariants in Planning

  • Vidal Alcázar
  • Álvaro Torralba

Throughout the years, extensive work has pointed out how important computing and exploiting invariants is in planning. However, no recent studies about their empirical impact regarding their ability to simplify and/or complete the model have been done. In particular, an analysis about the impact of invariants computed in regression from the goals is severely lacking, despite the existence of previous attempts to use this kind of invariants in different planning settings. In this work we focus on the ability of invariants to simplify the planning task in a preprocessing step. Our results show that this simplification significantly improves the performance of different optimal and satisficing planners.

Details

SoCS Conference 2015 Conference Paper

Focusing on What Really Matters: Irrelevance Pruning in Merge-and-Shrink

  • Álvaro Torralba
  • Peter Kissmann

Merge-and-shrink (M&S) is a framework to generate abstraction heuristics for cost-optimal planning. A recent approach computes simulation relations on a set of M&S abstractions in order to identify states that are better than others. This relation is then used for pruning states in the search when a "better" state is already known. We propose the usage of simulation relations inside the M&S framework in order to detect irrelevant transitions in abstract state spaces. This potentially simplifies the abstraction allowing M&S to derive more informed heuristics. We also tailor M&S to remove irrelevant operators from the planning task. Experimental results show the potential of our approach to construct well-informed heuristics and simplify the planning tasks prior to the search.

Details

ECAI Conference 2014 Conference Paper

"Distance"? Who Cares? Tailoring Merge-and-Shrink Heuristics to Detect Unsolvability

  • Jörg Hoffmann 0001
  • Peter Kissmann
  • Álvaro Torralba

Research on heuristic functions is all about estimating the length (or cost) of solution paths. But what if there is no such path? Many known heuristics have the ability to detect (some) unsolvable states, but that ability has always been treated as a by-product. No attempt has been made to design heuristics specifically for that purpose, where there is no need to preserve distances. As a case study towards leveraging that advantage, we investigate merge-and-shrink abstractions in classical planning. We identify safe abstraction steps (no information loss regarding solvability) that would not be safe for traditional heuristics. We design practical algorithm configurations, and run extensive experiments showing that our heuristics outperform the state of the art for proving planning tasks unsolvable.

Details

SoCS Conference 2013 Conference Paper

Constrained Symbolic Search: On Mutexes, BDD Minimization and More

  • Álvaro Torralba
  • Vidal Alcázar

Symbolic search allows saving large amounts of memory compared to regular explicit-state search algorithms. This is crucial in optimal settings, in which common search algorithms often exhaust the available memory. So far, the most successful uses of symbolic search have been bidirectional blind search and the generation of abstraction heuristics like Pattern Databases. Despite its usefulness, several common techniques in explicit-state search have not been employed in symbolic search. In particular, mutexes and other constraining invariants, techniques that have been proven essential when doing regression, are yet to be exploited in conjunction with BDDs. In this paper we analyze the use of such constraints in symbolic search and its combination with minimization techniques common in BDD manipulation. Experimental results show a significant increase in performance, considerably above the current state of the art in optimal planning.

Details

IJCAI Conference 2013 Conference Paper

Symbolic Merge-and-Shrink for Cost-Optimal Planning

  • Álvaro Torralba
  • Carlos Linares López
  • Daniel Borrajo

Symbolic PDBs and Merge-and-Shrink (M&S) are two approaches to derive admissible heuristics for optimal planning. We present a combination of these techniques, Symbolic Merge-and-Shrink (SM&S), which uses M&S abstractions as a relaxation criterion for a symbolic backward search. Empirical evaluation shows that SM&S has the strengths of both techniques deriving heuristics at least as good as the best of them for most domains.

PDF Details DOI

ICAPS Conference 2013 Conference Paper

Transition Trees for Cost-Optimal Symbolic Planning

  • Álvaro Torralba
  • Stefan Edelkamp
  • Peter Kissmann

Symbolic search with binary decision diagrams (BDDs) often saves huge amounts of memory and computation time. In this paper we propose two general techniques based on transition relation trees to advance BDD search by refining the image operator to compute the set of successors. First, the conjunction tree selects the set of applicable actions through filtering their precondition. Then, the disjunction tree combines each transition result. Transition trees are used to combine several transition relations, speeding up BDD search. Experiments with bidirectional symbolic blind and symbolic A* search on planning benchmarks are reported showing good performance on most IPC 2011 domains.

Details

SoCS Conference 2012 Conference Paper

Precomputed-Direction Heuristics for Suboptimal Grid-Based Path-finding

  • Álvaro Parra 0002
  • Álvaro Torralba
  • Carlos Linares López

This paper describes BubbleDragon, an entry in the 2012 Grid-based Path-Planning Competition. We aim to solve path-finding problems in the minimum time possible by precomputing paths from states in a region to its frontiers. Experimental results show that suboptimal paths for 1024x1024 grids can be retrieved in less than 1ms on average.

Details

ECAI Conference 2012 Conference Paper

Symbolic A * Search with Pattern Databases and the Merge-and-Shrink Abstraction

  • Stefan Edelkamp
  • Peter Kissmann
  • Álvaro Torralba

The efficiency of heuristic search planning crucially depends on the quality of the search heuristic, while succinct representations of state sets in decision diagrams can save large amounts of memory in the exploration. BDDA* - a symbolic version of A* search - combines the two approaches into one algorithm. This paper compares two of the leading heuristics for sequential-optimal planning: the merge-and-shrink and the pattern databases heuristic, both of which can be compiled into a vector of BDDs and be used in BDDA* . The impact of optimizing the variable ordering is highlighted and experiments on benchmark domains are reported.

Details

ICAPS Conference 2011 Conference Paper

Planning Multi-Modal Transportation Problems

  • José E. Flórez
  • Álvaro Torralba
  • Javier García 0001
  • Carlos Linares López
  • Ángel García Olaya
  • Daniel Borrajo

Multi-modal transportation is a logistics problem in which a set of goods have to be transported to different places, with the combination of at least two modes of transport, without a change of container for the goods. The goal of this paper is to describe TIMIPLAN, a system that solves multi-modal transportation problems in the context of a project for a big company. In this paper, we combine Linear Programming (LP) with automated planning techniques in order to obtain good quality solutions. The direct use of classical LP techniques is difficult in this domain, because of the non-linearity of the optimization function and constraints; and planning algorithms cannot deal with the entire problem due to the large number of resources involved. We propose a new hybrid algorithm, combining LP and planning to tackle the multi-modal transportation problem, exploiting the benefits of both kinds of techniques. The system also integrates an execution component that monitors the execution, keeping track of failures and replans if necessary, maintaining most of the plan in execution. We also present some experimental results that show the performance of the system.

Details

SoCS Conference 2011 Conference Paper

Size-Independent Additive Pattern Databases for the Pancake Problem

  • Álvaro Torralba
  • Carlos Linares López

The Pancake problem has become a classical combinatorial problem. Different attempts have been made to optimally solve it and/or to derive tighter bounds on the diameter of its state space for a different number of discs. Until very recently, the most successful technique for solving different instances optimally was based on Pattern Databases. Although different approaches have been tried, solutions with Pattern Databases on Pancakes with more than 19 discs have never been reported. In this work, a new technique is introduced which allows the definition of Additive Pattern Databases for solving Pancakes of an arbitrary length. As a result, this technique solves Pancake problems with twice as many discs as the largest ones solved nowadays with other techniques based on Pattern Databases saving up to two orders of magnitude of space.

Details
v2026.09.13