October 10 – 13 , 2010, Dagstuhl Seminar 10412
QSTRLib: A Benchmark Problem Repository for Qualitative Spatial and Temporal Reasoning
For support, please contact
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.
- Artificial Intelligence
- Data Structures / Algorithms / Complexity
- Semantics / Formal Methods
- Qualitative reasoning
- Spatial reasoning
- Temporal reasoning
- Constraint satisfaction
- Problem library
- Problem description language
- Reasoning systems