葛笑雨：應用於智能體的空間物理定性推理技術

知識 09-06

近年來人工智慧技術突飛猛進，越來越多的機器人正在走進我們的世界。與人類一樣，機器人在執行日常任務時往往需要具備一定的空間物理推理能力。具備這種能力不僅使機器人可以完成指定任務，更能讓他們避免在執行任務時作出對人類有潛在危害的行為。

空間物理推理是重要且有趣的領域。近日，在雷鋒網 AI 研習社公開課上，澳大利亞國立大學葛笑雨博士就帶領大家認識定性物理推理並感受其中的樂趣。公開課回放視頻網址：http://www.mooc.ai/open/course/531

葛笑雨：Dorabot 演算法團隊負責人，澳大利亞國立大學博士，計算機科學系人工智慧專業，導師是 Jochen Renz，主要研究方向為空間物理推理，研究成果在 IJCAI、AAAI、ECAI、KR 上發表過。

分享主題：應用於智能體（Agent）的空間物理定性推理技術

分享提綱：

1. 空間物理推理為什麼重要

2. 空間物理推理的背景與現狀

3. 定性空間物理推理的未來

5. 在機器人領域的實踐（Dorabot 相關）

雷鋒網 AI 研習社將其分享內容整理如下：

我們本次的主題為：智能體（Agent）的空間物理推理。智能體，英文名是 Agent，它可以使用一些人工智慧演算法做一些事情，通過它自己的感知、規劃與環境進行交互。空間物理推理，指的則是通過我們觀測到的空間和物理信息推出一些有用的信息。

大家都知道，很多術語原生詞都為英文，由於時間緊迫以及為了保證講述的準確性，因此後面都使用英文 PPT。

我們今天的話題聚焦於 Motivating。首先，探討一下為什麼我們需要空間物理推理？

包括機器人等硬體形體的 AI Agent 正逐漸走入我們的生活，它以前一般都存在於軟體中，對現實造成的影響不大，但是進入現實生活中會對我們的生活造成影響，一旦出現一些 bug 或者不能完整地理解它們所處的環境，就可能做出一些危害人類的行為。而我們現實世界到處充滿了空間與物理元素，我們平時做的一些例如搬東西、打包行李以及倒水倒酒等事情，都需要對空間與物理具備處理能力，而機器人一旦進入現實世界，也需要具備這種空間物理處理能力。

問大家一個問題：在解決這些問題時，你們是怎麼思考的呢？

有一種方法是在腦海里進行模擬、推演、想像。看右邊這張定滑輪的示意圖，當我用手拉起這根線，大家就會想下面這個箱子會怎麼動。這個時候我們就在進行模擬，會想：當我這根線拖動時，這個輪子就會上來，下面和最下面的輪子也都會上來，最後箱子也跟著上來了。

基於這種觀察，這就形成了一個理論：我們人腦中也許存在一種雜訊牛頓模擬器（Nosiy Newtonian Simulator）。每當我們進行推理的時候，我們就會使用它。

當情況變得複雜時，我們會怎麼做？大家可以看下 PPT 下方這個圖——齒輪，當人去搖動前面的桿，右邊的齒輪會怎麼轉動呢？順時針還是逆時針？遇到這個問題，我們就會進行推理，拿出手、筆和腦子去推算齒輪會怎麼動。Hegarty 就提出了一個理論讓這兩種方式完美融合在一起。

當一個機器人來到這個世界，需要具備什麼能力？

首先，它要理解世界的空間和物理性質，之後，才能理解空間上的變化，而這些變化，往往又是通過物理交互所產生的。最後，它需要知道動作執行後的結果。

舉個例子，搭積木搭成了塔時，如果要在塔上放一個方塊，這個方塊對這個塔會有什麼影響？我們必須先理解方塊和塔所組成的結構的性質以及放這個動作所能產生的空間上的變化，這樣我們才能預測到方塊放下去會對塔有什麼影響。

