[發明專利]基于網絡撕裂法的移動機器人路徑規劃方法

在審

• 申請號: 201910244831.6
• 申請日: 2019-03-28
• 公開（公告）號: CN110196588A
• 公開（公告）日: 2019-09-03
• 發明（設計）人: 張鵬超;李海婷
• 申請（專利權）人: 陜西理工大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 西安弘理專利事務所 61214
• 代理人: 談耀文

1.基于網絡撕裂法的移動機器人路徑規劃方法，其特征在于，以起始點到目標點的連線作為行駛的基本路線，利用網絡撕裂法建立障礙物網絡模型，并撕裂出子網絡，通過數學擬合分別計算移動機器人的路徑和時間的最小權值，得出移動機器人到達并繞過下一障礙物的最優路徑規劃，對基本路線進行調整，具體包括以下步驟：

步驟1)找出障礙物的幾何中心，估算障礙物的面積S，并將障礙物面積S作為類電阻Z，S＝Z；

步驟2)以各障礙物作為網絡節點，根據全局障礙物及其位置建立障礙物網絡模型，將障礙物所在位置及其面積大小總權值類比為電壓，網絡節點之間的距離類比為電阻，節點之間的有向依賴關系類比為電流，采用網絡撕裂法將障礙物網絡模型撕裂出子網絡；

步驟3)計算撕裂后的節點類電壓U_a，擬合類電阻Z與節點類電壓U_a的關系式；

步驟4)根據類電阻Z與節點類電壓U_a的關系式計算移動機器人繞過障礙物走過的弧長l₀，繼而得出移動機器人到達并繞過下一障礙物的最優路徑和完成最優路徑所需時間，移動機器人按照規劃的最優路徑對基本路線進行調整，由起始點行駛至目標點。

2.根據權利要求1所述的基于網絡撕裂法的移動機器人路徑規劃方法，其特征在于，所述步驟1)中估算障礙物的面積S具體為，以障礙物的幾何中心作為原點，以該障礙物的幾何中心到最遠邊界點的距離作為半徑，做該障礙物的外接圓，外接圓的面積即為該障礙物的面積S。

3.根據權利要求1所述的基于網絡撕裂法的移動機器人路徑規劃方法，其特征在于，所述步驟2)中采用網絡撕裂法將障礙物網絡模型撕裂出子網絡具體為，選定距離移動機器人移動起始點最近的點為參考點，從邊界點處撕裂出子網絡，子網絡所含節點總數不少于障礙物網絡模型節點總數的一半，子網絡由障礙物網絡模型被撕斷的支路組成，障礙物網絡模型除去子網絡的部分為保留網絡。

4.根據權利要求1所述的基于網絡撕裂法的移動機器人路徑規劃方法，其特征在于，所述步驟3)具體按照以下步驟實施：

步驟3.1)根據KCL基爾霍夫電流定律和KVL基爾霍夫電壓定律列出障礙物網絡模型撕裂前的節點電壓方程，為

Y_nU_n＝J_n (1)

式(1)中，J_n為n個節點的注入電流矩陣，Y_n為n個節點的導納矩陣，U_n為n個節點的節點電壓矩陣，n是障礙物網絡模型中的節點總數，n為不為0的自然數；

步驟3.2)根據電路的疊加定理、KCL基爾霍夫電流定律和KVL基爾霍夫電壓定律列出障礙物網絡模型撕裂后的節點電壓方程，為

Y_aU_a＝J_a+J_n (2)

式(2)中，下標a表示與子網絡具有公共節點的保留網絡部分，該部分為保留網絡G，Y_a為保留網絡G的節點類導納，Y_a為保留網絡G的分塊對角陣，J_a是撕斷支路所引起的注入保留網絡G節點的單位電流，J_a的方向為從移動起始點指向目標點，U_a＝U_n；

步驟3.3)設被撕斷支路的電流為單位電流I_s，則被撕斷支路與保留網絡G的電流關系為，

J_a＝C_asI_s (3)

式(3)中，下標s表示被撕斷的支路，C_as是關聯矩陣A的負子矩陣，關聯矩陣A為保留網絡G所有節點分別與所有被撕斷支路之間的有向線段構成的關聯矩陣，關聯矩陣A的列被撕斷支路，關聯矩陣A的行對應保留網絡G的節點，關聯矩陣A中數值分別為被撕斷支路指向網絡G的節點為-1、被撕斷支路離開網絡G的節點為1、被撕斷支路與網絡G的節點不相關為0，負子矩陣C_as的列對應被撕斷支路，負子矩陣C_as的行對應保留網絡G的節點；

步驟3.4)設被撕斷支路為純電阻支路，則

Z_sI_s＝U_s (4)

式(4)中，Z_s表示被撕斷支路阻抗矩陣，Z_s為被撕斷支路對角矩陣，U_s表示被撕斷支路電壓，

被撕斷支路與保留網絡G的電壓關系為，

U_S＝-C_as^TU_a (5)；

步驟3.5)將式(3)帶入式(2)得，

Y_aU_a-C_asI_s＝J_n (6)

將式(4)帶入式(5)得，

C_as^TU_a+Z_sI_s＝0 (7)

將(6)式帶入(7)式得，

I_s＝(Z_s+C_as^TY_a^-1C_as)C_as^TY_a^-1J_n (8)

設將(8)式帶入(6)式，計算U_a為，

將撕裂后的節點類電壓U_a作為機器人路徑途徑的等壓圓，即移動機器人碰到障礙物并避障的減速預警值；

步驟3.6)根據障礙物網絡模型中所有節點的類電阻z和其對應的節點類電壓U_a，通過最小二乘法擬合出其函數關系式為，

z＝f(u_a) (10)。

5.根據權利要求1所述的基于網絡撕裂法的移動機器人路徑規劃方法，其特征在于，所述步驟4)具體按照以下步驟實施：

設質點中心到幾何圖形邊界最遠距離為r，則

S＝πr² (11)

設機器人穿障礙區的區域面積為R，則

式(12)中，θ為將要繞行的障礙物外接圓的弦所對應的圓心角，該障礙物外接圓的弦為起始點到目標點連線穿過將要繞行的障礙物外接圓的線段；

計算的值，若則移動機器人左轉，若則移動機器人右轉，若則移動機器人左轉或右轉任選一種，若則移動機器人按原直線行駛無需轉動；

移動機器人將要繞行的障礙物走過的弧長l₀為，

移動機器人將要繞行的障礙物走過弧長l₀的時間為，

式(14)中，v₀為機器人的繞行速度，

移動機器人走過無障礙區的直線距離為l₁，走過無障礙區直線距離l₁的時間為，

式(15)中，v₁為機器人直線運動的速度，

則移動機器人到達并繞過下一障礙物的最優路徑為，

L＝l₁+l₀ (16)，

完成該最優路徑所需時間為，

T＝t₁+t₀ (17)，

移動機器人從起始點出發，沿起始點到目標點的連線行駛，在減速預警的等壓圓區域沿圓弧以繞行速度v₀行駛，駛出后減速預警的等壓圓區域后以直線運動速度v₁直線前行，依照此行駛方式直至到達目標點。