機器人柵格地圖編碼與索引方法

張藍天,王光霞,劉 旭,王瑋琦,王慧芳

(1.61646部隊，北京 100192；2.信息工程大學，鄭州 450052；3.空軍航空大學，長春 130022；4.61206部隊，北京 100043)

隨著人工智能、5G、物聯網等技術的發(fā)展，智能機器人與人共融共生態(tài)勢已悄然顯現，尤其是在單調重復、危險、未知環(huán)境中，智能機器人更具有優(yōu)勢。智能機器人高效執(zhí)行既定任務的前提是對所處環(huán)境及其預期影響的準確“理解”。這涉及到智能機器的環(huán)境感知、環(huán)境表示建模和空間推理計算等一系列理論和技術問題，既是新一代人工智能的關鍵共性技術[1]，也是人工智能時代測繪科學關注的新問題[2]。針對機器人環(huán)境表示建模的研究以即時定位與地圖構建技術(Simultaneous Localization and Mapping,SLAM)為主。SLAM技術在沒有環(huán)境先驗知識的前提下試圖完成增量式的機器人位姿估計與環(huán)境模型構建，盡管近年來蓬勃發(fā)展且成果顯著，但其研究重點始終聚焦于位姿估計的速度與精度，鮮有考慮機器人環(huán)境模型的應用(或稱為地圖復用)與管理的研究工作。機器人應用的環(huán)境模型應當盡可能涵蓋其所需環(huán)境信息，并滿足環(huán)境信息更新、空間推理決策等客觀需要。

顯而易見，單一的環(huán)境模型難以表達環(huán)境的全部特征信息，采用多圖層的方式是詳盡地對客觀環(huán)境進行準確刻畫的常見形式。Peter等人為解決足式機器人的室內導航問題，設計了包含障礙層、高程層、法向量層等圖層的室內環(huán)境模型[3]，并在機器人操作系統(Robot Operating System，ROS)中開源了其柵格地圖庫Grid Map Library，如圖1所示。Koch P等為解決輪式機器人在野外環(huán)境的定位導航問題，設計實現了包含拓撲層、三維模型層、正射影像層、DTM層等多圖層的野外環(huán)境模型[4],并使用3種不同的輪式機器人對環(huán)境模型的可用性進行驗證。

圖1 ROS中柵格地圖庫Grid Map Library的柵格編碼方式

在空間推理計算方面，柵格地圖是對連續(xù)空間的離散化表達，其離散化的特性適合高效的數據組織與索引、精準的空間分析與決策。當前機器人柵格地圖以占據柵格地圖為主，針對占據柵格地圖的研究主要涉及：①賦值方式的完善,將早期二值(0為空閑，1為被占據)描述的占據柵格地圖完善為[0,1]區(qū)間的賦值方式[5]，賦值方式的完善使得在建圖過程中能夠更連續(xù)地對環(huán)境進行表達；②表達維度的拓展，顯然2D占據柵格地圖無法滿足諸如無人機、無人艇等無人平臺的使用需求，2.5D占據柵格地圖與3D占據柵格地圖(又稱為八叉樹地圖)應運而生[6-7]，表達維度的拓展能夠滿足各類無人平臺的避障需求；③空間鄰近關系的約束，不論是2D或是3D占據柵格地圖，其在建圖過程中將每一個柵格/體素作為獨立的變量進行處理而不考慮柵格/體素間的空間關系，這種“分而治之”的方式極易導致地圖不連貫等現象的出現(例如，連續(xù)的障礙物區(qū)域中因探測數據缺失等原因出現的個別空閑區(qū)域)，為充分考慮柵格間的空間關系與鄰近關系，研究者們通過構建高斯過程模型或是選用Hilbert核函數等方式對柵格間的空間鄰近關系進行建模，生成一致性更強的占據柵格地圖[8-10]。多圖層的環(huán)境模型試圖解決環(huán)境表示上的詳盡性與完備性等問題，柵格化的表示形式試圖幫助機器人實現空間推理計算與智能決策。盡管在多圖層與柵格表示上成果顯著，但仍缺少多圖層柵格化環(huán)境模型的動態(tài)更新與編碼索引方面的針對性研究。高效的數據組織與索引是實現環(huán)境模型管理、環(huán)境信息聯動更新與空間推理決策的基礎。因此，文中在以上研究成果的基礎上，針對多圖層機器人柵格地圖的編碼與索引方法開展研究，在對柵格地圖進行形式化描述的基礎上，基于空間填充曲線——Hilbert曲線實現多圖層機器人地圖的編碼與索引。

