基于改進型Dijkstra算法的模塊機器人系統(tǒng)故障自診斷策略

管恩廣， 付　莊， 閆維新， 趙言正

(上海交通大學(xué) 機器人研究所， 上海 200240)

基于改進型Dijkstra算法的模塊機器人系統(tǒng)故障自診斷策略

管恩廣， 付莊， 閆維新， 趙言正

(上海交通大學(xué) 機器人研究所， 上海 200240)

面向模塊機器人系統(tǒng)，提出了一種全新的故障自診斷策略.該策略將故障自診斷過程分為兩個部分：故障檢測及故障消息傳遞.選用健康脈沖法實現(xiàn)模塊間的交互式故障檢測.設(shè)計優(yōu)化改進型Dijkstra距離計算方法，并依據(jù)這種方法引導(dǎo)故障消息在模塊間沿最優(yōu)路徑傳遞.通過仿真試驗，該自診斷策略的有效性和可靠性在M-Lattice模塊機器人系統(tǒng)上得到了驗證，表明該策略可以廣泛應(yīng)用于其他模塊機器人系統(tǒng).

模塊機器人系統(tǒng)； 故障自診斷； M-Lattice模塊機器人

在模塊機器人系統(tǒng)中，故障的發(fā)生是不可避免的.當(dāng)故障發(fā)生時，能否以最快速度發(fā)現(xiàn)并定位故障對于保證系統(tǒng)正常工作是至關(guān)重要的.模塊機器人系統(tǒng)的自診斷策略設(shè)計很大程度上受系統(tǒng)結(jié)構(gòu)影響.模塊機器人按結(jié)構(gòu)可以分為3個類別：晶格式、鏈?zhǔn)胶途C合式.晶格式模塊機器人系統(tǒng)結(jié)構(gòu)一般為網(wǎng)格狀，如CHOBIE[1]和ATRON[2].鏈?zhǔn)侥K機器人系統(tǒng)結(jié)構(gòu)一般為線形或樹形，如YaMor[3].綜合式模塊機器人可以同時完成晶格式和鏈?zhǔn)綐?gòu)型，如Roombots[4]、iMobot[5]和 UBot[6]，由于該系統(tǒng)具有靈活的構(gòu)型模式，其診斷策略設(shè)計難度也比前兩者大.

目前已有相關(guān)文獻介紹針對精密機器人個體的故障診斷方法[7]，但是對于模塊機器人系統(tǒng)的診斷策略研究并不多見.大多數(shù)對群體機器人系統(tǒng)的故障診斷研究集中于自主移動式群體機器人.在一些機器人系統(tǒng)中，系統(tǒng)狀態(tài)包括通信負載、故障定位等，通過圖的方式進行表達分析[8].在圖理論(graph theory)中，以節(jié)點(vertex)表示機器人個體，邊(edge)表示機器人間的物理或者通信連接關(guān)系.基于故障概率模型的診斷方法[9-10]在某些自主移動機器人群體中被證明是有效的，但是模塊機器人個體并不具備自主移動能力，所以這類方法很難應(yīng)用于模塊機器人系統(tǒng).超預(yù)期學(xué)習(xí)[11](surprise-based learning， SBL)，是目前面向模塊機器人系統(tǒng)容錯性設(shè)計最系統(tǒng)的指導(dǎo)理論，但其使用過程中需要不斷地進行全局訓(xùn)練以優(yōu)化故障對策，且算法本身非常復(fù)雜，因而無法作為離散的控制策略應(yīng)用于M-Lattice模塊機器人系統(tǒng)中.

為解決大規(guī)模模塊機器人系統(tǒng)的故障診斷問題，本文提出了一種故障自診斷策略.這種自診斷策略原理簡單，可以獨立運行于模塊機器人個體，僅通過模塊間的局部通信，就可以完成故障診斷.該自診斷策略主要由以下兩個部分組成：

(1) 故障檢測.選擇健康脈沖信號法作為交互式故障檢測方法.在模塊機器人系統(tǒng)中，每個模塊均以探測者的身份檢測與之相連接的模塊是否能夠周期性地發(fā)出健康信號.若沒有接收到某一鄰位模塊的健康信號，則認為該鄰位模塊為故障模塊，并生成一條包含故障位置坐標(biāo)的故障消息.

