[發明專利]智能體行進路徑的確定方法及裝置

有效

• 申請號: 201810914223.7
• 申請日: 2018-08-13
• 公開（公告）號: CN110826755B
• 公開（公告）日: 2022-06-28
• 發明（設計）人: 彭成;嚴孝偉;朱禮君;劉衡;周愷;楊志遠;趙海兵
• 申請（專利權）人: 菜鳥智能物流控股有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 北京清源匯知識產權代理事務所(特殊普通合伙) 11644
• 代理人: 馮德魁;竇曉慧

本申請提供一種智能體行進路徑的確定方法，包括：確定當前智能體的當前位置到目標位置之間的可達位置及可達位置對應的可達時間；根據可達位置及可達位置對應的可達時間，確定當前智能體由當前位置到目標位置的至少一個備選行進路徑；根據所述至少一個備選行進路徑，確定當前智能體由當前位置到目標位置的實際行進路徑。由于這種技術方案是通過可達時間來控制智能體到達可達位置的時刻，因此智能體在可達時間內到達可達位置即可，至于以何種速度行進至可達位置無需特殊要求，可以是非勻速運動等，可以是運動一段時間再停止一段時間，從而使智能體能在連續時間內非勻速地到達目標位置。

技術領域

本申請涉及路徑規劃領域，具體涉及一種智能體行進路徑的確定方法及裝置，還涉及一種電子設備、計算機可讀存儲介質。

背景技術

在物流領域，智能體(如物流機器人)可以代替人工完成分揀任務。其中，對大量智能體進行路徑規劃的技術尤為關鍵。對大量的智能體進行路徑規劃，是一個經典的優化問題，叫多智能體路徑規劃(Multi-Agent Path Planning，MAPF)。具體來說，給定一個由點集合和邊集合組成的地圖和一定數量的智能體(Agent)，并為這些智能體設置初始位置和目的地，求解出每個智能體的運動路線，使得每個智能體都能無沖突(不與固定障礙物，或者其他智能體發生沖突)的從各自的起始位置運動到各自的目的地。

此前，關于多智能體路徑規劃的研究，除了關于MAPF的研究之外，還有關于多機器運動規劃(Multi-Robot Motion Planning，MMP)的研究。幾乎所有MAPF的研究工作都有兩個設定：1)將時間離散化，即時間軸由一個個的單位時間組成；2)基于勻速網絡圖的(Constant Velocity Network，CVN)，沒有考慮智能體本身的運動模型，即認為所有的智能體在任意時刻都是勻速運動，即任何時候都是一個時間單位運動一個單位距離。研究者也提出了MAPF-POST算法，對傳統MAPF算法規劃的路徑做后處理。通過任意MAPF算法找到所有智能體在理想環境中的路徑后，將路徑畫為一張增強時序計劃圖，每一個智能體的路徑占一行，每個點代表一個事件，點表示智能體i將排在第j個訪問點X。如果有個點被多個智能體訪問，后一個智能體只能在前一個智能體離開后才能前進該點。MAPF-POST算法使得各種MAPF算法求解的方案可以轉換成一個不相撞的執行方案。

在現實場景中，比如物流機器人，是在連續時間中運行的，且每個機器人都有自身的物理運動模型，比如啟動的時候會有一個加速過程，停止前會有一個減速過程。以往MAPF算法無法有效處理這樣的連續時間、非勻速運動的現實場景。以往的MMP算法、MAPF-POST算法同樣不適合解決現實場景的大規模智能體路徑規劃問題。

發明內容

本申請提供一種智能體行進路徑的確定方法及裝置，旨在解決大量智能體在連續時間、非勻速運動中路徑規劃的技術問題。本申請還涉及一種電子設備以及一種計算機可讀存儲介質。

本申請提供的智能體行進路徑的確定方法包括：

確定當前智能體的當前位置到目標位置之間的可達位置及可達位置對應的可達時間；

根據可達位置及可達位置對應的可達時間，確定當前智能體由當前位置到目標位置的至少一個備選行進路徑；

根據所述至少一個備選行進路徑，確定當前智能體由當前位置到目標位置的實際行進路徑。

在本實施例中，所述當前位置到目標位置之間的可達位置通過以下方式確定：

針對當前智能體的當前位置和當前方向，確定第一可達方向，得到當前位置當前方向上的第一可達方向及對應的可達位置；

針對當前智能體的當前位置和當前方向，根據在當前方向上直行若干單位距離的動作空間，確定當前位置當前方向上的直行可達位置，得到第二可達方向及對應的可達位置；