Confirming the QSR Promise

No. 2: Benchmarking of Qualitative Spatial and Temporal Reasoning Systems

Volume

Papers from the 2009 AAAI Spring Symposium

Contents

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 sys- tems, 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 em- pirical 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 compet- itive, but still outperformed by a qualitative reasoner on the problem instances considered here.