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

常順 吳雪峰 劉向舉

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

關(guān)鍵詞：多任務(wù)規(guī)劃;人機交互;信息糾正;家庭仿真;機器人

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

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

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

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

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

1 家庭仿真機器人比賽

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

2 任務(wù)描述

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

本人主要研究這9中任務(wù)，使用線性規(guī)劃的方法規(guī)劃完成場景中的任務(wù)。任務(wù)的具體描述如下：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內(nèi)部8.close（A） 將容器A的門關(guān)閉9.takeout（A，B）將小物體A從容器B中拿出。完成這寫種類任務(wù)，不能在場景結(jié)束之后的最終狀態(tài)破壞（就是物體最終狀態(tài)與任務(wù)描述相同），否則相當于沒有完成。在每個場景中，這9種任務(wù)含有其中的一部分或者全部，并且每種的任務(wù)數(shù)量可能不唯一，比如：

3 任務(wù)規(guī)劃

3.1 任務(wù)優(yōu)先級調(diào)整

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

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

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

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

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

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

根據(jù)上面的分析可以很清楚地得出結(jié)果，優(yōu)先級順序可以設(shè)置為：putdown->open->putin->takeout->puton->give->close->pickup->goto.如果同一種任務(wù)出現(xiàn)多次，可以按照出現(xiàn)順序來排序同一種任務(wù)。上面分析所得結(jié)果中，優(yōu)先值越大執(zhí)行越靠后。

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

3.2 錯誤信息糾正

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

3.2.1 多次詢問

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

根據(jù)伯努利概率方程：

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

3.2.2 移動感知

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

3.2.3 混合方法

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

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

4 細節(jié)部分

4.1 分支結(jié)構(gòu)優(yōu)化

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

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

4.3 close、open任務(wù)處理

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

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

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

5 總結(jié)

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

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

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

參考文獻：

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

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

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

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

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

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

[7] 余伶俐 焦繼樂 蔡自興. 一種多機器人任務(wù)規(guī)劃算法及其系統(tǒng)實現(xiàn)[J].計算機科學.2010， 37（6）：252-255.

【通聯(lián)編輯：梁書】