機(jī)器人足球第四章多機(jī)器人規(guī)劃.ppt

《機(jī)器人足球第四章多機(jī)器人規(guī)劃.ppt》由會員分享，可在線閱讀，更多相關(guān)《機(jī)器人足球第四章多機(jī)器人規(guī)劃.ppt（36頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第四章 多機(jī)器人規(guī)劃,,2,內(nèi) 容 提 綱,為什么需要多個(gè)機(jī)器人完成任務(wù)？ 多機(jī)器人系統(tǒng)的分類 多機(jī)器人系統(tǒng)的路徑規(guī)劃思想,3,1. 多機(jī)器人系統(tǒng)的必要性,通過群體行為完成某種任務(wù)在自然界中無處不在。 如，蜂群，蟻群，菌群 雖然有的任務(wù)中只需要單個(gè)機(jī)器人，但是有的任務(wù)需要多個(gè)機(jī)器人。比如，探索一個(gè)未知的星球，推動物體，清理有毒垃圾。,4,,多機(jī)器人系統(tǒng)相對單機(jī)器人系統(tǒng)的優(yōu)勢 在某些情況下，使用多個(gè)小的、簡單的機(jī)器人比使用一個(gè)大的、復(fù)雜的機(jī)器人完成任務(wù)具有更高的效率 設(shè)計(jì)者可以選擇一些折衷的設(shè)計(jì)方案 更加經(jīng)濟(jì)，可擴(kuò)展，具有更好的抗失敗能力 簡單機(jī)器人比復(fù)雜機(jī)器人的造價(jià)低 多機(jī)器人系統(tǒng)可包含不同數(shù)

2、量的簡單機(jī)器人 多個(gè)簡單機(jī)器人執(zhí)行任務(wù)失敗的概率比單個(gè)復(fù)雜機(jī)器人執(zhí)行任務(wù)失敗的概率低,5,,群體機(jī)器人系統(tǒng)的兩個(gè)極端 一個(gè)群體可以由完全自治的機(jī)器人組成，它們兩兩之間可以通信。 另一個(gè)群體由受遠(yuǎn)程控制的多個(gè)附屬物組成，而整個(gè)群體可以看成是一個(gè)具有分布式執(zhí)行器的單機(jī)器人系統(tǒng)。,6,,多機(jī)器人系統(tǒng)稱為群體機(jī)器人系統(tǒng)（Collective of Robots），或者叫蜂群（Swarm），表示為ri 機(jī)器人成員在功能上不存在依賴性，也不存在持久的物理連接 由單個(gè)機(jī)器人構(gòu)成的系統(tǒng)為單機(jī)器人系統(tǒng)，表示為R,7,2.從多Agent角度對任務(wù)的分類,2.1 本質(zhì)上需要多Agent才能完成的任務(wù) 兩把距離遙遠(yuǎn)的

3、鑰匙，必須被同時(shí)旋轉(zhuǎn)才能打開某一扇門（需要多個(gè)Agent） 兩把距離較近的鑰匙，必須被同時(shí)旋轉(zhuǎn)才能打開某一扇門（需要一個(gè)Agent） 兩把距離遙遠(yuǎn)的鑰匙，必須在一段時(shí)間內(nèi)均被旋轉(zhuǎn)才能打開某一扇門（需要一個(gè)飛速的Agent）,8,,注：兩個(gè)Agent只有通過通信才能完成以上任務(wù) 執(zhí)行任務(wù)的初始時(shí)，通過同步時(shí)鐘，然后約定在某個(gè)時(shí)刻同時(shí)旋轉(zhuǎn)鑰匙 在一個(gè)Agent旋轉(zhuǎn)鑰匙的同時(shí)，發(fā)信號給另一個(gè)Agent,9,,2.2 傳統(tǒng)上，由多個(gè)Agent完成的任務(wù) 現(xiàn)代運(yùn)輸、工業(yè)生產(chǎn)（流水線）、農(nóng)業(yè)、漁業(yè) 這類任務(wù)的特點(diǎn)： 執(zhí)行任務(wù)之初，Agent相互通信用于分配任務(wù) 每個(gè)成員單獨(dú)執(zhí)行任務(wù)，忽略其他成員的存在 這

