基于市場(chǎng)法的多機(jī)器人協(xié)作未知環(huán)境探索?

趙慧潮 石朝俠

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

基于市場(chǎng)法的多機(jī)器人協(xié)作未知環(huán)境探索?

趙慧潮 石朝俠

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

多任務(wù)分配是多機(jī)器人未知環(huán)境協(xié)作探索的關(guān)鍵問(wèn)題。傳統(tǒng)市場(chǎng)法由于追求單體機(jī)器人最優(yōu)化，從而犧牲了整體最優(yōu)化，而基于蟻群算法的多任務(wù)分配方法雖然實(shí)現(xiàn)了整體最優(yōu)化，但是不適合在未知環(huán)境探索中使用。論文在市場(chǎng)法的基礎(chǔ)上提出了一種改進(jìn)方法，該方法將機(jī)器人到任務(wù)點(diǎn)所經(jīng)過(guò)路徑上的排斥素的多少作為拍賣(mài)獲勝的條件。該方法提高了多機(jī)器人系統(tǒng)完成環(huán)境探索的效率。通過(guò)實(shí)驗(yàn)驗(yàn)證該算法的有效性。

多機(jī)器人；協(xié)作探索；市場(chǎng)法；排斥素

1 引言

利用多機(jī)器人協(xié)作探索未知環(huán)境與單個(gè)機(jī)器人系統(tǒng)相比具有信息冗余、柔韌性、并行性等特點(diǎn)，但是在未知環(huán)境下也面臨多任務(wù)分配、有線通信和信息融合等挑戰(zhàn)。多機(jī)器人技術(shù)廣泛應(yīng)用于戰(zhàn)場(chǎng)偵察［1］、星球探測(cè)［2］、災(zāi)難救援等領(lǐng)域。

多機(jī)器人系統(tǒng)探索未知環(huán)境的關(guān)鍵則是如何更加有效地分配任務(wù)點(diǎn)，兼顧單個(gè)機(jī)器人和多機(jī)器人系統(tǒng)的整體效率［3］，減少任務(wù)目標(biāo)重復(fù)探索、區(qū)域重復(fù)等問(wèn)題，因此探索策略必須具備可靠性、魯棒性和高效性［4］。

目前廣泛應(yīng)用在多機(jī)器人協(xié)作探索未知環(huán)境中的方法主要包括：蟻群算法［5］、神經(jīng)網(wǎng)絡(luò)算法［6］、粒子群算法［7］、市場(chǎng)拍賣(mài)方法［8］和組合分配方法等等?，F(xiàn)在比較主流的方法為市場(chǎng)法、組合分配方法。市場(chǎng)法模擬拍賣(mài)行業(yè)制度，各機(jī)器人在每執(zhí)行完一次探索以后，根據(jù)剩余目標(biāo)任務(wù)的完成時(shí)間、能源消耗等指標(biāo)進(jìn)行投標(biāo)、相互競(jìng)價(jià)，通過(guò)拍賣(mài)機(jī)制將任務(wù)分配到具體的機(jī)器人［9］。市場(chǎng)法可以實(shí)現(xiàn)單個(gè)機(jī)器人的高效率，但是經(jīng)常會(huì)陷入局部最優(yōu)無(wú)法實(shí)現(xiàn)多機(jī)器人系統(tǒng)整體的最優(yōu)化。文獻(xiàn)［10］在市場(chǎng)拍賣(mài)方法的基礎(chǔ)上結(jié)合旅行商［11］解決方案和最短路徑算法［12］，提高了任務(wù)分配效率。文獻(xiàn)［13］利用市場(chǎng)拍賣(mài)方法獲得目標(biāo)點(diǎn)，在向目標(biāo)點(diǎn)運(yùn)動(dòng)的過(guò)程中預(yù)測(cè)下一個(gè)目標(biāo)點(diǎn)，從而節(jié)省目標(biāo)分配時(shí)間?；诮M合分配的優(yōu)化方法主要是對(duì)矩陣的運(yùn)算，在任務(wù)數(shù)量均勻分布的情況下能夠表現(xiàn)出比較良好的實(shí)驗(yàn)效果，當(dāng)任務(wù)點(diǎn)大量集中于某個(gè)區(qū)域的時(shí)候，探索效率較差。

