[發明專利]一種基于帶時間窗A*改進的多車路徑規劃方法

有效

• 申請號: 202011487316.X
• 申請日: 2020-12-16
• 公開（公告）號: CN112665603B
• 公開（公告）日: 2022-03-25
• 發明（設計）人: 王欣然
• 申請（專利權）人: 的盧技術有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34;G01C21/20
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 姜慧勤

1.一種基于帶時間窗A*改進的多車路徑規劃方法，其特征在于，包括如下步驟：

步驟1，獲取路網結構信息以及該路網上所有車輛的位置，生成動態拓撲圖；

步驟2，結合動態拓撲圖以及已規劃的其它車輛路徑的時間窗信息，采用帶時間窗的A*算法規劃當前車輛從起始節點到目標節點的全局路徑，并基于車輛動力學模型計算車輛遵循全局路徑行駛時的時間窗；

步驟3，對于當前車輛的全局路徑在其經過的路口處進行分割，將全局路徑分割為多個路徑段，將分割后的路徑段逐段下發給當前車輛執行，即當前車輛執行完前一個路徑段后到達該路徑段的出口停止等待，直到下一個路徑段下發后再執行下一個路徑段，直至所有路徑段都執行完；

步驟4，根據當前車輛到達前一個路徑段的出口時，實際時刻和理想時刻之間的差異，對下一個路徑段的時間窗進行調整，所述理想時刻即步驟2計算得到的車輛離開路徑段的時刻，具體如下：

1)若實際時刻與理想時刻差值的絕對值小于等于5秒，則下一個路徑段直接下發不做時間窗調整；

2)若實際時刻早于理想時刻Δt秒，Δt為設定值，并且當前車輛到達前一個路徑段的出口時無其他車輛等待或者當前車輛的優先級最高，則將下一個路徑段的時間窗都減去Δt秒；

3)若實際時刻早于理想時刻Δt秒，但在前一個路徑段的出口處有其他車輛并且其他車輛的優先級高于當前車輛，若等待優先級比當前車輛高的其他車輛通過的時間為k秒，則將下一個路徑段的時間窗都減去Δt-k秒。

2.根據權利要求1所述基于帶時間窗A*改進的多車路徑規劃方法，其特征在于，所述步驟1的具體過程如下：

步驟1.1，獲取路網結構信息，將路網上的道路段映射為拓撲圖上的節點，道路段之間的連接以及駛入駛出關系映射為拓撲圖上的邊，生成初始的動態拓撲圖；

步驟1.2，計算所有邊的權值，具體為：當邊前后兩側的道路段均為直行道時，邊的權值為0；當邊左右兩側的道路段均為直行道時，邊的權值為50；當前后兩側的道路段一個為直行道另一個為彎道時，邊的權值為20；

步驟1.3，計算所有節點的權值，具體為：當節點上未?？寇囕v時，節點的權值為該節點對應的道路段的長度；當節點上停靠車輛時，節點的權值為Weight＝Length*(1+2^K)，其中，Weight表示節點的權值，Length表示節點對應的道路段的長度，K表示節點上?？康能囕v的數目，K≥1；

步驟1.4，將邊的權值、節點的權值與初始的動態拓撲圖結合起來，得到動態拓撲圖。

3.根據權利要求1所述基于帶時間窗A*改進的多車路徑規劃方法，其特征在于，步驟2所述采用帶時間窗的A*算法規劃當前車輛從起始節點到目標節點的全局路徑中，將全局路徑視為依次連接的若干節點，在第n個節點的離開時刻規劃第n+1個節點時增加時間維度的約束條件：

條件1，對于當前車輛而言，選擇第n個節點的鄰接節點作為第n+1個節點，且第n個節點的鄰接節點中不包括第n-1個節點；

條件2，對于當前車輛而言，其在第n+1個節點的進入時刻至離開時刻的時間窗內未被其他已規劃好的車輛的全局路徑占用。

4.根據權利要求1所述基于帶時間窗A*改進的多車路徑規劃方法，其特征在于，步驟3所述路口包括十字路口和T型路口。

5.根據權利要求1所述基于帶時間窗A*改進的多車路徑規劃方法，其特征在于，步驟4所述優先級最高指的是車輛的理想時刻最早。