Seminar: Qualitative spatio-temporal reasoning - Organization

Organizer: Prof. Dr. Till Mossakowski

Time and Location

The seminar will take place as a block seminar on Monday, February 16, 2009, starting at 10 am in room 052-00-016.

Description

Spatial-temporal reasoning aims at describing the common-sense background knowledge on which our human perspective on the physical reality is based. Methodologically, qualitative constraint calculi restrict the vocabulary of rich mathematical theories dealing with temporal or spatial entities such that specific aspects of these theories can be treated within decidable fragments with simple qualitative (non-metric) languages. Contrary to mathematical or physical theories about space and time, qualitative constraint calculi allow for rather inexpensive reasoning about entities located in space and time. For this reason, the limited expressiveness of qualitative representation formalism calculi is a benefit if such reasoning tasks need to be integrated in applications. For example, some of these calculi may be implemented for handling spatial GIS queries efficiently and some may be used for navigating, and communicating with, a mobile robot.

The seminar will give an overview of different calculi:

Temporal calculi (reasoning about time)
Point algebra, Allen's Interval Algebra
Mereotopological calculi (reasoning about regions in space)
Region connection calculus, 9-intersection calculus
Orientation calculi (reasoning about orientations like left and right)
cardinal direction calculus, LR-calculus, double cross calculus, OPRA, dipole calculus
Spatio-temporal calculi (reasoning about moving objects)
Spatio-temporal Constraint Calculus, Qualitative Trajectory Calculus

Most of these calculi can be formalized as abstract relation algebras, such that reasoning can be carried out at a symbolic level. For computing solutions of a constraint network, there are serveral methods, like algebraic closure, backtracking using maximal tractable subsets, global consistency, and other constraint satisfaction methods. Two generic constraint solving tools (SparQ and GQR) for qualitative calculi are available.

Seminar talks

Seminar talks can be in English or German.

Important Dates

Deadline for seminar paper: Monday, 2. February 2009 (two weeks before the seminar)

Deadline for slides draft: Monday, 9. February 2009 (one week before the seminar)

Requirements

To obtain credit points, participants have to

give a 30 minutes presentation on their assigned topic,
submit their seminar paper, and
briefly comment about their second assigned topic (~5 minutes), after the corresponding presentation.

Seminar Paper

The paper should be about 15 pages. See the seminar guide for templates.