天天看點

夜光精講 Opentcs 三大算法(八)路徑算法

夜光序言:

一個具有思想天賦(Genius)的人過着在個人生活之外,還過着另一種思想上的生活,後者逐漸成為了他的唯一目标,而前者隻是作為實作自己目标的一種手段而已。

但對于芸芸衆生來說,隻有淺薄、空虛和充滿煩惱的生存才會被視為生活的目标,精神卓越的人首要關注的是精神上的生活。

随着他們對事物的洞察和認識持續地加深和增長,他們的生活獲得了一種整體的統一;精神生活的境界穩步提升而變得完整、美滿,就像一件逐漸變得完美的藝術品。

夜光精講 Opentcs 三大算法(八)路徑算法

正文:分層路徑算法實作

對于大型倉庫,整個系統的地圖資料量十分龐大,将總路徑存儲至一個哈希表中,将要占用巨大的空間。當某一點或邊有修改變動時,需要重新進行計算,計算量很大且效率急劇降低。

是以我們将倉庫進行分區,縮小每塊地圖的規模,每個區域均有自己的哈希表,區域之間的連接配接點和邊組成全局巧撲圖,為全局拓撲圖增添獨有的哈希表,毎個區域維護獨屬的哈希表。

當局部區域發生資料更新時,隻需更新其所屬區域的資料和哈希表,其他哈希表不做改動,極大地提高了系統的維護效率,降低了更新更新成本。同時實作了AGV跨樓層跨區域運輸作業。

做出如下規定:

(1)毎個地圖塊包含的點和邊同屬一種導航方式。

允許毎個區域之間有多個出口和入口點,整個倉庫系統可多個導航方式,同一個點可隸屬不同導航方式的地圖塊。

(2)—部電梯單獨屬于一個地圖塊。

跨區域路徑規劃時,将倉庫為全局搜尋層和局部搜尋層。

假設需要尋找從點Pi到Pj的全路徑,兩點分别隸屬區域i和j。首先找到從區域i跨到區域j的路線(通過總哈希表),得到區域之間通行的出口和入口點,再在毎個區域内規劃路線,最後進行路線按序拼接(CList*指針連結清單的合并)。

(3)全局環境中,Point收集的毎個地圖區域的出口/入口點。

夜光精講 Opentcs 三大算法(八)路徑算法
夜光精講 Opentcs 三大算法(八)路徑算法

繼續閱讀