多機(jī)器人系統(tǒng)的任務(wù)分配技術(shù)29張幻燈片

1、多機(jī)器人系統(tǒng)的任務(wù)分配技術(shù)Task Allocation of Multi-robot System許守培13721131論文結(jié)構(gòu)一、多機(jī)器人系統(tǒng)的概述（引言）二、多機(jī)器人系統(tǒng)任務(wù)分配問(wèn)題的概述（包括分類(lèi)）三、多機(jī)器人系統(tǒng)任務(wù)分配方法四、多機(jī)器人任務(wù)分配在機(jī)器人足球賽中的應(yīng)用現(xiàn)狀五、關(guān)于多機(jī)器人系統(tǒng)任務(wù)分配的發(fā)展與建議總結(jié)一、多機(jī)器人系統(tǒng)的概述 1. 多機(jī)器人系統(tǒng)簡(jiǎn)介 多機(jī)器人系統(tǒng)是指多個(gè)機(jī)器人組成的系統(tǒng)。面對(duì)復(fù)雜的環(huán)境與任務(wù)，與單機(jī)器人相比，多機(jī)器人系統(tǒng)具有許多優(yōu)越性：完成任務(wù)效率高、完成任務(wù)復(fù)雜程度高、信息傳遞速度快、定位信息準(zhǔn)確、系統(tǒng)魯棒性好以及優(yōu)化解決問(wèn)題方案。2.多機(jī)器人系統(tǒng)的結(jié)構(gòu)

2、1.從控制角度和信息交互方式上看，多機(jī)器人組織結(jié)構(gòu)可分為集中式、分布式和混合式三種。 .集中式 集中式控制結(jié)構(gòu)通常由主機(jī)器人和子機(jī)器人構(gòu)成，如圖1所示。. 分布式 分布式?jīng)]有主控單元，系統(tǒng)中機(jī)器人個(gè)體間地位平等，自主選擇行為以完成給定任務(wù)，這種結(jié)構(gòu)整體分散、局部集中。圖2所示。圖1圖2 .混合式 混合方式是將集中與分布控制相結(jié)合的控制方式它在一定程度上結(jié)合集中式結(jié)構(gòu)與分散式結(jié)構(gòu)的優(yōu)點(diǎn)，可克服分布式結(jié)構(gòu)中個(gè)體高度自治所造成的性能低下和集中式結(jié)構(gòu)缺乏控制靈活性等問(wèn)題。具有很好的魯棒性和適應(yīng)性，圖3 2. 多機(jī)器人系統(tǒng)領(lǐng)域的主要研究?jī)?nèi)容及亟待解決的問(wèn)題1.任務(wù)分配、動(dòng)作選擇、協(xié)調(diào)及控制結(jié)構(gòu)；2.物體

3、運(yùn)輸、操作及構(gòu)建；3.通信及感知；4.運(yùn)動(dòng)協(xié)調(diào)；5.學(xué)習(xí)；6.可重構(gòu)及可建模機(jī)器人；7.協(xié)作定位及地圖構(gòu)建。二、多機(jī)器人系統(tǒng)任務(wù)分配問(wèn)題的概述 早期研究集中于對(duì)多機(jī)器人系統(tǒng)基礎(chǔ)能力要求，即能夠順利的完成任務(wù); 現(xiàn)今研究重心為提高多機(jī)器人系統(tǒng)性能，即在保證完成任務(wù)的基礎(chǔ)上，增強(qiáng)機(jī)器人之間的合作，提高系統(tǒng)工作效率。 多機(jī)器人任務(wù)分配MRTA ( Multi-Robot task allocation)是多機(jī)器人系統(tǒng)應(yīng)用的基礎(chǔ)，能夠充分體現(xiàn)系統(tǒng)決策層組織形式與運(yùn)行機(jī)制。一方面，任務(wù)分配的好壞直接影響整個(gè)系統(tǒng)的探測(cè)效率，并且直接關(guān)系到系統(tǒng)中各個(gè)機(jī)器人能否最發(fā)揮其自身能力；另一方面，通過(guò)機(jī)器人之間的協(xié)調(diào)

