Arrow Research search

Author name cluster

Gabriele Röger

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.

30 papers
2 author rows

Possible papers

30

KR Conference 2025 Conference Paper

Automated Planning with Ontologies Under Coherence Update Semantics

  • Stefan Borgwardt
  • Duy Nhu
  • Gabriele Röger

Standard automated planning employs first-order formulas under closed-world semantics to achieve a goal with a given set of actions from an initial state. We follow a line of research that aims to incorporate background knowledge into automated planning problems, for example by means of ontologies, which are usually interpreted under open-world semantics. We present a new approach for planning with DL-Lite ontologies that combines the advantages of ontology-based action conditions provided by explicit-input knowledge and action bases (eKABs) and ontology-aware action effects under the coherence update semantics. We show that the complexity of the resulting formalism is not higher than that of previous approaches, and provide an implementation via a polynomial compilation into classical planning. An evaluation on existing and new benchmarks examines the performance of a planning system on different variants of our compilation.

PDF Details DOI

KR Conference 2025 Conference Paper

Domain-Independent Instance Generation for Classical Planning

  • Claudia Grundke
  • Malte Helmert
  • Gabriele Röger

Learning-based planning systems learn domain-specific knowledge that helps them to solve unseen tasks from the same planning domain. For this purpose they require a diverse set of training instances. A recent proposal for formal specifications of planning domains allows us to exactly characterize which instances are legal for a domain. We automatically generate planning tasks from such formal specifications by means of a translation to answer set programming. We experimentally examine the scalability of the approach and the suitability for learning-based planning, following the setup of the learning track of the International Planning Competition.

PDF Details DOI

ICAPS Conference 2024 Conference Paper

Formal Representations of Classical Planning Domains

  • Claudia Grundke
  • Gabriele Röger
  • Malte Helmert

Planning domains are an important notion, e. g. when it comes to restricting the input for generalized planning or learning approaches. However, domains as specified in PDDL cannot fully capture the intuitive understanding of a planning domain. We close this semantic gap and propose using PDDL axioms to characterize the (typically infinite) set of legal tasks of a domain. A minor extension makes it possible to express all properties that can be determined in polynomial time. We demonstrate the suitability of the approach on established domains from the International Planning Competition.

Details

ICAPS Conference 2024 Conference Paper

Merging or Computing Saturated Cost Partitionings? A Merge Strategy for the Merge-and-Shrink Framework

  • Silvan Sievers
  • Thomas Keller 0001
  • Gabriele Röger

The merge-and-shrink framework is a powerful tool for computing abstraction heuristics for optimal classical planning. Merging is one of its name-giving transformations. It entails computing the product of two factors of a factored transition system. To decide which two factors to merge, the framework uses a merge strategy. While there exist many merge strategies, it is generally unclear what constitutes a strong merge strategy, and a previous analysis shows that there is still lots of room for improvement with existing merge strategies. In this paper, we devise a new scoring function for score-based merge strategies based on answering the question whether merging two factors has any benefits over computing saturated cost partitioning heuristics over the factors instead. Our experimental evaluation shows that our new merge strategy achieves state-of-the-art performance on IPC benchmarks.

Details

ICAPS Conference 2022 Conference Paper

Cost Partitioning Heuristics for Stochastic Shortest Path Problems

  • Thorsten Klößner
  • Florian Pommerening
  • Thomas Keller 0001
  • Gabriele Röger

In classical planning, cost partitioning is a powerful method which allows to combine multiple admissible heuristics while retaining an admissible bound. In this paper, we extend the theory of cost partitioning to probabilistic planning by generalizing from deterministic transition systems to stochastic shortest path problems (SSPs). We show that fundamental results related to cost partitioning still hold in our extended theory. We also investigate how to optimally partition costs for a large class of abstraction heuristics for SSPs. Lastly, we analyze occupation measure heuristics for SSPs as well as the theory of approximate linear programming for reward-oriented Markov decision processes. All of these fit our framework and can be seen as cost-partitioned heuristics.

Details

SoCS Conference 2022 Conference Paper

On Producing Shortest Cost-Optimal Plans

  • Michael Katz 0001
  • Gabriele Röger
  • Malte Helmert

