|
|
Gabi Röger – Publications
(Show all abstracts)
(Hide all abstracts)
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).
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.
-
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.
AAAI Press 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.
AAAI Press 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)
(PS.GZ)
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.
Diploma thesis,
Albert-Ludwigs-Universität,
Freiburg, Germany 2006.
|
