[發明專利]一種揀貨路徑規劃方法和裝置

在審

• 申請號: 202010041933.0
• 申請日: 2020-01-15
• 公開（公告）號: CN113128743A
• 公開（公告）日: 2021-07-16
• 發明（設計）人: 朱瀅
• 申請（專利權）人: 北京京東振世信息技術有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06K9/62
• 代理公司: 中原信達知識產權代理有限責任公司 11219
• 代理人: 張一軍;李陽

本發明公開了揀貨路徑規劃方法和裝置，涉及計算機技術領域。該方法的一具體實施方式包括獲取待揀貨儲位在同一坐標軸下的坐標信息，基于待揀貨儲位的密度分布進行聚類，以生成子集；將子集的核心點作為該子集的坐標信息，計算出從距離目標位置最遠子集核心點到距離目標位置最近子集核心點的路徑，以得到各個子集的順序關系；基于各個子集的順序關系，選取每個子集中的路徑起始點和路徑結束點，生成每個子集對應的子路徑，進而順序連接所有子路徑得到揀貨路徑。從而，本發明的實施方式能夠解決現有生成路徑的算法其準確性和快速性都比較低的問題。

技術領域

本發明涉及計算機技術領域，尤其涉及一種揀貨路徑規劃方法和裝置。

背景技術

路徑規劃主要解決的問題是根據地理環境信息將地圖中的離散點連接成一條路徑，提供可行通路。其應用十分廣泛，包括各種機器人的路徑規劃、車輛導航、路由問題等。

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

現有的路徑規劃算法在生成路徑時，往往需要遍歷網格或圖中的每一個節點，存在容易陷入局部最優，響應速度較慢的缺陷。因此，目前生成路徑的算法其準確性和快速性都比較低。

發明內容

有鑒于此，本發明實施例提供一種揀貨路徑規劃方法和裝置，能夠解決現有生成路徑的算法其準確性和快速性都比較低的問題。

為實現上述目的，根據本發明實施例的一個方面，提供了一種揀貨路徑規劃方法，包括獲取待揀貨儲位在同一坐標軸下的坐標信息，基于待揀貨儲位的密度分布進行聚類，以生成子集；將子集的核心點作為該子集的坐標信息，計算出從距離目標位置最遠子集核心點到距離目標位置最近子集核心點的路徑，以得到各個子集的順序關系；基于各個子集的順序關系，選取每個子集中的路徑起始點和路徑結束點，生成每個子集對應的子路徑，進而順序連接所有子路徑得到揀貨路徑。

可選地，包括：

以橫向坐標的主通道為主路，基于預設行走方向，按照子集的坐標信息中的橫向坐標或者通過迪杰斯特拉算法，計算出從距離目標位置最遠子集核心點到距離目標位置最近子集核心點的最短路徑，以得到各個子集的順序關系。

可選地，基于各個子集的順序關系，選取每個子集中的路徑起始點和路徑結束點，生成每個子集對應的子路徑，包括：

根據各個子集的順序關系，在每個子集中選取距離前一個子集核心點最近的待揀貨儲位作為該子集的路徑起始點，距離后一個子集核心點最近的待揀貨儲位作為該子集的路徑結束點；進而基于子集中的每個待揀貨儲位的坐標信息，計算子集內的最短路徑，生成子集對應的子路徑。

可選地，計算子集內的最短路徑，生成子集對應的子路徑，包括：

采用網格法將障礙物位置進行標記，通過預設的尋路算法計算子集內的最短路徑，以生成子集對應的子路徑。

另外，本發明還提供了一種揀貨路徑規劃裝置，包括獲取模塊，用于獲取待揀貨儲位在同一坐標軸下的坐標信息，基于待揀貨儲位的密度分布進行聚類，以生成子集；處理模塊，用于將子集的核心點作為該子集的坐標信息，計算出從距離目標位置最遠子集核心點到距離目標位置最近子集核心點的路徑，以得到各個子集的順序關系；生成模塊，用于基于各個子集的順序關系，選取每個子集中的路徑起始點和路徑結束點，生成每個子集對應的子路徑，進而順序連接所有子路徑得到揀貨路徑。

可選地，所述處理模塊，還用于：

以橫向坐標的主通道為主路，基于預設行走方向，按照子集的坐標信息中的橫向坐標或者通過迪杰斯特拉算法，計算出從距離目標位置最遠子集核心點到距離目標位置最近子集核心點的最短路徑，以得到各個子集的順序關系。

可選地，所述生成模塊基于各個子集的順序關系，選取每個子集中的路徑起始點和路徑結束點，生成每個子集對應的子路徑，包括：