在最近幾年，學術界一直在推動 Intelligent Physical Systems（在這裡我們直接使用機器人一詞）。首先機器人必須是安全的，我們才允許它執行動作，如果你站在它旁邊影響了它的執行路徑，它就有可能把你傷到，那就要求它們必須知道它們的目標造成的結果。再者，我們的世界是連續的，存在無限的動作，例如當我們要讓機器人將水放到桌子上，我們就需要給它放置的坐標，而這個坐標的可能性也是無限的。此外，機器人的感知是不完美的，因此機器人一旦發現做出的動作與預期的不一樣，它就需要調整它的世界觀。

定性物理在 AI 出現的時候就出現了。研究者用定性化的語言去描述各種物理、空間問題。到 90 年代末漸漸沉寂。

然而，現在學術界為什麼又對這個感興趣？因為我們當下這個時代，硬體和機器學習技術都在飛速發展，越來越多機器人被應用於工業行業，也有一部分進入民用。商業化的推動和技術的發展，讓我們對定性物理這個非常難的領域又有了期待。

定性物理，就是用一種符號化的語言去表達物理系統，從而我們就可以用一些演算法和驗證方法去預測這個系統的行為。當這種符號化語言完善後，我們就可以預測系統在未來任何一個時間發生的行為——預測這個系統一定不會做什麼事情，它就不會做什麼事情。

為什麼物理推理是一個非常難的問題？

首先是它的計算複雜性非常高，舉幾個例子：

第一個跟蹤光線。在空間的某一點打出一束光，假設空間有鏡片、障礙物，光會發生折射與反射，當我們想預測光在未來某一時間點的位置時，這個問題就是一個圖靈完全的問題，即我們現在可以通過讓光線來模擬圖靈機。

第二個撞球問題。這也是一個圖靈完全問題，用撞球來模擬圖靈機——曾被數學證明過，當這個球打出，假設球之間發生的是無損失的碰撞，預測它將落到哪個位置。它有一個理論 Ergodic motion，只要給這個球無限的時間，當這個球不停地動，軌跡會布滿這個撞球桌。力越大，走得越多，覆蓋範圍越大，球在這裡是沒有體積的點。當然，球的初始方向選擇不當也會出現循環的軌跡。

第三個物理推理問題，比如我有一個學弟就曾證明出來 Angry Birds 是一個 NP-hard 問題。

在這三個問題中，我們做個預測都這麼難，那麼在無限多的動作里選擇一個動作做規劃和推理，就是一個更加難的問題了。

下圖中，左上圖是一個認知科學的實驗，黑色邊界是一個打不透的牆，裡面有一個小球往右下運動，會先到黑牆還是紅牆？我們都知道最終會到紅牆，但是如果用模擬的方法（預測），它們會持續隨機採樣，雖然大多數情況下結果都會是——紅牆，但是一旦我在牆上開一個小孔，隨機採樣就不一定成功。

右上圖是一位專家解決這個球在空間中運動的問題。給定軌跡後，球最終會是怎樣的軌跡和狀態？在定性物理中，我們會把空間離散化變成幾個區域（右下圖），小箭頭指球在這個區域可以前進的方向，同時，我們也有自己的一套規則和求狀態的描述來知道系統去推理球的運動方向，在這裡不展開，有興趣可以參考一下 1980 年 Forbus 的這篇文章。左下圖是在一個 3D 高爾夫球場，預測球的運動的問題，這是我最近比較關注的問題。

還有一個案例是，Forbus 曾經用約束力學（Constrained Mechanics）去描述鐘錶，用符號化的推理和表達模擬時鐘的走動。

他當時使用非常古老的掃描儀將零件掃描（如中間圖所示），每個齒輪都有自己的 ID 和全描述（最右圖），可以通過描述去推理時鐘是怎麼轉動的。在工業應用中，定性物理推理往往被用來定性的分析一個複雜物理系統的性質。其能快速得出初步的定性的結果。根據結果，再決定是否要進一步進行嚴密的模擬。

