外文翻譯--多機器人任務(wù)分配的勘探 中文版

1、<p>　　多機器人任務(wù)分配的勘探</p><p>　　高平安 蔡自興</p><p>　?。?. 中南大學(xué)信息科學(xué)與工程學(xué)院，中國長沙410083， 2.湘潭大學(xué)計算機科學(xué)系，中國湖南湘潭411105）</p><p>　　摘要：一個團(tuán)隊的移動機器人動態(tài)環(huán)境的探測任務(wù)分配的問題進(jìn)行了研究該小組的任務(wù)是訪問數(shù)分布路徑的目標(biāo)成本是成正比的，機器人移動

2、到訪問的的團(tuán)隊目標(biāo)是盡量減少成本的平均路徑目標(biāo)的所有目標(biāo)。找到一個最佳的分配是很難的。該算法可以產(chǎn)生后援分配接近最優(yōu)的解決方案，可以投在多輪的單件拍賣，機器人出價關(guān)于在每次拍賣輪，一個目標(biāo)被分配到一個機器人噸，產(chǎn)生的焦油的最低路徑成本的分配目標(biāo)，形成了一個森林里，每棵樹對應(yīng)一個機器人的探索目標(biāo)設(shè)置.每個機器人構(gòu)造通過深度優(yōu)先搜索在其目標(biāo)樹木.它的時間復(fù)雜度的算法的探索路徑是復(fù)雜的. 模擬實驗結(jié)果表明，分配方法是有效的。</p>

3、;<p>　　關(guān)鍵詞：多機器人系統(tǒng)任務(wù)分配，平均路徑開銷;多輪的單件拍賣，目標(biāo)樹</p><p>　　中圖分類號：TP24 文獻(xiàn)標(biāo)識碼：A</p><p><b>　　1引言</b></p><p>　　合作機器人可能具有較強的耐用性，故障容差，更高的效率不是單一的機器人，他們認(rèn)為的承諾證明表現(xiàn)為大規(guī)模的問題小號作為行星探測

4、，測繪，搜索和救援行動，偵察，等等。</p><p>　　機器人探測的在多個任務(wù)分配是一個關(guān)鍵問題.當(dāng)多臺機器人合作，執(zhí)行任務(wù)，它始終是必要的瑞銀目標(biāo)任務(wù)分解到，并決定機器人應(yīng)執(zhí)行的子目標(biāo)（即任務(wù)），以便有效地實現(xiàn)全球觀測問題的多機器人任務(wù)分配（MRTA）是打開的問題之一，它可以是簡單的說：給定一組機器人，一組任務(wù)，和一個用于評估實用程序的方法，如何分配任務(wù)的機器人，并找到所有的探索路徑，每個機器人以最大化總的，

5、它是很難找到一個最佳的任務(wù)分配一個有用的規(guī)模。應(yīng)用程序往往需要不同的不同的目標(biāo)需要不同的分配陽離子結(jié)果，問題它通常是與啟發(fā)式解決的。</p><p>　　雖然已研究的問題多機器人任務(wù)分配在最近幾年很廣泛。一些研究人員主要集中在如何以最小的平均任務(wù)完成時間，這是非常合適的搜索和搶救的應(yīng)用。健康幾名受害者的條件惡化，直到機器人去看望他們。在本文中，我們討論如何分配簡單的目標(biāo)，以機器人，并找到一個路徑為每個機器人，以盡

6、量減少的平均焦油所有分布在不同的目標(biāo)路徑開銷2D環(huán)境中的不同位置。</p><p>　　2多機器人任務(wù)分配的問題</p><p>　　給定一組機器人，一組的目標(biāo)，一個非負(fù)對稱成本函數(shù)C（I，）表示顯示距離I和J，我們有興趣找到每個機器人的探索之路所有目標(biāo)的平均輪候時間是迷你化，寬度的目標(biāo)是服務(wù)實例的訪問時，之間的距離和任何兩個目標(biāo)是大于傳感半徑每個機器人。</p><p

7、>　　目標(biāo)路徑成本是從機器人的探索路徑長度機器人的初始位置到目標(biāo)的位置。檢測說，如果機器人R先后走訪了目標(biāo)地點TL，T2，?，T，反過來從它的初始位置，目標(biāo)路徑成本的焦油得到是加一個公式啊和探索路徑開銷的機器人再加一個公式是機器人的問題我們會解決的是如何分配未訪問目標(biāo)的機器人，并發(fā)現(xiàn)每個機器人的路徑以訪問所有分配給它的目標(biāo)最小化平均成本的目標(biāo)路徑是一種變異的旅游修理工問題[14]。成本滿足三角不等式（機器人操作的歐幾里德平面上）為

