[發明專利]一種基于分支定界法的自動切圖方法

有效

• 申請號: 202110038919.X
• 申請日: 2021-01-12
• 公開（公告）號: CN112883290B
• 公開（公告）日: 2023-06-27
• 發明（設計）人: 陳龍;高凌霄;劉坤華
• 申請（專利權）人: 中山大學
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06F16/53;G06F16/56;G01S7/48
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 陳偉斌

本發明涉及機器人自主導航的技術領域，更具體地，涉及一種基于分支定界法的自動切圖方法。一種基于分支定界法的自動切圖方法，其中，包括切圖觸發器，離線處理和分支定界法三個部分。該自動切圖方法致力于解決上述提出的人工干預的問題，本方法的定位是一個輔助算法，在實際應用中一般會隨定位算法一起啟動。此外，該方法不僅能夠確定當前定位應該使用哪一個先驗地圖，同時也可以解決重定位的問題。

技術領域

本發明涉及機器人自主導航的技術領域，更具體地，涉及一種基于分支定界法的自動切圖方法。

背景技術

在現代的無人車中，定位是必不可少的一個技術部分。要實現自動駕駛，或者說自動導航，無人車需要獲得精準的定位，才能夠精準地導航。猶如人行走，必須知道自己的位置和方向，才能夠知道要往哪里去。現有的定位技術有許多種，有單點GPS定位，有差分GPS定位，有激光雷達定位，還有用計算機視覺的方法來定位。

每種定位技術都有各自的優缺點，例如：單點GPS依靠衛星的數量來衡量定位的質量；差分GPS需要兩個站來維持分米乃至厘米級的定位，往往來說，需要基站和移動站收發信號的穩定才能保證質量，而且信號的傳輸往往帶來技術成本的增加；激光雷達定位，需要很大的運算量來計算點云匹配，而且定位效果往往不佳；計算機視覺的定位方法十分依賴攝像頭的質量，還有光線的限制，等等。往往單靠一種技術是不夠得到魯棒性強的定位效果，需要融合多種傳感器設備數據。

同時，在實際應用中，經常會遇到這樣一個場景，即當前定位已經到達了地圖的邊緣，應該如何處理。一般的處理方法是啟動算法的同時定位于建圖模塊，或者停止算法，判斷當前將要去往哪個地圖，然后重啟算法并載入新地圖。第一種方法沒有用到先驗地圖，所以定位準確性會降低，第二種方法需要人工干預，降低了自動化，當有多臺小車時這種方法效率太低。

IMU(Inertial?measurement?unit)，是指慣性測量單元；slam(simultaneouslocalization?and?mapping)，是指即時定位與地圖構建。

發明內容

本發明旨在至少在一定程度上解決上述技術問題，提供一種基于分支定界法的自動切圖方法，該自動切圖方法致力于解決上述提出的人工干預的問題，本方法的定位是一個輔助算法，在實際應用中一般會隨定位算法一起啟動。此外，該方法不僅能夠確定當前定位應該使用哪一個先驗地圖，同時也可以解決重定位的問題。

本發明的技術方案是：一種基于分支定界法的自動切圖方法，其中，包括切圖觸發器，離線處理和分支定界法三個部分，其中，

切圖觸發器主要分為兩個部分，一個部分是判斷定位數據是否超出地圖邊界，另一個部分是判斷當前點云數據的占據柵格地圖與定位所屬子圖間的匹配得分；

離線處理主要是由用戶輸入某一地圖關聯的地圖，隨后算法通過簡單的邏輯，將地圖關系更新到數據庫中；

分支定界法尋找當前激光雷達采集到的點云屬于哪個占據柵格地圖；首先將下界定義為用戶提供的一個閾值，同時將搜索空間構造為樹形結構，內部節點代表一個子搜索空間，葉子節點代表一個精確的結果；開始搜索時從頂層節點開始往下搜索，當遇到一個節點時，根據該節點位姿變換矩陣旋轉當前幀占據柵格地圖得到新地圖，遍歷新地圖所有點，根據第二步中載入的子圖預算值更新相應子圖舊的占據值，將占據值進行加和，若小于下界，說明結果太差，該分支被剪枝；若大于上界，繼續往下搜索，直到葉子節點；抵達葉子節點后，使用葉子節點占據值得分更新下界，返回頂層重新查找。

進一步的，使用分支定界法縮小搜索域，找出唯一一個符合要求的占據柵格地圖。

進一步的，通過外置定位算法獲得定位結果，通過該定位結果判斷是否產生地圖越界情況，并以此判斷是否需要切圖。

進一步的，主線程處理判斷是否產生越界，當有越界情況發生時，開啟一個線程進行分支定界法搜索。