2 市場(chǎng)法

在人類(lèi)長(zhǎng)期的市場(chǎng)經(jīng)濟(jì)行為中，商家和個(gè)人通過(guò)貨物貿(mào)易實(shí)現(xiàn)個(gè)人利益的最大化。簡(jiǎn)單來(lái)說(shuō)就是實(shí)現(xiàn)資源的最優(yōu)化利用，這一點(diǎn)和多機(jī)器人任務(wù)分配十分相似，多機(jī)器人任務(wù)分配是為了以最合理優(yōu)化的方法將多任務(wù)分配到單個(gè)機(jī)器人，實(shí)現(xiàn)多機(jī)器人系統(tǒng)的整體最優(yōu)化。模仿人類(lèi)社會(huì)的拍賣(mài)行為，提出了基于拍賣(mài)方法的任務(wù)分配方式［14］。拍賣(mài)法是市場(chǎng)法的主要表現(xiàn)形式，具體步驟如下：

1）機(jī)器人將自己探測(cè)到的任務(wù)點(diǎn)以廣播的方式發(fā)布拍賣(mài)信息，該機(jī)器人被稱(chēng)為拍賣(mài)機(jī)器人。拍賣(mài)信息主要是任務(wù)點(diǎn)的位置信息。收到信息的機(jī)器人判斷自己是否可以到達(dá)任務(wù)點(diǎn)，如果可以到達(dá)就參與投標(biāo)。參與投標(biāo)的機(jī)器人被稱(chēng)為競(jìng)標(biāo)機(jī)器人。

2）每個(gè)競(jìng)標(biāo)機(jī)器人根據(jù)收到的拍賣(mài)信息計(jì)算到達(dá)任務(wù)點(diǎn)的耗時(shí)、路程和效益，從而得到自己的投標(biāo)值。將投標(biāo)信息以廣播的方式發(fā)送出去。

3）拍賣(mài)機(jī)器人將收到的所有競(jìng)標(biāo)機(jī)器人的投標(biāo)信息進(jìn)行排序比較，從而確定最終贏得拍賣(mài)的機(jī)器人。

基于市場(chǎng)法的多任務(wù)分配方法可以有效地適用于動(dòng)態(tài)環(huán)境全局信息不確定的環(huán)境中［15］。同時(shí)市場(chǎng)法任務(wù)分配對(duì)于機(jī)器人數(shù)量的變化具有很好的適應(yīng)性［16］，使得多機(jī)器人系統(tǒng)規(guī)模擴(kuò)大變得更加容易。市場(chǎng)法可以實(shí)現(xiàn)每個(gè)機(jī)器人的局部最優(yōu)化，但是局部最優(yōu)化并不代表整體最優(yōu)化。

3 基于排斥素的市場(chǎng)法

傳統(tǒng)市場(chǎng)法由于追求單體機(jī)器人最優(yōu)化從而犧牲了整體最優(yōu)化，而基于蟻群算法的多任務(wù)分配方法實(shí)現(xiàn)了整體最優(yōu)化但是不適合在未知環(huán)境探索中使用。傳統(tǒng)市場(chǎng)法中機(jī)器人選擇任務(wù)點(diǎn)主要是基于到達(dá)任務(wù)點(diǎn)的距離作為判斷標(biāo)準(zhǔn)，這樣就沒(méi)有考慮其他機(jī)器人的探索情況。相對(duì)于吸引信息素，排斥素更加適合于多機(jī)器人協(xié)作完成未知環(huán)境的探索，在未知環(huán)境探索中排斥素能夠更加直接有效。利用排斥素作為判斷標(biāo)準(zhǔn)，利用了之前機(jī)器人的探測(cè)信息，可以很好地考慮到機(jī)器人之前的探索情況，避免機(jī)器人過(guò)于集中在同于區(qū)域。

3.1 相關(guān)假設(shè)

