Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 10412

QSTRLib: A Benchmark Problem Repository for Qualitative Spatial and Temporal Reasoning

( Oct 10 – Oct 13, 2010 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:



The Dagstuhl seminar ”QSTRLib” was planned as a successor event of the previously mentioned AAAI Spring Symposium. The intention for organizing this seminar was to discuss requirements on a problem library in a small group of researchers with expertise in benchmarking, in formal approaches to qualitative reasoning, or in specific application areas of QSTR.

More specifically, the main objectives of the seminar were to identify (a) a set of typical spatial and temporal problems and query tasks used in real world applications, (b) significant benchmark domains and problem instances, (c) measures to compare different QSTR formalisms in terms of expressiveness and efficiency, and (d) parameters to evaluate the performance of reasoning systems. In the following we provide a brief report on the course of the meeting and summarize the results of the discussions in the working groups and plenary sessions.

The plan for the seminar was to first collect spatial problems from various application scenario, then to develop classifications of these problems according to different viewpoints, and finally to analyze for selected problem instances how these could be represented in a problem library for QSTR. The seminar started on Monday, Oct 11, with a welcome session. In a series of short talks all seminar participants introduced themselves, highlighted their research interests, and explained their expectations on the seminar. After this S. Wölfl presented more background information on the benchmarking initiative and sketched a first draft of the formal language for the problem library, which will be required to represent problem domains and problem instances. A major point in the following discussion was the expressive power of the proposed language, the underlying formal logic, and the abstraction level at which the repository language allows for expressing spatial representation and reasoning tasks. A broad agreement could be achieved in that the proposed language may serve as a starting point, but that further developments of the language should be backed up on the experience of users working with the repository.

The aim of the two afternoon sessions was to collect a wide range of spatial representation and reasoning problems from different application scenarios. To feed in material, most seminar participants contributed flash presentations each focussing on a different use case, reasoning problem, tool, or data set. Afterwards, tools and demos were discussed in a more informal setting with the presenters. In the following breakout session small working groups were formed to collect spatial reasoning problems in different application scenarios including spatial reasoning in GIS, human spatial reasoning and reasoning with natural language, and spatial reasoning with sensor data.

Results of this seminar will be integrated into the proposed benchmarking library step-by-step. It is planned to start with a specification of a rather limited formal language that covers the symbolic formalisms and prominent reasoning tasks in QSTR research. Currently, a first draft of the language proposal is compiled and is planned to be available to the public by the end of April 2011. In the following months also the development of tools (in particular, parsers) supporting the language and the integration into existing reasoners such as SparQ and GQR will play an important role. A crucial point for the further development of the library will be to bridge the gap between potential expectations towards a problem library (i.e., the kind of problems users of the problem library would like to see included) and the level of reasoning support that users can expect from currently available reasoning engines. Nevertheless, the discussions in the seminar confirmed that interesting problem instances for the problem repository may be contributed from the following research areas:

  • Geographic Information Systems. Qualitative reasoning methods are promising methods to check the integrity of information to be added to geographic knowledge bases and to rewrite possible queries against such knowledge bases.
  • Ontological reasoning. Many knowledge bases (e.g., medical knowledge bases) could be enhanced by spatial relations between objects and/or temporal relations between events. Hybrid methods integrating ontological and spatial reasoning may allow for answering queries efficiently against such knowledge bases.
  • High-level agent control. Qualitative representation formalisms provide natural representations of (spatial or temporal) situations arising in high-level agent control systems. In such systems the application of specialized qualitative spatial and temporal reasoning methods (used as external reasoning methods) can show considerable performance gains.

As a final remark, it should be mentioned that this 3-day seminar with 19 participants benefited greatly from the specific facilities at Schloss Dagstuhl, namely easy access to the relevant literature as well as the flexibility to work in small groups on specific topics and discuss the results in plenary sessions.

  • Alia Abdelmoty (Cardiff University, GB)
  • Brandon Bennett (University of Leeds, GB) [dblp]
  • Christoph Benzmüller (Berlin, DE) [dblp]
  • Mehul Bhatt (Universität Bremen, DE) [dblp]
  • Manuel Bodirsky (Ecole Polytechnique - Palaiseau, FR) [dblp]
  • Anthony Cohn (University of Leeds, GB) [dblp]
  • Matt Duckham (The University of Melbourne, AU) [dblp]
  • Jason Jingshi Li (EPFL - Lausanne, CH)
  • Sangjiang Li (University of Technology - Sydney, AU)
  • Reinhard Moratz (University of Maine, US)
  • Björn Pelzer (Universität Koblenz-Landau, DE)
  • Marco Ragni (Universität Freiburg, DE) [dblp]
  • Jochen Renz (Australian National University, AU) [dblp]
  • Paulo E. Santos (University Center of FEI - Sao Paolo, BR) [dblp]
  • Geoff Sutcliffe (University of Miami, US) [dblp]
  • Jan Oliver Wallgrün (Universität Bremen, DE)
  • Matthias Westphal (Universität Freiburg, DE)
  • Stefan Wölfl (Universität Freiburg, DE) [dblp]
  • Diedrich Wolter (Universität Bremen, DE) [dblp]

  • artificial intelligence
  • data structures / algorithms / complexity
  • semantics / formal methods
  • logic

  • Qualitative reasoning
  • spatial reasoning
  • temporal reasoning
  • constraint satisfaction
  • benchmarking
  • problem library
  • problem description language
  • reasoning systems