[發明專利]基于跳點路徑搜索的模式數據庫信息壓縮方法及系統

有效

• 申請號: 201911138912.4
• 申請日: 2019-11-20
• 公開（公告）號: CN111104471B
• 公開（公告）日: 2023-03-31
• 發明（設計）人: 秦龍;胡越;尹全軍;鞠儒生;彭勇;焦鵬;張琪;王鵬;楊妹
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/22;H03M7/30
• 代理公司: 長沙國科天河知識產權代理有限公司 43225
• 代理人: 邱軼

1.一種基于跳點路徑搜索的模式數據庫信息壓縮方法，其特征在于：

S1，對均勻網格地圖進行結構分析，識別出所有軸向跳點，生成軸向跳點集，所述軸向跳點識別步驟包括：

S11，掃描均勻網格地圖中所有節點，并識別出所有節點中存在的障礙物頂點；

S12，獲得所有障礙物頂點的可行對角節點；

S13，在包含障礙物頂點與該障礙物定點的可行對角節點的兩個公共鄰域節點均為可通行節點時，將該障礙點的可行對角節點識別為軸向跳點；

S14，重復步驟S13獲得均勻網格地圖中所有軸向跳點；

S2，根據軸向跳點集識別出所有有源對角跳點，生成有源對角跳點集，其中可通行節點在對角方向上由軸向跳點經過無障礙的移動到達時，認定該可通行節點為有源對角跳點；

S3，對均勻網格地圖所有可通行節點進行深度優先排序，獲得所有可通行節點按照位置相近程度建立的索引；

S4，以所有軸向跳點與有源對角跳點的塌縮位置為源節點進行全地圖搜索，得到所有源節點和所有可通行節點之間的最優路徑的初始邊，并結合索引，生成預處理信息；

S5，對上述預處理信息進行壓縮，生成壓縮模式數據庫。

2.如權利要求1所述的一種基于跳點路徑搜索的模式數據庫信息壓縮方法，其特征在于，所述步驟S2中有源對角跳點識別的步驟包括：

S21，計算均勻網格地圖上所有可通行節點軸向跳躍距離表，該表顯示每個可通行節點在軸向方向上至其他軸向跳點或障礙物的距離；

S22，計算均勻網格地圖上所有可通行節點對角跳躍距離表，該表顯示每個可通行節點在對角方向上至其他可通行節點的距離，該可通行節點可通過該對角方向的某一軸向分量的方向到達某一軸向跳點；

S23，以每個軸向跳點為源進行遍歷，反復讀取當前節點的對角距離，對角距離為正表明在該位置能夠將對角方向的移動轉入軸向移動，從而到達軸向跳點，則判斷當前節點為有源對角跳點。

3.如權利要求1所述的一種基于跳點路徑搜索的模式數據庫信息壓縮方法，其特征在于，S4中所述生成預處理信息具體包括：

預處理信息由二維矩陣組成，全地圖所有可通行節點中的每個節點對應一列，且按照S3中得到的可通行節點索引排列；

每個塌縮位置對應一行生成一類預處理信息，其中該行每個元素存儲該行塌縮位置到達該可通行節點的最優路徑的所有初始邊情況，用標識位來表示；

將每個塌縮位置拆分獲得塌縮位置對應的所有跳點，每個拆分的跳點對應一行，根據跳點類型確定了該跳點的主序擴展方向，對應行中僅取該跳點主序擴展方向與每個可通行節點初始邊的交集，記錄為該行的每個元素，生成二類預處理信息，其中每個元素存儲該行跳點到達該可通行節點的最優路徑的初始邊，用標識位來表示。

4.如權利要求3所述的一種基于跳點路徑搜索的模式數據庫信息壓縮方法，其特征在于，所述S5對上述預處理信息進行壓縮，生成壓縮模式數據庫的步驟包括：

在同類預處理信息中，將待壓縮元素的最優初始邊與該元素所在行前一元素所在回合的最優初始邊進行對比，若相同，則將當前元素并入前一元素所在的回合，否則重新開始一個新的回合，其中每個回合記錄其所包含的所有元素的起始位置和該回合代表的最優初始邊。

5.如權利要求3所述的一種基于跳點路徑搜索的模式數據庫信息壓縮方法，其特征在于，

所述標識位由8個bit位按固定順序分別表示塌縮位置或塌縮位置對應跳點的8個鄰域的初始邊；

當該鄰域具有最優路徑初始邊時，該鄰域對應的bit位設置為1，否則為0。

6.如權利要求5所述的一種基于跳點路徑搜索的模式數據庫信息壓縮方法，其特征在于，一類預處理信息進行壓縮生成一類模式數據庫的方法包括：

S51a，在壓縮當前塌縮位置對應的一行時，將該行第一個元素作為當前回合代表的最優初始邊；

S52a，對該行所有元素進行循環，若當前元素與當前回合的所有bit位都相同，則將其也并入此回合；

S53a，當相鄰兩個元素的標識位有任一bit不同，則重新開始一個回合。