[發明專利]機器人運行路徑生成方法及裝置

有效

• 申請號: 201810116720.2
• 申請日: 2018-02-06
• 公開（公告）號: CN110118566B
• 公開（公告）日: 2022-11-25
• 發明（設計）人: 李大雙
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京三高永信知識產權代理有限責任公司 11138
• 代理人: 劉映東

本發明實施例公開了一種機器人運行路徑生成方法及裝置，屬于計算機技術領域。所述方法包括：接收路徑查詢生成請求，根據起始路徑點、終止路徑點以及預設的所有路徑點，隨機生成多個備選路徑，根據每個備選路徑的至少一個目標值，通過調用目標組合算法，確定每個備選路徑的成本值，確定多組備選路徑，對每組備選路徑進行優化，基于每組優化路徑以及每個優化后的備選路徑的成本值，確定目標機器人運行路徑。采用本發明，可以得到更符合需求的機器人運行路徑，減少機器人運行的成本。

技術領域

本發明涉及計算機技術領域，特別涉及一種機器人運行路徑生成方法及裝置。

背景技術

對于機器人運行路徑規劃、深度學習、生成測試用例等問題，可以擁有多個解集，其中包含有滿足目標的最優解。例如，機器人路徑規劃的解集可以是多條路徑的集合，可以在其中找到一條最短路徑，或者是滿足多目標的路徑(如路徑距離、時長消耗和能源消耗最合適的路徑)作為最優解。

實際環境中的情況較為復雜，上述問題是NP-hard問題(non-deterministicpolynomial，NP，非確定性多項式)，其解集可能過多，無法在有限的時間內遍歷所有解以找到最優解，只能擴大搜尋的解空間，不斷尋找較優解。現有技術中一般采用NSGA-II(thefast elitism non-dominated sorting genetic algorithm，快速非支配排序遺傳算法)，對NP-hard問題進行求解。

在實現本發明的過程中，發明人發現現有技術至少存在以下問題：

現有的NSGA-II，搜索范圍較小，局部收斂過早，過度依賴初始種群，得到的較優解與最優解的差距較大。從而，導致對NP-hard問題進行求解時，得到的解集適應度較低，例如，生成機器人運行路徑時，得到的路徑可能不是最符合需求的路徑，增加了機器人運行的成本。

發明內容

為了解決現有技術的問題，本發明實施例提供了一種問題的解決方案確定方法及裝置。所述技術方案如下：

一方面，提供了一種機器人運行路徑生成方法，所述方法包括：

接收路徑生成請求，所述路徑生成請求攜帶起始路徑點和終止路徑點；

根據所述起始路徑點、所述終止路徑點以及預設的所有路徑點，隨機生成多個備選路徑；

根據每個備選路徑的至少一個目標值，調用目標組合算法，確定每個備選路徑的成本值，其中，所述至少一個目標值包括以下一項或多項：備選路徑的路徑長度、備選路徑的時長消耗、備選路徑的能源消耗；

根據所述每個備選路徑的成本值和至少一個目標值，確定多組備選路徑，每組備選路徑中包括一個第一備選路徑以及與所述第一備選路徑對應的第二備選路徑；

對每組備選路徑進行優化，生成多組優化路徑，每組優化路徑中包括優化后的第一備選路徑以及與優化后的第一備選路徑對應的第二備選路徑；

基于每組優化路徑以及每個優化后的備選路徑的成本值，確定目標機器人運行路徑。

一方面，提供了一種機器人運行路徑生成裝置，所述裝置包括：

接收模塊，用于接收路徑生成請求，所述路徑生成請求攜帶起始路徑點和終止路徑點；

生成模塊，用于根據所述起始路徑點、所述終止路徑點以及預設的所有路徑點，隨機生成多個備選路徑；

第一確定模塊，用于根據每個備選路徑的至少一個目標值，調用目標組合算法，確定每個備選路徑的成本值，其中，所述至少一個目標值包括以下一項或多項：備選路徑的路徑長度、備選路徑的時長消耗、備選路徑的能源消耗；

第二確定模塊，用于根據所述每個備選路徑的成本值和至少一個目標值，確定多組備選路徑，每組備選路徑中包括一個第一備選路徑以及與所述第一備選路徑對應的第二備選路徑；