机器人栅格地图编码与索引方法

张蓝天,王光霞,刘 旭,王玮琦,王慧芳

(1.61646部队，北京 100192；2.信息工程大学，郑州 450052；3.空军航空大学，长春 130022；4.61206部队，北京 100043)

随着人工智能、5G、物联网等技术的发展，智能机器人与人共融共生态势已悄然显现，尤其是在单调重复、危险、未知环境中，智能机器人更具有优势。智能机器人高效执行既定任务的前提是对所处环境及其预期影响的准确“理解”。这涉及到智能机器的环境感知、环境表示建模和空间推理计算等一系列理论和技术问题，既是新一代人工智能的关键共性技术[1]，也是人工智能时代测绘科学关注的新问题[2]。针对机器人环境表示建模的研究以即时定位与地图构建技术(Simultaneous Localization and Mapping,SLAM)为主。SLAM技术在没有环境先验知识的前提下试图完成增量式的机器人位姿估计与环境模型构建，尽管近年来蓬勃发展且成果显著，但其研究重点始终聚焦于位姿估计的速度与精度，鲜有考虑机器人环境模型的应用(或称为地图复用)与管理的研究工作。机器人应用的环境模型应当尽可能涵盖其所需环境信息，并满足环境信息更新、空间推理决策等客观需要。

显而易见，单一的环境模型难以表达环境的全部特征信息，采用多图层的方式是详尽地对客观环境进行准确刻画的常见形式。Peter等人为解决足式机器人的室内导航问题，设计了包含障碍层、高程层、法向量层等图层的室内环境模型[3]，并在机器人操作系统(Robot Operating System，ROS)中开源了其栅格地图库Grid Map Library，如图1所示。Koch P等为解决轮式机器人在野外环境的定位导航问题，设计实现了包含拓扑层、三维模型层、正射影像层、DTM层等多图层的野外环境模型[4],并使用3种不同的轮式机器人对环境模型的可用性进行验证。

图1 ROS中栅格地图库Grid Map Library的栅格编码方式

在空间推理计算方面，栅格地图是对连续空间的离散化表达，其离散化的特性适合高效的数据组织与索引、精准的空间分析与决策。当前机器人栅格地图以占据栅格地图为主，针对占据栅格地图的研究主要涉及：①赋值方式的完善,将早期二值(0为空闲，1为被占据)描述的占据栅格地图完善为[0,1]区间的赋值方式[5]，赋值方式的完善使得在建图过程中能够更连续地对环境进行表达；②表达维度的拓展，显然2D占据栅格地图无法满足诸如无人机、无人艇等无人平台的使用需求，2.5D占据栅格地图与3D占据栅格地图(又称为八叉树地图)应运而生[6-7]，表达维度的拓展能够满足各类无人平台的避障需求；③空间邻近关系的约束，不论是2D或是3D占据栅格地图，其在建图过程中将每一个栅格/体素作为独立的变量进行处理而不考虑栅格/体素间的空间关系，这种“分而治之”的方式极易导致地图不连贯等现象的出现(例如，连续的障碍物区域中因探测数据缺失等原因出现的个别空闲区域)，为充分考虑栅格间的空间关系与邻近关系，研究者们通过构建高斯过程模型或是选用Hilbert核函数等方式对栅格间的空间邻近关系进行建模，生成一致性更强的占据栅格地图[8-10]。多图层的环境模型试图解决环境表示上的详尽性与完备性等问题，栅格化的表示形式试图帮助机器人实现空间推理计算与智能决策。尽管在多图层与栅格表示上成果显著，但仍缺少多图层栅格化环境模型的动态更新与编码索引方面的针对性研究。高效的数据组织与索引是实现环境模型管理、环境信息联动更新与空间推理决策的基础。因此，文中在以上研究成果的基础上，针对多图层机器人栅格地图的编码与索引方法开展研究，在对栅格地图进行形式化描述的基础上，基于空间填充曲线——Hilbert曲线实现多图层机器人地图的编码与索引。

1 栅格地图的形式化描述

占据栅格地图(Occupancy Grid Map)是机器人利用激光雷达进行地图构建时得到的最为常见的一种地图形式，亦是机器人导航定位时应用最为广泛的地图形式。它以栅格地图作为基础，对每个栅格是否被“占据”加以描述，以概率累加的方式不断更新每个栅格的“占据”状态，进而完成地图构建。每个栅格随着新测量值的获取不断更新其占据状态，如图2所示简要描绘占据栅格地图构建过程[11]。

图2 占据栅格地图构建过程

