[發明專利]基于時序差分學習算法的最短路徑規劃方法和裝置

有效

• 申請號: 202010430881.6
• 申請日: 2020-05-20
• 公開（公告）號: CN111626489B
• 公開（公告）日: 2023-04-18
• 發明（設計）人: 劉晶;范淵
• 申請（專利權）人: 杭州安恒信息技術股份有限公司
• 主分類號: G06Q10/047
• 分類號: G06Q10/047;G06N3/092
• 代理公司: 杭州華進聯浙知識產權代理有限公司 33250
• 代理人: 賀才杰

本申請涉及一種基于時序差分學習算法的最短路徑規劃方法、裝置、計算機設備和計算機可讀存儲介質。其中，該基于時序差分學習算法的最短路徑規劃方法包括：獲取待規劃網絡的拓撲結構數據；根據拓撲結構數據，建立待規劃網絡的網絡模型；獲取場景信息，并根據場景信息確定最短路徑規劃模型，其中，最短路徑規劃模型是基于時序差分學習算法訓練的；根據最短路徑規劃模型，計算網絡模型中起點到終點的最短路徑。通過本申請，解決了相關技術中最短路徑算法在不同的策略應用中存在局限性的問題，提高了時序差分學習算法的實用性。

技術領域

本申請涉及計算機領域，特別是涉及基于時序差分學習算法的最短路徑規劃方法、裝置、計算機設備和計算機可讀存儲介質。

背景技術

尋找最短路徑是復雜網絡理論里的基礎算法，具有廣泛的應用場景，同時也是其它更復雜模型的重要基礎。

目前相關技術中復雜網絡理論里尋找最短路徑算法主要有Dijkstra算法、Bellman-Ford算法、Johnson算法以及Q學習算法，其中，Q學習算法只能在離軌策略下進行學習，無法應用于同軌策略；而Dijkstra算法、Bellman-Ford算法、Johnson算法雖然能在同軌策略中應用，但是這些算法對于三維或更高維的網絡計算時需要降解、分割等繁瑣的過程，同時計算量較大，另外這些應用在動態網絡中的擴展性不佳。

針對相關技術中最短路徑算法在不同的策略應用中存在局限性的問題，尚未提出有效的解決方案。

發明內容

本申請實施例提供了一種基于時序差分學習算法的最短路徑規劃方法、裝置、計算機設備和計算機可讀存儲介質，以至少解決相關技術中最短路徑算法在不同的策略應用中存在局限性的問題。

第一方面，本申請實施例提供了一種基于時序差分學習算法的最短路徑規劃方法，包括：

獲取待規劃網絡的拓撲結構數據；

根據所述拓撲結構數據，建立所述待規劃網絡的網絡模型；

獲取場景信息，并根據場景信息確定最短路徑規劃模型，其中，所述最短路徑規劃模型是基于時序差分學習算法訓練的；

根據所述最短路徑規劃模型，計算所述網絡模型中起點到終點的最短路徑。

在其中一些實施例中，根據與確定的路徑規劃策略對應的時序差分學習算法，根據場景信息確定最短路徑規劃模型包括：

在根據所述場景信息確定所述路徑規劃策略為同軌策略的情況下，根據基于Sarsa算法的最短路徑規劃模型計算所述網絡模型中起點到終點的最短路徑。

在其中一些實施例中，根據與確定的路徑規劃策略對應的時序差分學習算法，根據場景信息確定最短路徑規劃模型包括：

在根據所述場景信息確定所述路徑規劃策略為離軌策略的情況下，根據基于期望Sarsa算法的最短路徑規劃模型計算所述網絡模型中起點到終點的最短路徑。

在其中一些實施例中，根據Sarsa算法在所述網絡模型中進行最短路徑規劃包括：所述基于Sarsa算法的最短路徑規劃模型的訓練過程包括：

基于∈-貪婪法在所述網絡模型中的當前點S選擇第一動作A，以使得規劃的路徑從當前點S延伸到下一點S′，并確定即時獎勵R；

在所述下一點S′，計算基于∈-貪婪法在所述下一點S′選擇第二動作A′的收獲Gt，并根據所述收獲Gt和所述即時獎勵R，更新Sarsa算法的價值函數Q。

在其中一些實施例中，根據期望Sarsa算法在所述網絡模型中進行最短路徑規劃包括：所述基于期望Sarsa算法的最短路徑規劃模型的訓練過程包括：

基于∈-貪婪法在所述網絡模型中的當前點S選擇第一動作A，以使得規劃的路徑從當前點S延伸到下一點S′，并確定即時獎勵R；