[發明專利]一種基于時間代價函數的時間窗路徑規劃沖突解決方法

有效

• 申請號: 201710264277.9
• 申請日: 2017-04-21
• 公開（公告）號: CN107167154B
• 公開（公告）日: 2020-04-24
• 發明（設計）人: 李新德;何健
• 申請（專利權）人: 東南大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 梁耀文

1.一種基于時間代價函數的時間窗路徑規劃沖突解決方法，其特征在于，具體步驟如下：

第一步：采用拓撲建模法對AGV運行環境進行建模，得到一張有向連接圖G＝(V,E)，其中V代表圖中的所有節點，E代表圖中節點之間的邊，節點之間的每一條邊(u,v)都含有一個權值w_uv，表示節點之間的距離；

第二步：手動添加運輸任務，并針對每個任務，采用Dijkstra算法進行路徑規劃；

第三步：計算所有路段的時間窗，并檢查所有路段的時間窗是否出現沖突，如果出現沖突則進入第四步，如果沒有出現沖突則進入第六步；

第四步：重新采用Dijkstra算法進行路徑規劃，并計算等待代價函數C_W和二次規劃代價函數C_R的數值，其中等待代價函數C_W表示按原有規劃路徑在等待一段時間后繼續行駛所需的時間，二次規劃代價函數表示按重新規劃后的路徑行駛所需的時間；

第五步：比較兩個函數的值，觀察等待代價函數C_W是否大于二次規劃代價函數C_R，如果C_WC_R則按照重新規劃的路徑行駛并結束，如果C_W≤C_R則進入第六步；

第六步：按照原路徑行駛并結束；

所述等待代價函數C_W主要由等待時間代價C_W1、剩余路徑代價C_W2、剩余路徑沖突代價C_W3三個分量構成，并且C_W＝C_W1+C_W2+C_W3：

其中等待時間代價C_W1的計算方法如下

C_W1＝t_w

其中，t_w表示小車在執行任務過程中遇到沖突的等待時間；

剩余路徑代價C_W2的計算方法如下

其中，|e_j|表示剩余路徑中邊e_j的距離，邊e_j表示有向連接圖中兩個節點之間的線段，這里指代小車行進中的路線，m表示剩余路徑中起始邊的編號，n表示剩余路徑中終止邊的編號，v表示小車的行駛速度；

剩余路徑沖突代價C_W3的計算方法如下

其中，t_j表示小車在行駛剩余路徑的過程中在邊e_j的沖突代價，沖突代價表示在小車等待一段時間后經過邊e_j預估的二次等待時間，m表示剩余路徑中起始邊的編號，n表示剩余路徑中終止邊的編號；如果在邊e_j未發生沖突，則t_j的值為0。

2.根據權利要求1所述的一種基于時間代價函數的時間窗路徑規劃沖突解決方法，其特征在于，所述二次規劃代價函數C_R包含二次規劃后的路徑代價C_R1和二次規劃后的路徑沖突代價C_R2兩個分量，并且C_R＝C_R1+C_R2：

其中二次規劃后的路徑代價C_R1的計算方法如下

其中，|e_k|表示二次規劃路徑中邊e_k的距離，邊e_k表示有向連接圖中兩個節點之間的線段，這里指代小車行進中的路線，p表示二次規劃路徑中起始邊的編號，q表示二次規劃路徑中終止邊的編號，v表示小車的行駛速度；

二次規劃后的路徑沖突代價C_R2的計算方法如下

其中，t_k表示小車在行駛二次規劃路徑的過程中在邊e_k的沖突代價，沖突代價表示在小車等待一段時間后經過邊e_k預估的二次等待時間，p表示二次規劃路徑中起始邊的編號，q表示二次規劃路徑中終止邊的編號，需要注意的是，如果在邊e_k未發生沖突，則t_k的值為0。