趙慧潮 石朝俠

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

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

趙慧潮 石朝俠

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

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

多機器人；協(xié)作探索；市場法；排斥素

1 引言

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

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

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

2 市場法

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

1）機器人將自己探測到的任務(wù)點以廣播的方式發(fā)布拍賣信息，該機器人被稱為拍賣機器人。拍賣信息主要是任務(wù)點的位置信息。收到信息的機器人判斷自己是否可以到達任務(wù)點，如果可以到達就參與投標(biāo)。參與投標(biāo)的機器人被稱為競標(biāo)機器人。

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

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

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

3 基于排斥素的市場法

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

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

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

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

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

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

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

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

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

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

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

3.2 排斥素的計算

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

其中：節(jié)點nodeit

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

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

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

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

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

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

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

3.3 任務(wù)分配過程

3.3.1 任務(wù)點分配

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

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

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

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

2）投標(biāo)計算

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

圖2 投標(biāo)計算

3）合同授權(quán)

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

圖3 合同授權(quán)

4）合同建立

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

圖4 合同建立

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

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

3.3.2 任務(wù)點再分配

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

4 實驗對比

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

圖5 實驗環(huán)境

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

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

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

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

從圖7可知，在機器人數(shù)量相同的情況下，本文提出的算法在降低地圖重復(fù)率方面有顯著效果?；谂懦馑厥袌龇▽⑻剿魑粗h(huán)境的重復(fù)率降低了23%。同時可以看到無論采用何種算法隨著機器人數(shù)量的增加，雖然地圖重復(fù)率存在偶然的輕微下降，但是總體都是呈上升趨勢。

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

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

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

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

5 結(jié)語

根據(jù)仿真實驗結(jié)果分析可知，在機器人數(shù)量相同的情況下本文提出的算法可以在更短時間和更低重復(fù)率的情況下完成未知環(huán)境的探索。但是該算法也存在一些不足的地方。諸如無法有效降低多機器人系統(tǒng)的探索路徑長度，無法解決未知環(huán)境探索效率隨著機器人的數(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］王姝莉.基于多機器人協(xié)調(diào)的搜集與圍捕問題的研究［D］.北京：中國科學(xué)院自動化研究所，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)東，席裕庚.多機器人協(xié)作探索的改進市場法［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］陳建平.多機器人系統(tǒng)中的機器人合作問題研究［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］金涬，石純一.拍賣方法引入多Agent系統(tǒng)［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］崔一鳴.多機器人協(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日

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

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

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