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

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

關(guān)鍵詞：家庭仿真；機器人；任務(wù)規(guī)劃；人機交互；信息獲取

中圖分類號：TP242 文獻標(biāo)識碼：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

近年來隨著機器人工業(yè)應(yīng)用的普及，家庭服務(wù)機器人也逐漸成為了機器人研究領(lǐng)域的熱點，

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

1家庭機器人仿真

家庭機器人仿真基于一個3D機器人，針對這個機器人在一個模擬現(xiàn)實世界中的室內(nèi)環(huán)境來放置一系列的物體，設(shè)置一系列的任務(wù)。機器人有九種原子動作來實現(xiàn)九種物理行動，通過這九種物理行動，可以來給定的環(huán)境中完成各種任務(wù)。機器人設(shè)定有一個手爪和一個盤子，可以任意移動一個位置，所有物體的坐標(biāo)是一維的。手爪一次只能抓一個物體，盤子一次只能放一個物體。機器人可以詢問系統(tǒng)物體的位置，也可以自己感知當(dāng)前坐標(biāo)下的所有物體的集合。可以看出，機器人完成一個任務(wù)會有多種解法。

家庭服務(wù)機器人仿真項目比賽所有任務(wù)的評分標(biāo)準(zhǔn)為[3]：

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

2問題描述

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

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

3任務(wù)最優(yōu)規(guī)劃

3.1任務(wù)序列

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

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

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

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

需要執(zhí)行的任務(wù)的優(yōu)先級可以根據(jù)一個簡單的規(guī)則來設(shè)定：機器人在執(zhí)行下一任務(wù)時不能對已完成的任務(wù)造成破壞。機器人在執(zhí)行下一任務(wù)時盡可能使機器人手上為空。

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

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

給出每個任務(wù)的執(zhí)行次序，之后就可以具體處理每個任務(wù)了。

3.2預(yù)處理

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

3.2.1任務(wù)分組

假設(shè)場景信息中有以下描述：

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

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

任務(wù)信息中有以下描述：

（：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）））

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

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

對于putdown、goto這兩種任務(wù)要單獨處理。這就相當(dāng)于設(shè)定了四個優(yōu)先級，putdown的任務(wù)優(yōu)先級最高，有對小物體進行描述的一組任務(wù)優(yōu)先級第二，另一組的任務(wù)優(yōu)先級第三， goto的任務(wù)優(yōu)先級最低。

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

3.3人機交互

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

3.3.1重復(fù)詢問

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

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

3.3.2移動感知

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

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

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

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

3.3.3詢問感知

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

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

由概率統(tǒng)計隨機變量及其分布公式：P（n）=1-（1-p）^n（p為正確概率）算出概率。基于這樣的策略得出概率折線圖如圖2：

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

4 結(jié)語

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

參考文獻：

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

[2]XiaopingChen，JianminJi，JiehuiJiang， GuoqiangJin，F(xiàn)engWang，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] 家庭機器人仿真比賽規(guī)則2013：15-16. http：//www.wrighteagle.org/homesimulatin

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

[5] 吉建民. 提高ASP效率的若干途徑及服務(wù)機器人上應(yīng)用[D].中國科學(xué)技術(shù)大學(xué)，2010.

[6] 李星. 服務(wù)機器人仿真系統(tǒng)的動作序列規(guī)劃研究[D]. 安徽大學(xué)，2012.

[7] 王孝貴. 仿真服務(wù)機器人任務(wù)規(guī)劃研究[D]. 安徽大學(xué)，2013.

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

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