GENE_ARCH is a Generative Design System that combines Pareto Genetic Algorithms with an advanced energy simulation engine. This work explores its integration with a Shape Grammar, acting as GENE_ARCH’s shape generation module. The islamic patio house typology is readdressed in a contemporary context, by improving its energy-efficiency, and rethinking its role in the genesis of high-density urban areas, while respecting its specific spatial organization and cultural grounding. Field work was carried out in Marrakesh, surveying a number of patio houses, becoming the Corpus of Design, from where a shape grammar was generated. The computational implementation of the patio house grammar was done within GENE_ARCH. The resulting program was able to generate new, alternative patio houses designs that were more energy efficient, while respecting the traditional rules captured from the analysis of existing houses. After the computational system was fully implemented, it was possible to realise a large number of experiments. The first experiments kept more restrained rules, thus generating new designs that closer resembled the existing ones. The progressive relaxation of rules and constraints allowed for a larger number of variations to emerge. Analysis of energy results provide insight into the main patterns resulting from the GA search processes.

There has been a recent push in extraction of 3D spatial layout of scenes. However, none of these approaches model the 3D interaction between objects and the spatial layout. In this paper, we argue for a parametric representation of objects in 3D, which allows us to incorporate volumetric constraints of the physical world. We show that augmenting current structured prediction techniques with volumetric reasoning significantly improves the performance of the state-of-the-art.

In this paper we introduce a method for extending binary qualitative direction calculi with adjustable granularity like OPRAm or the star calculus with a granular distance concept. This method is similar to the concept of extending points with an internal reference direction to get oriented points which are the basic entities in the OPRAm calculus. Even if the spatial objects are from a geometrical point of view infinitesimal small points locally available reference measures are attached. In the case of OPRAm, a reference direction is attached. The same principle works also with local reference distances which are called elevations. The principle of attaching references features to a point is called hidden feature attachment.

An important issue in Qualitative Spatial Reasoning is the representation of relative direction. In this paper we present simple geometric rules that enable reasoning about relative direction between oriented points. This framework, the Oriented Point Algebra OPRA_m, has a scalable granularity m. We develop a simple algorithm for computing the OPRA_m composition tables and prove its correctness. Using a composition table, algebraic closure for a set of OPRA statements is sufficient to solve spatial navigation tasks. And it turns out that scalable granularity is useful in these navigation tasks.

Autonomous agents in real-time strategy (RTS) games lack an integrated framework for reasoning about choke points and regions of open space in their environment. This paper presents an algorithm which partitions the environment into a set of polygonal regions and computes optimal choke points between adjacent regions. This representation can be used as a component for AI agents to reason about terrain, plan multiple routes of attack, and make other tactical decisions. The algorithm is tested on a set of popular maps commonly used in international Starcraft competitions and evaluated against answers made by human participants. The algorithm identified 97% of the choke points that the participants found and also identified a number of bottlenecks that human participants did not recognize as choke points.

A topological approach to stratification learning is developed for point cloud data drawn from a stratified space. Given such data, our objective is to infer which points belong to the same strata. First we define a multi-scale notion of a stratified space, giving a stratification for each radius level. We then use methods derived from kernel and cokernel persistent homology to cluster the data points into different strata, and we prove a result which guarantees the correctness of our clustering, given certain topological conditions; some geometric intuition for these topological conditions is also provided. Our correctness result is then given a probabilistic flavor: we give bounds on the minimum number of sample points required to infer, with probability, which points belong to the same strata. Finally, we give an explicit algorithm for the clustering, prove its correctness, and apply it to some simulated data.

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.