4、與協(xié)作共同完成復(fù)雜任務(wù)已經(jīng)成為眾多研究者關(guān)注的問(wèn)題。 按照觀察角度選取的不同，多機(jī)器人的任務(wù)分配可以分成很多類(lèi)別。1. 多機(jī)器人任務(wù)分配的分類(lèi)通訊方式顯式通信隱式通信任務(wù)的動(dòng)態(tài)性靜態(tài)任務(wù)分配動(dòng)態(tài)任務(wù)分配任務(wù)完成復(fù)雜度簡(jiǎn)單任務(wù)分配復(fù)雜任務(wù)分配機(jī)器人功能結(jié)構(gòu)同構(gòu)系統(tǒng)任務(wù)分配異構(gòu)系統(tǒng)任務(wù)分配合作的動(dòng)機(jī)涌現(xiàn)式任務(wù)分配：如自然中螞蟻、蜜蜂意圖合作式任務(wù)分配2. 多機(jī)器人系統(tǒng)中的兩種任務(wù)和兩種機(jī)器人任務(wù)：機(jī)器人多機(jī)器人任務(wù)(MRT)多機(jī)器人任務(wù)(SRT)單任務(wù)機(jī)器人(STR)多任務(wù)機(jī)器人(MTR) 多機(jī)器人任務(wù)分配問(wèn)題是指各機(jī)器人分布式 地自主執(zhí)行任務(wù),由于任務(wù)類(lèi)型不同,各機(jī)器人的能力不同,當(dāng)發(fā) 現(xiàn)新 的

5、任務(wù)時(shí),各機(jī)器人能夠通過(guò)根據(jù)當(dāng)前態(tài)勢(shì)快速、合理地實(shí)現(xiàn)任務(wù)的動(dòng)態(tài)分配。3.任務(wù)分配問(wèn)題的形式化描述多機(jī)器人系統(tǒng)任務(wù)分配的目標(biāo)：（1）效能最大。 將任務(wù)分配給多機(jī)器人系統(tǒng)內(nèi)的各個(gè)機(jī)器人，既滿足 ，并保證每個(gè)任務(wù)只分配給一個(gè)機(jī)器人，即 ，則 。如果待分配的任務(wù)數(shù)量超過(guò)多機(jī)器人協(xié)作能夠執(zhí)行的最大任務(wù)數(shù)量，則按照能使多機(jī)器人協(xié)作完成任務(wù)后整體的效能 最大的原則對(duì)任務(wù)進(jìn)行選擇，以提高系統(tǒng)的整體效能。 （2）使系統(tǒng)的整體執(zhí)行能力提高，使任務(wù)盡可能均勻地分布在各個(gè)機(jī)器人上，各機(jī)器人的任務(wù)負(fù)載趨于平衡。設(shè)機(jī)器人Ri的任務(wù)負(fù)載為 ，系統(tǒng)內(nèi)機(jī)器人的平均任務(wù)負(fù)載為 則要保證 最小、其中，任務(wù)負(fù)載 為Ri當(dāng)前的任務(wù)數(shù)量

