淺談QSR（定性空間關係推理）演算法

定性的空間推理能力在很多AI子領域都很有用（比如機器人視覺和運動規劃、有關空間表達的自然語言理解、計算機輔助設計專家系統等等）

在一個典型的AI系統里，空間推理引擎是抽象的語言邏輯和現實物理世界間的紐帶：

要實現一個可用的空間推理系統我們可以從很多簡單的空間特性入手，最單的考慮一維空間上線段的方位關係 RA（Rectangle Algebra ）：

然後將之擴展到二維空間，我們就得到了兩個矩形在二維空間上的位置關係，共有13*13 = 169種，由於任何二維圖形我們總能用bounding box表示成矩形，所以這169中關係可以定性刻畫平面上任意兩物體的位置關係。

另外我們還可用在bounding box上做延長線，兩個bounding box就相交成一個3x3的封閉矩陣，通過這個矩陣也可以刻畫兩物體間的關係，這個方法我們叫CDC （Cardinal Directio

n Calculus）

另外除了相對的方位，我們也可以在從拓撲上定義兩個物體間的相對關係，比如著名的rcc8

另外空間中其他的特性也都可以進行定性的刻畫，比如遠近、大小

基於這些定性的刻畫方法，我們便可以做一些定性的計算，比如基於方位來計算位置關係的相似度：

個人感覺QSR目前的方嚮應該是在三維空間、多物體、層次化、複合邏輯的方向發展：

比如層次化方面的論文：

關於推理複合和由此帶來的計算複雜度衡量：

清華大學的李三江博士有RCC8和方向（RA&CDC）結合的探索（2009年）

Combining RCC-8 with Qualitative Direction Calculi: Algorithms and Complexity

布雷西亞大學的Alfonso Gerevini有RCC8和尺寸結合的探索（2002年）

Combining topological and size information for spatial reasoning

在這個領域近年的出版物：

Leeds QSR Group Publications