基于任務規劃的家庭仿真服務機器人的研究

章偉++蔡亞楠++楊為民

摘要：隨著智能產業的發展，家庭服務機器人越來越多的進入人們的視野。家庭服務機器人研究中兩個比較核心的問題是，機器人的任務規劃和人機交互。針對于一般的搜索算法會形成組合爆炸，難以求解的問題，本文提出一種任務拆分方法解決任務規劃的問題。并基于詢問和感知提出兩種處理人機交互的方法。通過應用在家庭服務機器人仿真平臺上取得的良好效果，證明該算法有效。

關鍵詞：家庭仿真；機器人；任務規劃；人機交互；信息獲取

中圖分類號：TP242 文獻標識碼：A 文章編號：1009-3044（2016）17-0188-04

Abstract： With the development of the intelligent industry， the home service robot gradually come into the people's eyes. For home service robots， the two core issues are robot task planning and human-computer interaction. For the problem that the general algorithm will cause the combination explosion and it is difficult to solve， this paper puts forward a method to solve task planning problem by the task resolution. Then puts forward two king of methods to solve human-computer interaction based on query and perception. Through the experiment applied in the simulation home service robots's platform， the result shows that this algorithm can solve the problem well.

Key words： family simulation， robot， mission planning， human computer interaction， information acquisition

近年來隨著機器人工業應用的普及，家庭服務機器人也逐漸成為了機器人研究領域的熱點，

這個領域的成果有助于解決中國人口老齡化，大量老人無人照顧的問題[1] 。為了推廣和發展家庭服務機器人的研究，RoboCup世界杯于2006年增加了家庭服務機器人的比賽。目前國內外已有很多一流大學開始了研究和競賽，在國內以中國科技大學的“可佳”服務機器人為代表。為了促進家庭仿真服務機器人的發展，2009年，由中國科學技術大學首次舉辦了家庭服務機器人仿真項目比賽，主要是模擬機器人和機器人所可能會處于的環境，致力于研究服務機器人的高層功能，包括機器人的人機對話、對任務的自動規劃和自動推理等[2]。由于仿真項目不涉及硬件，所以在很大程度上減少了研究的限制，加速了服務機器人的發展，有利于服務機器人的推廣和研究。對于服務機器人競賽也有很大的幫助。

1家庭機器人仿真

家庭機器人仿真基于一個3D機器人，針對這個機器人在一個模擬現實世界中的室內環境來放置一系列的物體，設置一系列的任務。機器人有九種原子動作來實現九種物理行動，通過這九種物理行動，可以來給定的環境中完成各種任務。機器人設定有一個手爪和一個盤子，可以任意移動一個位置，所有物體的坐標是一維的。手爪一次只能抓一個物體，盤子一次只能放一個物體。機器人可以詢問系統物體的位置，也可以自己感知當前坐標下的所有物體的集合?？梢钥闯?，機器人完成一個任務會有多種解法。

家庭服務機器人仿真項目比賽所有任務的評分標準為[3]：

仿真服務機器人運行于Challenge Server平臺上，由server向client發送場景信息和任務描述信息，client提取并處理信息發回server，server接收到處理的結果，給出判定的分數。Client端程序即為參賽的程序，通過server提供的接口來運行平臺。

2問題描述

在實際處理場景中會同時處理多個任務，研究的目的是如何能夠用最少的動作完成盡可能多的任務。在人工智能中描述為：從一個狀態通過一系列盡可能花費較少的原子行動到達最終狀態。圖（1）為其狀態空間分解圖：

