基于認知結(jié)構(gòu)SOAR的機器人路徑規(guī)劃

穆 楊

（海軍航空大學，遼寧葫蘆島125000）

實時避障及路徑規(guī)劃是自主移動機器人的核心技術，隨著機器人應用環(huán)境的復雜化，對這2項核心技術的要求也越來越高。根據(jù)環(huán)境及任務的復雜性，可以將研究背景劃分為以下4個等級：

1）環(huán)境已知、靜態(tài)、目標位置已知；

2）環(huán)境未知、靜態(tài)、目標位置已知；

3）環(huán)境未知、動態(tài)、目標位置已知；

4）環(huán)境未知、動態(tài)、目標位置未知。

當前，國內(nèi)研究主要集中在第一等級的全局規(guī)劃中[1-3]，而隨著環(huán)境的逐步惡劣，預載地圖由于精度及范圍等原因并不能夠提供足夠的信息[4-5]，而且當環(huán)境變化時，原規(guī)劃路徑很可能被障礙物截斷，導致采用原來規(guī)劃的路徑移動時，可能陷入陷阱或者發(fā)生無法到達目標位置的問題。所以，在其他3個等級的態(tài)勢下，機器人還須要具有局部規(guī)劃能力，使用傳感器探測到的信息控制機器人避免碰撞障礙物[6-7]。本文引入認知結(jié)構(gòu)SOAR，通過Visual SOAR開發(fā)環(huán)境設計SOAR-Agent控制機器人，模仿人在未知、動態(tài)環(huán)境下向已知的目標位置搜索路徑的行為，實現(xiàn)了在第三等級態(tài)勢下的路徑規(guī)劃能力。

1 SOAR的概念及基本原理

隨著人工智能技術的發(fā)展，為了彌補智能設計只能應用于設計好的領域的限制[8]，國外諸多學者于90年代開展了認知結(jié)構(gòu)的研究[9]。認知結(jié)構(gòu)旨在開發(fā)一種通用的架構(gòu)[10]，通過合理的設計，使開發(fā)的系統(tǒng)具有人的相同的認知能力，實現(xiàn)人級智能體（Human-level Agents）[11]。在之后的20多年的研究中，先后涌現(xiàn)出了諸 如 SOAR[12]、ACT-R[13]、EPIC[14]、Clarion[15]、SAL[16]、Icarus[17]等認知結(jié)構(gòu)。

SOAR是由Newell等人于1983年開發(fā)出來的一種認知結(jié)構(gòu)，它是State，Operator，Act and Result的縮寫，譯為狀態(tài)、操作、行動和結(jié)果。簡單地說，就是選擇操作，作用環(huán)境，改變狀態(tài)，從而產(chǎn)生相應的結(jié)果。經(jīng)過20多年的發(fā)展，SOAR在計算機生成兵力[18]，無人機任務規(guī)劃[19]等方面取得了諸多成果。以下結(jié)合圖1所示的箱子移動問題介紹SOAR的基本概念及其求解機制。

箱子移動問題，即將隨機放置的3個方塊按照期望狀態(tài)順序排列，每次只能移動1個方塊，期望狀態(tài)如圖1所示。

圖1 箱子移動的問題空間Fig.1 Problem space of box moving

1.1 基于問題空間的求解機制

從箱子的初始狀態(tài)轉(zhuǎn)換到箱子的期望狀態(tài)過程中，存在許多其他狀態(tài)，這些狀態(tài)構(gòu)成了箱子移動問題的“問題空間”。

1）問題空間[13]（Problem Space）：當前狀態(tài)到目標狀態(tài)轉(zhuǎn)換過程中，所有可能出現(xiàn)狀態(tài)的集合以及使狀態(tài)改變對應的操作。對于箱子移動問題，問題空間包括了箱子所有位置狀態(tài)的組合，如圖1中的S1～S5、G1、O1～O7。

2）狀態(tài)（State）。當前世界信息：對于箱子移動問題，狀態(tài)包含了箱子當前的位置信息。如圖1中D1下的S1、D2下的S2等。

3）操作（Operator）：控制狀態(tài)向目標轉(zhuǎn)化。操作包括前提條件及相應的行為，可對操作進行評估，設置優(yōu)先度（Preference），控制操作的選擇。對于箱子移動問題，操作包含了對箱子的移動。如圖1中的O1～O7。

4）短期知識（Working Memory，WM）：用于存儲各種臨時信息，包括當前的環(huán)境信息、當前的操作、當前的目標。

5）長期知識（Long Term Memory，LTM）：用于存儲規(guī)則等信息，長期知識只有通過操作才可以更改。

6）困境（Impasse）：基于問題空間的求解機制在求解過程中會出現(xiàn)以下4種困境，如表1所示。

表1 困境類型Tab.1 Impasse types

針對以上4種困境，SOAR通過在短期知識中創(chuàng)建子狀態(tài)（Substate），并在子狀態(tài)中創(chuàng)建新的問題空間去解決困境。具體解決方法如表2所示。

表2 困境解決方案Tab.2 Solution of impasse

1.2 基于經(jīng)驗的試錯學習機制——經(jīng)驗學習

