• English
• Deutsch

• University of Freiburg
• Faculty of Engineering
• Department of Computer Science

Matthias Westphal – Publications

(Show all abstracts) (Hide all abstracts)

2015

• Matthias Westphal, Stefan Wölfl, Bernhard Nebel and Jochen Renz.
  On qualitative route descriptions: Representation, agent models, and computational complexity.
  Journal of Philosophical Logic 44 (2), pp. 177-201. 2015.
  (Show abstract) (Hide abstract) (Online; DOI)
  

  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 and discuss which agent models can be translated into PDL programs. 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.

2014

• Matthias Westphal and Julien Hué.
  A Concise Horn Theory for RCC8.
  In Proceedings of European Conference on Artificial Intelligence (ECAI'14). 2014.
  (Show abstract) (Hide abstract) (Translation Script; TAR.GZ)
  

  RCC8 is a well-known constraint language for expressing and reasoning about spatial knowledge. We state a simple and concise Horn theory for RCC8 analogous to the ORD-Horn theory for temporal reasoning. This theory allows for expressing RCC8 and retains tractability of the well-known Horn reduct of RCC8. Further, it is much more adequate for practical purposes in the area of logic programming and surpasses previous attempts.

• Julien Hué, Matthias Westphal and Stefan Wölfl.
  Towards a new semantic for Possibilistic Answer Sets.
  In Proceedings of Advances in Artificial Intelligence (KI'14). 2014.
  (Show abstract) (Hide abstract) (Springer Online; DOI) (DBLP)
  

  Possibilistic Answer Set Programming is an extension of the standard ASP framework that allows for attaching degrees of certainty to the rules in ASP programs. In the literature, several semantics for such PASP-programs have been presented, each of them having particular strengths and weaknesses. In this work we present a new semantics that employs so-called iota-answer sets, a solution concept introduced by Gebser et al.~(2009), in order to find solutions for standard ASP programs with odd cycles or auto-blocking rules. This is achieved by considering maximal subsets of a given ASP program for which answer sets exist. The main idea of our work is to integrate iota-semantics into the possibilistic framework in such a way that degrees of certainty are not only assigned to atoms mentioned in the answer sets, but also to the answer sets themselves. Our approach gives more satisfactory solutions and avoids counter-intuitive examples arising in the other approaches. We compare our approach to existing ones and present a translation into the standard ASP framework allowing the computation of solutions by existing tools.

• Matthias Westphal, Julien Hué and Stefan Wölfl.
  On the scope of Qualitative Constraint Calculi.
  In Proceedings of Advances in Artificial Intelligence (KI'14). 2014.
  (Show abstract) (Hide abstract) (Springer Online; DOI) (DBLP)
  

  Qualitative constraint calculi are a special kind of relation algebras defined by Ligozat and Renz for reasoning about binary constraints. Although this approach is known to be limited it has prevailed in the area of qualitative spatial and temporal reasoning. In this paper we revisit the definition of these calculi, contrast it with alternative approaches, and analyze general properties. Our results indicate that the concept of qualitative constraint calculi is both too narrow and too general: it disallows different approaches, but its setup already enables arbitrarily hard problems.

2013

• Matthias Westphal, Julien Hué, Stefan Wölfl and Bernhard Nebel.
  Transition Constraints: A Study on the Computational Complexity of Qualitative Change.
  In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI'13), pp. 1169-1175. 2013.
  (Show abstract) (Hide abstract) (Online; PDF) (DBLP)
  

  Many formalisms discussed in the literature on qualitative spatial reasoning are designed for expressing static spatial constraints only. However, dynamic situations arise in virtually all applications of these formalisms, which makes it necessary to study variants and extensions involving change. This paper presents a study on the computational complexity of qualitative change. More precisely, we discuss the reasoning task of finding a solution to a temporal sequence of static reasoning problems where this sequence is subject to additional transition constraints. Our focus is primarily on smoothness and continuity constraints: we show how such transitions can be defined as relations and expressed within qualitative constraint formalisms. Our results demonstrate that for point-based constraint formalisms the interesting fragments become NP-complete in the presence of continuity constraints, even if the satisfiability problem of its static descriptions is tractable.

• Matthias Westphal, Julien Hué and Stefan Wölfl.
  On the Propagation Strength of SAT Encodings for Qualitative Temporal Reasoning.
  In Proceedings of International Conference on Tools for Artificial Intelligence (ICTAI'13). 2013.
  (Show abstract) (Hide abstract) (PDF) (DOI) (DBLP) (Translation Script; TAR.GZ)
  

  Several studies in Qualitative Spatial and Temporal Reasoning discuss translations of the satisfiability problem on qualitative constraint languages into propositional SAT. Most of these encodings focus on compactness, while propagation strength is seldom discussed. In this work, we focus on temporal reasoning with the Point Algebra and Allen's Interval Algebra. We understand all encodings as a combination of propagation and search. We first give a systematic analysis of existing propagation approaches for these constraint languages. They are studied and ordered with respect to their propagation strength and refutation completeness for classes of input instances. Secondly, we discuss how existing encodings can be derived from such propagation approaches. We conclude our work with an empirical evaluation which shows that the older ORD-encoding by Nebel and Bürckert performs better than more recently suggested encodings.

2012

• Julien Hué and Matthias Westphal.
  Revising Qualitative Constraint Network: Definition and Implementation.
  In Internationial Conference on Tools for Artificial Intelligence (ICTAI), pp. 548-555. 2012.
  (Show abstract) (Hide abstract) (PDF)
  

  Qualitative Spatial and Temporal Reasoning is a central topic in Artificial Intelligence. In particular, it is aimed at application scenarios dealing with uncertain information and thus needs to be able to handle dynamic beliefs. This makes merging and revision of qualitative information important topics. While merging has been studied extensively, revision which describes what is happening when one learns new information about a static world has been overlooked. In this paper, we propose to fill the gap by providing two revision operations for qualitative calculi. In order to implement these operations, we give algo- rithms for revision and analyze the computational complexity of these problems. Finally, we present an implementation of these algorithms based on a qualitative constraint solver and provide an experimental evaluation.

• Julien Hué, Matthias Westphal and Stefan Wölfl.
  An automatic decomposition method for qualitative spatial and temporal reasoning.
  In International Conference on Tools for Artificial Intelligence (ICTAI), pp. 588-595. 2012.
  (Show abstract) (Hide abstract) (PDF) (DBLP)
  

  Qualitative spatial and temporal reasoning is a research field that studies relational, constraint-based formalisms for representing, and reasoning about, spatial and temporal information. The standard approach for checking consistency is based on an exhaustive representation of possible configurations between three entities, the so-called composition tables. These tables, however, encode semantic background knowledge in a redundant way, which becomes a size and efficiency issue, when the composition table needs to be grounded as done in SAT encodings of problem instances. In this paper, we present a new framework that allows for decomposing composition tables into logically simpler parts, while preserving logical equivalence, e.g., the decomposition in start- and end-points for Allen’s Interval Calculus. We show that finding such decompositions is an NP-complete problem and present a SAT-based method to generate decompositions. Finally, we discuss the impact of our decomposition method on SAT encodings of problem instances, and present a reasoning system built on decompositions that compares favorably with state-of-the-art solvers.

• Matthias Westphal and Julien Hué.
  Nogoods in Qualitative Constraint-based Reasoning.
  In KI 2012: Advances in Artificial Intelligence (KI 2012), pp. 180-192. Springer-Verlag 2012.
  (Authors' preprint. The final publication is available at www.springerlink.com.).
  (Show abstract) (Hide abstract) (PDF)
  

  The prevalent method of increasing reasoning efficiency in the domain of qualitative constraint-based spatial and temporal reasoning is to use domain splitting based on so-called tractable subclasses. In this paper we analyze the application of nogood learning with restarts in combination with domain splitting. Previous results on nogood recording in the constraint satisfaction field feature learnt nogoods as a global constraint that allows for enforcing generalized arc consistency. We present an extension of such a technique capable of handling domain splitting, evaluate its benefits for qualitative constraint-based reasoning, and compare it with alternative approaches.

2011

• Matthias Westphal and Jochen Renz.
  Evaluating and Minimizing Ambiguities in Qualitative Route Instructions.
  In ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM-GIS 2011). ACM 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) (Online; PDF)
  

  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.
  (Show abstract) (Hide abstract) (Online; DOI) (BIB)
  

  Manipulation planning is a complex task for robots with a manipulator arm that need to grasp objects in the environment, specifically under narrow spatial conditions restricting the workspace of the robot. A popular approach for generating motion plans is probabilistic roadmap planning. However, the sampling strategy of such planners is usually unguided, and hence may lead to motion plans that seem counterintuitive for a human observer. In this article we present an approach that generates heuristics for the probabilistic sampling strategy from spatial plans that abstract from concrete metric data. These spatial plans describe a free trajectory in the workspace of the robot on a purely qualitative level, i.e., by employing spatial relations from formalisms considered in the domain of Qualitative Spatial and Tem- poral Reasoning. We discuss how such formalisms and constraint-based reasoning methods can be applied to approximate geometrically feasible motions. The paper is completed by an evaluation of a hybrid planning system in different spatial settings showing that run-times are notably improved when an abstract plan is considered as a guidance heuristic.

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.
  Also, see the follow up paper at KI 2012: Nogoods in Qualitative Constaint-based Reasoning.
  (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.

• Contact Legal Information