Many problems in AI, including planning, logical reasoning and probabilistic inference, have been shown to reduce to (weighted) constraint satisfaction. While there are a number of approaches for solving such problems, the recent gains in efficiency of the satisfiability approach have made SAT solvers a popular choice. Modern propositional SAT solvers are efficient for a wide variety of problems. However, particularly in the case of spatial reasoning, conversion to propositional SAT can sometimes result in a large number of variables and/or clauses. Moreover, spatial reasoning problems can often be more efficiently solved if the agent is able to exploit the geometric nature of space to make better choices during search and backtracking. The result of these two drawbacks — larger problem sizes and inefficient search — is that even simple spatial constraint problems are often intractable in the SAT approach. In this paper we propose a spatial reasoning system that provides significant performance improvements in constraint satisfaction problems involving spatial predicates. The key to our approach is to integrate a diagrammatic representation with a DPLL-based backtracking algorithm that is specialized for spatial reasoning. The resulting integrated system can be applied to larger and more complex problems than current approaches and can be adopted to improve performance in a variety of problems ranging from planning to probabilistic inference

An important challenge in understanding climate change is to uncover the dependency relationships between various climate observations and forcing factors. Graphical lasso, a recently proposed L 1 penalty based structure learning algorithm, has been proven successful for learning underlying dependency structures for the data drawn from a multivariate Gaussian distribution. However, climatological data often turn out to be non-Gaussian, e.g. cloud cover, precipitation, etc. In this paper, we examine nonparametric learning methods to address this challenge. In particular, we develop a methodology to learn dynamic graph structures from spatial-temporal data so that the graph structures at adjacent time or locations are similar. Experimental results demonstrate that our method not only recovers the underlying graph well but also captures the smooth variation properties on both synthetic data and climate data. An important challenge in understanding climate change is to uncover the dependency relationships between various climate observations and forcing factors. Graphical lasso, a recently proposed An important challenge in understanding climate change is to uncover the dependency relationships between various climate observations and forcing factors. Graphical lasso, a recently proposed L 1 penalty based structure learning algorithm, has been proven successful for learning underlying dependency structures for the data drawn from a multivariate Gaussian distribution. However, climatological data often turn out to be non-Gaussian, e.g. cloud cover, precipitation, etc. In this paper, we examine nonparametric learning methods to address this challenge. In particular, we develop a methodology to learn dynamic graph structures from spatial-temporal data so that the graph structures at adjacent time or locations are similar. Experimental results demonstrate that our method not only recovers the underlying graph well but also captures the smooth variation properties on both synthetic data and climate data.

Topological relations between spatial objects are the most important kind of qualitative spatial information. Dozens of relation models have been proposed in the past two decades. These models usually make a small number of distinctions and therefore can only cope with spatial information at a fixed granularity of spatial knowledge. In this paper, we propose a topological relation model in which the topological relation between two convex plane regions can be uniquely represented as a circular string over the alphabet {u; v; x; y}. A linear algorithm is given to compute the topological relation between two convex polygons. The infinite relation calculus could be used in hierarchical spatial reasoning as well as in qualitative shape description.

Tactile maps offer access to spatial-analog information for visually impaired people. In contrast to visual maps, a tactile map has a lower resolution and can only be inspected in a sequential way, complicating the extraction of spatial relations among distant map entities. Verbal assistance can help to overcome these difficulties by substituting textual labels with verbal descriptions and offering propositional knowledge about spatial relations. Like visual maps, tactile maps are based on visual, spatial-geometric representations that need to be reasoned about in order to generate verbal assistance. We present an approach towards a verbally assisting virtual-environment tactile map (VAVETaM) realized on a computer system utilizing a haptic force-feedback device. In particular, we discuss the tasks of understanding the user's map exploration procedures (MEPs), of exploiting the spatial-analog map to anticipate the user's informational needs, of reasoning about optimal assistance by taking assumed prior knowledge of the user into account, and of generating appropriate verbal instructions and descriptions to augment the map.