1 柵格地圖的形式化描述

占據柵格地圖(Occupancy Grid Map)是機器人利用激光雷達進行地圖構建時得到的最為常見的一種地圖形式，亦是機器人導航定位時應用最為廣泛的地圖形式。它以柵格地圖作為基礎，對每個柵格是否被“占據”加以描述，以概率累加的方式不斷更新每個柵格的“占據”狀態(tài)，進而完成地圖構建。每個柵格隨著新測量值的獲取不斷更新其占據狀態(tài)，如圖2所示簡要描繪占據柵格地圖構建過程[11]。

圖2 占據柵格地圖構建過程

受限于傳感器性能、機器人個體的動力學模型差異及任務多樣性等不同因素，不同的機器人個體對同一環(huán)境的觀測與建圖結果不盡相同。從機器人地圖應用的角度出發(fā)，機器人地圖應具備為各類無人平臺提供服務的能力，如圖3所示為本研究出發(fā)點：占據柵格地圖作為機器人環(huán)境探測的成果，對其進行形式化描述以滿足其為各種無人平臺所使用的需求，在形式化描述的基礎上，各類無人平臺依據自身的性能指標、動力學模型及載具要求等情況生成滿足自身需求的個性化柵格地圖。基于此認識，文中聚焦于機器人占據柵格地圖的形式化描述及柵格編碼與索引的研究工作，首先對機器人柵格地圖進行形式化描述，以機器人領域最為常見的占據柵格地圖為基礎，拓寬機器人領域柵格地圖的表達內容(不再局限于柵格的占據狀態(tài)描述)，形成機器人柵格地圖的統一接口，既能對占據柵格地圖進行形式化描述，又可以容納測繪領域的基礎地理信息、豐富每一柵格的表達內容。在柵格地圖形式化表達的基礎上，實現柵格地圖的編碼與索引，在后續(xù)的機器人應用中，可結合機器人效能模型生成個性化機器人柵格地圖，進而輔助機器人完成導航、定位、避障、地圖更新等任務。

圖3 基于形式化描述的個性化機器人地圖建模過程示意圖

柵格地圖形式化描述的意義在于統一機器人對環(huán)境的認識，以標準規(guī)范的形式幫助機器人理解所處環(huán)境，文中將機器人柵格地圖的數據類型及描述方式如表1、表2及圖4所示。

表1 GridMap數據類型與描述方式

表2 GridCell數據類型與描述方式

圖4 機器人柵格地圖的UML圖

2 基于Hilbert空間填充曲線的編碼與索引方法

占據柵格地圖本質上是柵格地圖，以柵格為基礎的圖層化表達形式為機器人認知環(huán)境提供了基礎框架，多圖層的機器人柵格地圖為地圖的管理與應用帶來了挑戰(zhàn)，本節(jié)主要研究機器人多圖層柵格地圖的柵格編碼與索引部分。為提高柵格編碼與索引能力及數據處理效率，采用一維的柵格編碼值替代二三維笛卡爾坐標值參與運算是常見方式之一。空間填充曲線(Space Filling Curve, SFC)作為一種能夠通過遞歸覆蓋指定區(qū)域的一維曲線，是設計離散網格編碼的重要方法。在地理信息系統領域，采用合適的空間填充曲線是對全球離散網格系統進行編碼的重要方法。文中借鑒空間填充曲線在全球多分辨率格網編碼的研究成果，設計實現機器人柵格地圖的四進制編碼方案，為高效的柵格計算與索引奠定基礎。