(2) 故障消息傳遞.在模塊機器人系統(tǒng)中，模塊個體可以通過局部通信將故障消息傳遞給與其連接的鄰位模塊.為了保證僅在局部通信的情況下，故障消息能夠沿最優(yōu)路徑傳遞到系統(tǒng)消息接收端，提出了一種改進型離散Dijkstra算法，用以適應(yīng)由故障模塊出現(xiàn)導(dǎo)致的最優(yōu)路徑變化.

為了驗證本文自診斷策略的有效性和可靠性，選擇M-Lattice模塊機器人系統(tǒng)作為驗證平臺，其是一種可以實現(xiàn)二維空間自構(gòu)型的晶格式模塊機器人.M-Lattice模塊相互連接可以形成網(wǎng)格狀平面.在驗證自診斷策略時，假設(shè)故障模塊不會脫離系統(tǒng)，即故障模塊群體至少與一個正常模塊相連接.

1　M-Lattice模塊機器人系統(tǒng)

M-Lattice機器人[12]是一種非緊密式的晶格式模塊機器人，如圖1所示.由圖1可知，每個模塊包含一個中心框體和三條兩自由度機械臂，并且每個模塊最多可以同時與3個模塊保持連接.作為分布式模塊機器人系統(tǒng)，每個機器人個體只能以局部通信的方式與鄰位模塊進行通信.

(a) 模塊結(jié)構(gòu)圖

(b) 模塊實物圖

(c) 模塊連接圖圖1　M-Lattice模塊機器人Fig.1　The M-Lattice modular robot

M-Lattice的系統(tǒng)結(jié)構(gòu)為網(wǎng)格狀平面結(jié)構(gòu).在描述模塊在系統(tǒng)中的位置時，使用一種有序整數(shù)對的索引位置來表示,其形式為(r,c),r表示模塊所在的行數(shù)，c表示模塊所在的列數(shù),如圖2所示.模塊在系統(tǒng)中的索引位置和實際位置可以由簡單的幾何變換得到.

圖2　M-Lattice系統(tǒng)拓撲結(jié)構(gòu)Fig.2　The topology structure of the M-Lattice system

2　故障自診斷策略

在M-Lattice系統(tǒng)中，模塊按工作狀態(tài)可分為故障模塊和正常模塊.當(dāng)正常模塊檢測到其鄰位模塊故障時，會自動生成一條故障信息，并將其發(fā)送給鄰位正常模塊.該消息可以在系統(tǒng)中通過局部通信傳輸，直至被系統(tǒng)監(jiān)測器收到，完成一個故障模塊的診斷過程.

2.1故障檢測

由于精密機器人個體的自身故障檢測方法很難直接應(yīng)用于運算能力有限的模塊機器人，所以選擇健康脈沖法來實現(xiàn)模塊間的故障交互檢測.通過預(yù)先設(shè)定，使得每一個模塊在工作正常時都可以定時發(fā)送一個類似心跳的脈沖信號，稱為健康脈沖.這個信號通過模塊間的連接通道發(fā)送給鄰位模塊.當(dāng)模塊功能部分不可控時，例如運動執(zhí)行機構(gòu)無反應(yīng)，或者傳感器響應(yīng)異常時，通過內(nèi)部有限狀態(tài)機的方式便可以停止脈沖定時發(fā)送.當(dāng)模塊遇到意外碰撞或者系統(tǒng)掉電時，模塊完全失效，也將無法繼續(xù)發(fā)送脈沖信號.健康脈沖信號法如圖3所示，可以通過檢測鄰位模塊是否定時發(fā)出脈沖的方式檢測該模塊是否發(fā)生故障.判斷準(zhǔn)則：若一個正常模塊在自己發(fā)送兩次健康信號之間接收到鄰位模塊的健康脈沖，則認為該鄰位模塊正常；反之，則認為檢測到一個故障.

圖3　健康脈沖信號法示意圖Fig.3　An illustration of the healthy pulse method

2.2故障消息傳遞