Reasoning by the usage of mental images has been the subject of much debate in Cognitive Science, especially among the schools of depictive and descriptive imagistic representations. Whether or not reasoning with mental images involves a mechanism or a process different from language based reasoning is an important question. This paper proposes that any theory which aims for a cohesive whole needs to be constrained by neurophysiological data and such data can be obtained by the Clock Drawing Test. The Clock Drawing Test (CDT) is a screening tool for cognitive impairment and can be used as a tool to test resilience of certain factors of visual spatial representations. Thus, it can help to form an empirical case for which factors are prone to debility and which factors are not during the onset and progress of cognitive impairment from a mental representation point of view. This paper presents 50 CDT tests done on patients with cognitive impairment and analyses the results which support the case for a depictive rather than a descriptive theory for imagistic representations. Lastly, this paper proposes that there is some evidence for a more dynamic and distributed nature of representation in the observations which question the above dichotomy and can be partly explained by certain aspects of the connectionist school of thought.

This paper proposes a layered graph model for representing the internal structure of complex plane regions, where each node represents the closure of a connected component of the interior or exterior of a complex region. The model provides a complete representation in the sense that the (global) nine-intersections between the interiors, the boundaries, and the exteriors of two complex regions can be determined by the (local) RCC8 relations between associated simple regions. 

In this paper we show how the shape of a 2D-landmark configuration can be encoded based on qualitative 1D-ordering information and how relevant geometric shape properties of a landmark configuration (strictly based on ordering information) can be detected by a sequence of view-based snapshots. Furthermore we show how shape of landmark configurations supports view-based localization tasks specially in the face of erroneous and missing sensor information.

Representing and comparing two-dimensional shapes is an important problem. Our hypothesis about human representations is that that people utilize two representations of shape: an abstract, qualitative representation of the spatial relations between the shape’s parts, and a detailed, quantitative representation. The advantage of relational, qualitative representations is that they facilitate shape comparison: two shapes can be compared via structural alignment processes which have been used to model similarity and analogy more broadly. This comparison process plays an important role in determining when two objects share the same shape, or in identifying transformations (rotations and reflections) between two shapes. Based on our hypothesis, we have built a computational model which automatically constructs both qualitative and quantitative representations and uses them to compare two-dimensional shapes in visual scenes. We demonstrate the effectiveness of our model by summarizing a series of studies which have simulated human spatial reasoning.

We develop an algorithm for efficient range search when the notion of dissimilarity is given by a Bregman divergence. The range search task is to return all points in a potentially large database that are within some specified distance of a query. It arises in many learning algorithms such as locally-weighted regression, kernel density estimation, neighborhood graph-based algorithms, and in tasks like outlier detection and information retrieval. In metric spaces, efficient range search-like algorithms based on spatial data structures have been deployed on a variety of statistical tasks. Here we describe the first algorithm for range search for an arbitrary Bregman divergence. This broad class of dissimilarity measures includes the relative entropy, Mahalanobis distance, Itakura-Saito divergence, and a variety of matrix divergences. Metric methods cannot be directly applied since Bregman divergences do not in general satisfy the triangle inequality. We derive geometric properties of Bregman divergences that yield an efficient algorithm for range search based on a recently proposed space decomposition for Bregman divergences.

The use of context is critical for scene understanding in computer vision, where the recognition of an object is driven by both local appearance and the objects relationship to other elements of the scene (context). Most current approaches rely on modeling the relationships between object categories as a source of context. In this paper we seek to move beyond categories to provide a richer appearance-based model of context. We present an exemplar-based model of objects and their relationships, the Visual Memex, that encodes both local appearance and 2D spatial context between object instances. We evaluate our model on Torralbas proposed Context Challenge against a baseline category-based system. Our experiments suggest that moving beyond categories for context modeling appears to be quite beneficial, and may be the critical missing ingredient in scene understanding systems.