4、類系統(tǒng)的缺點(diǎn) 群體成員未感知到的任務(wù)不會被完成,10,,2.3 本質(zhì)上由單Agent完成的任務(wù) 在單個(gè)地點(diǎn)上的單任務(wù) 這些任務(wù)的解決不宜采用多Agent群體,11,,2.4 用多Agent系統(tǒng)解決的效果可能比單Agent更好的任務(wù) 例1：在一個(gè)有限區(qū)域?qū)ふ乙粋€(gè)特定物體的任務(wù)，群體ri比單個(gè)機(jī)器人R完成任務(wù)的速度可能更快 但是，ri完成任務(wù)的速度不一定比R更快。取決于兩個(gè)因素：群體成員之間的通信和單個(gè)成員與R的能力的接近程度。,12,,如果群體成員不通信，可能發(fā)生什么情況？ 如果群體成員的能力比R的能力弱，可能發(fā)生什么情況？ 例2：排雷、清除航空母艦甲板上的異物。使用群體ri比單個(gè)機(jī)器人R，更加

5、可靠 成員很容易被損傷 單個(gè)成員的失敗不會導(dǎo)致任務(wù)執(zhí)行的失敗，而R的失敗必然導(dǎo)致任務(wù)執(zhí)行的失敗,13,,在2.4這類任務(wù)中，群體成員之間的通信對群體完成任務(wù)的性能具有重要的影響 通信的方式有兩種：直接的、間接的 直接通信：成員帶有一個(gè)專門的通信管道 間接通信：一個(gè)成員使用感知器觀測其他成員的行為 問題：成員間通信的量越大，則系統(tǒng)的性能就越高么？,14,3. 機(jī)器人群體系統(tǒng)的分類角度,Dudek等人提出了以上7個(gè)角度，用于分類多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ù)時(shí)，哪個(gè)完成任務(wù)的可能性更大？我們總能使用SIZE-INF型群體么？,16,3.2 通信范圍（Communication Range）,COM-NONE：機(jī)器人成員不能直接與其他機(jī)器人通信，智能通過感知器觀測到對方的存在、不存在和行為。成員之間也不可以互發(fā)信號 COM-NEAR：機(jī)器人成員只能與其附近的機(jī)器人通信（距離可以物理空間上的距離也可以是拓?fù)淇臻g上的距離） 拓?fù)淇臻g距離的例子：軍隊(duì)中的士兵由樹形的結(jié)構(gòu)組織 COM-INF：一個(gè)機(jī)器人

7、成員可以與其它任意機(jī)器人通信,17,3.3 通信的拓?fù)浣Y(jié)構(gòu)(Communication Topology),廣播式通信 按地址通信 樹形通信 網(wǎng)狀通信,18,3.4 通信帶寬（Communication Bandwidth）,通信影響群體的性能：如果成員具有專用的通信通道，則處理通信的時(shí)間很短；如果成員在通信時(shí)不能進(jìn)行其他動作，那么通信代價(jià)就高。 BAND-INF：在這種群體中，通信是無代價(jià)的。 BAND-MOTION：通信代價(jià)與移動成員的代價(jià)成正比。 例如：蜂群中，蜜蜂通過跳八字舞進(jìn)行通信。傳遞的信息與跳舞的運(yùn)動代價(jià)成正比,19,,BAND-LOW：通信代價(jià)高。遠(yuǎn)遠(yuǎn)高出將一個(gè)機(jī)器人叢一個(gè)位置

8、移動到另一個(gè)位置的代價(jià) BAND-ZERO：無通信，任何成員無法感知到其他成員,20,3.5 群體的可重配置程度（Collective Recongurability）,指 群體在空間上重新組織的速度。 蜂群中的成員可根據(jù)其他成員的空間位置快速改變自身的空間位置。以固定步伐前進(jìn)的部隊(duì)和高速公路上的汽車重新配置空間距離的速度就慢。,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),群體中的每個(gè)成員具有不同的計(jì)算模型。有的成員的計(jì)算模型可能比圖靈機(jī)弱一些，比如，有窮狀態(tài)自動機(jī)。但是，即使單個(gè)成員的計(jì)算模型簡單，整個(gè)群體的計(jì)算能力可能是很強(qiáng)的。,23,3.6 成員的處理能力(Processing ability of each collective unit),PROC-SUM：成員的計(jì)算模型是一個(gè)非線性求和單元。例如，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元。 PROC-FSA：成員的計(jì)算模型是一個(gè)有窮狀態(tài)自動機(jī)。 PROC-PDA：成員的計(jì)算模型是一個(gè)下推自動機(jī) PROC-TME：成員的計(jì)算模型