本文研究采用市場(chǎng)算法實(shí)現(xiàn)動(dòng)態(tài)多任務(wù)的分布式分配，對(duì)多機(jī)器人系統(tǒng)特性、任務(wù)特點(diǎn)和環(huán)境特征有如下假設(shè)：

1）機(jī)器人具有誠(chéng)實(shí)性，當(dāng)遇到相同情況機(jī)器人執(zhí)行的動(dòng)作都是一樣的，不具有隨機(jī)性；

2）機(jī)器人具有自私性，機(jī)器人所做的一切行為都是為了實(shí)現(xiàn)自身利益最大化；

3）機(jī)器人是理性的，機(jī)器人所執(zhí)行的一切動(dòng)作都是在允許的范圍內(nèi)的；

4）任何機(jī)器人之間都可以進(jìn)行廣播或者點(diǎn)播方式進(jìn)行通信，但是通信的可靠性并不能得到保證；

5）多機(jī)器人系統(tǒng)中機(jī)器人的數(shù)量可以增減；

6）多機(jī)器人系統(tǒng)中每個(gè)機(jī)器人之間的關(guān)系是完全分布式的，不存在“領(lǐng)導(dǎo)者”和“跟隨者”的關(guān)系；

7）待分配的任務(wù)是簡(jiǎn)單任務(wù)，不可以進(jìn)行分解，每個(gè)任務(wù)都可以由單個(gè)機(jī)器人完成不需要協(xié)作完成；

8）任務(wù)是動(dòng)態(tài)出現(xiàn)的。

3.2 排斥素的計(jì)算

假設(shè)節(jié)點(diǎn)nodei為任務(wù)點(diǎn)，則稱(chēng)節(jié)點(diǎn)nodei為任務(wù)點(diǎn)taski。在競(jìng)爭(zhēng)蟻群算法中利用Dijkstra最短路徑算法計(jì)算機(jī)器人robotk當(dāng)前所在路口nodeo到任務(wù)點(diǎn)taski的最短路徑，最短路徑所經(jīng)過(guò)的邊的集合為PAT={n odeo，…，nodei} 。假設(shè)機(jī)器人robotk從節(jié)點(diǎn)nodei1到任務(wù)點(diǎn)taskin的最短路徑為 nodei1，nodei2，nodei3，nodei4，…，nodein。則從節(jié)點(diǎn)node到任務(wù)點(diǎn)task的排斥素為i1in

其中：節(jié)點(diǎn)nodeit

與節(jié)點(diǎn)nodeit+1為相鄰節(jié)點(diǎn)，且nodeit、nodeit+1之間的通路為itit+1；Phekitit+1表示相鄰節(jié)點(diǎn)nodeit到nodeit+1的排斥素。

假設(shè)節(jié)點(diǎn)nodei與節(jié)點(diǎn)nodej相鄰，則機(jī)器人robotk從節(jié)點(diǎn)nodei到節(jié)點(diǎn)nodej的排斥素的計(jì)算表達(dá)式為

其中：Nj表示節(jié)點(diǎn)nodej的相鄰節(jié)點(diǎn)的集合，t∈Nj表示節(jié)點(diǎn)nodeit為節(jié)點(diǎn)nodej的相鄰節(jié)點(diǎn)；Phe(ij)表示邊ij自身的排斥素；表示節(jié)點(diǎn)nodej其他各分支上排斥素和；μij為調(diào)整對(duì)Phek

ij影響大小的參數(shù)。

假設(shè)從節(jié)點(diǎn)i到節(jié)點(diǎn) j至少需要經(jīng)l條邊，稱(chēng)節(jié)點(diǎn)i到節(jié)點(diǎn) j的距離為lij，則 μij的計(jì)算表達(dá)式為

其中：sumr表示該路口有幾個(gè)機(jī)器人路口經(jīng)過(guò)；maxl表示路口到當(dāng)前機(jī)器人所在路口允許的最多路口個(gè)數(shù)，maxl的計(jì)算公式如下