當(dāng)一個故障模塊被檢測到，其鄰位的正常模塊將生成一條包含故障位置的故障消息，并將其在系統(tǒng)中傳遞.故障消息通過局部通信的方式在正常模塊間傳遞，最終到達系統(tǒng)監(jiān)測器位置，也稱為消息收集器.在故障消息傳遞的路徑規(guī)劃方面，最重要的問題在于如何找到一種適用于離散模塊機器人系統(tǒng)的路徑長度表示方式.這種方法能夠直觀地反映系統(tǒng)的狀態(tài)變化，并且能夠直接被模塊機器人個體執(zhí)行.為此本文設(shè)計了一種改進型離散Dijkstra算法來計算模塊機器人系統(tǒng)中的路徑長度.

2.2.1消息傳遞路徑描述

M-Lattice系統(tǒng)網(wǎng)絡(luò)可以用一種無向圖的方式表示，記為G=(V,E,w)，其中，V表示模塊機器人集合，E表示模塊間的連接狀態(tài)，w表示連接關(guān)系權(quán)重.邊的表達方式為無序?qū)?m1,m2)，其中m1和m2為相鄰模塊.在傳統(tǒng)的圖理論中，u和v兩點間的路徑可記為一個有限序列：

p = {u≡ v0, v1, …， vk≡ v}，

滿足0≤i

整個路徑的權(quán)重為

此所謂的尋找最短路徑的問題就轉(zhuǎn)化為尋找u和v之間所有路徑中權(quán)重之和最小的那一條路徑.在M-Lattice系統(tǒng)中，由于沒有全局廣播通道，模塊間只能夠進行局部通信.對于模塊u而言，它和目標(biāo)模塊v之間的路徑就變?yōu)?/p>

p = {u, v0≡v1, v2, …, vk≡v}，滿足0≤i

在這種情況下，u與v之間路徑權(quán)重也變?yōu)?/p>

如果規(guī)定任意相鄰模塊間的權(quán)重值都相同，那么最短路徑必定包含一個具有最小權(quán)重之和的鄰位模塊.

2.2.2改進型離散Dijkstra算法

在上述內(nèi)容的基礎(chǔ)上，選用離散Dijkstra算法來計算系統(tǒng)的路徑長度.在Dijkstra算法[13]中，當(dāng)前模塊和目標(biāo)模塊間最短路徑所包含的模塊個數(shù)稱為Dijkstra距離，記作D.系統(tǒng)中的每一個模塊都可以保存并更新當(dāng)前的Dijkstra距離.Dijkstra距離示意如圖4所示，規(guī)定消息收集器的位置為系統(tǒng)目標(biāo)模塊所在位置，即D=0，這樣其鄰位模塊的Dijkstra距離記為D=1，并以此類推.在消息傳遞過程中，只需要保證將消息傳遞給Dijkstra 距離最小的那個模塊，則可以保證消息傳遞路徑最優(yōu).

圖4　Dijkstra距離示意圖Fig.4　Some illustrations of Dijkstra distance

模塊個體更新自身Dijkstra距離值依照的規(guī)則如下：

(1) 當(dāng)連接狀態(tài)發(fā)生變化時，模塊觸發(fā)更新Dijkstra距離值操作，并向所有鄰位模塊發(fā)送讀取其Dijkstra距離值的請求；

(2) 讀取鄰位Dijkstra距離值過程中，若鄰位為空位或故障模塊，則其Dijkstra距離值視為無窮大，記作INTMAX；

(3) 選擇所有鄰位Dijkstra距離值中最小的一個，記為Df，則更新自身Dijkstra距離值為Df+1.

在實際應(yīng)用Dijkstra算法過程中，為避免過多的消息同時傳送給一個模塊，引發(fā)消息過載，給出了一個廣義距離函數(shù)對Dijkstra距離值進行處理.這種處理后的Dijkstra距離值被稱為改進型Dijkstra距離值，記為MD(Modified Dijkstra)距離.與其相對應(yīng)的，之前介紹的Dijkstra距離值稱為標(biāo)準(zhǔn)Dijkstra距離值，記為SD(Standard Dijkstra )距離.廣義距離函數(shù)形式為

(1)

