基于線性規劃的家庭仿真機器人的研究

常順 吳雪峰 劉向舉

摘要： 由于家庭仿真機器人比賽在第二階段場景信息中存在錯誤信息，導致常規算法難以實現且效果不佳。針對該問題提出線性規劃算法予以解決，首先，對不同種類任務進行優先級排序，采用混合人機交互方式糾正場景中的錯誤信息;其次，采用分而治之方法規劃每個任務，并根據場景進行優先級實時調整;最后，在Ubuntu16.04系統下進行大量實驗，結果表明我們所提方法能有效完成多任務規劃問題并可以準確糾正錯誤信息以完成任務。

關鍵詞：多任務規劃;人機交互;信息糾正;家庭仿真;機器人

中圖分類號：TP311? ? ?文獻標識碼：A

文章編號：1009-3044（2019）18-0183-04

隨著智能科技的發展，智能產品在人們生活中隨處可見，對其研究也是一種熱門，其中機器人的研究也是其中一項重要研究。現在各大高校也開始研究這個領域，其中一些高校也取得了一些成績。為了促進大學生也參與到這一項目中，全國乃至全世界也舉辦了很多的機器人比賽。在安徽，2009年中國科學技術大學首次舉辦了家庭仿真機器人比賽，主要針對自主機器人在家庭環境中的典型應用，主要研究人機交互、自動規劃、推理、環境感知和重新規劃。

在機器人的研究中，其中任務規劃部分一直是難點，而且在近些年來也有許多的算法應用到任務規劃中，比如：蟻群算法[1]、A*算法[2]、文化算法[4] 、遺傳算法[5]等。這些算法在場景全部為正確信息或者人機交互結果全為正確位置結果時，使用起來效果較好，這些算法對任務進行規劃，可以很好地完成任務并且損耗比較小。但是現在存在的問題是：在中國科學技術大學舉辦的家庭仿真機器人比賽中，第二階段的比賽場景不僅有錯誤信息而且人機交互返回的結果也不一定正確，這樣在使用上面的算法就會出現嚴重的錯誤。因為在上面的算法中，對動作結點進行規劃時需要的信息是正確的，這樣就會出錯。

本文主要研究家庭仿真機器人比賽的第二階段的任務規劃，與第一階段不同的是在這個階段中所給的場景信息有可能出錯;以及人機交互中的詢問（askloc）有60%返回正確位置關系，30%返回錯誤位置關系，10%返回“not_know”。在這篇文章中，提出的線性規劃就可以很好地解決這個問題。通過對任務類型進行線性排序然后在逐一完成，再根據每個任務中的具體場景進行規劃，可以很好地解決這個問題。

1 家庭仿真機器人比賽

家庭仿真機器人比賽簡單說就是一個虛擬3D機器人在一個模擬環境下完成一些任務。完成任務需要做的動作有九個原子動作：move、pickup、putdown、toplate、fromplate、open、close、putin、takeout。機器人的設定為一只手一個盤子，手和盤子上只能放入一個小物體。

2 任務描述

在家庭仿真比賽中，任務種類有多種：give（human，A）、puton（A，B）、goto（A） 、putdown（A）、pickup（A）、open（A）、putin（A，B） 、close（A） 、takeout（A，B）。在任務種類中B表示大物體A表示小物體，機器人通過拿起小物體完成相應的任務要求獲得分數。在任務信息中不僅有任務信息，還有約束信息：not task，not info，not not info，維護約束是非常必要的。

本人主要研究這9中任務，使用線性規劃的方法規劃完成場景中的任務。任務的具體描述如下：1. give（human，A）是將小物體A移動到human的位置2. puton（A，B）將小物體A放到大物體B的位置3. goto（A） 是機器人移動到小物體A的位置4.putdown（A）將機器人手中或者盤子中的物體A放下5.pickup（A）使機器人拿起小物體A放在手中或者盤子中6.open（A）將容器A的門打開7.putin（A，B） 將小物體A放入容器B內部8.close（A） 將容器A的門關閉9.takeout（A，B）將小物體A從容器B中拿出。完成這寫種類任務，不能在場景結束之后的最終狀態破壞（就是物體最終狀態與任務描述相同），否則相當于沒有完成。在每個場景中，這9種任務含有其中的一部分或者全部，并且每種的任務數量可能不唯一，比如：

3 任務規劃

3.1 任務優先級調整

有許多算法可以完成多任務，比如：A*算法、進化算法、ASP、文化算法等。這里主要針對家庭仿真機器人比賽的第二階段，在場景信息中存在錯誤信息和缺失信息，以及人機交互時返回的信息并不全是正確位置信息，所以使用這些算法可能會出現許多異常問題。為了避免錯誤信息帶來困擾，提出一個算法：線性規劃，也就是將多個任務進行逐一完成，采取分而治之的方法。