10、是一個(gè)圖靈機(jī),24,3.7 群體的構(gòu)成,群體成員可能在物理構(gòu)成上是異構(gòu)的。即使使用相同的物理部件，也可能在軟件上是異構(gòu)的。 CMP-IDENT：群體的成員均具有相同的硬件和軟件 CMP-HET：群體成員具有不同的硬件，導(dǎo)致軟件也不相同,25,3.8 群體系統(tǒng)的案例,研究者成功設(shè)計(jì)了多個(gè)具有相對優(yōu)勢的群體機(jī)器人系統(tǒng) 案例1：成員具有有窮狀態(tài)自動機(jī)的計(jì)算模型，而群體的計(jì)算能力與圖靈機(jī)接近 案例2：對于搜索任務(wù)，群體系統(tǒng)比單獨(dú)一個(gè)移動的、能做標(biāo)記的機(jī)器人更高效,26,,案例3： 群體機(jī)器人中，如果每個(gè)成員都能感知到對方，可以在一個(gè)存在少量路標(biāo)的環(huán)境中進(jìn)行自我定位，而單個(gè)機(jī)器人不能。 案例4： 在無路

11、標(biāo)環(huán)境中，群體機(jī)器人可以通過相互感知實(shí)現(xiàn)自我定位。,27,4. 多機(jī)器人規(guī)劃的基本思想,多Agent系統(tǒng)（Multi-Agent System, MAS）：在同一環(huán)境中，存在協(xié)作關(guān)系的多個(gè)Agent組成的系統(tǒng)。 特點(diǎn)：控制多Agent系統(tǒng)的路徑規(guī)劃系統(tǒng)的復(fù)雜度隨著移動Agent的數(shù)目呈指數(shù)級別增長,28,,單Agent路徑規(guī)劃方法不能用于求解多Agent規(guī)劃問題，原因包括: 成員之間要避免碰撞 成員之間要避免死鎖 多Agent規(guī)劃系統(tǒng)的難點(diǎn)包括： 計(jì)算代價(jià) 信息交換策略 通信代價(jià),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ī)劃方法,使用一個(gè)方法對所有的Agent的路徑進(jìn)行規(guī)劃 優(yōu)點(diǎn)： 可以找到最優(yōu)解 使用系統(tǒng)的全部信息 缺點(diǎn)： 計(jì)算復(fù)雜度隨著Agent的數(shù)目呈指數(shù)級別增長 對一個(gè)

13、Agent的規(guī)劃失敗，則無法繼續(xù)對其他Agent進(jìn)行規(guī)劃,32,4.2.2 多Agent系統(tǒng)的分散式路徑規(guī)劃方法,該方法首先為每個(gè)機(jī)器人Ri計(jì)算一條相應(yīng)的規(guī)劃解Plani，然后處理這些解之間的路徑?jīng)_突，如果解決沖突成功則將規(guī)劃解作為每個(gè)機(jī)器人的路徑規(guī)劃解，否則返回“無解”。 優(yōu)點(diǎn)： 一個(gè)Agent的路徑的計(jì)算時(shí)間和相鄰Agent的數(shù)目成正比 具有健壯性 缺點(diǎn)： 不完備：為什么？例：多Agent系統(tǒng)內(nèi)有兩個(gè)機(jī)器人R1和R2，對于它們的目標(biāo)，R1存在兩個(gè)規(guī)劃解Plan11,Plan12，R2存在兩個(gè)規(guī)劃解Plan21,Plan22，并且Plan11和Plan21之間的沖突是無法解決的。那么，如果分

14、散式規(guī)劃方法首先為R1計(jì)算出Plan11、為R2計(jì)算出Plan21，由于Plan11和Plan21的沖突無法解決，分散式規(guī)劃方法將返回“無解”。然而，實(shí)際上，Plan11和Plan22是該多Agent規(guī)劃問題的一個(gè)解，未被分散式方法計(jì)算出，因此說，分散式方法是不完備的。,33,4.2.3 多Agent系統(tǒng)的組合式路徑規(guī)劃方法,Use cumulative information for global path planning, use local information for local planning（使用累積的信息對單個(gè)Agent的全局路徑進(jìn)行規(guī)劃，使用本地信息對該Agent局部的路徑進(jìn)行規(guī)劃） “Think Global Act Local”,34,,Thinking Globally 對于一個(gè)Agent，計(jì)算從其從當(dāng)前位置到目的位置的完整路徑 使用A*算法完成,35,,Act Locally： 為了避開障礙物，采用反應(yīng)式的規(guī)劃方法，基于局部信息進(jìn)行路徑規(guī)劃 優(yōu)點(diǎn)是： 不需要環(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)動,