其中：D*為當(dāng)前模塊的MD距離值；D為當(dāng)前模塊的SD距離值；M為模塊的最大消息負載上限；L為當(dāng)前消息負載；α為功能因子，后續(xù)試驗中設(shè)為0.2.當(dāng)模塊已經(jīng)接收到大量的故障消息時，其返回的MD距離值會增大，這樣新的消息將不會繼續(xù)傳遞給這個模塊.

3　故障自診斷策略仿真

本文使用Matlab軟件對故障診斷策略進行仿真，其工作平臺為CPU Pentium E5200 Dual-Core, RAM 2 GB.在仿真過程中，模塊機器人系統(tǒng)以無向圖的方式表達，即G=(V,E,w)，其中連接關(guān)系權(quán)重值w以相鄰模塊間的Dijkstra距離值表示.系統(tǒng)網(wǎng)格形狀定義為矩形，模塊規(guī)模為m×n，其中，m為行數(shù)，n為列數(shù).系統(tǒng)中的消息收集器可被安置于任意位置.依據(jù)Dijkstra算法，模塊更新Dijkstra距離值.在仿真開始前初始化階段中，設(shè)定系統(tǒng)規(guī)模、故障模塊規(guī)模、消息收集器數(shù)量及位置以及模塊消息負載上限.仿真開始后，依據(jù)故障規(guī)模隨機選擇模塊將其設(shè)定為故障模塊，這時系統(tǒng)中模塊將更新Dijkstra距離值.當(dāng)正常模塊檢測到鄰位模塊為故障模塊后，將生成一條包含故障位置的故障消息，并將其發(fā)送給擁有最小Dijkstra距離值的正常鄰位模塊.故障診斷流程如圖5所示.在仿真過程中，故障消息的傳遞路徑由仿真程序獨立保存.如果系統(tǒng)中沒有消息進行傳遞，則認為一個仿真試驗完成.

圖5　故障診斷流程圖Fig.5　Flow diagram of fault diagnosis

3.1系統(tǒng)擴展性測試

首先測試診斷策略的系統(tǒng)擴展性.試驗中，系統(tǒng)規(guī)模由100×100變化至200×200，消息收集器個數(shù)為1, 2和4，消息收集器的位置對稱分布于矩形平面的4個頂點，以減少相互間影響，故障模塊數(shù)量為系統(tǒng)模塊數(shù)量的1%，模塊個體的消息負載上限為無窮大.每個狀態(tài)下規(guī)模重復(fù)試驗30次.

變系統(tǒng)規(guī)模情況故障診斷仿真結(jié)果如圖6所示.圖6中平面內(nèi)點表示故障模塊所在位置，其位置表示方式已經(jīng)轉(zhuǎn)換為笛卡爾坐標(biāo)，而不是索引坐標(biāo)，這樣更能直觀地表示故障位置與消息傳輸路徑的關(guān)系.柱狀圖給出了路徑的長度.由于故障規(guī)模比較小，所以相互間影響有限，因而將相同規(guī)模的試驗數(shù)據(jù)取平均后，在同一個圖里表示出來.從圖6(a)和6(b) 中可以看出，在故障規(guī)模較小的情況下，故障消息的路徑長度基本正比于故障模塊位置與消息收集器間的距離.由圖6(c)和6(d)可知，消息收集器的增加顯著縮短了故障消息的傳輸路徑長度，即提高了診斷效率.這是由于在M-Lattice系統(tǒng)中，多個Dijkstra距離為0的消息收集器的引入，縮短了系統(tǒng)的平均Dijkstra距離值.由于多個消息收集器的存在，消息可以被傳遞給最近的消息收集器，而不必再穿過整個系統(tǒng)，這樣提高了消息傳遞的并行性，即提高了消息傳輸效率.

(a) 10000個模塊1個消息收集器

(b) 40000個模塊1個消息收集器

(c) 10000個模塊2個消息收集器

(d) 10000個模塊4個消息收集器圖6　變系統(tǒng)規(guī)模情況的故障診斷Fig.6　Fault diagnosis with different system scales

3.2消息負載上限的影響

