張藍(lán)天,王光霞,劉 旭,王瑋琦,王慧芳

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

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

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

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

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

1 柵格地圖的形式化描述

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

圖2 占據(jù)柵格地圖構(gòu)建過(guò)程

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

圖3 基于形式化描述的個(gè)性化機(jī)器人地圖建模過(guò)程示意圖

柵格地圖形式化描述的意義在于統(tǒng)一機(jī)器人對(duì)環(huán)境的認(rèn)識(shí)，以標(biāo)準(zhǔn)規(guī)范的形式幫助機(jī)器人理解所處環(huán)境，文中將機(jī)器人柵格地圖的數(shù)據(jù)類型及描述方式如表1、表2及圖4所示。

表1 GridMap數(shù)據(jù)類型與描述方式

表2 GridCell數(shù)據(jù)類型與描述方式

圖4 機(jī)器人柵格地圖的UML圖

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

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

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

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

圖5 Hilbert空間填充曲線的構(gòu)造模板

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與分析

3.1 柵格地圖形式化描述

以20×20的柵格作為實(shí)驗(yàn)數(shù)據(jù)，介紹機(jī)器人柵格地圖的形式化描述過(guò)程(由GridMap與GridCell建模而成)，由數(shù)據(jù)結(jié)構(gòu)組織xml語(yǔ)言，如圖7所示為柵格地圖示例。

圖7 機(jī)器人柵格地圖示例

其形式化描述

...

...

...

...

...

3.2 柵格地圖編碼

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

圖8 一階二階機(jī)器人地圖柵格編碼圖

圖9 三階四階機(jī)器人地圖柵格編碼圖

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

3.3 空間鄰近性對(duì)比

文獻(xiàn)[13]在時(shí)空數(shù)據(jù)索引的研究中指出，對(duì)于柵格編碼的最理想目標(biāo)是保持柵格數(shù)據(jù)與柵格編碼的時(shí)空鄰近性，即時(shí)間和空間上相近的柵格數(shù)據(jù)在柵格編碼索引上也是相近的，柵格編碼上相近的數(shù)據(jù)在時(shí)間先后和空間位置上也是相近的。良好的時(shí)空鄰近性使得數(shù)據(jù)訪問(wèn)強(qiáng)度大大降低，對(duì)于提高數(shù)據(jù)操作性能作用顯著。文中未涉及時(shí)空數(shù)據(jù)，故而選用空間鄰近性作為體現(xiàn)編碼索引性能的評(píng)價(jià)指標(biāo)。

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

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

表4 平均鄰近距離對(duì)比

4 結(jié)束語(yǔ)

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