Cost-optimal planning is at the heart of planning research, with many existing planners that produce provably optimal solutions. While some applications pose additional restrictions, such as producing shortest (in the number of actions) among the cost-optimal plans, standard cost-optimal planning does not provide such a guarantee. We discuss two possible approaches to produce provably the shortest among the cost-optimal plans, one corresponding to an instantiation of cost-algebraic A∗, the other based on a cost transformation. We formally prove that the new cost-transformation method indeed produces the shortest among the cost-optimal plans and empirically compare the performance of the approaches in different configurations.

Details

SoCS Conference 2020 Conference Paper

An Atom-Centric Perspective on Stubborn Sets

  • Gabriele Röger
  • Malte Helmert
  • Jendrik Seipp
  • Silvan Sievers

Stubborn sets are an optimality-preserving pruning technique for factored state-space search, for example in classical planning. Their applicability is limited by their computational overhead. We describe a new algorithm for computing stubborn sets that is based on the state variables of the state space, while previous algorithms are based on its actions. Typical factored state spaces tend to have far fewer state variables than actions, and therefore our new algorithm is much more efficient than the previous state of the art, making stubborn sets a viable technique in many cases where they previously were not.

Details

IJCAI Conference 2020 Conference Paper

Lagrangian Decomposition for Classical Planning (Extended Abstract)

  • Florian Pommerening
  • Gabriele Röger
  • Malte Helmert
  • Hadrien Cambazad
  • Louis-Martin Rousseau
  • Domenico Salvagnin

Optimal cost partitioning of classical planning heuristics has been shown to lead to excellent heuristic values but is often prohibitively expensive to compute. We analyze the application of Lagrangian decomposition, a classical tool in mathematical programming, to cost partitioning of operator-counting heuristics. This allows us to view the computation as an iterative process that can be seeded with any cost partitioning and that improves over time. In the case of non-negative cost partitioning of abstraction heuristics the computation reduces to independent shortest path problems and does not require an LP solver.

PDF Details DOI

ICAPS Conference 2019 Conference Paper

Lagrangian Decomposition for Optimal Cost Partitioning

  • Florian Pommerening
  • Gabriele Röger
  • Malte Helmert
  • Hadrien Cambazard
  • Louis-Martin Rousseau
  • Domenico Salvagnin

Optimal cost partitioning of classical planning heuristics has been shown to lead to excellent heuristic values but is often prohibitively expensive to compute. Lagrangian decomposition and Lagrangian relaxation are classical tools in mathematical programming that apply to optimization problems with a special block structure. We analyze the application of Lagrangian decomposition to cost partitioning in the context of operator-counting heuristics and interpret Lagrangian multipliers as cost functions for the combined heuristics. This allows us to view the computation of an optimal cost partitioning as an iterative process that can be seeded with any cost partitioning and improves over time. We derive an anytime algorithm to compute an optimal non-negative cost partitioning of abstraction heuristics without involving an LP solver. In each iteration, the computation reduces to independent shortest path problems in all abstractions. Finally, we discuss the extension to general cost functions.

Details

ICAPS Conference 2019 Conference Paper

Theoretical Foundations for Structural Symmetries of Lifted PDDL Tasks

  • Silvan Sievers
  • Gabriele Röger
  • Martin Wehrle
  • Michael Katz 0001

We transfer the notion of structural symmetries to lifted planning task representations, based on abstract structures which we define to model planning tasks. We show that symmetries are preserved by common grounding methods and we shed some light on the relation to previous symmetry concepts used in planning. Using a suitable graph representation of lifted tasks, our experimental analysis of common planning benchmarks reveals that symmetries occur in the lifted representation of many domains. Our work establishes the theoretical ground for exploiting symmetries beyond their previous scope, such as for faster grounding and mutex generation, as well as for state space transformations and reductions.

Details

ICAPS Conference 2018 Conference Paper

A Proof System for Unsolvable Planning Tasks

  • Salomé Eriksson
  • Gabriele Röger
  • Malte Helmert

While traditionally classical planning concentrated on finding plans for solvable tasks, detecting unsolvable instances has recently attracted increasing interest. To preclude wrong results, it is desirable that the planning system provides a certificate of unsolvability that can be independently verified. We propose a rule-based proof system for unsolvability where a proof establishes a knowledge base of verifiable basic statements and applies a set of derivation rules to infer the unsolvability of the task from these statements. We argue that this approach is more flexible than a recent proposal of inductive certificates of unsolvability and show how our proof system can be used for a wide range of planning techniques.

