Matthias Westphal – Publications

(Show all abstracts) (Hide all abstracts)

2011

Matthias Westphal, Stefan Wölfl, Bernhard Nebel and Jochen Renz.
On Qualitative Route Descriptions: Representation and Computational Complexity.
In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 1120-1125. AAAI Press 2011.
(Show abstract) (Hide abstract) (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 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.
Silvia Richter, Matthias Westphal and Malte Helmert.
LAMA 2008 and 2011 (planner abstract).
In Seventh International Planning Competition (IPC 2011), Deterministic Part, pp. 50-54. 2011.
(Show abstract) (Hide abstract) (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 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.
Matthias Westphal, Christian Dornhege, Stefan Wölfl, Marc Gissler and Bernhard Nebel.
Guiding the Generation of Manipulation Plans by Qualitative Spatial Reasoning.
Spatial Cognition & Computation: An Interdisciplinary Journal 11 (1), pp. 75-102. 2011.
(BIB)

2010

Silvia Richter and Matthias Westphal.
The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.
Journal of Artificial Intelligence Research 39, pp. 127-177. 2010.
(Show abstract) (Hide abstract) (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 and Jason Jingshi Li.
Restarts and Nogood Recording in Qualitative Constraint-based Reasoning.
In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), pp. 1093-1094. IOS Press 2010.
(Show abstract) (Hide abstract) (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 and Matthias Westphal.
Right-of-Way Rules as Use Case for Integrating GOLOG and Qualitative Reasoning.
In Bärbel Mertsching, Marcus Hund and Muhammad Zaheer Aziz (eds.), Proceedings of the 32nd Annual Conference on Artificial Intelligence (KI 2009), pp. 468-475. Springer-Verlag 2009.
(Show abstract) (Hide abstract) (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 and 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.
(Show abstract) (Hide abstract) (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 and Matthias Westphal.
On combinations of binary qualitative constraint calculi.
In Proceedings of the 21th International Joint Conference on Artificial Intelligence (IJCAI 2009). 2009.
(Show abstract) (Hide abstract) (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 and 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.
(Show abstract) (Hide abstract) (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 and 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.
(Show abstract) (Hide abstract) (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 and Stefan Wölfl.
Bipath Consistency Revisited.
In Proceedings of the ECAI'08 Workshop on Spatial and Temporal Reasoning. Patras, Greece 2008.
(Show abstract) (Hide abstract) (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 and 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.
(Show abstract) (Hide abstract) (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 and Matthias Westphal.
Landmarks Revisited.
In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), pp. 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.
(Show abstract) (Hide abstract) (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.