Author name cluster

Alvaro 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.

8 papers

1 author row

JAIR Journal 2025 Journal Article

Symbolic Search for Cost-Optimal Planning with Expressive Model Extensions

David Speck
Jendrik Seipp
Alvaro Torralba

In classical planning, the task is to derive a sequence of deterministic actions that changes the current fully-observable world state into one that satisfies a set of goal criteria. Algorithms for classical planning are domain-independent, i.e., they are not limited to a particular application and instead can be used to solve different types of reasoning problems. The main language for modeling such problems is the Planning Domain Definition Language (PDDL). Even though it provides many language features for expressing a wide range of planning tasks, most of today’s classical planners, especially optimal ones, support only a small subset of its features. The most widely supported fragment is lifted STRIPS plus types and action costs. While this fragment suffices to model some interesting planning tasks, using it to model more realistic problems often incurs a much higher modeling effort. Even if modeling is possible at all, solving the resulting tasks is often infeasible in practice, as the required encoding size increases exponentially. To address these issues, we show how to support more expressive modeling languages natively in optimal classical planning algorithms. Specifically, we focus on symbolic search, a state-of-the-art search algorithm that operates on sets of world states. We show how to extend symbolic search to support classical planning with conditional effects, axioms, and state-dependent action costs. All of these modeling features are expressive in the sense that compiling them away incurs a significant blow-up, so is it often necessary to support them natively. Except for blind (non-symbolic) search, our new symbolic search is the first optimal classical planning algorithm that supports these three modeling extensions in combination, and it even compares favorably to other state-of-the-art approaches that only support a subset of the extensions.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

What Makes You Special? Contrastive Heuristics Based on Qualified Dominance

Rasmus G. Tollund
Kim G. Larsen
Alvaro Torralba

In cost-optimal planning, dominance pruning methods discard states during the search that are dominated by others. However, the binary nature of pruning fails to exploit information when we cannot prove that a state is fully dominated. To this end, we introduce qualified dominance, an automatic method that given a pair of states s, t synthetizes a finite state automaton that represents a language of plans from s that are dominated by t. This not only explains why s cannot be pruned, but also can be used to improve the heuristic function to guide the search. This results in a new type of heuristic, which we call contrastive heuristics, that are dependent on the search performed so far. We provide the theoretical foundation for showing that contrastive heuristics can be used to find optimal plans even when their more informative estimates are not admissible.

PDF Details DOI

AAAI Conference 2024 Conference Paper

When CEGAR Meets Regression: A Love Story in Optimal Classical Planning

Martín Pozo
Alvaro Torralba
Carlos Linares Lopez

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, finding a flaw of the current optimal abstract plan. All existing approaches find these flaws by executing the abstract plan using progression in the original state space. Instead, we propose to do backward refinements by using regression from the goals. This results in a new type of flaw, that can identify invalid plan suffixes. The resulting abstractions are less focused on the initial state, but more informative on average, significantly improving the performance of current CEGAR-based techniques. Furthermore, they can be combined with forward refinements in several bidirectional strategies that provide the benefits of both methods.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Can I Really Do That? Verification of Meta-Operators via Stackelberg Planning

Florian Pham
Alvaro Torralba

Macro-operators are a common reformulation method in planning that adds high-level operators corresponding to a fixed sequence of primitive operators. We introduce meta-operators, which allow using different sequences of actions in each state. We show how to automatically verify whether a meta-operator is valid, i. e. , the represented behavior is always doable. This can be checked at once for all instantiations of the meta-operator and all reachable states via a compilation into Stackelberg planning, a form of adversarial planning. Our results show that meta-operators learned for multiple domains can often express useful high-level behaviors very compactly, improving planners' performance.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Reshaping State-Space Search: From Dominance to Contrastive Analysis

Alvaro Torralba

State-space search is paramount for intelligent decision making when long-term thinking is needed. We introduce dominance and contrastive analysis methods, which enable reasoning about the relative advantages among different courses of action. This re-shapes how agents reason and leads to new families of state-space search algorithms.

PDF Details DOI

IJCAI Conference 2021 Conference Paper

Polynomial-Time in PDDL Input Size: Making the Delete Relaxation Feasible for Lifted Planning

Pascal Lauer
Alvaro Torralba
Daniel Fišer
Daniel Höller
Julia Wichlacz
Jörg Hoffmann

Polynomial-time heuristic functions for planning are commonplace since 20 years. But polynomial-time in which input? Almost all existing approaches are based on a grounded task representation, not on the actual PDDL input which is exponentially smaller. This limits practical applicability to cases where the grounded representation is "small enough". Previous attempts to tackle this problem for the delete relaxation leveraged symmetries to reduce the blow-up. Here we take a more radical approach, applying an additional relaxation to obtain a heuristic function that runs in time polynomial in the size of the PDDL input. Our relaxation splits the predicates into smaller predicates of fixed arity K. We show that computing a relaxed plan is still NP-hard (in PDDL input size) for K>=2, but is polynomial-time for K=1. We implement a heuristic function for K=1 and show that it can improve the state of the art on benchmarks whose grounded representation is large.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Novel Is Not Always Better: On the Relation between Novelty and Dominance Pruning

Joschka Gross
Alvaro Torralba
Maximilian Fickert

Novelty pruning is a planning technique that focuses on exploring states that are novel, i. e. , those containing facts that have not been seen before. This seemingly simple idea has had a huge impact on the state of the art in planning though its effectiveness is not entirely understood yet. We relate novelty to dominance pruning, which compares states to previously seen states to eliminate those that are provably worse in terms of goal distance. Novelty can be interpreted as an unsafe approximation of dominance, where states containing novel facts are relevant because they enable new paths to the goal and, therefore, they are less likely to be dominated by others. This provides a framework to understand the success of novelty, resulting in new variants that combine both techniques.

PDF Details

AAAI Conference 2015 Conference Paper

BDDs Strike Back (in AI Planning)

Stefan Edelkamp
Peter Kissmann
Alvaro Torralba

The cost-optimal track of the international planning competition in 2014 has seen an unexpected outcome. Different to the precursing competition in 2011, where explicit-state heuristic search planning scored best, advances in the state-set exploration with BDDs showed a significant lead. In this paper we review the outcome of the competition, briefly looking into the internals of the competing systems.

PDF Details