其中：Vk表示地圖中已經(jīng)探索過(guò)的路口個(gè)數(shù)，maxl的大小由Vk所決定。距離機(jī)器人越遠(yuǎn)的路口對(duì)機(jī)器人選擇運(yùn)動(dòng)方向的影響越小，式（2）是一個(gè)遞歸公式，如果對(duì)該公式不加限制地一直進(jìn)行遞歸會(huì)嚴(yán)重影響該算法的效率，本文提出了maxl這個(gè)概念，將距離超過(guò)maxl的路口的影響全部視為0，這樣就會(huì)減少遞歸次數(shù)，提高算法的效率。

3.3 任務(wù)分配過(guò)程

3.3.1 任務(wù)點(diǎn)分配

本文采用拍賣(mài)法實(shí)現(xiàn)任務(wù)點(diǎn)分配，拍賣(mài)過(guò)程中會(huì)出現(xiàn)兩個(gè)角色“拍賣(mài)方”和“競(jìng)拍方”，發(fā)現(xiàn)任務(wù)點(diǎn)的機(jī)器人被稱(chēng)為“拍賣(mài)方”，可能完成該任務(wù)的機(jī)器人被稱(chēng)為“競(jìng)拍方”。多機(jī)器人系統(tǒng)中在不同的時(shí)刻每個(gè)機(jī)器人都有扮演不同角色的可能性，但是每個(gè)機(jī)器人同一時(shí)刻最多只能扮演其中一種角色?！芭馁u(mài)方”將待分配的任務(wù)分配給最合理的“競(jìng)拍方”來(lái)完成該任務(wù)；“競(jìng)拍方”基于自身能力和所處環(huán)境位置對(duì)被拍賣(mài)的任務(wù)進(jìn)行投標(biāo)，由“拍賣(mài)方”機(jī)器人做出決定，從眾多“競(jìng)拍方”中選擇最優(yōu)的“拍賣(mài)方”將任務(wù)分配給它。任務(wù)點(diǎn)的分配主要包括四個(gè)步驟，分別為任務(wù)發(fā)布、投標(biāo)計(jì)算、合同授權(quán)以及合同建立。

1）任務(wù)發(fā)布

當(dāng)“拍賣(mài)方”發(fā)現(xiàn)有任務(wù)沒(méi)有被分配，將該任務(wù)的相關(guān)信息利用廣播的方式發(fā)送給可能對(duì)該任務(wù)做出拍賣(mài)響應(yīng)的機(jī)器人。如圖1所示，任務(wù)相關(guān)信息主要包括任務(wù)位置和最晚投標(biāo)時(shí)間等等。

圖1 任務(wù)發(fā)布

2）投標(biāo)計(jì)算

接收到“拍賣(mài)方”發(fā)送的任務(wù)信息后，機(jī)器人判斷該任務(wù)點(diǎn)是否在自己的地圖范圍內(nèi)，如果機(jī)器人可以找到到達(dá)該任務(wù)點(diǎn)路徑，就計(jì)算到達(dá)任務(wù)點(diǎn)的路徑上的排斥素。如果機(jī)器人可以到達(dá)該任務(wù)，就將信息排斥素作為“投標(biāo)價(jià)格”，利用點(diǎn)對(duì)點(diǎn)的通信方式將“投標(biāo)價(jià)格”發(fā)送給拍賣(mài)方，“投標(biāo)價(jià)格”的內(nèi)容主要有機(jī)器人自身的信息和到達(dá)任務(wù)點(diǎn)的排斥素。如圖2所示。

圖2 投標(biāo)計(jì)算

3）合同授權(quán)

“拍賣(mài)方”將任務(wù)信息廣播出去后就進(jìn)入等待投標(biāo)階段，當(dāng)收到“競(jìng)拍方”發(fā)來(lái)的關(guān)于此次拍賣(mài)的投標(biāo)，將該投標(biāo)信息保存下來(lái)。當(dāng)投標(biāo)時(shí)間結(jié)束，“拍賣(mài)方”停止接收其他機(jī)器人的投標(biāo)，“拍賣(mài)方”對(duì)所收到的所有投標(biāo)進(jìn)行排序，選擇排斥素最少的“競(jìng)拍方”作為此次拍賣(mài)的獲勝方，并向其發(fā)送競(jìng)拍勝利建立合同的信息。如圖3所示。