Details

IJCAI Conference 2018 Conference Paper

Inductive Certificates of Unsolvability for Domain-Independent Planning

  • Salomé Eriksson
  • Gabriele Röger
  • Malte Helmert

If a planning system outputs a solution for a given problem, it is simple to verify that the solution is valid. However, if a planner claims that a task is unsolvable, we currently have no choice but to trust the planner blindly. We propose a sound and complete class of certificates of unsolvability which can be verified efficiently by an independent program. To highlight their practical use, we show how these certificates can be generated for a wide range of state-of-the-art planning techniques with only polynomial overhead for the planner.

PDF Details

ICAPS Conference 2018 Conference Paper

Symmetry-Based Task Reduction for Relaxed Reachability Analysis

  • Gabriele Röger
  • Silvan Sievers
  • Michael Katz 0001

Relaxed reachability analysis is relevant to efficient grounding, invariant synthesis as well as the computation of relaxation-based heuristics. Planning domains are typically specified in a lifted representation, where the size of the tasks grows exponentially with the number of objects in the world. This growth also affects the analysis of relaxed reachability. We present a task reduction based on symmetries of the lifted representation that allows to perform the same analysis on smaller tasks.

Details

SoCS Conference 2017 Conference Paper

Optimal Solutions to Large Logistics Planning Domain Problems

  • Gerald Paul
  • Gabriele Röger
  • Thomas Keller 0001
  • Malte Helmert

We propose techniques for efficiently determining optimal solutions to large logistics planning domain problems. We map a problem instance to a directed graph and show that no more than one vehicle per weakly connected component of the graph is needed for an optimal solution. We propose techniques for efficiently finding the vehicles which must be employed for an optimal solution. Also we develop a strong admissible heuristic based on the analysis of a directed graph, the cycles of which represent situations in the problem state in which a vehicle must visit a location more than once. To the best of our knowledge, ours is the first method that determines optimal solutions for large logistics instances (including the largest instances in the IPC 1998 and IPC 2000 problem sets).

Details

IJCAI Conference 2017 Conference Paper

Towards Certified Unsolvability in Classical Planning

  • Gabriele Röger

While it is easy to verify that an action sequence is a solution for a classical planning task, there is no such verification capability if a task is reported unsolvable. We are therefore interested in certificates that allow an independent verification of the absence of solutions. We identify promising concepts for certificates that can be generated by a wide range of planning approaches. We present a first proposal of unsolvability certificates and sketch ideas how the underlying concepts can be used as part of a more flexible unsolvability proof system.

PDF Details

ICAPS Conference 2017 Conference Paper

Unsolvability Certificates for Classical Planning

  • Salomé Eriksson
  • Gabriele Röger
  • Malte Helmert

The plans that planning systems generate for solvable planning tasks are routinely verified by independent validation tools. For unsolvable planning tasks, no such validation capabilities currently exist. We describe a family of certificates of unsolvability for classical planning tasks that can be efficiently verified and are sufficiently general for a wide range of planning approaches including heuristic search with delete relaxation, critical-path, pattern database and linear merge-and-shrink heuristics, symbolic search with binary decision diagrams, and the Trapper algorithm for detecting dead ends. We also augmented a classical planning system with the ability to emit certificates of unsolvability and implemented a planner-independent certificate validation tool. Experiments show that the overhead for producing such certificates is tolerable and that their validation is practically feasible.

Details

SoCS Conference 2015 Conference Paper

Finding and Exploiting LTL Trajectory Constraints in Heuristic Search

  • Salomé Simon
  • Gabriele Röger

We suggest the use of linear temporal logic (LTL) for expressing declarative information about optimal solutions of search problems. We describe a general framework that associates LTLf formulas with search nodes in a heuristic search algorithm. Compared to previous approaches that integrate specific kinds of path information like landmarks into heuristic search, the approach is general, easy to prove correct and easy to integrate with other kinds of path information.

Details

AAAI Conference 2015 Conference Paper

From Non-Negative to General Operator Cost Partitioning

  • Florian Pommerening
  • Malte Helmert
  • Gabriele Röger
  • Jendrik Seipp

