RCC8 is a well-known constraint language for expressing and reasoning about spatial knowledge. We state a simple and concise Horn theory for RCC8 analogous to the ORD-Horn theory for temporal reasoning. This theory allows for expressing RCC8 and retains tractability of the well-known Horn reduct of RCC8. Further, it is much more adequate for practical purposes in the area of logic programming and surpasses previous attempts.

Several studies in Qualitative Spatial and Temporal Reasoningdiscuss translations of the satisfiability problem on qualitativeconstraint languages into propositional SAT. Most of these encodings focus on compactness, while propagation strength is seldom discussed. In this work, we focus on temporal reasoning with the Point Algebra and Allen's Interval Algebra. We understand all encodings as a combination of propagation andsearch. We first give a systematic analysis of existing propagation approachesfor these constraint languages. They are studied and ordered with respect to their propagation strengthand refutation completeness for classes of input instances. Secondly, we discuss how existing encodings can be derived fromsuch propagation approaches. We conclude our work with an empirical evaluation which shows that theolder ORD-encoding by Nebel and Bürckert performs better than more recently suggested encodings.

Qualitative Spatial and Temporal Reasoning is a central topic in Artificial Intelligence. In particular, it is aimed at application scenarios dealing with uncertain information and thus needs to be able to handle dynamic beliefs. This makes merging and revision of qualitative information important topics. While merging has been studied extensively, revision which describes what is happening when one learns new information about a static world has been overlooked. In this paper, we propose to fill the gap by providing two revision operations for qualitative calculi. In order to implement these operations, we give algorithms for revision and analyze the computational complexity of these problems. Finally, we present an implementation of these algorithms based on a qualitative constraint solver and provide an experimental evaluation.

Qualitative spatial and temporal reasoning is a research field that studies relational, constraint-based formalisms for representing, and reasoning about, spatial and temporal information. The standard approach for checking consistency is based on an exhaustive representation of possible configurations between three entities, the so-called composition tables. These tables, however, encode semantic background knowledge in a redundant way, which becomes a size and efficiency issue, when the composition table needs to be grounded as done in SAT encodings of problem instances. % In this paper, we present a new framework that allows for decomposing composition tables into logically simpler parts, while preserving logical equivalence, e.g., the decomposition in start- and end-points for Allen's Interval Calculus. We show that finding such decompositions is an NP-complete problem and present a SAT-based method to generate decompositions. Finally, we discuss the impact of our decomposition method on SAT encodings of problem instances, and present a reasoning system built on decompositions that compares favorably with state-of-the-art solvers.

Route navigation is a widely studied subject from both cognitive and practical points of view. A particular aspect is the generation of (verbal) route instructions that are robust with respect to ambiguous verbal terms. Work in this area usually builds on counting the number of ambiguous turn options along a route. Simple graph search can then be used to derive a route whose description is the most fault-tolerant according to this measure.

The generation of route descriptions is a fundamental task of navigation systems. A particular problem in this context is to identify routes that can easily be described and processed by users. In this work, we present a framework for representing route n

This paper introduces restart and nogood recording techniques in the domain of qualitative spatial and temporal reasoning. Nogoods and restarts can be applied orthogonally to usual methods for solving qualitative constraint satisfaction problems. In particular, we propose a more general definition of nogoods that allows for exploiting information about nogoods and tractable subclasses during backtracking search. First evaluations of the proposed techniques show promising results.

LAMA is a classical planning system based on heuristic forward search. Its core feature is the use of a pseudo-heuristic derived from landmarks, propositional formulas that must be true in every solution of a planning task. LAMA builds on the Fast Downward planning system, using finite-domain rather than binary state variables and multi-heuristic search. The latter is employed to combine the landmark heuristic with a variant of the well-known FF heuristic. Both heuristics are cost-sensitive, focusing on high-quality solutions in the case where actions have non-uniform cost. A weighted A* search is used with iteratively decreasing weights, so that the planner continues to search for plans of better quality until the search is terminated. LAMA showed best performance among all planners in the sequential satisficing track of the International Planning Competition 2008. In this paper we present the system in detail and investigate which features of LAMA are crucial for its performance. We present individual results for some of the domains used at the competition, demonstrating good and bad cases for the techniques implemented in LAMA. Overall, we find that using landmarks improves performance, whereas the incorporation of action costs into the heuristic estimators proves not to be beneficial. We show that in some domains a search that ignores cost solves far more problems, raising the question of how to deal with action costs more effectively in the future. The iterated weighted A* search greatly improves results, and shows synergy effects with the use of landmarks.