針對任務規劃問題，已經涌現出幾種策略，例如中山大學的A*算法，廣東工業大學的文化算法[4]，中國科學技術大學的回答集編程[5]，以及安徽大學也曾采用A*算法[6][7]。這些算法都屬于啟發式搜索，類似于遺傳算法，都是利用搜索給出的原子行動，進行不斷試探，尋找一個最短的動作序列來完成狀態的轉換，并通過一定的約束條件簡化計算得出一個最優序列再去執行。這些算法對于任務數較少的時候有著精確的序列和路徑規劃，隨著任務數的增多會組合出非常復雜的序列，難以在規定時間內給出解，在此稱之為“組合爆炸”。隨著家庭仿真server版本的不斷更新，任務數逐漸增多，對時間的要求也越來越嚴格。對于需要實時完成的動作序列，大量的計算根本無法在規定的時間（目前為5秒）之內計算出最優路徑。

3任務最優規劃

3.1任務序列

為了解決組合爆炸所帶來的復雜性難以求解的問題，提出一種將任務分成單個任務，逐一完成的方法。在文獻[8]中，多機器人行為序列也比較復雜，但是通過將行為拆分單個機器人，研究其行動序列，再將其組合為多機器人行為，可以大大簡化機器人的行動序列復雜度[8]。類比于單機器人多任務，對于單個任務手算即可產生最佳解法，也可以大大降低了求解難度。這種方法帶來的另一個好處就是任務可以實時處理，即使得不出總體最優解，也可以在計算的過程中，解決已經計算出的任務，而不會一直計算無法給出解。并且由于任務描述基本都是每次給出一條任務，因此只需按照其給出的描述拆成單一的任務即可，對于同時給出兩條的任務，可以拆成兩條描述語句。

然而任務拆分也會帶來缺點，即任務拆分之后會大大降低全局的可靠性。在執行任務的過程中由于多個任務可能涉及操作同一個物體，而系統判斷有沒有完成任務是依據最終每個物體的狀態，因此經常會出現一個任務將另一個任務破壞了的情況，達不到最終期望的狀態。例如如下任務：1.Close A，2.Takeout B from A。若先執行任務1在執行任務2，任務2要從A里拿出B物體，肯定要把A的門打開才能完成任務2，。執行完1，2后系統判斷最后的狀態，只完成了任務2，任務1沒有完成。

針對任務拆分帶來的缺點，通過分析實驗各個任務和場景之間的聯系，將拆分過后的任務進行排序，增大全局可靠性，給出一個最好的動作序列，保證每個任務都不會被其后的任務破壞。這樣既可以解決“組合爆炸”的問題，又可以保證完成每個任務，達到實時給出最優解的目的。排序需要一個好的規則，對于各種不同的場景需要得出一個統一的規律，下面給出試驗中所得的規律及優先級設置的思路。

在設置優先級的時候將info設置為最高優先級，這是比較好的一種方式，因為info的信息是確定的，將其解析可以把信息放入初始狀態中，這樣就可以增加所知道的信息。對于維護任務consnot和consnotnot為第二優先級，維護任務的狀態是已經確定的，不可以被破壞掉，因此將次物體的id存到一個單獨的集合，在任務搜索的時候搜索不到這些物體，可以保證狀態不被破壞。剩下的就是需要執行的任務，為了最快的完成的每個任務而不會將其他任務的狀態破壞，采用給每個任務設置不同的優先級方法來完成。

需要執行的任務的優先級可以根據一個簡單的規則來設定：機器人在執行下一任務時不能對已完成的任務造成破壞。機器人在執行下一任務時盡可能使機器人手上為空。

經過大量的測試分析，對于goto應該放到最后來做，因為若goto后有任務，必定會移動到其他地方，則此任務失敗。對于pickup放在倒數第二個，此后不需要再操作物體，因此手里的物體不會放下。其他任務依次分析，一些需要對容器操作的動作優先級最高，對于open優先級其次，其后是close，再是puton?？紤]到涉及容器的操作，應該先開門后關門，對于give放在close之后。

經過以上分析，和實際實驗測試得出一個高效的動作序列如下：

給出每個任務的執行次序，之后就可以具體處理每個任務了。

3.2預處理