真實的模塊機器人個體不可能具有無限的消息負載能力，所以模塊負載能力對診斷效率的影響不能被忽略.在消息負載上限的影響試驗中，系統(tǒng)規(guī)模為50×50，消息收集器數(shù)量分別為1和4；故障規(guī)模分別為系統(tǒng)規(guī)模的5%， 10%和15%；消息負載(最大接收消息數(shù)量)上限范圍為1～10.同等情況下重復(fù)試驗10次.在每一組試驗中，系統(tǒng)分別使用SD算法和MD算法計算Dijkstra距離值.消息在模塊間的連續(xù)傳遞離散化為一系列的傳遞單元.在每個仿真周期(step)內(nèi)，消息只從一個模塊傳遞到另一個模塊.若當(dāng)前模塊接收到的消息已經(jīng)達到最大負載上限，則不能再接收消息.

變消息負載上限的故障自診斷仿真結(jié)果如圖7所示,其中診斷時間以消息傳遞的步數(shù)表示，每一步表示系統(tǒng)中的故障消息由當(dāng)前模塊傳遞給鄰位模塊.由圖7可知，增加模塊消息負載上限對于整體診斷效率的提高并不是無限的.由于故障模塊發(fā)生位置上的差異，必定導(dǎo)致其故障消息傳輸?shù)较⑹占鞯臅r間存在差異，這就降低了模塊發(fā)生消息過載的幾率.與此同時，提高模塊的消息負載上限會導(dǎo)致模塊個體成本的上升，這對于大規(guī)模系統(tǒng)也是不能忽略的.由圖7還可以發(fā)現(xiàn)，在同等故障條件下，MD算法要優(yōu)于SD算法.這主要是由于MD算法將當(dāng)前模塊的消息負載情況作為一個前饋值引入到Dijkstra距離值計算中，避免了消息過載發(fā)生的概率，也就提高了系統(tǒng)的診斷效率.另外，系統(tǒng)消息收集器的數(shù)量改變只影響整體的診斷效率，并不改變模塊消息負載上限和系統(tǒng)故障規(guī)模之間的對應(yīng)關(guān)系.也就是說，為了提高診斷效率，考慮以增加消息收集器的方法更為有效.

(a) 1個消息收集器

(b) 4個消息收集器圖7　變消息負載上限情況的故障診斷Fig.7　Fault diagnosis with changeable message load capacity

在測試故障自診斷策略在大規(guī)模M-Lattice模塊機器人系統(tǒng)中的表現(xiàn)時，系統(tǒng)規(guī)模為100×100，故障規(guī)模分別為系統(tǒng)規(guī)模的5%， 10%和15%，消息收集器數(shù)量分別為1和4，模塊個體最大消息負載上限為6條消息.在每組試驗中分別使用MD算法和SD算法計算Dijkstra距離值.每種情況重復(fù)試驗30次，試驗結(jié)果如表1所示.由表1可以看到，在大故障規(guī)模下MD算法在診斷效率上較SD算法表現(xiàn)更為突出.同時，在中等規(guī)模的故障系統(tǒng)中，自診斷策略都有非常高的直接診斷成功率，而且增加消息收集器可以非常明顯地提高系統(tǒng)診斷效率.

表1　故障自診斷策略仿真結(jié)果Table 1　Simulation results of the self-diagnosis strategy

4　結(jié)　語

本文介紹了一種針對模塊機器人系統(tǒng)的故障自診斷策略，并通過M-Lattice模塊機器人系統(tǒng)對該策略的有效性和可靠性進行了仿真驗證.整個故障診斷任務(wù)基于局部通信完成，不需要全局廣播.模塊間使用交互式健康脈沖法進行故障檢測，可以保證同一個故障模塊可以同時被多個鄰位模塊檢測到，進而提高了故障檢測環(huán)節(jié)的可靠性.在故障消息傳遞過程中，通過使用改進型Dijkstra算法，確保故障消息在模塊機器人系統(tǒng)中始終沿最優(yōu)路徑進行傳遞，有效提高了診斷效率.通過仿真試驗可以證明，該故障自診斷策略對于大規(guī)模模塊機器人系統(tǒng)是有效可靠的.在今后的工作中，計劃繼續(xù)改進故障自診斷策略，以適應(yīng)在復(fù)雜故障類型下的模塊機器人自診斷任務(wù)，同時，在自構(gòu)型和自修復(fù)任務(wù)中，如何發(fā)揮自診斷策略的作用也是今后研究的重點.

