基于GIS的复杂环境空间通达性预测方法研究

孙 骞，许 睿，万 航

（1.桂林市环境监测中心站, 广西 桂林 541002；2.桂林电子科技大学, 广西 桂林 541004）

路径通达性预测方法是人工智能领域中的一个研究热点问题，并且已经在交通旅游、城市规划、电子导航等领域得到了广泛的应用。求解路径可达性的预测算法很多，如Floyd算法、Dijkstra算法等[1]。这些算法在进行最佳路径的规划时，往往依赖于现存的交通路网，大多依赖于固定的路网节点，以路网固定节点间的路径距离为因素建立权矩阵，然后通过分析计算，求解路网中任意两点的最佳路径；而对于没有固定路网、地质起伏、障碍繁多的野外复杂空间环境，整个空间区域节点数目不确定，通达性计算方法复杂、工作量大，传统的导航寻路方法已经很难满足复杂空间环境中目的点最佳路径的规划要求，这就需要对现有的寻路方法进行改进研究，以满足无路网空间环境中最佳路径的选取和规划。

A*算法是一种启发式算法，它能够在有限步内终止，并找到最优解，通过改进A*算法能够实现野外复杂环境中目的点最佳路径的搜索[2-4]。

1 野外复杂环境空间数据的处理

1.1 研究方法

根据通达性预测方法，选取特定地形影响因子数据，通过对各影响因子权重关系的分析，确定算法的估价函数。最终，结合高精DEM数据、NDVI植被数据以及Landsat影像数据，实现对野外复杂环境空间通达性的预测分析，为以后的路径选取工作提供决策支持。具体研究步骤如图1所示。

1.2 影响因子分析

通过DEM数据，预测空间的通达性状况，实际上就是通过DEM高程数据，结合路径搜索算法，实现空间起点和目的点最佳路径的搜索。在对起点和目的点最佳路径的分析计算之前，必须对影响路径搜索的数值因子进行分析计算，它们包括：数字高程值Dk，用来描述当前点位置的数字高程信息；格网相邻个数N，描述格网间的空间距离；坡度值P，描述空间点位置地形的起伏状况；坡度容忍度T，坡度值在（-T，T）里格网才可达；格网地貌值GE（k），用来表示不同的地貌状况，如山地、平原、河流等[5]； NDVI植被指数Z，用于检测空间点位置植被覆盖情况，取值在[-1,1]之间，负值表示地面覆盖为冰、雨、雪等，对可见光反射，0表示地面为裸土岩石，数值越大，表示地面植被覆盖度越高，通达性越差。

1.3 区域可达模型建立

利用GIS技术结合高精度DEM，通过分析和计算，确定区域邻接格网的穿行代价。最终，根据空间穿行代价函数，建立野外复杂环境区域可达模型。

图1 研究步骤

首先，结合DEM，通过移动窗口数据优化方法，判别点位置8方向DEM网格的可达性，确定区域可达网格集，实现DEM高程数据的优化[6-8]。然后，结合GIS的空间分析和图像渲染技术，根据DEM高程图和NDVI植被覆盖图，提取区域内空间环境的坡度和植被覆盖情况。最终，通过改进A*算法，实现起始点和目的点最佳路径的搜索。

坡度分析实现步骤：

1）加载DEM数字数据。

2）利用空间分析工具，实现对研究区DEM高程图的裁剪。

3）根据DEM数字高程图，计算区域坡度信息，选择坡度表示方法，生成区域坡度渲染图，如图2所示。

图2 坡度变化图

NDVI植被指数分析步骤：

1）加载ENVI植被数据。

2）实现研究区NDVI植被图的裁剪获取。

3）通过计算，分析区域植被覆盖情况，计算公式如下：

式中，NIR为近红外波段；R为红光波段。

4）进行辐射定标与大气校正。

5）输出NDVI植被覆盖图，植被覆盖情况如图3所示。

2 算法分析

2.1 A*算法估价函数选取

A*算法像Dijkstra算法一样，能够实现起始点到目的点最佳路径的搜索[9-11]。区别在于A*算法具有启发性，它能够在启发函数的引导下进行有目的的路径搜索。A*算法的核心是估价函数f（n），算法如下：

图3 植被覆盖图

式中，g（n）为出发网格到第n个网格的实际代价，因为DEM格网是规则等分网格，所以相邻距离都是一定的。同时根据野外地形的实际情况，结合实地区域的距离、植被、坡度和地貌信息，定义A*的实际估价函数：

h（n）体现了算法的启发性，它能够估算当前节点到目标节点的代价值，引导算法快速、高效地获取到达目的点的最短路径。地理信息系统中的最短路径搜索问题，大多数都是给定起始点，经过一定的中间节点，搜索最佳路径。对于启发式搜索方法来说，如果中间节点到目的点的方向与起始点到目的点的方向一致，那么最短路径经过这个点的可能性就更大[12]。在用二维数组表示的DEM网格中，与起始点到目的点方向一致的中间节点往往就是中间点到目的点距离最短的点，所以定义启发函数为：

式中，X（n）、Y（n）分别为节点在二维数组中的x，y下标。

2.2 算法优化

采用上述方法已经能够实现野外环境空间通达性的预测，但算法的实现效率和准确度仍不是很高，需要对算法进一步优化。

A*算法的优化主要分为2个方面：①对Open表的优化，加快Open表的存储访问速度；②对估价函数f（n）的优化，改变估价函数的权值，实现搜索速度和准确率的提高。