稍微講一下表達方法。

首先，方向可以離散化和符號化，提到方向關係問題，在左圖中會說 B 在 A 的 S6 方向，而右圖中會說 B 在 A 的右邊。同時，旋轉和運算都可以符號化，這樣就能在不能求到精確值的情況下，依舊能得到比較好用的解。此外，拓撲結構符號化後，可以描述兩個空間物體的相離、相交或者包含等拓撲關係。比如右圖描述 2D 空間，機器人想將易拉罐扔到垃圾桶，我們同樣採取了空間離散化來進行表達，另外，我們通過對這個場景進行描述，能夠做模型追蹤，還能進行形式化驗證機器人對所處的環境所造成的影響。

接下來講推理。

第一個就是字面的推理，指在有限、不精確的信息裡面，我們還能找到一些比較有用的結果。

第二個是一致性，即探索空間中物體的關係是否真實，是否會有不正常的情況。左上圖的案例是最簡單的事件表達方法，before 指事件 A 發生在事件 B 之前，meet 指 A、B 相鄰發生，依次類推。右下圖，說的就是從 A 和 B 的關係和 B 和 C 的關係中推出 A 和 C 的關係。

上面講的是定性物理，而對於物理推理，還有一個流派叫模擬推理（Simulation-based reasoning），它通過不停做模擬，用概率分布做採樣，得到可接受的解。比如問到下面這個塔會向左倒還是向右倒的問題，我們的腦子就會不停做模擬、預測，最後得到答案。不過，這個方法還是存在很多問題的，模擬很難做到盡善盡美，根基就不太穩的話，模擬的結果就不能很精確。

之前講到很多圖靈完全問題，就是指你給它輸入，它會停機，我們無法在有限的時間裡確定答案。

而當我們給這個問題設定一個時間限制的時候，圖靈完全問題就會變成半圖靈問題或者一個有效演算法可以解決的問題。當我們遇到一個計算很複雜的問題，可以找出一個可被利用的結構，通過多項式演算法或者估算的方式去解決。

提一下我們這個領域一直在研究的三個問題：

動作預測問題：比如打高爾夫球——打出第一桿怎麼去預測球去哪。

感知：大家要注意視覺是感知的一種，感知也可以感知物體的物理性質。

規劃：前兩個問題解決後我們才能談規劃，需要對這個世界的感知、行為理解，最後需要一個演算法從上面的行為中找解。

目前主流的物理推理包括以下四個：

第一個是模擬推理（Simulation-based reasoning）。在吳同學 2015 年的這篇論文中，探索用手推一下這個 Cube，物體會發生怎樣的運動的問題。實驗中，系統首先有一套深度學習去學習它的物理性質，再去（不停）做模擬，直到找到一個概率很高的結果做預測。最後通過真正去推這個 Cube 得到真實結果，去跟之前的預測做比較。

第二個是遷移學習（Transfer learning），即在模擬中進行深度學習，我對這個領域我不太了解就不多說，不過我建議有需要的同學使用 Mujoco 這個物理模擬器。

第三個是聯合任務規劃（Combined-task planning），它跟物理推理沒什麼關係，但是跟機器人相關。它指在抽象層面用定性物理去找到定性的解，發現行為可執行後，就會用數字模型計算數值的解。

第四個是定性物理推理（Qualitative physical reasoning），這也是我主要在研究的領域。領域背景在此不多做介紹，大家感興趣可以去看一下 Davis 的這篇《物理推理調查》（Physical reasoning survey）。而我之前做的研究主要是把物理推理用到感知、運動、穩定性和解釋物理運動這些方面。比如下圖中我動了一下木塊，要找出到底動了哪一塊，就可以使用這個方法，推理出來所有有可能被動過的木塊。

研究過程中，我總結了一些方法論：