多個操作可選以及操作存在沖突的解決方案是通過采用復制上一層狀態(tài)，在子狀態(tài)的問題空間中使用向前搜索策略，重新對操作進行評估，對比人的行為方式，當已有規(guī)則無法判斷哪一種決策更合適時，人通常是對決策的下一狀態(tài)進行評估，最優(yōu)解即能使狀態(tài)更接近目標的決策。通過采用向前搜索策略，人可以對決策進行評估，將評估結(jié)果及環(huán)境信息存儲在記憶中，在將來碰到相同情況下，直接使用，避免二次推理。Newell等學者通過引入實踐法則[20]設計了基于經(jīng)驗的試錯學習機制——經(jīng)驗學習，實現(xiàn)了相同的能力，從而使在子狀態(tài)的問題空間中推理得到的規(guī)則能夠作為長期知識直接使用。

1.3 基于強化學習的學習機制

在加入了chunking功能之后，利用SOAR開發(fā)的agent具備一定的學習能力，但是，該學習能力是建立在外部環(huán)境不變的前提下，當外部環(huán)境出現(xiàn)變化，chunking習得的知識以及已有的規(guī)則知識顯然不再正確。為了能夠調(diào)整已有的知識以應對變化的態(tài)勢，SOAR加入了如圖2所示的基于強化學習（Reinforcement Learning，RL）的學習機制[21]，即通過對能夠到達目標的一系列操作給予獎勵，并將獎勵信息作為知識的一部分，從而使SOAR開發(fā)的agent能夠在行動—評價的模式中改變操作優(yōu)先度以適應充滿噪聲、變化的動態(tài)環(huán)境。

圖2 基于強化學習的學習機制Fig.2 Learning mechanism based on reinforcement learning

2 基于SOAR-Agent的行為建模方法

由于在未知的、動態(tài)環(huán)境下無法使用任務先驗信息，從而無法使用任何算法對全局路徑進行規(guī)劃。為了保證機器人在不觸碰障礙物的前提下，同時實現(xiàn)到達目標位置的目的，本文通過使用認知結(jié)構(gòu)SOAR開發(fā)agent，模擬人在此環(huán)境下的行為方式，使機器人具有人的思考能力，從而能夠應對動態(tài)的未知環(huán)境。首先對人的行為模型進行分析。

2.1 人的行為模型

Rasmussen等人在分析了人類行為模型當中不同元素之間的區(qū)別及聯(lián)系基礎上，總結(jié)出行為的3個層級[22]，如圖3所示。

圖3 人的行為模型Fig.3 Model of human behavior

1）基于本能層級。該層級，人是基于本能對外界做出反應，是未經(jīng)思考的。例如，開車時，車前突然出現(xiàn)一只動物，沒有經(jīng)驗的駕駛員通常會立即打方向盤以趨避（結(jié)果非常危險）。

2）基于規(guī)則層級。人通過感知器官獲取外界信息，部分信息能夠直接轉(zhuǎn)換成可以識別的符號，被識別之后，結(jié)合當前任務或是狀態(tài)，將之與記憶當中類似問題相關聯(lián)，確定是否有明確的行動規(guī)則，最后尋找到相應的反應行為。

3）基于知識層級。人在面對未知事物時，外界信息只是具有象征意義的符號，記憶當中不包含相應規(guī)則。此時，需要利用已有知識結(jié)合所要達到的目標進行推理并找到正確的答案。這一層級是人類行為的最高層級。

2.2 SOAR的決策過程

SOAR的決策過程如圖4所示。具體分析如下：

1）信息輸入。使用SOAR設計的agent可以通過輸入鏈接（input-link）動態(tài)的獲取諸如傳感器探測到的外部信息，將這部分信息存儲在WM中。

2）狀態(tài)細化、操作建議、操作評估。狀態(tài)細化（Elaborate State）復制外部信息，通過與LTM中的長期知識比對產(chǎn)生環(huán)境的理解知識；操作建議根據(jù)當前的環(huán)境知識，給出符合條件的操作，并將這些操作存儲在WM中；操作評估通過比較備選操作，設置優(yōu)先度。

3）決策。根據(jù)備選操作的優(yōu)先度決定操作的選擇。此時，可能會出現(xiàn)困境，產(chǎn)生子狀態(tài)，重新執(zhí)行步驟2）。

4）操作細化。在步驟2）中只給出了符合條件的操作，如需對其動作進行修改，可以在操作細化階段重新設計。

5）操作執(zhí)行。操作指令寫入WM中，將操作對應的動作作用于內(nèi)部狀態(tài)，如果存在對外部環(huán)境的作用，則將操作指令傳至輸出鏈接（output-link）中。由于環(huán)境的改變可能需要時間，從而需要重復執(zhí)行操作。如果當前給出的操作過于抽象，需要重新執(zhí)行步驟4），將操作分解成外部執(zhí)行機構(gòu)能夠執(zhí)行的動作。

6）輸出。執(zhí)行輸出指令，作用于外部環(huán)境。

