home   Qualitative Representation   Qualitative spatial reasoning

Qualitative spatial reasoning   (written by Michał Zawidzki)

Qualitative spatial reasoning (QSR) is a field of research within AI whose aim is to provide means to represent and reason about spatial environment without resorting to quantitative measures and only utilizing their symbolic abstractions. Cohn and Renz distinguish in (Cohn & Renz 2008) several elements that need to be considered within QSR:

1. Spatial representation There are several aspects that are clarified within this point, such as:

  1. - ontology (which spatial entities should be considered primitive?);
  2. - spatial relations (which relations between spatial entities should be distinguished?);
  3. - mereology (how to define the parthood-whole relation?);
  4. - mereotopology (which traditional topological notions can we extend mereology with?);
  5. - mereogeometry (which traditional geometrical notions can we extend mereology with?).

2. Spatial reasoning Within this point various formalisms are being devised which enable to perform reasoning about represented static aspects of spatial environment.

3. Reasoning about spatial change Within this point spatial calculi are being developed which encapsulate represented dynamic aspects of spatial environment.

Several most notable examples of QSR methods that can deal with two-dimensional space are: Region Connection Calculus, Allen's Interval Algebra, and Rectangle Algebra (RA).

In (Zang & Renz 2013) and (Zang & Renz 2014) an extended version of RA, called Extended Rectangle Algebra (ERA), is introduced. RA considers objects' Minimum Bounding Rectangles (MBRs) with sides parallel to the axes of a coordinate system. Each MBR is projected on the coordinate axes. Then, start and end points of such intervals are used to define a relation between two MBRs. ERA takes into account not only the start and end points of an interval but also its centre.

References

  1. Cohn, A. G., & Renz, J. (2008). Qualitative spatial representation and reasoning. Handbook of knowledge representation, 3, 551-596.
  2. Zhang, P., & Renz, J. (2013). Qualitative spatial representation and reasoning in Angry Birds: First results. In 27th International Workshop on Qualitative Reasoning, 123.
  3. Zhang, P., & Renz, J. (2014). Qualitative spatial representation and reasoning in Angry Birds: The extended rectangle algebra.