圖3 合同授權(quán)

4）合同建立

如圖4所示，獲得本次拍賣(mài)的“競(jìng)拍方”向“拍賣(mài)方”發(fā)送合同確認(rèn)信息，與“拍賣(mài)方”建立合同關(guān)系，將該任務(wù)加入到自己的任務(wù)表序列中，保證該機(jī)器人執(zhí)行該任務(wù)。在合同建立的過(guò)程中，如果“競(jìng)拍方”發(fā)現(xiàn)自身情況發(fā)生改變不適合執(zhí)行該合同，就需要向“拍賣(mài)方”發(fā)送合同取消信息，此時(shí)“拍賣(mài)方”重新進(jìn)入合同授權(quán)階段，重新選擇“拍賣(mài)方”作為任務(wù)的執(zhí)行者向其授權(quán)合同。

圖4 合同建立

該分配方法雖然解決了分布式多機(jī)器人系統(tǒng)的任務(wù)分配問(wèn)題，但是由于該方法對(duì)網(wǎng)絡(luò)通信十分依賴(lài)，如果在任務(wù)分配的過(guò)程中出現(xiàn)通信中斷或者丟包等情況，可能直接導(dǎo)致任務(wù)分配失敗，甚至可能導(dǎo)致多機(jī)器人系統(tǒng)整體出現(xiàn)奔潰。

為了防止系統(tǒng)奔潰的情況出現(xiàn)，如果在規(guī)定時(shí)間內(nèi)沒(méi)有將任務(wù)拍賣(mài)出去就取消本次任務(wù)拍賣(mài)，避免由于通信等問(wèn)題導(dǎo)致系統(tǒng)出現(xiàn)奔潰，在下次任務(wù)拍賣(mài)過(guò)程中再次對(duì)該任務(wù)進(jìn)行拍賣(mài)。

3.3.2 任務(wù)點(diǎn)再分配

機(jī)器人通過(guò)拍賣(mài)獲得完成任務(wù)點(diǎn)的“合同”，但是隨著時(shí)間的遷移，機(jī)器人的狀態(tài)發(fā)生改變，有些任務(wù)可能不再適合自己去完成，此時(shí)就需要對(duì)這些已經(jīng)經(jīng)過(guò)一次拍賣(mài)的任務(wù)進(jìn)行再次拍賣(mài)分配。任務(wù)點(diǎn)再分配的過(guò)程和3.3.1小節(jié)的分配過(guò)程基本相似，區(qū)別主要集中在任務(wù)發(fā)布過(guò)程中。機(jī)器人每完成一個(gè)任務(wù)后，計(jì)算自己的任務(wù)表序列中排斥素最高的任務(wù)點(diǎn)對(duì)其進(jìn)行“拍賣(mài)”，如果該任務(wù)點(diǎn)被成功“拍賣(mài)”出去，則從自己的任務(wù)表中將該任務(wù)點(diǎn)刪除。

4 實(shí)驗(yàn)對(duì)比

本文以南京理工大學(xué)校園地圖作為實(shí)驗(yàn)的模擬環(huán)境，在此基礎(chǔ)上進(jìn)行仿真實(shí)驗(yàn)。如圖5為部分實(shí)驗(yàn)環(huán)境，實(shí)驗(yàn)范圍為1100m×1300m，機(jī)器人運(yùn)行速度為5m/s。將本文提出的方法與市場(chǎng)法、組合拍賣(mài)方法進(jìn)行比較，得出該方法的優(yōu)劣性。本文在不同的機(jī)器人數(shù)量的情況，分別針對(duì)算法的搜索完成時(shí)間、搜索路徑以及重復(fù)率進(jìn)行比較。在實(shí)驗(yàn)過(guò)程中，隨機(jī)選取20組機(jī)器人的初始位置，排除初始位置的選取不同對(duì)實(shí)驗(yàn)結(jié)果造成干擾。同時(shí)每組初始位置重復(fù)十次實(shí)驗(yàn)過(guò)程，排除實(shí)驗(yàn)過(guò)程中可能存在的一些不可預(yù)知的偶然性因素對(duì)實(shí)驗(yàn)結(jié)果造成誤差干擾。