受限于传感器性能、机器人个体的动力学模型差异及任务多样性等不同因素，不同的机器人个体对同一环境的观测与建图结果不尽相同。从机器人地图应用的角度出发，机器人地图应具备为各类无人平台提供服务的能力，如图3所示为本研究出发点：占据栅格地图作为机器人环境探测的成果，对其进行形式化描述以满足其为各种无人平台所使用的需求，在形式化描述的基础上，各类无人平台依据自身的性能指标、动力学模型及载具要求等情况生成满足自身需求的个性化栅格地图。基于此认识，文中聚焦于机器人占据栅格地图的形式化描述及栅格编码与索引的研究工作，首先对机器人栅格地图进行形式化描述，以机器人领域最为常见的占据栅格地图为基础，拓宽机器人领域栅格地图的表达内容(不再局限于栅格的占据状态描述)，形成机器人栅格地图的统一接口，既能对占据栅格地图进行形式化描述，又可以容纳测绘领域的基础地理信息、丰富每一栅格的表达内容。在栅格地图形式化表达的基础上，实现栅格地图的编码与索引，在后续的机器人应用中，可结合机器人效能模型生成个性化机器人栅格地图，进而辅助机器人完成导航、定位、避障、地图更新等任务。

图3 基于形式化描述的个性化机器人地图建模过程示意图

栅格地图形式化描述的意义在于统一机器人对环境的认识，以标准规范的形式帮助机器人理解所处环境，文中将机器人栅格地图的数据类型及描述方式如表1、表2及图4所示。

表1 GridMap数据类型与描述方式

表2 GridCell数据类型与描述方式

图4 机器人栅格地图的UML图

2 基于Hilbert空间填充曲线的编码与索引方法

占据栅格地图本质上是栅格地图，以栅格为基础的图层化表达形式为机器人认知环境提供了基础框架，多图层的机器人栅格地图为地图的管理与应用带来了挑战，本节主要研究机器人多图层栅格地图的栅格编码与索引部分。为提高栅格编码与索引能力及数据处理效率，采用一维的栅格编码值替代二三维笛卡尔坐标值参与运算是常见方式之一。空间填充曲线(Space Filling Curve, SFC)作为一种能够通过递归覆盖指定区域的一维曲线，是设计离散网格编码的重要方法。在地理信息系统领域，采用合适的空间填充曲线是对全球离散网格系统进行编码的重要方法。文中借鉴空间填充曲线在全球多分辨率格网编码的研究成果，设计实现机器人栅格地图的四进制编码方案，为高效的栅格计算与索引奠定基础。

空间填充曲线的概念最早源于数学家Peano在 1890年所著的文章，随后，著名数学家Hilbert于 1891年第一次对空间填充曲线进行了几何表达。空间填充曲线建立了一维填充曲线到二维或三维区域Q的映射关系，根据函数的不同性质，目前为止较为常用的空间填充曲线主要有Peano空间填充曲线、Lebesgue空间填充曲线、Osgood空间填充曲线、Sierpinski空间填充曲线、Morton空间填充曲线、Hilbert空间填充曲线、Gosper空间填充曲线等。虽然任何一种空间填充曲线都不能保证对多维空间关系进行完全保留，但不同的空间填充曲线具有不同的局部聚簇性[12]。研究人员经过广泛研究和应用的对比后发现，Hilbert空间填充曲线具有最好的空间聚簇性，即多维空间中位置相邻或相近的空间目标映射到Hilbert曲线后能够保持最佳的邻近关系，并可有效提高多维数据在磁盘等一维物理存储中的访问效率[13]。

Hilbert空间填充曲线具有自相似性与自复制性，高阶曲线由低阶曲线经特定变换后生成。各阶曲线的构造均从一个生成器“模板”开始，它规定了象限的遍历顺序，然后模板经特定变换(相同，镜像或旋转)应用于遍历的每个象限中，并通过连接不同象限曲线的起止点，生成空间填充曲线。在规则栅格中，依据Hilbert曲线的特性及起止点的不同，可归纳出8个曲线填充方式，同四象限相结合即可得到填充模板，如图5所示。

图5 Hilbert空间填充曲线的构造模板

构造模板定义了曲线的初始填充顺序及方向，由低阶曲线确定的填充顺序可进一步通过状态向量得到高阶填充曲线，如图6所示。构造模板与状态向量展现了低阶曲线向高阶曲线的演进过程，并具备对应关系。譬如一阶曲线确定选取模板0作为初始填充顺序，演进为二阶曲线时则选择状态向量0进行填充，再演进为三阶曲线时，二阶曲线状态向量0对应的{3, 0, 0, 7}在三阶曲线中对应为状态向量3,0,0,7的填充方式，以此类推，直至演进到所需分辨率的栅格为止。为便于描述及程序计算，文中引入构造模板与状态向量来记录，如表3所示。

图6 Hilbert空间填充曲线的状态向量

表3 Hilbert 空间填充曲线构造模板与状态向量

