Arbeitsgruppe Grundlagen der Künstlichen Intelligenz

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

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, 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.
  

• 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.
  

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.