圖5 實(shí)驗(yàn)環(huán)境

4.1 探索未知環(huán)境完成時(shí)間對(duì)比

從圖6可知，在機(jī)器人數(shù)量相同的情況下，相較于傳統(tǒng)市場(chǎng)法和組合分配算法本文提出的基于排斥素市場(chǎng)法的探索完成時(shí)間相對(duì)較短，比其他兩種方法完成時(shí)間減少了8%。同時(shí)還可以發(fā)現(xiàn)隨著機(jī)器人數(shù)量的增加，多機(jī)器人系統(tǒng)完成未知環(huán)境探索的時(shí)間也在逐漸下降，但是當(dāng)機(jī)器人的個(gè)數(shù)增加到一定數(shù)量以后，多機(jī)器人系統(tǒng)探索完成時(shí)間并不會(huì)持續(xù)下降，而是在一定的時(shí)間范圍內(nèi)波動(dòng)。由此可以得出多機(jī)器人探索未知環(huán)境并不是機(jī)器人的數(shù)量越多探索時(shí)間就一定會(huì)越短。

圖6 在不同機(jī)器人數(shù)量的情況下，各算法的完成時(shí)間

4.2 探索未知環(huán)境重復(fù)率對(duì)比

從圖7可知，在機(jī)器人數(shù)量相同的情況下，本文提出的算法在降低地圖重復(fù)率方面有顯著效果?；谂懦馑厥袌?chǎng)法將探索未知環(huán)境的重復(fù)率降低了23%。同時(shí)可以看到無(wú)論采用何種算法隨著機(jī)器人數(shù)量的增加，雖然地圖重復(fù)率存在偶然的輕微下降，但是總體都是呈上升趨勢(shì)。

4.3 探索未知環(huán)境行駛路徑對(duì)比

從圖8可知，在機(jī)器人數(shù)量相同的情況下，本文提出的算法在降低完成路徑方面略有改進(jìn)并沒(méi)有取得較顯著的效果。

圖7 在不同機(jī)器人數(shù)量的情況下，各算法的重復(fù)率

圖8 在不同機(jī)器人數(shù)量的情況下，各算法的完成路徑

5 結(jié)語(yǔ)

根據(jù)仿真實(shí)驗(yàn)結(jié)果分析可知，在機(jī)器人數(shù)量相同的情況下本文提出的算法可以在更短時(shí)間和更低重復(fù)率的情況下完成未知環(huán)境的探索。但是該算法也存在一些不足的地方。諸如無(wú)法有效降低多機(jī)器人系統(tǒng)的探索路徑長(zhǎng)度，無(wú)法解決未知環(huán)境探索效率隨著機(jī)器人的數(shù)量增加一直持續(xù)提高存在性能瓶頸。

［1］Hougen D F，Benjaafar S，Bonney J C，et al.A miniature robotic system for reconnaissance and surveillance［C］//IEEE International Conference on Robotics&Automation，2000：501-507.

［2］Apostolopoulos D S，Pedersen L，Shamah B N，et al.Robotic Antarctic Meteorite Search：Outcomes［C］//Proceedings-IEEE International Conference on Robotics and Automation，2001：4174-4179 vol.4.

［3］王姝莉.基于多機(jī)器人協(xié)調(diào)的搜集與圍捕問(wèn)題的研究［D］.北京：中國(guó)科學(xué)院自動(dòng)化研究所，2003.WANG Shuli.Research on the Multi-Robot System Cooperation Based on Foraging and Pursuit Game［D］.Beijing：Instltute of Automation，Chinese Academy of Sclences，2003.

［4］張飛，陳衛(wèi)東，席裕庚.多機(jī)器人協(xié)作探索的改進(jìn)市場(chǎng)法［J］.控制與決策，2005，20（5）：516-520.ZHANG Fei，CHEN Weidong，XI Yugeng.Improved market-based approach to collaborative multi-robot exploration［J］.Control and Decision，2005，20（5）：516-520.

