[發明專利]應急救援場景下多任務沖突檢測與消解的路徑規劃方法

在審

• 申請號: 202111594937.2
• 申請日: 2021-12-24
• 公開（公告）號: CN114659533A
• 公開（公告）日: 2022-06-24
• 發明（設計）人: 劉豐愷;王闊;趙婧瑩;梁光楠;熊家樂;史海鷗
• 申請（專利權）人: 中國電子科技集團公司第十五研究所
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 代麗

1.一種應急救援場景下多任務沖突檢測與消解的路徑規劃方法，其特征在于，包括：

步驟1，以區域內可供轉向的路口作為結點，道路作為邊，構建區域的路網有向帶權圖G(V,E)，其中，V為路網中結點的集合，E為路網中有向邊的集合；其中邊E的權重包括動態權重E.length、E.value和靜態權重E.val；其中，E.val為當前待規劃車隊在理想情況下通過邊E的時間；

步驟2，考慮待規劃車隊和已規劃車隊的沖突情況，對G(V,E)數據進行更新：

S21，提取集合V中未被標記的、value值最小的結點Vmin，并根據G(V,E)獲取其鄰接點，所述鄰接點未被標記；其中value值為當前待規劃車隊到達此結點的時間；路徑起始結點的value值初始化為0；其他結點的value值初始化為無窮大；若集合V中的結點均已被標記，則執行步驟3；

S22，選取Vmin的鄰接結點中未被遍歷的點Vtt，更新結點Vmin與Vtt的邊Ett的權重Ett.length：

1)判斷結點Vmin與結點Vtt的邊Ett是否被其他已規劃車隊所占用，如果未被占用，則令Ett.value＝Ett.val，Ett.length＝Ett.value+fleet.length/velocity；執行2)；其中，fleet.length為待規劃車隊的長度；velocity為待規劃車隊的平均速度；

否則，令Ett.value＝Vmin.end-Vmin.value+Ett.val，Ett.length＝Vmin.end-Vmin.value+Ett.value+fleet.length/velocity；執行2)；

2)判斷待規劃車隊到達結點Vtt時，是否與已規劃車隊相沖突；若不沖突，則令Ett.length＝Ett.value，執行S23；若沖突，則轉入3)；所述沖突是指兩個車隊通過結點Vtt的時間段有重疊；

3)判斷待規劃車隊是否先到達結點Vtt：若待規劃車隊先到達，且待規劃車隊的優先級大于或等于已規劃車隊，則令Ett.length＝Ett.value，執行S23，并通知該沖突已規劃車隊重新規劃；若待規劃車隊先到達，但待規劃車隊的優先級小于已規劃車隊，則執行4)；

若待規劃車隊后到達，但待規劃車隊的優先級大于已規劃車隊，則令Ett.length＝Ett.value，執行S23，并通知該已規劃車隊重新規劃；若待規劃車隊后到達，且待規劃車隊的優先級不大于已規劃車隊，則判斷已規劃車隊的下一個結點是否是Vmin，若是，則令Ett.length＝Vmin.end-Vmin.value+Ett.val，執行S23；否則令Ett.length＝end-Vmin.value，執行S23；

4)判斷已規劃車隊的下一個結點是否是Vmin，若不是，則令Ett.length＝end-Vmin.value，執行S23；若是，則令Ett.length＝Vmin.end-Vmin.value+Ett.val，執行S23；

S23，計算Vtt.value′＝Vmin.value+Ett.length；若Vtt.value′小于結點Vtt的value值，則更新Vtt.value＝Vtt.value′，并將Vmin記錄到回溯向量res當中；

S24，判斷Vmin的鄰接點是否均已遍歷，若未全部遍歷，則返回S22；若均已遍歷則標記當前結點Vmin，返回S21；

步驟3，從路徑終點向前回溯res向量，得到最短路徑。

2.如權利要求1所述的應急救援場景下多任務沖突檢測與消解的路徑規劃方法，其特征在于，所述S22中，判斷結點Vmin與結點Vtt的邊Ett是否被其他已規劃車隊所占用的方式為：

在邊Ett的參數中設置state，用于存放已規劃車隊在邊Ett的占用時間，即[Vmin.start,Vtt.end]或[Vtt.start,Vmin.end]；其中，Vmin.start為已規劃車隊經過結點Vmin的開始時間，Vtt.end為該車隊離開結點Vtt的結束時間；Vtt.start為已規劃車隊經過結點Vtt的開始時間，Vmin.end為該車隊離開結點Vmin的結束時間；

則若待規劃車隊的Vmin.value在state存儲的時間段內，則表明表Ett已被占用，否則，表明未被占用。