7）目標狀態(tài)識別。目標狀態(tài)知識隱含在長期知識中，所以目標狀態(tài)識別需要通過與環(huán)境知識區(qū)配，使用相應的操作判斷，然后終止整個過程。

圖4 SOAR的決策過程Fig.4 Decision process of SOAR

2.3 基于SOAR-Agent的行為建模方法

對比人的行為模型和SOAR的決策過程可以發(fā)現(xiàn)，通過將感知到的外界信息以及內(nèi)部產(chǎn)生的操作信息存儲在agent的短期知識中，設計長期知識庫（特征知識、任務知識、目標知識、規(guī)劃知識），利用SOAR的基于問題空間的求解機制，對相關任務及目標進行推理，從而實現(xiàn)模擬人的行為能力，進而應用到機器人的路徑規(guī)劃當中，具體設計如圖5所示。

圖5 基于SOAR-Agent的行為建模方法Fig.5 Behavior modeling based on SOAR-Agent

3 仿真實驗分析

3.1 環(huán)境描述

為了驗證本方法的有效性，采用文獻[23]中的柵格模型地圖，同時增加地圖難度，其中一個障礙物能夠向左移動2個單位距離，從而影響機器人的行進路線，機器人能夠感知周圍一個單位距離的信息，如圖6所示。

圖6 避障地圖Fig.6 Avoidance map

3.2 長期知識設計

長期知識設計體現(xiàn)了任務的描述程度以及人的行為方式、人對外界環(huán)境的認知。本文通過設計2組長期知識以體現(xiàn)不同長期知識的設計對機器人的影響。

第1組：

1）特征知識。黑色物體是障礙物。

2）任務知識、目標知識。本實驗任務知識和目標知識一致，在不觸碰障礙物的前提下到達F點。

3）規(guī)劃知識。規(guī)劃知識控制著操作的選擇，具體設計如表3所示。

表3 規(guī)劃知識（1）Tab.3 Planning knowledge（1）

第2組：

特征知識、任務知識、目標知識不變，規(guī)劃知識設計如表4所示。

表4 規(guī)劃知識（2）Tab.4 Planning knowledge（2）

3.3 仿真實驗分析

使用Visual SOAR開發(fā)環(huán)境設計SOAR-Agent，寫入上述長期知識，在Visual C++環(huán)境下設計地圖，作為外部環(huán)境，并使用SOAR Debugger軟件觀察SOARAgent的決策過程以及其與外界環(huán)境的交互過程。第1組長期知識設計下的運動軌跡如圖6中的實線所示，但是，當移動障礙向左運動一個單位之后，形成了U型陷阱，此時，機器人無法逃離，當障礙物向右移動至原位時，機器人才能繼續(xù)前進。第2組長期知識設計下的運動軌跡如圖6中的虛線①所示，實驗結(jié)果表明，機器人可以應對動態(tài)的未知環(huán)境，并從U型陷阱中逃離，但是，該路線并不是全局最優(yōu)的，最優(yōu)路徑如圖6中的虛線②所示。

從實驗結(jié)果可以看出，通過預先載入的認知模型（長期知識）進行路徑探索，符合人在未知環(huán)境下探索路徑的認知規(guī)律。在未知且變化的環(huán)境中，依然可以尋找到通往目標的路徑。與傳統(tǒng)路徑規(guī)劃研究方法（基于A*[23]搜索算法、遺傳算法[24]、蟻群算法[25]、深度學習[26]等算法的路徑規(guī)劃）不同的是，該方法是將人思考問題的機制引入到路徑規(guī)劃中，即根據(jù)當前狀態(tài)（環(huán)境），在可選方案中選擇最佳方案行動，行動作用于環(huán)境，改變當前狀態(tài)，在未到達目的地之前，按照長期知識繼續(xù)行動。而傳統(tǒng)研究方法的重點是設計模型及相關函數(shù)，且需要進行多次訓練，而且當環(huán)境變化時，需要對模型進行重新訓練，如果環(huán)境持續(xù)變化，則不能采用傳統(tǒng)算法，而本文提出的方法能夠彌補傳統(tǒng)方法的缺點，實現(xiàn)在環(huán)境持續(xù)變化情況下的路徑規(guī)劃。

4 結(jié)論

本文提出了一種基于認知結(jié)構(gòu)SOAR的機器人路徑規(guī)劃方法。與傳統(tǒng)方法相比，該方法的優(yōu)點在于能夠讓機器人模擬人的行為，通過預先載入的認知模型（長期知識）進行路徑探索，在改進規(guī)則之后，能夠處理變化環(huán)境下的路徑選擇。從仿真實驗結(jié)果可以看出，由于沒有任何先驗信息，機器人無法找到最優(yōu)路徑。但是，隨著地圖信息的逐漸完備，可以先采用傳統(tǒng)的全局規(guī)劃方法，在找到全局最優(yōu)路徑，并將其離散化為多個航路點的基礎上，結(jié)合本文提出的方法，實現(xiàn)機器人向下一航路點移動同時避開動態(tài)的障礙物。同時，可以加入chunking功能，設計強化學習機制，提高機器人探索環(huán)境的速度，這也是下一步工作的重點。