Gabriele Röger – Publikationen

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

2012

Jens Claßen, Gabriele Röger, Gerhard Lakemeyer und Bernhard Nebel.
PLATAS – Integrating Planning and the Action Language Golog.
KI – Künstliche Intelligenz 26, S. 61-67. 2012.
(Authors' preprint. The final publication is available at www.springerlink.com.).
(Abstract einblenden) (Abstract ausblenden) (PDF)

Action programming languages like Golog allow to define complex behaviors for agents on the basis of action representations in terms of expressive (first-order) logical formalisms, making them suitable for realistic scenarios of agents with only partial world knowledge. Often these scenarios include sub-tasks that require sequential planning. While in principle it is possible to express and execute such planning sub-tasks directly in Golog, the system can performance-wise not compete with state-of-the-art planners. In this paper, we report on our efforts to integrate efficient planning and expressive action programming in the Platas project. The theoretical foundation is laid by a mapping between the planning language Pddl and the Situation Calculus, which is underlying Golog, together with a study of how these formalisms relate in terms of expressivity. The practical benefit is demonstrated by an evaluation of embedding a Pddl planner into Golog, showing a drastic increase in performance while retaining the full expressiveness of Golog.

2011

Carmel Domshlak, Malte Helmert, Erez Karpas, Emil Keyder, Silvia Richter, Gabriele Röger, Jendrik Seipp und Matthias Westphal.
BJOLP: The Big Joint Optimal Landmarks Planner (planner abstract).
In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 91-95. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

BJOLP, The Big Joint Optimal Landmarks Planner uses landmarks to derive an admissible heuristic, which is then used to guide a search for a cost-optimal plan. In this paper we review landmarks and describe how they can be used to derive an admissible heuristic. We conclude with presenting the BJOLP planner.
Malte Helmert, Gabriele Röger, Jendrik Seipp, Erez Karpas, Jörg Hoffmann, Emil Keyder, Raz Nissim, Silvia Richter und Matthias Westphal.
Fast Downward Stone Soup (planner abstract).
In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 38-45. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Fast Downward Stone Soup is a sequential portfolio planner that uses various heuristics and search algorithms that have been implemented in the Fast Downward planning system.

We present a simple general method for concocting "planner soups", sequential portfolios of planning algorithms, and describe the actual recipes used for Fast Downward Stone Soup in the sequential optimization and sequential satisficing tracks of IPC 2011.
Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger und Jendrik Seipp.
FD-Autotune: Automated Configuration of Fast Downward (planner abstract).
In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 31-37. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The FD-Autotune submissions for the IPC-2011 sequential tracks consist of three instantiations of the latest, highly parametric version of the Fast Downward Planning Framework. These instantiations have been automatically configured for performance on a wide range of planning domains, using the well-known ParamILS configurator. Two of the instantiations were entered into the sequential satisficing track and one into the sequential optimising track. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by state-of-the-art automated configuration procedures, and how ParamILS was then used to obtain performance-optimised configurations.
Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger und Jendrik Seipp.
FD-Autotune: Domain-Specific Configuration using Fast Downward (planner abstract).
In Seventh International Planning Competition (IPC 2011), Planning and Learning Part. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The FD-Autotune learning planning system is based on the idea of domain-specific configuration of the latest, highly parametric version of the Fast Downward Planning Framework by means of a generic automated algorithm configuration procedure. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by state-of-the-art automated configuration procedures. FD-Autotune uses the well-known ParamILS configurator and was realised using the recently developed HAL experimentation environment.
Malte Helmert, Gabriele Röger und Erez Karpas.
Fast Downward Stone Soup: A Baseline for Building Planner Portfolios.
In Proceedings of the ICAPS-2011 Workshop on Planning and Learning (PAL), S. 28-35. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Fast Downward Stone Soup is a sequential portfolio planner that uses various heuristics and search algorithms that have been implemented in the Fast Downward planning system.

We present a simple general method for concocting "planner soups", sequential portfolios of planning algorithms, and describe the actual recipes used for Fast Downward Stone Soup in the sequential optimization and sequential satisficing tracks of IPC 2011.

This paper is, first and foremost, a planner description. Fast Downward Stone Soup was entered into the sequential (non-learning) tracks of IPC 2011. Due to time constraints, we did not enter it into the learning competition at IPC 2011. However, we believe that the approach might still be of interest to the planning and learning community, as it represents a baseline against which other, more sophisticated portfolio learners can be usefully compared.
Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger und Jendrik Seipp.
FD-Autotune: Domain-Specific Configuration using Fast Downward.
In Proceedings of the ICAPS-2011 Workshop on Planning and Learning (PAL), S. 13-20. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

In this work, we present the FD-Autotune learning planning system, which is based on the idea of domain-specific configuration of the latest, highly parametric version of the Fast Downward Planning Framework by means of a generic automated algorithm configuration procedure. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by a state-of-the-art automated configuration procedure. Additionally, we give preliminary results obtained from applying our approach to the nine domains of the IPC-2011 learning track, using the well-known ParamILS configurator and the recently developed HAL experimentation environment.

2010

Malte Helmert und Gabriele Röger.
Relative-Order Abstractions for the Pancake Problem.
In Helder Coelho, Rudi Studer und Michael Wooldridge (Hrsg.), Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), S. 745-750. IOS Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF)

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.
Gabriele Röger und Malte Helmert.
The More, the Merrier: Combining Heuristic Estimators for Satisficing Planning.
In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 246-249. AAAI Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF) (technical report; PDF)

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.

