Matthias Westphal Publikationen
(Alle Abstracts einblenden)
(Alle Abstracts ausblenden)
2011
-
Matthias Westphal, Stefan Wölfl, Bernhard Nebel und Jochen Renz.
On Qualitative Route Descriptions: Representation and
Computational Complexity.
In
Proceedings of the 22nd International Joint
Conference on Artificial Intelligence
(IJCAI 2011), S. 1120-1125.
AAAI Press 2011.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
(DBLP)
The generation of route descriptions is a fundamental
task of navigation systems. A particular problem in this context
is to identify routes that can easily be described and processed
by users. In this work, we present a framework for representing
route networks with the qualitative information necessary to
evaluate and optimize route descriptions with regard to
ambiguities in them. We identify different agent models that
differ in how agents are assumed to process route descriptions
while navigating through route networks. Further, we analyze the
computational complexity of matching route descriptions and paths
in route networks in dependency of the agent model. Finally we
empirically evaluate the influence of the agent model on the
optimization and the processing of route instructions.
-
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.
-
Silvia Richter, Matthias Westphal und Malte Helmert.
LAMA 2008 and 2011 (planner abstract).
In
Seventh
International Planning Competition (IPC 2011), Deterministic Part, S. 50-54.
2011.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
LAMA is a propositional planning system based on heuristic
search with landmarks. This paper describes two versions of
LAMA that were entered into the 2011 International Planning
Competition: the original LAMA as developed for the 2008
competition and a new re-implementation of LAMA that uses the
latest version of the Fast Downward Planning Framework.
Landmarks are propositions that must be true in every solution
of a planning task. LAMA uses a heuristic derived from
landmarks in conjunction with the well-known FF
heuristic. LAMA builds on the Fast Downward Planning System
using non-binary (but finite domain) state variables and
multi-heuristic search. A weighted A* search is used with
iteratively decreasing weights, so that the planner continues
to search for plans of better quality until the search is
terminated. LAMA combines cost-to-goal and distance-to-goal
estimates with the aim of finding good solutions using
reasonable runtime.
-
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.
-
Matthias Westphal, Christian Dornhege, Stefan Wölfl, Marc Gissler und Bernhard Nebel.
Guiding the Generation of Manipulation Plans by Qualitative Spatial Reasoning.
Spatial Cognition & Computation: An Interdisciplinary Journal 11 (1), S. 75-102. 2011.
(BIB)
2010
-
Silvia Richter und Matthias Westphal.
The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.
Journal of Artificial Intelligence Research 39, S. 127-177. 2010.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
LAMA is a classical planning system based on heuristic forward search. Its core feature is
the use of a pseudo-heuristic derived from landmarks, propositional formulas that must be true
in every solution of a planning task. LAMA builds on the Fast Downward planning system, using
finite-domain rather than binary state variables and multi-heuristic search. The latter is employed to
combine the landmark heuristic with a variant of the well-known FF heuristic. Both heuristics are
cost-sensitive, focusing on high-quality solutions in the case where actions have non-uniform cost.
A weighted A∗ search is used with iteratively decreasing weights, so that the planner continues to
search for plans of better quality until the search is terminated.
LAMA showed best performance among all planners in the sequential satisficing track of the
International Planning Competition 2008. In this paper we present the system in detail and investigate
which features of LAMA are crucial for its performance. We present individual results for
some of the domains used at the competition, demonstrating good and bad cases for the techniques
implemented in LAMA. Overall, we find that using landmarks improves performance, whereas the
incorporation of action costs into the heuristic estimators proves not to be beneficial. We show that
in some domains a search that ignores cost solves far more problems, raising the question of how
to deal with action costs more effectively in the future. The iterated weighted A∗ search greatly
improves results, and shows synergy effects with the use of landmarks.
-
Matthias Westphal, Stefan Wölfl und Jason Jingshi Li.
Restarts and Nogood Recording in Qualitative Constraint-based Reasoning.
In
Proceedings of the 19th European Conference on
Artificial Intelligence (ECAI
2010), S. 1093-1094.
IOS Press 2010.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
(DBLP)
This paper introduces restart and nogood recording techniques in the
domain of qualitative spatial and temporal reasoning.
Nogoods and restarts can be applied orthogonally to usual
methods for solving qualitative constraint satisfaction problems.
In particular, we propose a more general definition of nogoods
that allows for exploiting information about nogoods and tractable
subclasses during backtracking search.
First evaluations of the proposed techniques show promising results.
2009
-
Florian Pommerening, Stefan Wölfl und Matthias Westphal.
Right-of-Way Rules as Use Case for Integrating GOLOG and Qualitative Reasoning.
In
Bärbel Mertsching, Marcus Hund und Muhammad Zaheer Aziz (Hrsg.),
Proceedings of the 32nd Annual Conference on Artificial
Intelligence (KI 2009), S. 468-475.
Springer-Verlag 2009.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
(DBLP)
Agents interacting in a dynamically changing spatial environment often
need to access the same spatial resources. A typical example is
given by moving vehicles that meet at an intersection in a street
network. In such situations right-of-way rules regulate the
actions the vehicles involved may perform.
For this application scenario we show how the Golog framework for
reasoning about action and change can be enhanced by external
reasoning services that implement techniques known from the domain of
Qualitative Spatial Reasoning.
-
Matthias Westphal und Stefan Wölfl.
Qualitative CSP, finite CSP, and SAT: Comparing methods for qualitative constraint-based reasoning.
In
Proceedings of the 21th International Joint Conference
on Artificial Intelligence (IJCAI 2009).
2009.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
(DBLP)
Qualitative Spatial and Temporal Reasoning (QSR) is concerned with
constraint-based formalisms for representing, and reasoning with,
spatial and temporal information over infinite domains. Within the
community it has been a widely accepted assumption that genuine
qualitative reasoning methods outperform other reasoning methods
that are applicable to encodings of qualitative CSP instances.
Recently this assumption has been tackled by several authors, who
proposed to encode qualitative CSP instances as finite CSP or SAT
instances. In this paper we report on the results of a broad empirical
study in which we compared the performance of several reasoners on
instances from different qualitative formalisms.
Our results show that for small-sized qualitative
calculi (e.g. Allen's interval algebra and RCC-8) a state-of-the-art
implementation of QSR methods currently gives the most efficient
performance. However, on recently suggested large-size calculi, e.g.
OPRA_4, finite CSP encodings provide a considerable performance gain.
These results confirm a conjecture by Bessière stating that
support-based constraint propagation algorithms provide better
performance for large-sized qualitative calculi.
-
Stefan Wölfl und Matthias Westphal.
On combinations of binary qualitative constraint calculi.
In
Proceedings of the 21th International Joint Conference
on Artificial Intelligence (IJCAI 2009).
2009.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
(DBLP)
Qualitative constraint calculi are representation formalisms that
allow for efficient reasoning about spatial and temporal information.
Many of the calculi discussed in the field of Qualitative Spatial
and Temporal Reasoning can be defined as combinations of other, simpler
and more compact formalisms. On the other hand, existing calculi can
be combined to a new formalism in which one can represent, and reason
about, different aspects of a domain at the same time. For example,
Gerevini and Renz presented a loose combination of the region
connection calculus RCC-8 and the point algebra: the resulting
formalism integrates topological and qualitative size relations between
spatially extended objects. In this paper we compare the approach by
Gerevini and Renz to a method that generates a new qualitative
calculus by exploiting the semantic interdependencies between the
component calculi.
We will compare these two methods and analyze some formal
relationships between a combined calculus and its components. The
paper is completed by an empirical case study in which the reasoning
performance of the suggested methods is compared on random test
instances.
-
Matthias Westphal und Stefan Wölfl.
Confirming the QSR Promise.
In
AAAI Spring Symposium on Benchmarking of Qualitative Spatial and Temporal Reasoning Systems.
2009.
AAAI Technical Report SS-09-02.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
Within the qualitative spatial reasoning community it has been a
widely accepted commonplace that reasoning in qualitative constraint
calculi outperforms reasoning in other more general and expressive
formalisms. To check the correctness of this assumption we conducted
some empirical case studies in which we compared the performance of
a qualitative constraint solver with different automated reasoning
systems, namely first-order and description logic reasoners. We also
report on some first results from comparing the performance of
qualitative and finite constraint solvers. Our empirical tests are
based on randomly generated instances of qualitative constraint
satisfaction problems, which have been encoded as reasoning problems
for first-order reasoners, description logic reasoners, and finite
CSP solvers, respectively. Given our currently used encodings,
these studies show that first-order and description logic reasoners
are far from being feasible for problem sizes that can easily be
solved by a qualitative reasoner. In contrast, finite CSP solvers
are competitive, but still outperformed by a qualitative reasoner on
the problem instances considered here.
-
Matthias Westphal, Stefan Wölfl und Zeno Gantner.
GQR: A Fast Solver for Binary Qualitative Constraint Networks.
In
AAAI Spring Symposium on Benchmarking of Qualitative Spatial and Temporal Reasoning Systems.
2009.
AAAI Technical Report SS-09-02.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
Qualitative calculi are constraint-based representation formalisms
that allow for efficient reasoning about continuous aspects of the
world with inherently infinite domains, such as time and space. GQR
(Generic Qualitative Reasoner) is a tool that provides reasoning
services for arbitrary binary qualitative calculi. Given
qualitative information expressible in a qualitative calculus, GQR
checks whether this information is consistent w.r.t. the calculus
definition. GQR employs state-of-the-art techniques in both
qualitative and constraint reasoning, such as heuristic search and
usage of known tractable subclasses. In contrast to specialized
reasoners, it offers reasoning services for a variety of calculi
known in the literature, which can be defined in a simple
specification language. The main focus in the design and
implementation of GQR is to provide a generic and extensible solver
that preserves efficiency and scalability.
2008
-
Matthias Westphal und Stefan Wölfl.
Bipath Consistency Revisited.
In
Proceedings of the ECAI'08 Workshop on Spatial and Temporal Reasoning.
Patras, Greece 2008.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
In the field of qualitative spatial and temporal reasoning
combinations of constraint calculi have attracted considerable
research interest in recent years. Beside combinations of spatial
and temporal calculi, it is an important research topic to develop
generic methods for combining calculi dealing with different spatial
aspects. The prototypical example is the combination of the region
connection calculus RCC8 and the point algebra first discussed by
Gerevini and Renz, which allows to represent, and reason about,
topological and size information about spatially extended objects.
To solve constraints in this calculus, Gerevini and Renz also
proposed an algorithm, the bipath consistency algorithm, which
allows for deciding consistency of a given constraint network for
specific sets of relations combining topology and size. In this
article we will compare the "bipath consistency"-based combination
method to the standard method, which is to combine calculi by
generating a new calculus and applying the standard path
consistency method. Gerevini and Renz's calculus combining
topological and size information will serve as the running example
of such combinations and also as a test case for an empirical
analysis.
-
Zeno Gantner, Matthias Westphal und Stefan Wölfl.
GQR - A Fast Reasoner for Binary Qualitative Constraint Calculi.
In
Proceedings of the AAAI'08 Workshop on Spatial and Temporal Reasoning.
Chicago, USA 2008.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
GQR (Generic Qualitative Reasoner) is a solver for binary
qualitative constraint networks. GQR takes a calculus description
and one or more constraint networks as input, and tries to solve the
networks using the path consistency method and (heuristic)
backtracking. In contrast to specialized reasoners, it offers
reasoning services for different qualitative calculi, which means
that these calculi are not hard-coded into the reasoner. Currently,
GQR supports arbitrary binary constraint calculi developed for
spatial and temporal reasoning, such as calculi from the RCC family,
the intersection calculi, Allen's interval algebra, cardinal
direction calculi, and calculi from the OPRA family. New calculi
can be added to the system by specifications in a simple text format
or in an XML file format. The tool is designed and implemented with
genericity and extensibility in mind, while preserving efficiency
and scalability. The user can choose between different data
structures and heuristics, and new ones can be easily added to the
object-oriented framework. GQR is free software distributed under
the terms of the GNU General Public License.
-
Silvia Richter, Malte Helmert und Matthias Westphal.
Landmarks Revisited.
In
Proceedings of the 23rd AAAI Conference on Artificial Intelligence
(AAAI 2008), S. 975-982.
AAAI Press 2008.
Note: After publication, we found a bug in our implementation
that affects the results in the columns "CG heuristic/local" and
"blind heuristic/local" of Table 1. The version of the paper available
for download here corrects these errors.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
(slides; PDF)
Landmarks for propositional planning tasks are variable
assignments that must occur at some point in every solution
plan. We propose a novel approach for using landmarks in
planning by deriving a pseudo-heuristic and combining it with
other heuristics in a search framework. The incorporation of
landmark information is shown to improve success rates and
solution qualities of a heuristic planner. We furthermore show
how additional landmarks and orderings can be found using the
information present in multi-valued state variable
representations of planning tasks. Compared to previously
published approaches, our landmark extraction algorithm provides
stronger guarantees of correctness for the generated landmark
orderings, and our novel use of landmarks during search solves
more planning tasks and delivers considerably better solutions.