將任務逐一完成雖然簡單，但是依然存在問題，比如：1. close（A） 2.putin（B，A）。在執行任務1之后，再執行任務2，任務2完成之后就默認這個場景的所有任務已經完成，繼續執行下一個場景，這樣就將任務1的場景破壞，在進行評分時就會判定任務1沒有完成。不僅僅沒有完成任務，而且執行了一系列動作，消耗了時間，帶來的損失較大。

為此，我們對任務優先級進行排序，盡量避免上述存在的問題。但是如何進行排序呢？需要明確在任務描述中存在的任務信息種類：task、info、cons。

在任務處理中info中的信息是對場景信息的補充，需要進行優先處理，因為在以后的任務中可能會需要到這些信息，所以將info類優先等級設置為第一等級。

在cons中，可能約束信息會和任務發生沖突，如1.not info|A on B 2.task|put A on B，這時如果以cons為主，經過計算雖然完成任務比約束多20分，但是減去原子動作、時間消耗、人機交互會損失更多的分數，所以將cons設為第二等級。

接下來是task信息，這里也是最重要的部分，任務的種類如下：give（human，A）， puton（A， B），goto（A）， putdown（A）， pickup（A）， open（A）， putin（A， B）， close（A）， takeout（A， B）。將這些任務類型進行優先級排序，顯而易見goto任務需要排在最后一個，優先級為9，如果將這個任務排在前面，在完成其他任務時，會破壞這個任務的完成情況，所以goto優先級必須為9;在執行任務之前首先需要處理機器人手中的物體（除非手中的物體和此任務直接相關），處理手中物體動作為putdown|toplate，所以處理手中的物體是完成每個任務的第一步，因此將putdown任務等級設為1，pickup任務等級設為8;可以將give（human，A）和puton進行合并，二者的任務類型非常相似，puton使用的物體可能存在某個大物體內部，完成takeout、putin、open之后可以將門打開比較方便（確保門的確是打開的，不用進行判斷），close可能會阻礙takeout、putin、open、give、puton完成，因此close優先級設為7，puton、give分別為5、6（順序可以交換）;如果open任務和putin任務發生了關聯（即open（B），putin（A，B）），由于open完成一般需要move、open兩個動作putin完成一般需要move、pickup、move、putdown、open、pickup、putin，如果執行順序為open、putin需要：move、open、move、pickup、move、putin，動作損耗為：18分，需6個原子動作，如果執行順序是putin、open：move、pickup、move、putdown、open、pickup、putin，動作損耗為：18分，需7個原子動作，這樣時間損耗就會少一些，takeout任務和putin任務是兩個相反的，二者比較相似，所以open優先級為2;如果takeout任務和putin任務有聯系（如：takeout（A，B）和putin（C，B）），執行順序為takeout，putin需要動作：move，open，takeout，putdown，move，pickup，move，putin，動作損耗：22分，需8個原子動作，執行順序為putin ，takeout需要動作：move，pickup，move，putdown，open，pickup，putin，takeout，動作損耗：20分，需8個原子動作，如果沒有聯系二者近似等價所以takeout為3，putin為4。

根據上面的分析可以很清楚地得出結果，優先級順序可以設置為：putdown->open->putin->takeout->puton->give->close->pickup->goto.如果同一種任務出現多次，可以按照出現順序來排序同一種任務。上面分析所得結果中，優先值越大執行越靠后。

將任務優先級調整之前與調整之后對比，拿2018安徽省省賽題目做對比，調整之前得分為7994;調整之后得分為8862。這之間的差距非常明顯，可以充分展示出進行優先級調整之后的作用。

3.2 錯誤信息糾正

在任務線性規劃之后，需要逐一完成。做任務時可能會遇到場景信息出錯的情況，這就需要進行人機交互以糾正錯誤信息。

3.2.1 多次詢問

在調用askloc接口詢問信息時，60%返回正確位置信息，30%返回錯誤位置信息，10%返回“不知道”，可以簡單調整為：60%返回正確位置信息，40%返回錯誤位置信息。

根據伯努利概率方程：

通過多次詢問將返回的結果存儲并比較，如果有兩次或者兩次以上結果相同，就默認這個結果為正確位置信息。

3.2.2 移動感知