[1] SUZUKI Y. Reconfigurable modular robot adaptively transforming a mechanical structure [J]. J Robot So, 2008, 26(1): 74-81.

[2] ?STERGAARD E H, KASSOW K, BECK R, et al. Design of the ATRON lattice-based self-reconfigurable robot [J]. Autonomous Robots, 2006, 21(2): 165-183.

[3] MOECKEL R, JAQUIER C, DRAPEL K, et al. Exploring adaptive locomotion with YaMoR, a novel autonomous modular robot with bluetooth interface [J]. Industrial Robot: An International Journal, 2006, 33(4): 285-290.

[4] SPROEWITZ A, LAPRADE P, BONARDI S, et al. Roombots-towards decentralized reconfiguration with self-reconfiguring modular robotic metamodules [C]// IEEE/RSJ International Conference on Intelligent Robots and Systems. Taipei, Taiwan: IEEE, 2010: 1126-1132.

[5] RYLAND G G, CHENG H H. Design of iMobot, an intelligent reconfigurable mobile robot with novel locomotion [C]// IEEE International Conference on Robotics and Automation. Anchorage, USA: IEEE, 2010: 60-65.

[6] ZHAO J, CUI X, ZHU Y, et al. UBot: A new reconfigurable modular robotic system with multimode locomotion ability [J]. Industrial Robot: An International Journal, 2012, 39(2): 178-190.

[7] CICERONE S, STEFANO G D, FRIGIONI D, et al. A fully dynamic algorithm for distributed shortest paths [J]. Theoretical Computer Science, 2003, 297(1): 83-102.

[8] MOURAD E, NAYAK A. Comparison-based system-level fault diagnosis: A neural network approach [J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(6): 1047-1059.

[9] GARCIA R, SCHULTZ U, STOY K. On the efficiency of local and global communication in modular robots [C] //IEEE/RSJ International Conference on Intelligent Robots and Systems. St Louis, MO: IEEE, 2009: 1502-1508.

[10] MARTIN A, EMAMI M. A fault-tolerant approach to robot teams [J]. Robotics and Autonomous Systems, 2013,61(12): 1360-1378.

[11] RANASINGHE N, SHEN W M. Autonomous adaptation to simultaneous unexpected changes in modular robots [C]// IEEE/RSJ International Conference on Intelligent Robots and Systems. San Francisco, CA: IEEE, 2011.

[12] GUAN E G, YAN W X, JIANG D S, et al. A novel design for the self-reconfigurable robot module and connection mechanism [C] //International Conference on Intelligent Robotics and Applications. Shanghai, China: IEEE, 2010: 400-408.

[13] DIJKSTRA E W. A note to two problems in connection with graphs [J]. Numerische Mathematik, 1959, 1(2): 269-271.

Fault Self-diagnosis for Modular Robotic System Based on Modified Dijkstra Method

GUANEn-guang,FUZhuang,YANWei-xin,ZHAOYan-zheng

(Research Institute of Robotics, Shanghai Jiaotong University, Shanghai 200240, China)

A novel fault self-diagnosis strategy for modular robotic system is presented. The strategy consists of two parts: fault detection and fault message transmission. A healthy pulse method is used to realize the exogenous detection. And the Dijkstra method is modified to be capable of guiding the passage of fault messages along the optimal path. Computational simulations of one system form, M-Lattice, have demonstrated the validity and reliability of the proposed strategy. And the strategy should be applicable in modular robotic systems in general.

modular robotic system; fault self-diagnosis; M-Lattice modular robot

1671-0444(2015)06-0788-07

2014-09-03

國家自然科學(xué)基金資助項目(60875058, 61473192)

管恩廣(1983—)，男，山東膠州人，博士研究生，研究方向為模塊機器人控制算法.E-mail: enguangovo@sjtu.edu.cn

趙言正(聯(lián)系人)，男，教授，E-mail: yz-zhao@sjtu.edu.cn

TP 206； TP 242

A