第一，給定一個問題，去設計一個好的定性表達方式，它需要要保證能涵蓋解，同時，該表達方式的解跟其他的有誤導的解應該是可區別的。

第二，表達方式會形成一個約束網路，在這個網路上進行推理，就能拿到一套定性的解，但是解還是太模糊。

第三，在被縮減的解空間進行數值計算，最終得到具體的解。

第四，得到解之後，還需要根據在現實環境中的反饋對模型進行更改。

為了鼓勵世界範圍內的研究者一起研究該領域，我們 2012 年開始舉辦 AI Birds 國際人工智慧比賽。

我們會提前幾天去設置遊戲關卡，關卡中就涉及到物理推理的因素。此外，我們還做了一套伺服器，所有的 AI 都部署在獨立的筆記本上，AI 只能從伺服器獲得遊戲截圖。而遊戲動作包括發射小鳥，以及點擊屏幕觸發小鳥的技能。

六年以來，共有三十幾個國家的四十幾個參賽隊伍參與比賽，其中表現最佳的幾個參賽隊伍使用的方法包括：

邏輯編程（Logic programming）：用符號化的語言描述場景再進行符號化的推理，找出獲勝策略。

調試法（Heuristics-based）：其中一個韓國隊伍使用的調參方法，最後調的參數非常好，取得了不錯的成績。

模擬（Simulation）：因為遊戲的物理引擎是不被公布的，參賽隊伍是不知道參數的，因此有一些參賽隊伍自己用 Box2D 寫了一個類似的環境，通過自己的模擬去玩，但是因為遊戲中 Action 的可能性非常多，他們無法很有效的找到最佳 Action。

機器學習（Machine learning）：2012/2013 年的時候深度學習還沒有起飛，大家普遍使用經典機器學習方法。

至今所有的參賽選手的 AI 都是貪心的（greedy-based），意思是說他們在當前時刻只做對當前最有益的事情。例如，面對圖中的關卡，貪心的演算法會採用獲得當前最高得分的方法，即盡量多的破壞當前障礙物。但是藍色的冰一旦被打掉，就會掉下來堵住路，使他們最終無法打到豬。而可取的方式是，他們可以放棄掉藍色的小鳥，用黃色的小鳥打掉木頭，再打掉豬。

我們這個比賽明年會在澳門舉行，歡迎大家參加。

在 ANU 的物理推理研究組，主要做三件事情：

感知：從多個視圖的照片中，找出真正的結構。

知識表示和推理：例如我一個師弟 2018 年發表論文講怎麼統一空間表達法；我近一年則關注在 3D 空間中做一些理論去描述空間物理運動。

物理、空間規劃：比如堆盤子的實驗。

重點說一下我目前所在公司 Dorabot 的研究和開發。我是演算法研究負責人，下面為四個我認為比較有意思的方向：

第一個方向，對機器人進行形式化驗證。我們將一套空間表達方法邏輯化，對機器人進行驗證，以保證機器人不會做出異常行為。

第二個方向，多機器人協作。比如，探索機器人怎麼從類型不同感測器的輸入找出它們所處世界的真實樣貌，實現機器人本地協作，以及在 2D 模擬都是元胞機（圖靈完全）的情況下，怎麼解決 3D 環境中多機器人的模擬、規劃和協作等問題。

第三個方向，感知問題。包括從原始點雲檢測空間實體，比如機器人洗盤子，看到廚房一堆碗，需要分清哪個是盤子，哪個是抹布，這就需要使用深度感知器去觀察點雲；以及通過實質性空間變化去跟蹤空間實體。

第四個方向，規劃。比如對將箱子裝入集裝箱、拖車或輪船等地方的動作進行規劃，以及對靜態和動態穩定性的考量。

上面四個方向都是我們公司在研發的問題，感興趣的同學可以加入我們這個演算法團隊。

另外我們公司急需以下崗位，歡迎大家的加入。