8、如下</p><p>　　三角不等式原理表明，成本最低的兩個地點之間的直接路由開銷。機器人更喜歡移動直接從當(dāng)前位置到下一個置中所有的時間。該問題可以表示為一個加權(quán)無向，以及完整的圖的頂點集是相對應(yīng)的機器人的位置和目標(biāo)。邊的權(quán)重相對應(yīng)的成本從一個位置移動到另一個，作為給定由成本函數(shù)，加圖</p><p>　　我們的目標(biāo)是1升分區(qū)，使每個劃分的頂點分區(qū)包括一個機器人的頂點。找到從機器人頂點開始

9、的路徑和包括所有頂點在每個重量頂點的所有頂點的平均路徑是微量嗯。</p><p>　　例如，有三個均勻的滾裝漫游器（R1，R2和R3）和6個目標(biāo)（G1，G2， G3，G4，G5和G6）位于上的加強格柵作為所示Fig.1.If G1和G2被分配給R1。G3和G4被分配給R2.and G5和G6是分配至R3，則C（R1，G1）是2個單位， Cr（G6）中的6個單位，平均成本的目標(biāo)是22/6是最小的。有一個表格這個例子

10、也表明，最大限度地減少球隊的總成本是不同的，從最小化平均路徑成本目標(biāo)的所有目標(biāo)。 有圖</p><p>　　三角不等式原理表明，成本最低的兩個地點之間的直接路由開銷。機器人更喜歡移動直接從當(dāng)前位置到下一個置中所有的時間。該問題可以表示為一個加權(quán)無向，以及完整的圖的頂點集是相對應(yīng)的機器人的位置和目標(biāo)。邊的權(quán)重相對應(yīng)的成本從一個位置移動到另一個，作為給定由成本函數(shù)，加圖</p><p>

11、　　我們的目標(biāo)是1升分區(qū)，使每個劃分的頂點分區(qū)包括一個機器人的頂點。找到從機器人頂點開始的路徑和包括所有頂點在每個重量頂點的所有頂點的平均路徑是微量嗯。</p><p>　　例如，有三個均勻的滾裝漫游器（R1，R2和R3）和6個目標(biāo)（G1，G2， G3，G4，G5和G6）位于上的加強格柵作為所示Fig.1.If G1和G2被分配給R1。G3和G4被分配給R2.and G5和G6是分配至R3，則C（R1，G1）是2

12、個單位， Cr（G6）中的6個單位，平均成本的目標(biāo)是22/6是最小的。有一個表格這個例子也表明，最大限度地減少球隊的總成本是不同的，從最小化平均路徑成本目標(biāo)的所有目標(biāo)。 加圖</p><p>　　很顯然如果該小組的目標(biāo)是盡量減少能源消耗總量的所有訪問所有的.他的路徑開銷的機器人R1，R2和R3是11個單位，0，和0分別的六個目標(biāo)的成本10臺，6臺，9臺，六的平均成本2臺，3臺，51輛。目標(biāo)是32/6單位。&

13、lt;/p><p><b>　　3 分配方法</b></p><p>　　拍賣為基礎(chǔ)的方法是眾所周知的在動態(tài)環(huán)境中是有效的，經(jīng)常分配計劃所需的通過拍賣過程中的任務(wù)分配：每機器人在本地計劃實現(xiàn)所提供的任務(wù)，其成本計算，評估的目的功能，并封裝在其投標(biāo)的成本;機器人提供的最低投標(biāo)價將獲得是一項重要的任務(wù)。</p><p>　　拍賣的算法，算法1中，只產(chǎn)

14、生一個接近最優(yōu)的分配算法包括兩個主要步驟：（1）進(jìn)行目標(biāo)樹為每個機器人分配;（2）詮釋婷的連接路徑樹中的所有頂點。</p><p>　　算法1：迷你大道- 成本（VR，VR）對于每個的機器人一個樹TR含只有相應(yīng)的機器人寧頂點對于所有的r，使用深度優(yōu)先搜索TR建設(shè)的路徑分配處理是類似的使最小生成樹森林的加權(quán)，無向，和完全圖的頂點圖對應(yīng)的位置的目標(biāo)（Vr）的機器人，重對應(yīng)的歐幾里德距離從一個位置到另一臺大戲集對應(yīng)所有