［5］Dorigo M，Bonabeau E，Theraulaz G.Ant algorithms and stigmergy［J］.Future Generation Computer Systems，2000，16（8）：851-871.

［6］Colby M，Chung J J，Tumer K.Implicit adaptive multi-robot coordination in dynamic environments［C］//Ieee/rsj International Conference on Intelligent Robots and Systems.IEEE，2015.

［7］Cai Y，Yang S X.An improved PSO-based approach with dynamic parameter tuning for cooperative multi-robot target searching in complex unknown environments［J］.

［8］Vig L，Adams J A.Market-Based Multi-robot Coalition Formation［M］.Springer Japan，2006.

［9］陳建平.多機(jī)器人系統(tǒng)中的機(jī)器人合作問(wèn)題研究［D］.廣州：廣東工業(yè)大學(xué)，2011.CHEN Jianping.Research on the Multi-Robot System Cooperation Based on Foraging and Pursuit Game［D］.Guangzhou：Guangdong University of Technology，2011.

［10］rk，Sava&#，Kuzucuo&#，Lu A E.Optimal bid valuation using path finding for multi-robot task allocation［J］.Journal of Intelligent Manufacturing，2015，26（5）：1049-1062.

［11］Michail O，Spirakis P G.Traveling salesman problems in temporal graphs☆，☆☆［J］.Theoretical Computer Science，2016，634：1-23.

［12］Yue Y.An Efficient Implementation of Shortest Path Algorithm Based on Dijkstra Algorithm［J］.Journal of Wuhan Technical University of Surveying&Mapping，1999.

［13］Wei C，Hindriks K V，Jonker C M.Dynamic task allocation for multi-robot search and retrieval tasks［J］.Applied Intelligence，2016：1-19.

［14］金涬，石純一.拍賣(mài)方法引入多Agent系統(tǒng)［J］.計(jì)算機(jī)科學(xué)，2003，30（8）：104-107.JIN Xing，SHI Chunyi.The Auction and its Application in Multi-Agent System［J］.Computer Science，2003，30（8）：104-107.

［15］呂洪莉.面向多目標(biāo)優(yōu)化的多AUVs群體協(xié)同任務(wù)分配［D］.哈爾濱：哈爾濱工程大學(xué)，2012.LV Hongli.Task Allocation of Multi-AUV System Based on Multi-objective Optimization［D］.Harbin：Harbin Engineering University，2012.

［16］崔一鳴.多機(jī)器人協(xié)作的關(guān)鍵技術(shù)研究［D］.南京：南京理工大學(xué)，2008.CUI Yiming.Key Technology of multi-robot collaboration［D］.Nanjing：Nanjing University of Science and Technology，2008.

Unknown Environment Exploration of Multi-robot Based on Market

ZHAO Huichao SHI Chaoxia
（School of Computer Science and Engineering，Nanjing University of Science&Technology，Nanjing 210094）

Multi-task assignment is a key problem in multi-robot's collaborative exploration of unknown environment.Traditional market methods sacrifice the overall optimization because of the pursuit of single-robot's optimization.However，the method basing on the partition exploration can achieve the overall optimization，which is not suitable for exploration in the unknown environment.This paper put forward a market approach based on improved the traditional market approach，this method took the number of rejection pheromones in the path through the robot as the condition of winning the auction.The method improves the efficiency of the multi-robot system to complete the environment exploration.What's more，the effectiveness of the algorithm has been verified by experiments.

multi-robot，cooperative exploration，market-based，rejection of pheromone

TP242.6

10.3969/j.issn.1672-9722.2017.11.001

Class Number TP242.6

2017年5月10日，

2017年6月17日

國(guó)家自然科學(xué)基金項(xiàng)目“基于XX環(huán)境搜索面上研究”（編號(hào)：61371040）資助。

趙慧潮，男，碩士研究生，研究方向：多機(jī)器人協(xié)同和未知環(huán)境探索。石朝俠，男，博士，副教授，研究方向：

移動(dòng)機(jī)器人自主導(dǎo)航、多機(jī)器人協(xié)同。