對任務描述進行預處理，可以任務進行解析、提取出有用信息：要執行什么動作、要對哪些物體進行操作。經過預處理之后，仿真機器人的執行效率能得到很大的提升。但僅僅是這樣簡單的預處理并不能順利完成所有的任務。在家庭仿真服務機器人比賽的中，一個任務文檔內的兩個不同任務之間可能并不完全的獨立，而是在執行完一個任務后會對已完成的任務造成破壞。在家庭仿真服務機器人比賽中，導致這種情況發生的大部分原因是機器人在執行不同任務時處理的是同一小物體[9]。

3.2.1任務分組

假設場景信息中有以下描述：

（sort 12 book） （size 12 small） （color 12 black）

（sort 13 book） （size 13 small） （color 13 green）

任務信息中有以下描述：

（：task （putin X Y） （：cond （sort X book） （sort Y closet）））

（：task （puton X Y） （：cond （sort X book） （color X black） （sort Y table）））

按照之前設定的動作序列，先執行putin任務，在執行puton任務。但是在實際過程中，若搜索函數每次都是順序搜索，在執行兩個任務時，搜索到的均是black book。顯然，執行完puton任務之后把之前執行過的putin任務給破壞掉了。此時對任務進行預處理可以有效解決此問題。

可以看到，putin中的有效信息為（putin X Y）、（sort X book）、（sort Y closet），有效信息數為3。puton中的有效信息為（puton X Y）、 （sort X book）、（color X black） （sort Y table），有效信息數為4。兩組信息之間僅僅是差了一條關于小物體的描述信息。這樣就可以在執行任務之前先將所要處理的任務分成兩組。將任務信息中有對小物體進行描述的任務分成一組并優先處理這一組的任務，將任務信息中沒有對小物體進行描述的任務分成另一組，執行每組的任務時同樣是按照之前設定的動作序列依次執行。

對于putdown、goto這兩種任務要單獨處理。這就相當于設定了四個優先級，putdown的任務優先級最高，有對小物體進行描述的一組任務優先級第二，另一組的任務優先級第三， goto的任務優先級最低。

通過這種簡單的分組排序來對任務優先級進行劃分，這樣在合理的安排任務執行順序就可以得到最優的任務規劃。這樣處理起來簡單有效，基本可以保證每個任務都能完成。

3.3人機交互

在家庭仿真機器人的比賽中，比賽第二階段所給的任務文檔里給出的任務場景是不完整的，還有錯誤的，需要智能體機器人去問系統或感知周圍環境來獲取任務所需的正確信息。但是通過詢問系統所給出的答案只有60%的正確率，感知周圍環境得到的信息則是100%正確。根據正確的信息才能進行任務的正確的規劃。下面提出三種人機交互的方式，經過實驗均為可行策略。

3.3.1重復詢問

在處理任務時，為了順利完成任務，必須獲取正確的信息。對于未知物體的位置的獲取，重復詢問可以算是最簡單的一種策略了。在家庭仿真服務機器人第二階段的比賽中，通過AskLoc動作詢問系統得到的信息只有60%的正確率，錯誤為30%，不知道為10%。不知道不算在內，實際上正確率為66.6%，錯誤率為33.3%。根據伯努利概型，二項概率公式，可以計算出得到n次之內對的概率。二項概率公式如下：

其中p為正確概率，q為錯誤概率。在考慮AskLoc動作所花的代價，每次詢問都會扣除2分，而完成一個任務得40分。所以，重復詢問策略一般是：詢問系統三次，將兩次或兩次以上的相同的信息視為正確信息。通過這種策略最后得到的信息有74.07%的概率為正確信息。

3.3.2移動感知

通過重復詢問得到的信息的正確率始終達不到100%。而通過sense動作感知周圍環境所得到的信息能保證是100%正確的。這時，就可以將Move動作與Sense動作交替使用，從而得到任務所需的正確信息。再判斷Sense得到的信息中是否有需要的信息，如果有，則繼續往下執行任務；如果沒有，則移動到下一位置，再次感知當前位置上的所有物品信息，直到找到所需信息。