Operator cost partitioning is a well-known technique to make admissible heuristics additive by distributing the operator costs among individual heuristics. Planning tasks are usually defined with non-negative operator costs and therefore it appears natural to demand the same for the distributed costs. We argue that this requirement is not necessary and demonstrate the benefit of using general cost partitioning. We show that LP heuristics for operator-counting constraints are cost-partitioned heuristics and that the state equation heuristic computes a cost partitioning over atomic projections. We also introduce a new family of potential heuristics and show their relationship to general cost partitioning.

PDF Details

ICAPS Conference 2015 Conference Paper

On the Expressive Power of Non-Linear Merge-and-Shrink Representations

  • Malte Helmert
  • Gabriele Röger
  • Silvan Sievers

We prove that general merge-and-shrink representations are strictly more powerful than linear ones by showing that there exist problem families that can be represented compactly with general merge-and-shrink representations but not with linear ones. We also give a precise bound that quantifies the necessary blowup incurred by conversions from general merge-and-shrink representations to linear representations or BDDs/ADDs. Our theoretical results suggest an untapped potential for non-linear merging strategies and for the use of non-linear merge-and-shrink-like representations within symbolic search.

Details

ICAPS Conference 2014 Conference Paper

LP-Based Heuristics for Cost-Optimal Planning

  • Florian Pommerening
  • Gabriele Röger
  • Malte Helmert
  • Blai Bonet

Many heuristics for cost-optimal planning are based on linear programming. We cover several interesting heuristics of this type by a common framework that fixes the objective function of the linear program. Within the framework, constraints from different heuristics can be combined in one heuristic estimate which dominates the maximum of the component heuristics. Different heuristics of the framework can be compared on the basis of their constraints. With this new method of analysis, we show dominance of the recent LP-based state-equation heuristic over optimal cost partitioning on single-variable abstractions. We also show that the previously suggested extension of the state-equation heuristic to exploit safe variables cannot lead to an improved heuristic estimate. We experimentally evaluate the potential of the proposed framework on an extensive suite of benchmark tasks.

Details

ECAI Conference 2014 Conference Paper

Optimal Planning in the Presence of Conditional Effects: Extending LM-Cut with Context Splitting

  • Gabriele Röger
  • Florian Pommerening
  • Malte Helmert

The LM-Cut heuristic is currently the most successful heuristic in optimal STRIPS planning but it cannot be applied in the presence of conditional effects. Keyder, Hoffmann and Haslum recently showed that the obvious extensions to such effects ruin the nice theoretical properties of LM-Cut. We propose a new method based on context splitting that preserves these properties.

Details

IJCAI Conference 2013 Conference Paper

Getting the Most Out of Pattern Databases for Classical Planning

  • Florian Pommerening
  • Gabriele Röger
  • Malte Helmert

The iPDB procedure by Haslum et al. is the stateof-the-art method for computing additive abstraction heuristics for domain-independent planning. It performs a hill-climbing search in the space of pattern collections, combining information from multiple patterns in the so-called canonical heuristic. We show how stronger heuristic estimates can be obtained through linear programming. An experimental evaluation demonstrates the strength of the new technique on the IPC benchmark suite.

PDF Details DOI

SoCS Conference 2013 Conference Paper

SoCS 2013 Organization

  • Malte Helmert
  • Gabriele Röger

List of organizers of the Sixth International Symposium on Combinatorial Search.

Details

SoCS Conference 2012 Conference Paper

Non-Optimal Multi-Agent Pathfinding is Solved (Since 1984)

  • Gabriele Röger
  • Malte Helmert

Optimal solutions for multi-agent pathfinding problems are often too expensive to compute. For this reason, suboptimal approaches have been widely studied in the literature. Specifically, in recent years a number of efficient suboptimal algorithms that are complete for certain subclasses have been proposed at highly-rated robotics and AI conferences, all mentioning that it is an open problem which subclasses of non-optimal multi-agent pathfinding are tractable. However, it turns out that this problem has already been completely solved in another research community in the 1980s by a constructive proof that provides a polynomial algorithm that is complete for the entire class of problems. In this paper, we would like to bring this earlier related work to the attention of the robotics and AI communities.

Details

ECAI Conference 2010 Conference Paper

Relative-Order Abstractions for the Pancake Problem

  • Malte Helmert
  • Gabriele Röger

