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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、</b></p><p><b>　　有圖</b></p><p>　　在很大程度上是因?yàn)樘剿髀窂胶雎缘脑L(fǎng)問(wèn)次序的影響，結(jié)果是次優(yōu)的。</p><p><b>　　5結(jié)論</b></p><p>　　一個(gè)簡(jiǎn)單的拍賣(mài)為基礎(chǔ)的分配算法開(kāi)發(fā)的多機(jī)器人.他的復(fù)雜性是.他是快速的多項(xiàng)式時(shí)間復(fù)雜性，