空間填充曲線的概念最早源于數學家Peano在 1890年所著的文章，隨后，著名數學家Hilbert于 1891年第一次對空間填充曲線進行了幾何表達?？臻g填充曲線建立了一維填充曲線到二維或三維區(qū)域Q的映射關系，根據函數的不同性質，目前為止較為常用的空間填充曲線主要有Peano空間填充曲線、Lebesgue空間填充曲線、Osgood空間填充曲線、Sierpinski空間填充曲線、Morton空間填充曲線、Hilbert空間填充曲線、Gosper空間填充曲線等。雖然任何一種空間填充曲線都不能保證對多維空間關系進行完全保留，但不同的空間填充曲線具有不同的局部聚簇性[12]。研究人員經過廣泛研究和應用的對比后發(fā)現，Hilbert空間填充曲線具有最好的空間聚簇性，即多維空間中位置相鄰或相近的空間目標映射到Hilbert曲線后能夠保持最佳的鄰近關系，并可有效提高多維數據在磁盤等一維物理存儲中的訪問效率[13]。

Hilbert空間填充曲線具有自相似性與自復制性，高階曲線由低階曲線經特定變換后生成。各階曲線的構造均從一個生成器“模板”開始，它規(guī)定了象限的遍歷順序，然后模板經特定變換(相同，鏡像或旋轉)應用于遍歷的每個象限中，并通過連接不同象限曲線的起止點，生成空間填充曲線。在規(guī)則柵格中，依據Hilbert曲線的特性及起止點的不同，可歸納出8個曲線填充方式，同四象限相結合即可得到填充模板，如圖5所示。

圖5 Hilbert空間填充曲線的構造模板

構造模板定義了曲線的初始填充順序及方向，由低階曲線確定的填充順序可進一步通過狀態(tài)向量得到高階填充曲線，如圖6所示。構造模板與狀態(tài)向量展現了低階曲線向高階曲線的演進過程，并具備對應關系。譬如一階曲線確定選取模板0作為初始填充順序，演進為二階曲線時則選擇狀態(tài)向量0進行填充，再演進為三階曲線時，二階曲線狀態(tài)向量0對應的{3, 0, 0, 7}在三階曲線中對應為狀態(tài)向量3,0,0,7的填充方式，以此類推，直至演進到所需分辨率的柵格為止。為便于描述及程序計算，文中引入構造模板與狀態(tài)向量來記錄，如表3所示。

圖6 Hilbert空間填充曲線的狀態(tài)向量

表3 Hilbert 空間填充曲線構造模板與狀態(tài)向量

Hilbert 空間填充曲線保證了一維線段與每一柵格的一一映射關系，曲線與柵格的對應關系主要有兩個特性，一是柵格是通過分層進行嵌套的；二是空間曲線的填充順序即可作為該柵格的唯一空間排列碼。記錄Hilbert曲線填充順序的方式：①根據柵格層級的變化過程，完整記錄柵格在每階中的填充順序；②不考慮柵格層級的變化過程，順序記錄曲線的填充過程。采用四進制編碼方式：上述方式中①編碼記錄形式，依照柵格層級的演進順序，依次記錄柵格階數的Hilbert碼，m層級的柵格其四進制編碼為：

Codem=h1⊕h2⊕h3⊕…⊕hm.

其中，h1,h2,…,hm為柵格在演進過程中其父格元的填充順序，⊕表示左移一位后相加。四進制的編碼方式記錄了柵格的演進順序，且保證了子格元與父格元編碼的一致性(僅相差最后一位)，并且同屬一父格元的子格元僅最后一位不同。與十進制編碼方式相比，四進制編碼方式能夠更好地記錄柵格所處層級，且其編碼形式更便于多分辨率柵格地圖的后續(xù)更新與管理。

基于Hilbert 空間填充曲線的柵格編碼方式，即柵格的Hilbert碼具有如下特點：①空間尺度上的唯一性，Hilbert 空間填充曲線是全球離散網格編碼的經典方法，能夠很好地實現經緯度到Hilbert碼的轉換。雖然目前機器人領域中柵格地圖的研究與應用多是在局部小范圍的場景中實現的，但隨著無人平臺的蓬勃發(fā)展，機器人柵格地圖需要具備唯一性的柵格表示方式，Hilbert碼能夠完美的勝任機器人應用場景的需求，不論是室內室外還是局部全局，其都具備空間尺度上的唯一性；②編碼的唯一性與可拓展性，Hilbert 空間填充曲線能夠按照柵格層級的深化而不斷演進，在演進過程中保持了不同層級柵格之間的關聯或從屬關系，能夠支撐后續(xù)多分辨率柵格地圖的發(fā)展需求。換言之，每個柵格的Hilbert 碼包含其演進過程中父柵格的各層級信息，即m層級柵格的Hilbert 碼繼承了從第1 級至第m-1級的層級信息，這種編碼方式保證了機器人柵格地圖中每個柵格編碼的唯一性與可拓展性，隨著柵格分辨率的逐步精細，(x,y)式的坐標式編碼方式難以滿足編碼的唯一性與可拓展性的需求。