2009

Patrick Eyerich, Robert Mattmüller und Gabriele Röger.
Using the Context-enhanced Additive Heuristic for Temporal and Numeric Planning.
In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 130-137. AAAI Press 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF) (BIB)

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.
Gabriele Röger und Malte Helmert.
Combining Heuristic Estimators for Satisficing Planning.
In Proceedings of the 2nd Workshop on Heuristics for Domain-independent Planning at ICAPS 2009. 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The problem of effectively combining multiple heuristic estimators has been studied extensively in the context of optimal planning, but not in the context of satisficing planning. To narrow this gap, 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 and runtime. Our empirical results indicate that using multiple heuristics for satisficing search is indeed useful and that the best results are not obtained by the most obvious combination methods.

2008

Gabriele Röger, Malte Helmert und Bernhard Nebel.
On the Relative Expressiveness of ADL and Golog: The Last Piece in the Puzzle.
In Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), S. 544-550. AAAI Press 2008.
(Abstract einblenden) (Abstract ausblenden) (PDF)

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.
Jens Claßen, Viktor Engelmann, Gerhard Lakeymeyer und Gabriele Röger.
Integrating Golog and Planning: An Empirical Evaluation.
In Proceedings of the 12th International Workshop on Nonmonotonic Reasoning (NMR 2008), S. 10-18. 2008.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The Golog family of action languages has proven to be a useful means for the high-level control of autonomous agents, such as mobile robots. In particular, the IndiGolog variant, where programs are executed in an online manner, is applicable in realistic scenarios where agents possess only incomplete knowledge about the state of the world, have to use sensors to gather necessary information at runtime and need to react to spontaneous, exogenous events that happen unpredictably due to a dynamic environment. Often, the specification of such an agent’s program also involves that certain subgoals have to be solved by means of planning. IndiGolog supports this in principle by providing a variety of lookahead mechanisms, but when it comes to pure, sequential planning, these usually cannot compete with modern state-of-the-art planning systems, most of which being based on the Planning Domain Definition Language PDDL. Previous theoretical results provide insights on the semantical compatibility between Golog and PDDL and how they compare in terms of expressiveness. In this paper, we complement these results with an empirical evaluation that shows that equipping IndiGolog with a PDDL planner (FF in our case) pays off in terms of the runtime performance of the overall system. For that matter, we study a number of example application domains and compare the needed computation times for varying problem sizes and difficulties.
Malte Helmert und Gabriele Röger.
How Good is Almost Perfect?
In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 944-949. AAAI Press 2008.
(Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)

Heuristic search using algorithms such as A* and IDA* is the prevalent method for obtaining optimal sequential solutions for classical planning tasks. Theoretical analyses of these classical search algorithms, such as the well-known results of Pohl, Gaschnig and Pearl, suggest that such heuristic search algorithms can obtain better than exponential scaling behaviour, provided that the heuristics are accurate enough.

Here, we show that for a number of common planning benchmark domains, including ones that admit optimal solution in polynomial time, general search algorithms such as A* must necessarily explore an exponential number of search nodes even under the optimistic assumption of almost perfect heuristic estimators, whose heuristic error is bounded by a small additive constant.

Our results shed some light on the comparatively bad performance of optimal heuristic search approaches in "simple" domains such as GRIPPER. They suggest that in many domains, further improvements in run-time require changes to other parts of the planning algorithm than the heuristic estimator.

2007

Malte Helmert und Gabriele Röger.
How Good is Almost Perfect?
In Proceedings of the ICAPS-2007 Workshop on Heuristics for Domain-independent Planning: Progress, Ideas, Limitations, Challenges. 2007.
Superseded by the AAAI 2008 paper by the same name.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Heuristic search using algorithms such as A* and IDA* is the prevalent method for obtaining optimal sequential solutions for classical planning tasks. Theoretical analyses of these classical search algorithms, such as the well-known results of Pohl, Gaschnig and Pearl, suggest that such heuristic search algorithms can obtain better than exponential scaling behaviour, provided that the heuristics are accurate enough.

Here, we show that for a number of common planning benchmark domains, including ones that admit optimal solution in polynomial time, general search algorithms such as A* must necessarily explore an exponential number of search nodes even under the optimistic assumption of almost perfect heuristic estimators, whose heuristic error is bounded by a small additive constant.

Our results shed some light on the comparatively bad performance of optimal heuristic search approaches in "simple" domains such as GRIPPER. They suggest that in many domains, further improvements in run-time require changes to other parts of the planning algorithm than the heuristic estimator.
Gabriele Röger und Bernhard Nebel.
Expressiveness of ADL and Golog: Functions Make a Difference.
In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI 2007), S. 1051-1056. AAAI Press 2007.
(Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)

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

2006

Malte Helmert, Robert Mattmüller und Gabriele Röger.
Approximation Properties of Planning Benchmarks.
In Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006), S. 585-589. 2006.
(Abstract einblenden) (Abstract ausblenden) (PDF)

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.
Gabriele Röger.
Aufbau von Abhängigkeitsnetzwerken fuer den Mehrroboter-Kartenbau.
Diplomarbeit, Albert-Ludwigs-Universität, Freiburg, Germany 2006.