We conceive of space as a completely empty, infinite, three-dimensional, isotropic, disembodied receptacle distinct from the earth or any object that might be located on the earth, one that is capable of housing not only things but also such incorporeal mathematical entities as points and infinite straight lines. Such a strange idea--especially if it were taken to describe something that exists in this world--was unthinkable before the seventeenth century; yet not even Galileo fully accepted the idea of such a world as real. For him, a "straight line" was still bound to the earth- 's surface. Not until Newton was the task of "geometrization of the world" … completed. The transformation that led to the reification of geometry, though basically one of attitude and perception rather than of empirical observation, profoundly affected the course of science.

Reasoning about spatial data is a key task in many applications, including geographic information systems, meteorological and fluid-flow analysis, computer-aided design, and protein structure databases. Such applications often require the identification and manipulation of qualitative spatial representations, for example, to detect whether one object will soon occlude another in a digital image or efficiently determine relationships between a proposed road and wetland regions in a geographic data set. Qualitative spatial reasoning (QSR) provides representational primitives (a spatial "vocabulary") and inference mechanisms for these tasks. This article first reviews representative work on QSR for data-poor scenarios, where the goal is to design representations that can answer qualitative queries without much numeric information. It then turns to the data-rich case, where the goal is to derive and manipulate qualitative spatial representations that efficiently and correctly abstract important spatial aspects of the underlying data for use in subsequent tasks.

With increases in the complexity of information that must be communicated either by or to computers comes a corresponding need to find ways to communicate that information simply and effectively. It makes little sense to force the burden of communication on a single medium, restricted to just one of spoken or written text, gestures, diagrams, or graphical animation, when in many situations information is only communicated effectively through combinations of media. In response to requests for directions, respondents often choose to provide both a sketch map (for visual indications of relative distance, spatial relationships, etc.) as well as verbal guidance as to landmarks to attend to, obstacles to watch out for, opportunities to take, etc. Instructors training a subject in a new task often choose to present the task in at least two ways: they demonstrate what motions the trainee is supposed to carry out, using direct training, film or graphic media, and they convey what intentional actions those motions are meant to represent, through naturallanguage text or speech. Graphic media (diagrams and animation) can provide a way of visualizing significant patterns in situations (cf. the current interest in Scientific Visualization), while natural-language text (either spoken or written) can provide needed information on what the patterns may mean, why they may have developed, or what may be done to deal with them. Naturallanguage narration is necessary to convey the meaning and significance of such visualizations.)

IAAI seeks out applications of artificial intelligence that either demonstrate new technology or use previously known technology in innovative ways. IAAI particularly seeks out examples of deployments of AI technology that tackle the problems of demonstrating value and planning for long-term deployment. The five articles we have selected for this special issue are extended versions of papers that appeared in the conference. Two of the articles are deployed applications that have already demonstrated practical value. The remaining three articles are particularly innovative emerging applications.

To solve the problems, from 1991 to 1993, Korea Advanced Institute of Science and Technology (KAIST) and Daewoo jointly conducted the Daewoo Shipbuilding Scheduling (das) Project. To integrate the scheduling expert systems for shipbuilding, we used a hierarchical scheduling architecture. To automate the dynamic spatial layout of objects in various areas of the shipyard, we developed spatial scheduling expert systems. For reliable estimation of person-hour requirements, we implemented the neural network-based person-hour estimator. In addition, we developed the paneledblock assembly shop scheduler and the longrange production planner.

This article describes a method for building a cognitive map of a virtual urban environment. Our routines enable virtual humans to map their environment using a realistic model of perception. We based our implementation on a computational framework proposed by Yeap and Jefferies (1999) for representing a local environment as a structure called an absolute space representation (ASR). Their algorithms compute and update ASRs from a 2-1/2-dimensional (2-1/2D) sketch of the local environment and then connect the ASRs together to form a raw cognitive map. Our work extends the framework developed by Yeap and Jefferies in three important ways.

I am pleased to present this issue, most of which is devoted to a single subject-Spatial Reasoning. Our guest editor is Avi Kak, of Purdue University. Avi called me in the Summer of 1987, very enthused about a workshop he had recently attended. The idea of a "theme issue" on spatial reasoning sounded like a winner to me. I asked Avi to take the responsibility for selecting and editing the articles, and he agreed.

Keith M. Andress, coauthor of "Evidence Accumulation and Flow of Control in a Hierarchical Spatial Reasoning System, " is a research associate in the Robot Vision Lab at Purdue University His research interests are in formalisms for accumulation of evidence, expert systems, and computer vision. Steven J. Frank, author of "What AI Practitioners Should Know about the Law. Part Two" is an attorney practicing with Nutter, McClennen & Fish, One International Place, Boston, Massachusetts 02210-2699. Martin Herman, coauthor of "A Framework for Representing and Reasoning about Three-Dimensional Objects for Vision" is group leader of the Sensory Intelligence Group in the Robot Systems Division at the National Bureau of Standards, Gaithersburg, MD 20899. His research interests are robotics, robot vision, image understanding, world modeling, real-time planning, autonomous vehicles, and remotely operated vehicles Avinash C. Kak, coauthor of "Evidence Accumulation and Flow of Control in a Hierarchical Spatial Reasoning System, " is a professor of electrical engineering at Purdue University.

The processes that affect the distributions of animals and plants operate at multiple spatial and temporal scales, presenting a unique challenge for the development and coordination of effective conservation strategies, particularly for wide-ranging species. In order to study ecological systems across scales, data must be collected at fine resolutions across broad spatial and temporal extents. Crowdsourcing has emerged as an efficient way to gather these data by engaging large numbers of people to record observations. However, data gathered by crowdsourced projects are often biased due to the opportunistic approach of data collection. In this article, we propose a general class of models called AdaSTEM (for adaptive spatiotemporal exploratory models) that are designed to meet these challenges by adapting to multiple scales while exploiting variation in data density common with crowdsourced data.

We treat robotic assembly planning on two distinct conceptual levels. Planning at the higher level involves deriving nominal trajectories along which the bodies to be assembled are to be moved. These trajectories are nominal in the sense that they would accomplish the assembly were we to have a perfect robot manipulating bodies whose shapes were perfectly accurate. Planning at the lower level transforms such a high-level specification into an assembly plan that takes account of uncertainty. High-level robotic assembly planning is concerned with how bodies fit together and how spatial relationships among bodies are established over time.