从A*搜索原理来看，随着搜索范围的扩大，Open表中的节点数量会呈几何倍数增长。对于越来越多的节点数量，算法根据启发性原理，往往希望向最有可能达到目的点的方向进行搜索，这就需要在Open表中取出具有最小估价总值的节点。因此，有必要对Open表中的节点进行估价值计算，并按照估价值大小进行递增排序，这样每次进行算法运算时，只需取出第一个节点即可，可以降低算法的时间复杂度，提高路径搜索的效率[13]。

对于估价函数，g（n）是源点到节点n的路径代价，而启发函数h（n）是节点n到目的点最短路径的估价值，它决定了算法的搜索效率。理论上h（n）不能大于当前节点n到目的点的实际最短距离，最理想的情况是启发函数的估计值与实际值相等，但在实际应用中估计值的大小只能尽可能地接近实际值。同时为保证算法的完备性和高效性，需要引入加权模型来平衡估价函数中各影响因子的权重。本文针对高精度DEM数据，引入加权因子，定义如下：

随着n的增大，减小k2的取值，使启发函数的值接近实际值，以此提高搜索的精度和效率。

2.3 实现步骤

根据分析结果，确定算法流程（图4）：

1）DEM格网的初始化。

2）创建Open表，加载源点信息。

3）判断Open表是否为空，若为空则寻路失败。

图4 算法流程

4）取出Open表中估价值最小的节点V，并放入Close表中。

5）如果节点V为终点，则寻路成功，转向7）。

6）如果V不是终点，则对相邻的8个方向节点进行判断：①如果节点在Close表中，则返回6）继续；②如果该节点不在Open表中，则将节点添加到Open表中，计算估价值，并按照大小顺序进行递增排序；③如果节点在Open表中，则计算节点的估价值，并与旧值进行比较，选择较小值，更新Open表；④如果8个方向检查完毕，则转向3），否则，转向6）。

7）输出路径。

3 实验结果与验证

根据实验需求，选取比例尺为1∶10 000，格网间距为5 m的高分辨率DEM数字高程图，结合算法，在图层范围内任意选取2点作为算法的起始点和目的点，通过仿真，建立空间通达性预测模型，实现源点和目的点最佳路径的规划。路径输出渲染结果如图5所示。

图5 路径输出图

根据数值高程图，选取左上角A点作为方法的起点，B点作为方法的目的点。结合改进A*算法，方法能够根据DEM和NDVI数据信息，实现空间最短路径的准确、快速搜索。路径表现为一条细长曲折的运动轨迹线。实验结果表明，野外环境中建立空间可达性模型，能够在野外行军、森林救火、雪崩救援、抗洪救灾等方面得到应用。

4 结 语

构建了一种基于GIS的野外复杂环境空间通达性预测方法。通过改进A*算法，该方法能够实现野外环境中最佳路径的搜索，可在野外无拓扑道路的地形环境中得以应用，具有一定的合理性和实用性。但在现实应用中，模型仍存在着一些不足之处，主要包括DEM格网的采集精度、Landsat影像数据和NDVI植被覆盖数据的分辨率、NDVI大气影响校正指数、坡度提取的准确度等，这都需要进一步研究和探讨。目前，本系统仅能对单一精度的遥感影像数据进行最佳路径的规划分析，而对不同精度、不同需求的影像数据的分析计算，系统仍需优化完善。后续可采用分层和并行计算的思想来完善系统，提高方法的运行速度与计算效率。

[1]Felner A, Stern R, Ben-Yair A, et al.PHA*:Finding the Shortest Path with A* in an Unknown PhysicaL Environment[J].Journal of Artif icial Intelligence Research, 2004(21): 631-670

[2]张和平, 张前哨.A*算法在游戏地图寻径中的应用与实现[J].计算机应用与软件, 2005 (12): 198-200

[3]刘浩.A*算法在矢量地图最优路径搜索中的应用[J].计算机仿真, 2008, 25(4): 253-257

[4]Goldberg A, Kaplan H, Werneck R.Reach for A*: Efficient Point–to-Point Shortest Path Algorithms[C].Philadelphia,United States: Workshop on Algorithm Engineering and Experiments, Miami Society for Industrial and Applied Mathematics Publications, 2006

[5]胡伟, 卢小平, 卢遥, 等.基于移动窗口法的DEM数据优化方法研究[J].测绘通报, 2011(5): 45-47

[6]原江波, 母攀良, 史乐,等.大场景中虚拟车辆自动寻路的高效算法[J].计算机工程与设计, 2008, 29(10): 2 622-2 625

[7]陈易, 王晶.带通行限制的加权A*算法及其数据库实现[J].北京化工大学学报, 2009, 36(5): 107-111

[8]李建元, 师军, 曹菡, 等.一种分层寻路算法中的域值放弃策略[J].计算机应用, 2007, 27(2): 473-478

[9]于晓艳, 马劲松, 刘艳, 等.城市通达性面状分布模型研究[J].水电能源科学, 2010, 28(6): 56-58

[10]林笃斌, 李欣.基于DEM格网的改进型A*路径搜索算法[J].计算机工程与设计, 2011, 32(10): 3 414-3 418

[11]刘学军, 卞璐, 卢华兴.顾及DEM误差自相关的坡度计算模型精度分析[J].测绘学报, 2008, 37(2): 200-206

[12]曹强, 张明智, 李志强, 等.CTI中车辆实时最佳路径搜索算法设计与实现[J].系统仿真学报, 2009, 21(21):6 777-6 780

[13]严寒冰, 刘迎春.基于GIS的城市道路网最短路径算法探讨[J].计算机学报, 2000, 23(2): 210-215