3 實驗與分析

3.1 柵格地圖形式化描述

以20×20的柵格作為實驗數據，介紹機器人柵格地圖的形式化描述過程(由GridMap與GridCell建模而成)，由數據結構組織xml語言，如圖7所示為柵格地圖示例。

圖7 機器人柵格地圖示例

其形式化描述

...

...

...

...

...

3.2 柵格地圖編碼

基于構造模板與狀態(tài)向量的Hilbert空間填充曲線生成方法能夠快速實現不同層級曲線的填充。文中以1～4階曲線填充為例(若四階柵格假設其分辨率為1 m，等效于分辨率由8 m經4 m、2 m細分為1 m)，依據編碼原則實現了不同層級柵格的高效編碼，如圖8、圖9所示。

圖8 一階二階機器人地圖柵格編碼圖

圖9 三階四階機器人地圖柵格編碼圖

階數的提升使得分辨率逐漸精細，Hilbert空間填充曲線通過遞歸的方式能夠輕松勝任高分辨率柵格或是多分辨率柵格的編碼與索引需求，展現出編碼的唯一性與可拓展性等特點。

3.3 空間鄰近性對比

文獻[13]在時空數據索引的研究中指出，對于柵格編碼的最理想目標是保持柵格數據與柵格編碼的時空鄰近性，即時間和空間上相近的柵格數據在柵格編碼索引上也是相近的，柵格編碼上相近的數據在時間先后和空間位置上也是相近的。良好的時空鄰近性使得數據訪問強度大大降低，對于提高數據操作性能作用顯著。文中未涉及時空數據，故而選用空間鄰近性作為體現編碼索引性能的評價指標。

參照文獻[13]的評價方式，空間鄰近性可以通過平均鄰近距離來表示，平均鄰近距離越小，則表明編碼的鄰近性越強，空間連續(xù)性越好。平均最大鄰近距離計算方式為：針對編碼Codem及其對應柵格g，給定柵格編碼距離(柵格間編碼差值的絕對值)半徑R，計算所有柵格距離小于R的柵格編碼所對應的柵格gR與g之間的曼哈頓距離，求取其平均值即為平均鄰近距離。為對比文中Hilbert 碼方法與(x,y)坐標直接編碼的空間鄰近性，分別計算了這兩種編碼在層級的平均鄰近距離，其中編碼半徑R=2m-1。

表4為1～4層級下，文中Hilbert 碼與(x,y)坐標直接編碼的平均鄰近距離統計數據。隨著層級的深化，平均鄰近距離均逐步增加；相同層級下，Hilbert 碼的平均鄰近距離小于(x,y)坐標直接編碼方式，顯示出Hilbert碼能夠保持更好的空間鄰近性，其一維編碼的特性在進行索引時能夠顯著提升原有根據(x,y)坐標直接進行編碼與索引的效率。

表4 平均鄰近距離對比

4 結束語

從機器人認知環(huán)境的角度出發(fā)，適用于機器人的地圖模型應當具備多圖層統一管理、表達形式規(guī)范、支持空間推理計算等特點。文中針對多圖層柵格地圖的形式化描述與編碼索引等方面開展針對性研究，設計形式化描述的數據結構，并基于Hilbert空間填充曲線實現多分辨率柵格地圖的編碼與索引。通過實驗驗證其可行性，針對機器人地圖的研究，當前過多拘泥于SLAM技術，希望文中研究能夠將機器人地圖的深入研究為測繪領域的應用提供思路與方法。另外，三維柵格地圖(或稱為體素，機器人領域特指為八叉樹地圖)的編碼與索引研究將是筆者持續(xù)研究方向。