6、與其能夠執(zhí)行的任務(wù)數(shù)量的比值。2.4 多機(jī)器人任務(wù)分配的性能指標(biāo)1.魯棒性2.快速性3.最優(yōu)性4.學(xué)習(xí)能力三、多機(jī)器人系統(tǒng)任務(wù)分配方法 多機(jī)器人任務(wù)分配問(wèn)題MRTA(Multi-Robot Task Allocation)是多機(jī)器人系統(tǒng)研究的一個(gè)基礎(chǔ)問(wèn)題,體現(xiàn)了系統(tǒng)高層組織形式與運(yùn)行機(jī)制,是多機(jī)器人系統(tǒng)實(shí)現(xiàn)目標(biāo)的基礎(chǔ)。隨著系統(tǒng)中機(jī)器人數(shù)目和任務(wù)難度的增加,任務(wù)分配問(wèn)題就顯得越來(lái)越重要。1. 基于市場(chǎng)機(jī)制的任務(wù)分配市場(chǎng)法定義為： 多機(jī)器人系統(tǒng)采用全分布式方法，只有目標(biāo)信息由機(jī)器人共享，而機(jī)器人間的協(xié)作通過(guò)投標(biāo)來(lái)體現(xiàn)。機(jī)器人根據(jù)本地地圖計(jì)算得到目標(biāo)點(diǎn)的花費(fèi)，并將其作為投標(biāo)價(jià)格。1.1單任務(wù)拍賣(mài) 單

7、個(gè)任務(wù)分配時(shí)每次只能對(duì)單個(gè)任務(wù)進(jìn)行投標(biāo), 重復(fù)對(duì)每個(gè)任務(wù)進(jìn)行拍賣(mài), 直到所有任務(wù)分配完。該方法不保證求得最優(yōu)解, 但其計(jì)算量和通信量比組合任務(wù)分配小, 實(shí)現(xiàn)也比較簡(jiǎn)單, 目前應(yīng)用比較多。 研究表明尋找單任務(wù)最優(yōu)分配為 NP 難題, 并提出 PRIMALLOCATION 算法, 該算法與傳統(tǒng)的單任務(wù)拍賣(mài)算法類(lèi)似, 但機(jī)器人以它已擁有的目標(biāo)與當(dāng)前投標(biāo)任務(wù)之間的最小距離為投標(biāo)價(jià)格。1.2 組合拍賣(mài) 當(dāng)任務(wù)之間存在協(xié)同關(guān)系時(shí), 單任務(wù)拍賣(mài)可能導(dǎo)致極不理想的分配方案, 組合任務(wù)拍賣(mài)通過(guò)允許投標(biāo)人對(duì)任務(wù)組合進(jìn)行投標(biāo), 試圖改進(jìn)單任務(wù)拍賣(mài), 每個(gè)機(jī)器人權(quán)衡接受任意多個(gè)任務(wù)子集的價(jià)格, 這有利于找到最優(yōu)分配方

8、案。1.3. 合同網(wǎng)任務(wù)分配方法 合同網(wǎng)是一種面向談判的任務(wù)分配和協(xié)作機(jī)制，通過(guò)模仿經(jīng)濟(jì)行為中“招標(biāo)-投標(biāo)-中標(biāo)”機(jī)制實(shí)現(xiàn)任務(wù)的委派和遷移，現(xiàn)已廣泛應(yīng)用到編隊(duì)協(xié)同作戰(zhàn)、衛(wèi)星和多UCAV等領(lǐng)域。 基于合同網(wǎng)的多機(jī)器人系統(tǒng)任務(wù)分配過(guò)程的協(xié)商算法如下： Step1：招標(biāo)。當(dāng)某個(gè)機(jī)器人發(fā)現(xiàn)新的任務(wù)時(shí)，作為招標(biāo)者，向其他機(jī)器人宣布任務(wù)。 Step2：投標(biāo)。收到拍賣(mài)信息后，機(jī)器人根據(jù)自己當(dāng)前的能力和狀態(tài)計(jì)算買(mǎi)入任務(wù)后自身效能并決定是否發(fā)出買(mǎi)賣(mài)合同標(biāo)書(shū)。 Step3：通知中標(biāo)和落標(biāo)。當(dāng)收到標(biāo)書(shū)后，機(jī)器人對(duì)標(biāo)書(shū)進(jìn)行處理，誰(shuí)投價(jià)高，就將任務(wù)轉(zhuǎn)交給誰(shuí)執(zhí)行。 Step4：Ri收到中標(biāo)信息后，任務(wù)集被更新為 ，并執(zhí)行

