[發明專利]基于模擬退火蟻群算法的電力巡檢機器人路徑規劃方法

有效

• 申請號: 201811026526.1
• 申請日: 2018-09-04
• 公開（公告）號: CN109141430B
• 公開（公告）日: 2022-02-18
• 發明（設計）人: 李勝;袁佳泉;郭健;吳益飛;史一露;危海明;朱禹璇;施佳偉;趙超;王天野
• 申請（專利權）人: 南京理工大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 南京理工大學專利中心 32203
• 代理人: 薛云燕

1.一種基于模擬退火蟻群算法的電力巡檢機器人路徑規劃方法，其特征在于，包括以下步驟：

步驟1、根據室外變電站環境構建地圖，規劃電力巡檢機器人的運行路徑與?？奎c，根據?？奎c坐標信息構建拓撲地圖；

步驟2、根據巡檢任務，利用經典Dijkstra算法得到任意兩個巡檢點的局部最短路徑，同時構建無向圖；

步驟3、根據路徑長度以及經過的?？奎c數，將全局最優路徑規劃問題轉化為多目標的旅行商問題，并利用模擬退火蟻群算法規劃全局最優路徑，具體為：

步驟3-1、參數初始化；設置路徑解(d,n)用于儲存路徑規劃計算過程中的解，d為路徑距離，n為經過?？奎c的個數，路徑解(d,n)組成的解集為S；

步驟3-2、設置退火初始溫度T＝T_max，螞蟻數量m為巡檢點個數，設置所有螞蟻的起點為v₀；

步驟3-3、螞蟻k根據下式選擇下一巡檢點：

式中，τ_ij(t)表示t時刻螞蟻殘留在(i,j)之間的信息素濃度，初始時刻信息素濃度τ₀相同；螞蟻使用偽隨機比例規則，則螞蟻以概率q₀從位置i轉移到位置j,其中位置j是使得[τ_ij(t)]^α·[η_ij(t)]^β達到最大的位置；q₀∈(0,1)為常數，而q∈(0,1)為隨機數；j∈allowK表示螞蟻k沒有到過的位置；

η_ij(t)為啟發函數，表示螞蟻從位置i轉移到位置j的期望程度，采用進行計算；

由于(i,j)之間的距離d_ij與經過?？奎c的個數n_ij有數量級的差別，故先進行標準化將d_ij、n_ij映射到[0，1]區間得到即：

其中，d_min、d_max分別為兩節點間的最短路徑、最長路徑，n_min、n_max分別為兩節點間的最少節點個數、最多節點個數；

然后，根據下式局部更新信息素濃度：

τ_ij＝(1-ξ)τ_ij+ξτ₀

其中，ξ為可調參數；

重復步驟3-3直至螞蟻k訪問完所有節點；

步驟3-4、所有螞蟻完成搜索任務，得到初始路徑解集S₁，更新最短距離d^*，最少經過?？奎c數n^*，根據下式計算每只螞蟻的偏離度D，得到當前全局最優路徑A₀：

w₁+w₂＝1

其中，d^*、n^*是當前最優解，w₁、w₂權值表示路徑距離、節點數的重要程度；偏離度D越小即全局路徑解越優，滿意度越高；

步驟3-5、將當前最優路徑A₀作為初始解，執行解中任意節點互換、逆轉、平移的操作，對當前全局最優路徑根據模擬退火原理產生新解，若新解為非劣解，則更新d^*，n^*，重新計算A₀的偏離度；

新解是否非劣解的判斷依據如下式：

其中ΔD＝D-D₀表示新解與初始解偏離度的差，T為當前的溫度，T∈[T_min,T_max]；

步驟3-6、對全局最優路徑A₀進行全局信息素更新，更新依據為：

其中D^best表示當前最優解的偏離度，ρ為信息素揮發系數；

利用偏離度指導更新全局信息素；

步驟3-7、根據下式進行降溫操作：

T＝T·a

其中a為降溫系數，a∈(0,1)，若T＜T_min則退出循環，輸出全局最優路徑A₀，否則轉步驟3-3；

步驟4、用局部最短路徑替換全局最優路徑中的局部路徑，得到完整的最終路徑。