This chapter approaches QSTR from an application perspective. Considering the exemplary application domains of robot navigation, GIS, and computer-aided design, the authors conclude that reasoning must be interpreted in a broader sense than the often-considered constraint-based reasoning and that supporting tools must become available. The authors then discuss the newly identified reasoning tasks and how they can be supported by QSTR toolboxes to foster the dissemination of QSTR in applications. Furthermore, the authors explain how they aim to overcome the lack-of-tools dilemma through the development of the QSTR toolbox SparQ.
Top1. Introduction
Qualitative Spatial and Temporal Reasoning (QSTR) (Cohn & Hazarika, 2001; Cohn & Renz, 2007; Renz & Nebel, 2007) is the subfield of knowledge representation and symbolic reasoning that deals with knowledge about an infinite spatio-temporal domain using a finite set of qualitative relations. One particular aim is to model human common-sense understanding of space. Qualitative approaches have therefore been promoted as a basis for connecting human cognition and intelligent agents. Moreover, qualitative approaches offer compact representations that are supposed to enable complex decision tasks. However, despite these rationales, we still observe a lack of success stories of QSTR in the sense of successful applications that make use of QSTR, or, ultimately, applications that are successful because they make use of QSTR.
In this chapter, we explore qualitative reasoning from an application oriented point of view. One possible reason for the comparatively small number of QSTR applications could be seen in a lack of adequate software toolboxes which provide the results of QSTR research in a form which enables application developers to incorporate QSTR techniques easily into their own software. Throughout the last years, first QSTR toolboxes have started to emerge (e.g., GQR [Gantner, Westphal, & Wölfl, 2008], QAT [Condotta, Ligozat, & Saade, 2006], and our own toolbox SparQ [Wallgrün, Frommberger, Wolter, Dylla, & Freksa, 2007]). However, so far these efforts have been very much concentrated on the problem of deciding satisfiability of sets of qualitative constraints. This emphasis on what we will term constraint-based reasoning is easily understandable because, technically speaking, qualitative relations constrain the valuation of variables and, hence, deciding satisfiability has been in the center of theoretical research in QSTR during the last two decades. Contrary to classical constraint-based techniques, QSTR has pursued a purely relation algebraic approach: qualitative relations and operations on them constitute a qualitative calculus (Ligozat & Renz, 2004) and the operations provide a symbolic approach to deciding consistency (Renz & Nebel, 2007)1.
One thesis underlying this work is that qualitative reasoning goes beyond constraint-based reasoning and, hence, different forms of reasoning need to be supported by the toolboxes. To corroborate this claim we look at three potential application domains of QSTR, namely the areas of robot navigation, Geographic Information Systems (GIS), and computer-aided design. Our goal is to identify which kind of qualitative reasoning is required to solve the individual problems of spatial knowledge processing occurring in these domains and our conclusion will be that constraint-based satisfiability testing often only plays a minor role.
Based on this result, we organize the newly identified reasoning tasks into groups and discuss how well they are currently understood, how they need to be supported in QSTR toolboxes, and what kind of theoretical research is still required. We then provide a glimpse at our own QSTR toolbox SparQ which we are developing with the goal of providing an easy-to-use interface to a rich repository of qualitative calculi and reasoning methods. In particular, we describe to which extent SparQ already supports some of the newly identified reasoning tasks and sketch its future development.
While the focus of this chapter will be on different kinds of reasoning tasks where reasoning is interpreted in a rather broad sense, there are clearly other issues involved that would improve the dissemination of QSTR techniques and toolboxes, e.g., representational aspects and integration with other AI methodology. We will address some of these points in the final section of this text containing conclusions and an outlook.
The chapter is organized as follows. In Section 2 we look at the different kinds of reasoning tasks occurring in the previously mentioned application domains. In Section 3 we classify and discuss the newly identified reasoning tasks. Our own toolbox SparQ will then be presented in Section 4, followed by conclusions and an outlook in Section 5.