很顯然，這種策略在足夠大的代價下是能夠可以找到所有物品的位置信息。但是這種策略往往具有盲目性，它只是不斷從一個大物體的位置移動到另一個大物體的位置。很多情況快只移動一次是并不能找到所需的位置信息，需要繼續尋找下去，而如果這時整個任務中所需要小物體的位置信息只有一個，這樣所花的代價往往是過大的，甚至超過了重復詢問所花費的代價。

同時這種策略還會導致另一個問題：超時問題。由于一直沒有找到所需要的小物體，就會導致機器人在處理任務時超過了比賽規定的時間。

相對于重復詢問策略，在家庭仿真服務機器人比賽中，這種移動感知策略更佳被優先采用，而且在比賽中這種策略出現超時的情況也比較少。

3.3.3詢問感知

在家庭仿真服務機器人比賽的第二階段中，除了要處理任務文檔中的缺失信息外，還要處理文檔中給出的錯誤信息。這時可以考慮使用比賽平臺提供的AskLoc（）和Sense（）函數一起配合使用。

將每次AskLoc得到的有效信息都當做正確信息使用，這時得到的信息的正確率為66.6%。然后繼續處理任務。在執行任務時，無論是因為之前到的信息錯誤還是任務文檔中的錯誤場景描述導致平臺返回“false”信息，都可以使用Sense動作來更新得到的物體位置信息。然后重新執行AskLoc動作獲取有效信息，重復之前的過程直到任務完成。

由概率統計隨機變量及其分布公式：P（n）=1-（1-p）^n（p為正確概率）算出概率?；谶@樣的策略得出概率折線圖如圖2：

根據圖2（其中橫坐標為詢問次數，縱坐標為理論正確概率）可以看出，這種策略通過兩次AskLoc動作得到正確信息的概率要比重復詢問三次得到的正確信息的概率要高得多，理論上三次詢問就能得到正確信息了。

4 結語

在家庭服務仿真機器人的比賽中，機器人到每一個坐標的代價是相等的。因此給出的最優任務序列是實驗和分析得出的，只能是在大部分情況下最優，在某些情境下不一定是最優序列。一個正確信息的獲取是整個任務規劃的基礎，如何快速高效的獲取所需的正確信息將是提高提高任務規劃效率的關鍵方法。

參考文獻：

[1] 田國會，李曉磊，趙守鵬，等.家庭服務機器人智能空間技術研究與進展[J].山東大學學報：工學版，2007，37（5）：53-59.

[2]XiaopingChen，JianminJi，JiehuiJiang， GuoqiangJin，FengWang，JiongkunXie.Developing High-level Cognitive Functions for Service Robots， In： Proc. of 9th Int. Conf. on Autonomous Agents and Multi-agent Systems （AAMAS 2010）， Toronto， Canada， May 2010.， 2012，2（1）： 100-117.

[3] 家庭機器人仿真比賽規則2013：15-16. http：//www.wrighteagle.org/homesimulatin

[4] 陳樹斌，陳瑋，李劍平. 基于文化算法的家庭服務機器人任務規劃[J].計算機工程與應用，2012，48（33）：212-216.

[5] 吉建民. 提高ASP效率的若干途徑及服務機器人上應用[D].中國科學技術大學，2010.

[6] 李星. 服務機器人仿真系統的動作序列規劃研究[D]. 安徽大學，2012.

[7] 王孝貴. 仿真服務機器人任務規劃研究[D]. 安徽大學，2013.

[8] 余婷，梁阿磊.基于局部行為序列的多機器人曲線移動技術[J].計算機應用與軟件，2009，26（12）：40-43.

[9]劉巖愷，薛毅.家庭仿真求解最優路徑問題算法研究，2006，11（6）：28-29.