15、未分配的目標(biāo)，是集機器人在團(tuán)隊。任何兩個機器人之間的距離是正.所有的目標(biāo)是初步機器人維護(hù)一個樹，機器人每個目標(biāo)分配給一輪招標(biāo)中，機器人的出價未分配的目標(biāo)B，（£）。在算法1中，CR（T）表示機器人R評估的成本消耗訪問T中的所有目標(biāo)，和Cr（£）表示估計路徑成本的目標(biāo)交配，如果它被訪問的機器人R。</p><p>　　機器人將總體最低出價任何目標(biāo)被分配特定的機器人的構(gòu)造了一個路徑，連接在聯(lián)合國的

16、所有頂點訪問目標(biāo)樹的使用深度優(yōu)先搜索策略。然后機器人開始訪問未訪問過的目標(biāo)沿著從機器人的當(dāng)前的位置的路徑直到所有的訪問目標(biāo)或者未訪問過的目標(biāo)必須重新分配環(huán)境信息變化發(fā)生在算法1可以實現(xiàn)與多個優(yōu)先級隊列，維護(hù)每個優(yōu)先級隊列的7/robots，每個隊列包含未分配的索引至少連接成本的目標(biāo)機器人的樹這些隊列進(jìn)行初始化。</p><p>　　時間為每個每次迭代中，一個隊列中選擇時間，其頂端元件中提取時間和被分配給相應(yīng)的樹。

17、獲獎最多的隊列中有迄今為止所有剩余的未分配中的元素隊列中的新的成本，同時，分配特德所有其他元素應(yīng)該被刪除可以做到在.他的時間。</p><p>　　算法的時間復(fù)雜性為這意味著，該算法是很實際的，大問題，涉及到許多機器人和號碼中，這是一個非常有用的功能項的目標(biāo)。動態(tài)環(huán)境下任務(wù)再分配的背景下經(jīng)常需要。</p><p>　　雖然機器人在部分未知的探索已廢除環(huán)境功能，環(huán)境功能或信息它可能改變.例如

18、，機器人可能不知道兩個目標(biāo)之間的障礙在移動在附近的.這之前，情況下，機器人的最初樂觀消耗，它們之間的路徑是很容易.當(dāng)一個機器人發(fā)現(xiàn)了其上的障礙要方式。將估計的成本探索如果估算的變化的計劃目標(biāo)。</p><p>　　成本是大于的重新分配.對于算法2未訪問過的目標(biāo)重新分配的機器人在動態(tài)環(huán)境中。VR代表還沒有訪問過的的目標(biāo)垂直CAS。</p><p>　　算法2：DyMinLAve成本（VR，V

19、T）</p><p>　　更新的費用的未訪問的目標(biāo)運行M INL-大道- 成本（VR，VT）只要沿其路徑移動機器人有沒有訪問過的目標(biāo)和變化不比閾值。</p><p><b>　　4實驗結(jié)果</b></p><p>　　對于有效性進(jìn)行驗證的上述算法，我們實現(xiàn)了在VC++。探索區(qū)域的大小被設(shè)置于600米×400米的，并位置的目標(biāo)（空間圓）

20、和機器人（同心）隨機分布在團(tuán)隊由顯示了1 2目標(biāo)分配給3個機器人的屏幕截圖。</p><p><b>　　有圖</b></p><p>　　圖2目標(biāo)分配在靜態(tài)模擬實驗的結(jié)果環(huán)境的示于表1的目標(biāo)N為初始未分配.數(shù)中號的- 大道 - 成本表示得出的結(jié)果算法的的成本是指所有目標(biāo)的最優(yōu)平均成本。</p><p><b>　　表1的仿真實驗結(jié)果

21、</b></p><p><b>　　有圖</b></p><p>　　在很大程度上是因為探索路徑忽略的訪問次序的影響，結(jié)果是次優(yōu)的。</p><p><b>　　5結(jié)論</b></p><p>　　一個簡單的拍賣為基礎(chǔ)的分配算法開發(fā)的多機器人.他的復(fù)雜性是.他是快速的多項式時間復(fù)雜性，