基于任務(wù)規(guī)劃的家庭仿真服務(wù)機(jī)器人的研究

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

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

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

中圖分類號(hào)：TP242 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

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

1家庭機(jī)器人仿真

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

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

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

2問題描述

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

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

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

3.1任務(wù)序列

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

然而任務(wù)拆分也會(huì)帶來缺點(diǎn)，即任務(wù)拆分之后會(huì)大大降低全局的可靠性。在執(zhí)行任務(wù)的過程中由于多個(gè)任務(wù)可能涉及操作同一個(gè)物體，而系統(tǒng)判斷有沒有完成任務(wù)是依據(jù)最終每個(gè)物體的狀態(tài)，因此經(jīng)常會(huì)出現(xiàn)一個(gè)任務(wù)將另一個(gè)任務(wù)破壞了的情況，達(dá)不到最終期望的狀態(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沒有完成。

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

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

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

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

經(jīng)過以上分析，和實(shí)際實(shí)驗(yàn)測(cè)試得出一個(gè)高效的動(dòng)作序列如下：

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

3.2預(yù)處理

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

3.2.1任務(wù)分組

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

（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è)定的動(dòng)作序列，先執(zhí)行putin任務(wù)，在執(zhí)行puton任務(wù)。但是在實(shí)際過程中，若搜索函數(shù)每次都是順序搜索，在執(zhí)行兩個(gè)任務(wù)時(shí)，搜索到的均是black book。顯然，執(zhí)行完puton任務(wù)之后把之前執(zhí)行過的putin任務(wù)給破壞掉了。此時(shí)對(duì)任務(wù)進(jìn)行預(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ù)信息中有對(duì)小物體進(jìn)行描述的任務(wù)分成一組并優(yōu)先處理這一組的任務(wù)，將任務(wù)信息中沒有對(duì)小物體進(jìn)行描述的任務(wù)分成另一組，執(zhí)行每組的任務(wù)時(shí)同樣是按照之前設(shè)定的動(dòng)作序列依次執(zhí)行。

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

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

3.3人機(jī)交互

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

3.3.1重復(fù)詢問

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

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

3.3.2移動(dòng)感知

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

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

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

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

3.3.3詢問感知

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1] 田國(guó)會(huì)，李曉磊，趙守鵬，等.家庭服務(wù)機(jī)器人智能空間技術(shù)研究與進(jìn)展[J].山東大學(xué)學(xué)報(bào)：工學(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] 家庭機(jī)器人仿真比賽規(guī)則2013：15-16. http：//www.wrighteagle.org/homesimulatin

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

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

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

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

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

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