這種方法類似于暴力破解，通過一直調用move、sence來一直感知，通過判斷sence返回的正確信息中是否有任務需要的信息，若有，執行任務;否則，繼續調用move、sence獲得信息直到獲得正確的位置信息。該方法簡單而且可以幫助我們準確的獲得全部信息，可以更好地完成任務。但是帶來的損耗也是無法承受的。該方法糾正錯誤場景信息需要調用大量move、sence方法，這兩種方法會消耗較長時間，如果一個場景文件存在的錯誤信息較多將會消耗較多的時間。然而比賽規定一個場景運行時間不超過5s，因此該方法可能會超時如果規定一個場景為5s，這樣的方法在未完成任務的情況下就已經超時，所以不建議采用這種方法。

3.2.3 混合方法

將上述兩種方法進行結合，通過進行詢問，并對詢問的結果進行移動感知，判定場景信息正確與否。即每次詢問之后調用move和sence接口判斷返回結果是否正確（這兩個方法損耗比較小）。

根據伯努利概率方程，可知詢問三次大概率（90%以上）可以得到正確的結果。可以設置處理一個錯誤信息時最多詢問三次（可以根據自己的需要調整），如果三次沒有得到正確結果，放棄這個任務。

4 細節部分

4.1 分支結構優化

家庭仿真機器人比賽的代碼量較大（我的代碼大概有5000行），在場景信息處理、任務信息處理和其他部分會使用到大量條件語句if{}else if{}…else{}這個分支結構雖然簡單，但是相對效率較低，更替為switch case語句可以節約很多時間（大概一個場景可以節約0.3s），獲得更高的分數。

4.2 pickup任務量大于一經過大量數據測試以及對比一些參賽隊伍的log文件發現，當一個場景出現多個pickup任務時，許多隊伍將會出錯。大多是由于潛意識認為一個場景中指揮出現一個pickup任務，這樣在處理時將會出現錯誤。

4.3 close、open任務處理

在3.1中，我們將close、open任務的優先級設為7，這個優先級比較低，基本上在一個場景中是最后一個任務或者倒數第二個。

在處理任務信息時，可以將close、open任務的目標放入集合中，每當移動到大物體旁時，可以判斷這個大物體是否在集合中，如果在集合中在移走之前關閉一下，這樣就可以節約一些不必要的損耗。以colse為例：

如果按照固定的優先級，執行完putin任務之后，移動到另一個位置執行另一個任務。然后在移動到2位置執行close在無形中多移動了一次，無論在動作損耗還是時間損耗上都增加了，而就這個整個場景而言損失了3分。

5 總結

在本文中，首先給出了一些應用在家庭仿真機器人中的算法，但是在家庭仿真機器人比賽中第二階段存在錯誤場景信息使得這些算法難以實現且效果不理想，為了解決這個問題提出了線性規劃。線性規劃只需要根據任務類型對任務進行優先級排序，然后逐一完成，這樣可以避免錯誤信息給任務執行時帶來的困擾。對任務進行優先級排序之后，對場景中的任務按照優先順序逐一完成，不僅可以避免破壞已經完成的任務，還可以為后面的任務坐下鋪墊。但是在使用線性規劃時，也不能完全按照這種優先級順序，有時需要根據具體情況具體分析，這樣可以更好的完成任務規劃。

在任務規劃之后，更需要注意的是細節部分，這些不僅影響一個場景對整個比賽的過程都有很大的影響，比如close和open類型的任務，這種任務可以用于貫穿全局完成，如果在完成其余任務之時能完成，這樣最好，如果不能完成也沒有任何損失。類似問題仍然存在，可以經過大量實驗發現這些問題，在進行改良會取得較好效果。

經過線性規劃實現算法之后，需要經過調試，以及大量數據測試，不斷發現問題并進行解決才能有更好的效果。個人覺得半人工半智能的方法是非常有效的，希望經過不斷地測試、調整之后使得家庭服務機器人更加智能。

參考文獻：

[1]余伶俐，蔡自興，劉曉瑩，高平安.均分點蟻群算法在群集機器人任務規劃中的應用與研究[J].高技術通訊.2009， 19（10）： 1054-1060.

[2]喬文莉，陳萬米.基于A*算法的家庭服務機器人仿真設計[J].工業控制計算機. 2004， 27（04）： 128-129.

[3] 章偉，蔡亞楠，楊為民. 基于任務規劃的家庭仿真服務機器人的研究[J].電腦知識與技術.2016，12（17）：188-191.

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

[5]周友行，何清華，謝習華. 基于遺傳算法的鑿巖機器人孔序規劃[J].機器人.2002，24（1）： 62-65.

[6] 范佳， 錢徽，朱淼良， 陳武斌. 優化路徑分配的多作業機器人任務規劃[J]. 計算機工程.2010， 36（23）： 142-145.

[7] 余伶俐 焦繼樂 蔡自興. 一種多機器人任務規劃算法及其系統實現[J].計算機科學.2010， 37（6）：252-255.

【通聯編輯：梁書】