IJCAI-95 Tutorial on ``Representation of Spatial Knowledge''

Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95)
Sunday Aug 20, 1995, 9AM - 1PM, Montreal, Canada

Amitabha Mukerjee, Indian Institute of Technology, Kanpur, India
and
Daniel Hernández, Technische Universität München, Germany

Brief description

This tutorial is aimed at AI researchers and engineers interested in representing and reasoning with spatial knowledge, i.e., shape, size, relative position, connectivity, etc. The need to represent spatial knowledge explicitly arises in applications as diverse as Geographical Information Systems, Image Analysis, Robot Navigation, Natural Language Understanding, and Visual Modeling. Techniques that evolved in the Physical Sciences, involving quantitative description based on coordinate frames, do not work well for abstraction - e.g. in describing a class of shapes. This is the problem of {\em abstraction} which is one of the key issues addressed by AI.

The full notes from this tutorial (1140 K, 124 pages) are now available via FTP from this site. [NEW]. For European users, it may be easier from flop.informatik.tu-muenchen.de.

An expanded version of the list of Spatial Reasoning Resources on the Internet is now available.

Also, the bibliography is available for online WWW search along with six other Bibliographies including one with many reviews of 2500 entries .

Representation Methodologies

In this tutorial, we highlight the progress that has been made in representing space at different levels of abstraction, with particular emphasis on applications. We first compare traditional quantitative approaches with recent qualitative and hybrid approaches. We then cover interval algebras and present a 2D application for block-based image structures such as documents. Next we give an overview of extant approaches to the representation of arrangement, topology, orientation, size, distance, and shape together with the corresponding reasoning mechanisms. Along the way we discuss general representational aspects (frames of reference, points vs. extension, granularity, vagueness) and illustrate these with some specific applications.

Applications

  1. Block-Layout Analysis of Documents: Many tasks (VLSI/piping/GIS) involve orthogonal layouts. Here we consider documents, and the logical nature of blocks are identified based on qualitative model.
  2. Extended spatial query languages for GIS: Here we investigate how a query language with spatial abstraction ability is integrated on a Geographic Information System.
  3. Hybrid model for conceptual design involving shapes in 2D and 3D: Here we show how Hybrid Spatial Reasoning can help in understanding design sketches, and highlight an implementation for designing scooter crankshafts.

We have provided extensive course notes covering a large body of research, and used several slides contributed by other researchers. The course notes are actually quite voluminous (173 slides); we cover more details than we can possibly cover during the actual presentation; in case of specific areas of user interest, we can go deeper (we will be delighted to receive your e-mail feedback). The course notes also include about 400 references, organized into topics via a Thematic Bibliography , and a long list of internet on-line sources of further information.

Prerequisite Knowledge:

The tutorial is reasonably self-contained; the equivalent of an introductory AI course should be sufficient.

o Table of Contents of Course Notes

o A Synopsis is now available (contains condensed bibliography) [NEW]

o Registration Information

o Original IJCAI-95 Tutorial Announcement Page

Daniel Hernández, Mon Mar 6 13:25:46 MET 1995
Amitabha Mukerjee, Thu Jun 15 14:33:30 CDT 1995