《機(jī)器人足球第四章多機(jī)器人規(guī)劃.ppt》由會員分享,可在線閱讀,更多相關(guān)《機(jī)器人足球第四章多機(jī)器人規(guī)劃.ppt(36頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、第四章 多機(jī)器人規(guī)劃,,2,內(nèi) 容 提 綱,為什么需要多個機(jī)器人完成任務(wù)? 多機(jī)器人系統(tǒng)的分類 多機(jī)器人系統(tǒng)的路徑規(guī)劃思想,3,1. 多機(jī)器人系統(tǒng)的必要性,通過群體行為完成某種任務(wù)在自然界中無處不在。 如,蜂群,蟻群,菌群 雖然有的任務(wù)中只需要單個機(jī)器人,但是有的任務(wù)需要多個機(jī)器人。比如,探索一個未知的星球,推動物體,清理有毒垃圾。,4,,多機(jī)器人系統(tǒng)相對單機(jī)器人系統(tǒng)的優(yōu)勢 在某些情況下,使用多個小的、簡單的機(jī)器人比使用一個大的、復(fù)雜的機(jī)器人完成任務(wù)具有更高的效率 設(shè)計者可以選擇一些折衷的設(shè)計方案 更加經(jīng)濟(jì),可擴(kuò)展,具有更好的抗失敗能力 簡單機(jī)器人比復(fù)雜機(jī)器人的造價低 多機(jī)器人系統(tǒng)可包含不同數(shù)
2、量的簡單機(jī)器人 多個簡單機(jī)器人執(zhí)行任務(wù)失敗的概率比單個復(fù)雜機(jī)器人執(zhí)行任務(wù)失敗的概率低,5,,群體機(jī)器人系統(tǒng)的兩個極端 一個群體可以由完全自治的機(jī)器人組成,它們兩兩之間可以通信。 另一個群體由受遠(yuǎn)程控制的多個附屬物組成,而整個群體可以看成是一個具有分布式執(zhí)行器的單機(jī)器人系統(tǒng)。,6,,多機(jī)器人系統(tǒng)稱為群體機(jī)器人系統(tǒng)(Collective of Robots),或者叫蜂群(Swarm),表示為ri 機(jī)器人成員在功能上不存在依賴性,也不存在持久的物理連接 由單個機(jī)器人構(gòu)成的系統(tǒng)為單機(jī)器人系統(tǒng),表示為R,7,2.從多Agent角度對任務(wù)的分類,2.1 本質(zhì)上需要多Agent才能完成的任務(wù) 兩把距離遙遠(yuǎn)的
3、鑰匙,必須被同時旋轉(zhuǎn)才能打開某一扇門(需要多個Agent) 兩把距離較近的鑰匙,必須被同時旋轉(zhuǎn)才能打開某一扇門(需要一個Agent) 兩把距離遙遠(yuǎn)的鑰匙,必須在一段時間內(nèi)均被旋轉(zhuǎn)才能打開某一扇門(需要一個飛速的Agent),8,,注:兩個Agent只有通過通信才能完成以上任務(wù) 執(zhí)行任務(wù)的初始時,通過同步時鐘,然后約定在某個時刻同時旋轉(zhuǎn)鑰匙 在一個Agent旋轉(zhuǎn)鑰匙的同時,發(fā)信號給另一個Agent,9,,2.2 傳統(tǒng)上,由多個Agent完成的任務(wù) 現(xiàn)代運(yùn)輸、工業(yè)生產(chǎn)(流水線)、農(nóng)業(yè)、漁業(yè) 這類任務(wù)的特點: 執(zhí)行任務(wù)之初,Agent相互通信用于分配任務(wù) 每個成員單獨(dú)執(zhí)行任務(wù),忽略其他成員的存在 這
4、類系統(tǒng)的缺點 群體成員未感知到的任務(wù)不會被完成,10,,2.3 本質(zhì)上由單Agent完成的任務(wù) 在單個地點上的單任務(wù) 這些任務(wù)的解決不宜采用多Agent群體,11,,2.4 用多Agent系統(tǒng)解決的效果可能比單Agent更好的任務(wù) 例1:在一個有限區(qū)域?qū)ふ乙粋€特定物體的任務(wù),群體ri比單個機(jī)器人R完成任務(wù)的速度可能更快 但是,ri完成任務(wù)的速度不一定比R更快。取決于兩個因素:群體成員之間的通信和單個成員與R的能力的接近程度。,12,,如果群體成員不通信,可能發(fā)生什么情況? 如果群體成員的能力比R的能力弱,可能發(fā)生什么情況? 例2:排雷、清除航空母艦甲板上的異物。使用群體ri比單個機(jī)器人R,更加
5、可靠 成員很容易被損傷 單個成員的失敗不會導(dǎo)致任務(wù)執(zhí)行的失敗,而R的失敗必然導(dǎo)致任務(wù)執(zhí)行的失敗,13,,在2.4這類任務(wù)中,群體成員之間的通信對群體完成任務(wù)的性能具有重要的影響 通信的方式有兩種:直接的、間接的 直接通信:成員帶有一個專門的通信管道 間接通信:一個成員使用感知器觀測其他成員的行為 問題:成員間通信的量越大,則系統(tǒng)的性能就越高么?,14,3. 機(jī)器人群體系統(tǒng)的分類角度,Dudek等人提出了以上7個角度,用于分類多Agent系統(tǒng)。,15,3.1 群體規(guī)模(Collective Size),SIZE-ALONE: 單機(jī)器人系統(tǒng) SIZE-PAIR:雙機(jī)器人系統(tǒng) SIZE-LIM:多機(jī)
6、器人系統(tǒng)。成員數(shù)目n相對于任務(wù)規(guī)模來看比較小。 SIZE-INF:規(guī)模無限的機(jī)器人系統(tǒng)。 問題: SIZE-LIM型群體和SIZE-INF型群體執(zhí)行搜索任務(wù)時,哪個完成任務(wù)的可能性更大?我們總能使用SIZE-INF型群體么?,16,3.2 通信范圍(Communication Range),COM-NONE:機(jī)器人成員不能直接與其他機(jī)器人通信,智能通過感知器觀測到對方的存在、不存在和行為。成員之間也不可以互發(fā)信號 COM-NEAR:機(jī)器人成員只能與其附近的機(jī)器人通信(距離可以物理空間上的距離也可以是拓?fù)淇臻g上的距離) 拓?fù)淇臻g距離的例子:軍隊中的士兵由樹形的結(jié)構(gòu)組織 COM-INF:一個機(jī)器人
7、成員可以與其它任意機(jī)器人通信,17,3.3 通信的拓?fù)浣Y(jié)構(gòu)(Communication Topology),廣播式通信 按地址通信 樹形通信 網(wǎng)狀通信,18,3.4 通信帶寬(Communication Bandwidth),通信影響群體的性能:如果成員具有專用的通信通道,則處理通信的時間很短;如果成員在通信時不能進(jìn)行其他動作,那么通信代價就高。 BAND-INF:在這種群體中,通信是無代價的。 BAND-MOTION:通信代價與移動成員的代價成正比。 例如:蜂群中,蜜蜂通過跳八字舞進(jìn)行通信。傳遞的信息與跳舞的運(yùn)動代價成正比,19,,BAND-LOW:通信代價高。遠(yuǎn)遠(yuǎn)高出將一個機(jī)器人叢一個位置
8、移動到另一個位置的代價 BAND-ZERO:無通信,任何成員無法感知到其他成員,20,3.5 群體的可重配置程度(Collective Recongurability),指 群體在空間上重新組織的速度。 蜂群中的成員可根據(jù)其他成員的空間位置快速改變自身的空間位置。以固定步伐前進(jìn)的部隊和高速公路上的汽車重新配置空間距離的速度就慢。,21,3.5 群體的可重配置程度(Collective Recongurability),ARR-STATIC:靜態(tài)組織。群體的拓?fù)浣Y(jié)構(gòu)式固定的 ARR-COM:群體可以通過通信進(jìn)行重組 ARR-DYN:動態(tài)組織。群體中成員的拓?fù)潢P(guān)系可以任意改變,22,3.6 成員的
9、處理能力(Processing ability of each collective unit),群體中的每個成員具有不同的計算模型。有的成員的計算模型可能比圖靈機(jī)弱一些,比如,有窮狀態(tài)自動機(jī)。但是,即使單個成員的計算模型簡單,整個群體的計算能力可能是很強(qiáng)的。,23,3.6 成員的處理能力(Processing ability of each collective unit),PROC-SUM:成員的計算模型是一個非線性求和單元。例如,神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元。 PROC-FSA:成員的計算模型是一個有窮狀態(tài)自動機(jī)。 PROC-PDA:成員的計算模型是一個下推自動機(jī) PROC-TME:成員的計算模型
10、是一個圖靈機(jī),24,3.7 群體的構(gòu)成,群體成員可能在物理構(gòu)成上是異構(gòu)的。即使使用相同的物理部件,也可能在軟件上是異構(gòu)的。 CMP-IDENT:群體的成員均具有相同的硬件和軟件 CMP-HET:群體成員具有不同的硬件,導(dǎo)致軟件也不相同,25,3.8 群體系統(tǒng)的案例,研究者成功設(shè)計了多個具有相對優(yōu)勢的群體機(jī)器人系統(tǒng) 案例1:成員具有有窮狀態(tài)自動機(jī)的計算模型,而群體的計算能力與圖靈機(jī)接近 案例2:對于搜索任務(wù),群體系統(tǒng)比單獨(dú)一個移動的、能做標(biāo)記的機(jī)器人更高效,26,,案例3: 群體機(jī)器人中,如果每個成員都能感知到對方,可以在一個存在少量路標(biāo)的環(huán)境中進(jìn)行自我定位,而單個機(jī)器人不能。 案例4: 在無路
11、標(biāo)環(huán)境中,群體機(jī)器人可以通過相互感知實現(xiàn)自我定位。,27,4. 多機(jī)器人規(guī)劃的基本思想,多Agent系統(tǒng)(Multi-Agent System, MAS):在同一環(huán)境中,存在協(xié)作關(guān)系的多個Agent組成的系統(tǒng)。 特點:控制多Agent系統(tǒng)的路徑規(guī)劃系統(tǒng)的復(fù)雜度隨著移動Agent的數(shù)目呈指數(shù)級別增長,28,,單Agent路徑規(guī)劃方法不能用于求解多Agent規(guī)劃問題,原因包括: 成員之間要避免碰撞 成員之間要避免死鎖 多Agent規(guī)劃系統(tǒng)的難點包括: 計算代價 信息交換策略 通信代價,29,4.1 對障礙物的分類,Usually other agents are modelled as unsch
12、eduled, non-negotiable, mobile obstacles in MASPPs. Category of Obstacles from Arai et. al. (89),30,4.2 多Agent系統(tǒng)的規(guī)劃方法,集中式(Centralised Approaches) 分散式(Decoupled Approaches) 組合式(Combined Techniques),31,4.2.1 多Agent系統(tǒng)的集中式路徑規(guī)劃方法,使用一個方法對所有的Agent的路徑進(jìn)行規(guī)劃 優(yōu)點: 可以找到最優(yōu)解 使用系統(tǒng)的全部信息 缺點: 計算復(fù)雜度隨著Agent的數(shù)目呈指數(shù)級別增長 對一個
13、Agent的規(guī)劃失敗,則無法繼續(xù)對其他Agent進(jìn)行規(guī)劃,32,4.2.2 多Agent系統(tǒng)的分散式路徑規(guī)劃方法,該方法首先為每個機(jī)器人Ri計算一條相應(yīng)的規(guī)劃解Plani,然后處理這些解之間的路徑?jīng)_突,如果解決沖突成功則將規(guī)劃解作為每個機(jī)器人的路徑規(guī)劃解,否則返回“無解”。 優(yōu)點: 一個Agent的路徑的計算時間和相鄰Agent的數(shù)目成正比 具有健壯性 缺點: 不完備:為什么?例:多Agent系統(tǒng)內(nèi)有兩個機(jī)器人R1和R2,對于它們的目標(biāo),R1存在兩個規(guī)劃解Plan11,Plan12,R2存在兩個規(guī)劃解Plan21,Plan22,并且Plan11和Plan21之間的沖突是無法解決的。那么,如果分
14、散式規(guī)劃方法首先為R1計算出Plan11、為R2計算出Plan21,由于Plan11和Plan21的沖突無法解決,分散式規(guī)劃方法將返回“無解”。然而,實際上,Plan11和Plan22是該多Agent規(guī)劃問題的一個解,未被分散式方法計算出,因此說,分散式方法是不完備的。,33,4.2.3 多Agent系統(tǒng)的組合式路徑規(guī)劃方法,Use cumulative information for global path planning, use local information for local planning(使用累積的信息對單個Agent的全局路徑進(jìn)行規(guī)劃,使用本地信息對該Agent局部的路徑進(jìn)行規(guī)劃) “Think Global Act Local”,34,,Thinking Globally 對于一個Agent,計算從其從當(dāng)前位置到目的位置的完整路徑 使用A*算法完成,35,,Act Locally: 為了避開障礙物,采用反應(yīng)式的規(guī)劃方法,基于局部信息進(jìn)行路徑規(guī)劃 優(yōu)點是: 不需要環(huán)境的全部信息; 制定決策的過程快速,36,,反應(yīng)式避障規(guī)劃的思想 根據(jù)成員的優(yōu)先級進(jìn)行反應(yīng)(Priority assignment) 根據(jù)規(guī)則進(jìn)行反應(yīng)(Rule-Based methods) 例如:出于左側(cè)的Agent首先運(yùn)動,