Gabriele Röger Publications
(Show all abstracts)
(Hide all abstracts)
2018
-
Salomé Eriksson, Gabriele Röger and Malte Helmert.
A Proof System for Unsolvable Planning Tasks.
In
Proceedings of the 28th International Conference on Automated Planning and Scheduling
(ICAPS 2018).
2018.
(Show abstract)
(Hide abstract)
(PDF)
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.
-
Gabriele Röger, Silvan Sievers and Michael Katz.
Symmetry-based Task Reduction for Relaxed Reachability Analysis.
In
Proceedings of the 28th International Conference on Automated Planning and Scheduling
(ICAPS 2018).
2018.
(Show abstract)
(Hide abstract)
(PDF)
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.
2017
-
Gabriele Röger.
Towards Certified Unsolvability in Classical Planning.
In
Proceedings of the 26th International Joint Conference on
Artificial Intelligence (IJCAI 2017), pp. 5141-5145.
2017.
Early career track.
(Show abstract)
(Hide abstract)
(PDF)
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 certifi-
cates that allow an independent verification of the
absence of solutions. We identify promising con-
cepts 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.
-
Salomé Eriksson, Gabriele Röger and Malte Helmert.
Unsolvability Certificates for Classical Planning.
In
Proceedings of the 27th International Conference on Automated Planning and Scheduling
(ICAPS 2017), pp. 88-97.
2017.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
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.
-
Silvan Sievers, Gabriele Röger, Martin Wehrle and Michael Katz.
Structural Symmetries of the Lifted Representation of Classical Planning Tasks.
In
Proceedings of the ICAPS-2017 Workshop on Heuristics and Search
for Domain-independent Planning (HSDIP 2017), pp. 67-74.
2017.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
We transfer the notion of structural symmetries to lifted
planning task representations, based on a generalizing
concept of abstract structures we use to model planning
tasks. We show that symmetries are preserved by common
grounding methods and shed some light on the relation to
previous symmetry concepts. An analysis of common planning
benchmarks reveals that symmetries occur in the lifted
representation of many domains. Our concept prepares the
ground for exploiting symmetries beyond their current scope,
such as for faster grounding and mutex generation, as well
as for state space transformations and state space
reductions.
-
Gerald Paul, Gabriele Röger, Thomas Keller and Malte Helmert.
Optimal Solutions to Large Logistics Planning Domain Problems.
In
Proceedings of the 10th Annual Symposium on Combinatorial Search
(SoCS 2017), pp. 73-81.
2017.
(Show abstract)
(Hide abstract)
(PDF)
(technical report; PDF)
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).
2016
-
Jendrik Seipp, Florian Pommerening, Gabriele Röger and Malte Helmert.
Correlation Complexity of Classical Planning Domains.
In
Proceedings of the 25th International Joint Conference on
Artificial Intelligence (IJCAI 2016), pp. 3242-3250.
2016.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
We analyze how complex a heuristic function must be to directly guide
a state-space search algorithm towards the goal. As a case study, we
examine functions that evaluate states with a weighted sum of state
features. We measure the complexity of a domain by the complexity of
the required features. We analyze conditions under which the search
algorithm runs in polynomial time and show complexity results for
several classical planning domains.
-
Jendrik Seipp, Florian Pommerening, Gabriele Röger and Malte Helmert.
Correlation Complexity of Classical Planning Domains.
In
Proceedings of the ICAPS-2016 Workshop on Heuristics and Search
for Domain-independent Planning (HSDIP 2016), pp. 12-20.
2016.
Superseded by the IJCAI 2016 paper by the same name.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
We analyze how complex a heuristic function must be to directly guide
a state-space search algorithm towards the goal. As a case study, we
examine functions that evaluate states with a weighted sum of state
features. We measure the complexity of a domain by the complexity of
the required features. We analyze conditions under which the search
algorithm runs in polynomial time and show complexity results for
several classical planning domains.
2015
-
Florian Pommerening, Gabriele Röger, Malte Helmert and Blai Bonet.
Heuristics for Cost-Optimal Classical Planning based on Linear Programming.
In
Proceedings of the 24th International Joint Conference on
Artificial Intelligence (IJCAI 2015), pp. 4303-4309.
2015.
Note: This paper was invited for submission to the Best Papers
From Sister Conferences Track, based on a paper that appeared in
the International Conference on Automated Planning and
Scheduling (ICAPS) 2014. When referring to this work,
please cite the ICAPS 2014 paper instead of this version.
(Show abstract)
(Hide abstract)
(PDF)
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. We
present theoretical results on the relation between
existing heuristics and experimental results that
demonstrate the potential of the proposed framework.
-
Salomé Simon and Gabriele Röger.
Finding and Exploiting LTL Trajectory Constraints in Heuristic Search.
In
Proceedings of the 8th Annual Symposium on
Combinatorial Search (SoCS
2015), pp. 113-121.
2015.
A non-archival version of this paper was also presented at the
ICAPS-2015 Workshop on Heuristics and Search for Domain-independent
Planning (HSDIP).
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(slides HSDIP; PDF)
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.
-
Malte Helmert, Gabriele Röger and Silvan Sievers.
On the Expressive Power of Non-Linear Merge-and-Shrink
Representations.
In
Proceedings of the 25th International Conference on Automated
Planning and Scheduling (ICAPS 2015), pp. 106-114.
2015.
(Show abstract)
(Hide abstract)
(PDF)
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.
-
Florian Pommerening, Malte Helmert, Gabriele Röger and Jendrik Seipp.
From Non-Negative to General Operator Cost Partitioning.
In
Proceedings of the 29th AAAI Conference on Artificial Intelligence
(AAAI 2015), pp. 3335-3341.
2015.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(technical report; PDF)
(erratum; PDF)
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.
-
Gabriele Röger and Florian Pommerening.
Linear Programming for Heuristics in Optimal Planning.
In
Proceedings of the AAAI-2015 Workshop on Planning, Search, and Optimization
(PlanSOpt), pp. 69-76.
2015.
(Show abstract)
(Hide abstract)
(PDF)
Many recent planning heuristics are based on LP optimization. However,
planning experts mostly use LP solvers as a black box and it is often
not obvious to them which LP techniques would be most suitable for their
specific applications.
To foster the communication between the planning and the optimization
community, this paper gives an easily accessible overview over these
recent LP-based heuristics, namely the optimal cost partitioning
heuristic for abstractions, the post-hoc optimization heuristic, a
landmark heuristic, the state-equation heuristic, and a delete
relaxation heuristic. All these heuristics fit the framework of
so-called operator-counting constraints, which we also present.
2014
-
Gabriele Röger, Florian Pommerening and Malte Helmert.
Optimal Planning in the Presence of Conditional Effects: Extending LM-Cut with Context-Splitting.
In
Proceedings of the 21st European Conference on
Artificial Intelligence (ECAI 2014), pp. 765-770.
2014.
(Show abstract)
(Hide abstract)
(PDF)
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.
-
Gabriele Röger, Florian Pommerening and Jendrik Seipp.
Fast Downward Stone Soup 2014 (planner abstract).
In
Eighth International Planning Competition (IPC 2014),
Deterministic Part, pp. 28-31.
2014.
(PDF)
-
Florian Pommerening, Gabriele Röger, Malte Helmert and Blai Bonet.
LP-based Heuristics for Cost-optimal Planning.
In
Proceedings of the 24th International Conference on Automated
Planning and Scheduling (ICAPS 2014), pp. 226-234.
2014.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(poster; PDF)
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.
-
Gabriele Röger, Florian Pommerening and Malte Helmert.
Optimal Planning in the Presence of Conditional Effects: Extending LM-Cut with Context-Splitting.
In
Proceedings of the ICAPS-2014 Workshop on Heuristics and Search
for Domain-independent Planning (HSDIP), pp. 80-87.
2014.
Superseded by the ECAI 2014 paper by the same name.
(Show abstract)
(Hide abstract)
(PDF)
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.
-
Gabriele Röger.
Planning Techniques and the Action Language Golog.
Dissertation, Albert-Ludwigs-Universität Freiburg,
Germany,
2014.
(PDF)
2012
-
Gabriele Röger and Malte Helmert.
Non-optimal Multi-Agent Pathfinding is Solved (Since
1984).
In
Proceedings of the Fifth Annual Symposium on Combinatorial
Search (SoCS 2012), pp. 173-174.
2012.
A non-archival version of this paper was also presented at the
AAAI
2012 Workshop on Multi-Agent Pathfinding (WoMP)..
(Show abstract)
(Hide abstract)
(PDF)
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.
-
Jens Claßen, Gabriele Röger, Gerhard Lakemeyer and Bernhard Nebel.
PLATAS – Integrating Planning and the Action Language Golog.
KI – Künstliche Intelligenz 26 (1), pp. 61-67. 2012.
Authors' preprint. See also the
final publication at www.springerlink.com.
(Show abstract)
(Hide abstract)
(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 and Matthias Westphal.
BJOLP: The Big Joint Optimal Landmarks Planner
(planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Deterministic Part, pp. 91-95.
2011.
(Show abstract)
(Hide abstract)
(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 and Matthias Westphal.
Fast Downward Stone Soup (planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Deterministic Part, pp. 38-45.
2011.
(Show abstract)
(Hide abstract)
(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 and Jendrik Seipp.
FD-Autotune: Automated Configuration of Fast Downward
(planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Deterministic Part, pp. 31-37.
2011.
(Show abstract)
(Hide abstract)
(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 and Jendrik Seipp.
FD-Autotune: Domain-Specific Configuration using Fast Downward
(planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Planning and
Learning Part.
2011.
(Show abstract)
(Hide abstract)
(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 and Erez Karpas.
Fast Downward Stone Soup: A Baseline for Building Planner Portfolios.
In
Proceedings of the ICAPS-2011 Workshop on Planning and
Learning (PAL), pp. 28-35.
2011.
(Show abstract)
(Hide abstract)
(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 and Jendrik Seipp.
FD-Autotune: Domain-Specific Configuration using Fast Downward.
In
Proceedings of the ICAPS-2011 Workshop on Planning and Learning
(PAL), pp. 13-20.
2011.
(Show abstract)
(Hide abstract)
(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 and Gabriele Röger.
Relative-Order Abstractions for the Pancake Problem.
In
Proceedings of the 19th European Conference on
Artificial Intelligence (ECAI
2010), pp. 745-750.
2010.
(Show abstract)
(Hide abstract)
(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 and Malte Helmert.
The More, the Merrier: Combining Heuristic Estimators for
Satisficing Planning.
In
Proceedings of the 20th International Conference on
Automated Planning and Scheduling
(ICAPS 2010), pp. 246-249.
2010.
(Show abstract)
(Hide abstract)
(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 and 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), pp. 130-137.
2009.
(Show abstract)
(Hide abstract)
(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 and Malte Helmert.
Combining Heuristic Estimators for Satisficing Planning.
In
Proceedings of the
2nd
Workshop on Heuristics for Domain-independent Planning
at ICAPS 2009.
2009.
(Show abstract)
(Hide abstract)
(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 and 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), pp. 544-550.
2008.
(Show abstract)
(Hide abstract)
(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 Lakemeyer and Gabriele Röger.
Integrating Golog and Planning: An Empirical Evaluation.
In
Proceedings of the 12th International Workshop on
Nonmonotonic Reasoning
(NMR 2008), pp. 10-18.
2008.
(Show abstract)
(Hide abstract)
(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 and Gabriele Röger.
How Good is Almost Perfect?
In
Proceedings of the 23rd AAAI Conference on Artificial Intelligence
(AAAI 2008), pp. 944-949.
2008.
(Show abstract)
(Hide abstract)
(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 and 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.
(Show abstract)
(Hide abstract)
(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 and Bernhard Nebel.
Expressiveness of ADL and Golog:
Functions Make a Difference.
In
Proceedings of the 22nd AAAI Conference on Artificial
Intelligence (AAAI 2007), pp. 1051-1056.
2007.
(Show abstract)
(Hide abstract)
(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 and Gabriele Röger.
Approximation Properties of Planning Benchmarks.
In
Proceedings of the 17th European Conference on Artificial
Intelligence (ECAI 2006), pp. 585-589.
2006.
(Show abstract)
(Hide abstract)
(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.