Hilbert 空间填充曲线保证了一维线段与每一栅格的一一映射关系，曲线与栅格的对应关系主要有两个特性，一是栅格是通过分层进行嵌套的；二是空间曲线的填充顺序即可作为该栅格的唯一空间排列码。记录Hilbert曲线填充顺序的方式：①根据栅格层级的变化过程，完整记录栅格在每阶中的填充顺序；②不考虑栅格层级的变化过程，顺序记录曲线的填充过程。采用四进制编码方式：上述方式中①编码记录形式，依照栅格层级的演进顺序，依次记录栅格阶数的Hilbert码，m层级的栅格其四进制编码为：

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

其中，h1,h2,…,hm为栅格在演进过程中其父格元的填充顺序，⊕表示左移一位后相加。四进制的编码方式记录了栅格的演进顺序，且保证了子格元与父格元编码的一致性(仅相差最后一位)，并且同属一父格元的子格元仅最后一位不同。与十进制编码方式相比，四进制编码方式能够更好地记录栅格所处层级，且其编码形式更便于多分辨率栅格地图的后续更新与管理。

基于Hilbert 空间填充曲线的栅格编码方式，即栅格的Hilbert码具有如下特点：①空间尺度上的唯一性，Hilbert 空间填充曲线是全球离散网格编码的经典方法，能够很好地实现经纬度到Hilbert码的转换。虽然目前机器人领域中栅格地图的研究与应用多是在局部小范围的场景中实现的，但随着无人平台的蓬勃发展，机器人栅格地图需要具备唯一性的栅格表示方式，Hilbert码能够完美的胜任机器人应用场景的需求，不论是室内室外还是局部全局，其都具备空间尺度上的唯一性；②编码的唯一性与可拓展性，Hilbert 空间填充曲线能够按照栅格层级的深化而不断演进，在演进过程中保持了不同层级栅格之间的关联或从属关系，能够支撑后续多分辨率栅格地图的发展需求。换言之，每个栅格的Hilbert 码包含其演进过程中父栅格的各层级信息，即m层级栅格的Hilbert 码继承了从第1 级至第m-1级的层级信息，这种编码方式保证了机器人栅格地图中每个栅格编码的唯一性与可拓展性，随着栅格分辨率的逐步精细，(x,y)式的坐标式编码方式难以满足编码的唯一性与可拓展性的需求。

3 实验与分析

3.1 栅格地图形式化描述

以20×20的栅格作为实验数据，介绍机器人栅格地图的形式化描述过程(由GridMap与GridCell建模而成)，由数据结构组织xml语言，如图7所示为栅格地图示例。

图7 机器人栅格地图示例

其形式化描述

...

...

...

...

...

3.2 栅格地图编码

基于构造模板与状态向量的Hilbert空间填充曲线生成方法能够快速实现不同层级曲线的填充。文中以1～4阶曲线填充为例(若四阶栅格假设其分辨率为1 m，等效于分辨率由8 m经4 m、2 m细分为1 m)，依据编码原则实现了不同层级栅格的高效编码，如图8、图9所示。

图8 一阶二阶机器人地图栅格编码图

图9 三阶四阶机器人地图栅格编码图

阶数的提升使得分辨率逐渐精细，Hilbert空间填充曲线通过递归的方式能够轻松胜任高分辨率栅格或是多分辨率栅格的编码与索引需求，展现出编码的唯一性与可拓展性等特点。

3.3 空间邻近性对比

文献[13]在时空数据索引的研究中指出，对于栅格编码的最理想目标是保持栅格数据与栅格编码的时空邻近性，即时间和空间上相近的栅格数据在栅格编码索引上也是相近的，栅格编码上相近的数据在时间先后和空间位置上也是相近的。良好的时空邻近性使得数据访问强度大大降低，对于提高数据操作性能作用显著。文中未涉及时空数据，故而选用空间邻近性作为体现编码索引性能的评价指标。

参照文献[13]的评价方式，空间邻近性可以通过平均邻近距离来表示，平均邻近距离越小，则表明编码的邻近性越强，空间连续性越好。平均最大邻近距离计算方式为：针对编码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 结束语

从机器人认知环境的角度出发，适用于机器人的地图模型应当具备多图层统一管理、表达形式规范、支持空间推理计算等特点。文中针对多图层栅格地图的形式化描述与编码索引等方面开展针对性研究，设计形式化描述的数据结构，并基于Hilbert空间填充曲线实现多分辨率栅格地图的编码与索引。通过实验验证其可行性，针对机器人地图的研究，当前过多拘泥于SLAM技术，希望文中研究能够将机器人地图的深入研究为测绘领域的应用提供思路与方法。另外，三维栅格地图(或称为体素，机器人领域特指为八叉树地图)的编码与索引研究将是笔者持续研究方向。