The pancake problem is a famous search problem where the objective is to sort a sequence of objects (pancakes) through a minimal number of prefix reversals (flips). The best approaches for the problem are based on heuristic search with abstraction (pattern database) heuristics. We present a new class of abstractions for the pancake problem called relative-order abstractions. Relative-order abstractions have three advantages over the object-location abstractions considered in previous work. First, they are size-independent, i. e. , do not need to be tailored to a particular instance size of the pancake problem. Second, they are more compact in that they can represent a larger number of pancakes within abstractions of bounded size. Finally, they can exploit symmetries in the problem specification to allow multiple heuristic lookups, significantly improving search performance over a single lookup. Our experiments show that compared to object-location abstractions, our new techniques lead to an improvement of one order of magnitude in runtime and up to three orders of magnitude in the number of generated states.

Details

ICAPS Conference 2010 Conference Paper

The More, the Merrier: Combining Heuristic Estimators for Satisficing Planning

  • Gabriele Röger
  • Malte Helmert

We empirically examine several ways of exploiting the information of multiple heuristics in a satisficing best-first search algorithm, comparing their performance in terms of coverage, plan quality, speed, and search guidance. Our results indicate that using multiple heuristics for satisficing search is indeed useful. Among the combination methods we consider, the best results are obtained by the alternation method of the "Fast Diagonally Downward" planner.

Details

ICAPS Conference 2009 Conference Paper

Using the Context-enhanced Additive Heuristic for Temporal and Numeric Planning

  • Patrick Eyerich
  • Robert Mattmüller
  • Gabriele Röger

Planning systems for real-world applications need the ability to handle concurrency and numeric fluents. Nevertheless, the predominant approach to cope with concurrency followed by the most successful participants in the latest International Planning Competitions (IPC) is still to find a sequential plan that is rescheduled in a post-processing step. We present Temporal Fast Downward (TFD), a planning system for temporal problems that is capable of finding low-makespan plans by performing a heuristic search in a temporal search space. We show how the context-enhanced additive heuristic can be successfully used for temporal planning and how it can be extended to numeric fluents. TFD often produces plans of high quality and, evaluated according to the rating scheme of the last IPC, outperforms all state-of-the-art temporal planning systems.

Details

KR Conference 2008 Conference Paper

On the Relative Expressiveness of ADL and Golog: The Last Piece in the Puzzle

  • Gabriele Röger
  • Malte Helmert
  • Bernhard Nebel

Integrating agent programming languages and efficient action planning is a promising approach because it combines the expressive power of languages such as Golog with the possibility of searching for plans efficiently. In order to integrate a Golog interpreter with a planner, one has to understand, however, which part of the expressiveness of Golog can be captured by the planning language. Using Nebel's compilation framework, we identify a maximal fragment of basic action theories, the formalism Golog is based on, that is expressively equivalent to the ADL subset of PDDL. As we will show, almost all features that permit to specify incomplete information in basic action theories cannot be compiled to ADL.

AAAI Conference 2007 Conference Paper

Expressiveness of ADL and Golog: Functions Make a Difference

  • Gabriele Röger

The main focus in the area of action languages, such as GOLOG, was put on expressive power, while the development in the area of action planning was focused on efficient plan generation. An integration of GOLOG and planning languages would provide great advantages. A user could constrain a system’s behavior on a high level using GOLOG, while the actual low-level actions are planned by an efficient planning system. First endeavors have been made by Eyerich et al. by identifying a subset of the situation calculus (which is the basis of GOLOG) with the same expressiveness as the ADL fragment of PDDL. However, it was not proven that the identified restrictions define a maximum subset. The most severe restriction appears to be that functions are limited to constants. We will show that this restriction is indeed necessary in most cases.

PDF Details

ECAI Conference 2006 Conference Paper

Aproximation Properties of Planning Benchmarks

  • Malte Helmert
  • Robert Mattmüller
  • Gabriele Röger

For many classical planning domains, the computational complexity of non-optimal and optimal planning is known. However, little is known about the area in between the two extremes of finding some plan and finding optimal plans. In this contribution, we provide a complete classification of the propositional domains from the first four International Planning Competitions with respect to the approximation classes PO, PTAS, APX, poly-APX, and NPO.

Details
v2026.09.13