9、任務(wù)。2.基于群體智能的任務(wù)分配 基于群體智能的方法是受到社會(huì)性昆蟲(chóng)行為的啟發(fā),通過(guò)對(duì)社會(huì)性昆蟲(chóng)覓食任務(wù)等的模擬產(chǎn)生的任務(wù)分配方法。由于群體中相互合作的個(gè)體是分布的,不會(huì)由于某一個(gè)或者某幾個(gè)個(gè)體的故障而影響整個(gè)問(wèn)題的求解,而且個(gè)體之間通過(guò)非直接通信進(jìn)行合作,使系統(tǒng)具有更好的可擴(kuò)充性。因此群體智能方法非常適合于分布式多機(jī)器人系統(tǒng),而且也有越來(lái)越多的研究者將群體智能方法應(yīng)用到多機(jī)器人任務(wù)分配中。 主要方法包括閾值法和蟻群方法，系統(tǒng)具有魯棒性實(shí)時(shí)性及高效性，適用于分布式MRTA; 在MRTA的研究中，群體智能方法是解決MRTA的主要發(fā)展方向。2.1 閾值法 基于閾值的任務(wù)分配是一種用涌現(xiàn)式任務(wù)分配,

10、 該方法中每個(gè)機(jī)器人對(duì)每個(gè)任務(wù)都有一個(gè)閾值, 用激素反映任務(wù)的緊迫性和重要性, 機(jī)器人不斷感知任務(wù)發(fā)出的激素。當(dāng)感知的激素值超過(guò)對(duì)應(yīng)的閾值, 機(jī)器人執(zhí)行該任務(wù), 而當(dāng)感知的激素值降低到低于閾值時(shí)( 如任務(wù)完成) , 機(jī)器人停止執(zhí)行。 基于行為的多機(jī)器人分布式合作結(jié)構(gòu)ALLICANCE以及具有相應(yīng)參數(shù)學(xué)習(xí)能力的系統(tǒng) L- ALLIANCE, 采用基于閾值的任務(wù)分配, 定義了兩個(gè)動(dòng)機(jī)模型: 焦躁和默許, 用這兩個(gè)動(dòng)機(jī)作為開(kāi)關(guān)激活模型選擇相應(yīng)的行為進(jìn)行任務(wù)的動(dòng)態(tài)分配。 A.Gage 提出一種依據(jù)情緒的雇傭方法來(lái)解決多機(jī)器人的任務(wù)分配問(wèn)題, 每個(gè)機(jī)器人都有一定的情緒值, 用來(lái)表征其對(duì)任務(wù)的熱情程度。2

11、.2 蟻群算法 通過(guò)研究發(fā)現(xiàn)，單個(gè)螞蟻在覓食的過(guò)程中會(huì)分泌一種啟發(fā)性的信息素（Pheromone）來(lái)和其他螞蟻傳遞信息。螞蟻通過(guò)不同路徑上的信息素濃度來(lái)選擇路徑，濃度越大的路徑被選擇的幾率也就越大。由于信息素會(huì)隨著時(shí)間的推移而揮發(fā)，因而較短的路徑上信息素濃度較大，使得這種路徑更具有吸引力，從而吸引更多的螞蟻選擇該路徑，而使這又得該路徑上信息素的濃度更大。蟻群的這種行為形成了一種正反饋機(jī)制，使得最優(yōu)的覓食路徑被越來(lái)越多的螞蟻選擇。 基于行為的任務(wù)分配3. 其他任務(wù)分配方法基于情感情感招募方法的任務(wù)分配Lynne E. Parker. ALLIANCE: An Architecture for Fault Tolerant Multirobot CooperationFang Tang and Lynne E. Parker. Distributed Multi-Robot Coalitions through ASyMTRe-DGAGEA , MURP HY R , VAIAVANISKP, et al. Affective task allocation for distributed multi-robot teams四、多機(jī)器人任務(wù)分配技術(shù)在足球機(jī)器人中的應(yīng)用 在