一种基于缓冲区分析的A*算法路径规划

康传利,张临炜,2,陈 洋,时满星,顾俊峰

(1.桂林理工大学 a.广西空间信息与测绘重点实验室;b.测绘地理信息学院,广西 桂林 541006;2.广东省土地调查规划院，广州 510075)

0 引 言

地理信息系统是一种采集、存储、管理、分析、显示和应用地理信息的计算机系统,是分析和处理海量地理数据的通用技术。GIS空间分析是对地理空间中目标的空间关系和空间行为进行描述,为目标的空间查询和空间相关分析提供参考,进一步为空间决策提供服务的技术。空间分析是地理信息系统区别于一般信息系统、CAD或电子地图系统的主要功能特征,是GIS的核心和灵魂[1-2]。

路径规划技术在众多领域都有着广泛的应用,如机器人自主无碰运动、无人机避障突防飞行、巡航导弹躲避雷达搜索、GPS导航、基于GIS的道路规划、城市道路网规划导航等[3]。凡是可以拓扑为电线网络的规划问题,基本上都可以采用路径规划的方法来解决。路径规划的核心是算法的设计,目前路径规划算法的研究已经得到了广泛的关注。传统解决最短路径规划问题的算法包括Floyd算法、Dijkstra算法,它们需要较大的存储空间,并且随着顶点的增多,复杂度急剧上升。为了更好地解决最短路径规划问题,学者们受自然界生物群体活动或者自然现象的启发,开始关注智能算法的研究,并不断在原有基本算法的基础上开拓创新,提出新的启发式算法[4-5]，比较常见的有遗传算法(GA)、 蚁群算法(ACO)、 粒子群算法(PSO)。这些基于自然界特征的算法都有各自的不足之处,如遗传算法容易出现早熟现象、粒子群算法容易陷入局部最优解并且对初始种群依赖性太大、蚁群算法收敛速度较慢。因此,对算法的改进是学者们近年的重点研究方向[5-6]。A*算法是一种启发式搜索算法,通过设定合理的启发式评估函数,全面评估网格化区域内各扩展节点权重,从而规划最优行进路线。

本文提出一种基于GIS空间分析的A*算法路径规划方法,通过对景区空间地理数据进行整理编辑,将景区空间信息进行可视化表达,并对空间信息进行充分解译与利用,结合A*算法,对传统路径规划方法加以改进,优化旅游路线。

1 专题地图的生成与解译

1.1 GIS缓冲区分析

缓冲区分析是地理信息系统重要的空间操作功能之一,基本思想是给定一个空间实体,在实体周围建立一定缓冲半径的带状区域, 以确定这些物体对周围环境的影响范围或服务范围。缓冲区分析主要用来解决地理空间中地物距离相近程度问题。一般情况下,缓冲区分析与叠加分析、网络分析、服务设施查询等空间分析功能相结合,处理地理空间信息数据,解决空间决策问题。缓冲区分析在城市规划、道路交通管理、环境监测、军事应用等领域得到广泛应用[6-8]。

对于不同的目标要素类型,所产生的缓冲区也不同。点缓冲区通常是以点为圆心,以一定距离为半径的圆;线缓冲区是以线为中心轴线,距离中心轴线一定距离的平行条带多边形;面缓冲区是以面的边界向外或向内扩展一定距离所生成的新的多边形。其中，线状目标的缓冲区的生成是关键和基础。图1a—c分别是点、线、面元素缓冲区建立的基本方式。

在地理信息桌面软件中,加载景区影像数据,依据网络开源数据及实地考察,用点要素代表景点、车站;线要素代表道路网;面要素代表景点参观区域、水域、休闲活动区域等在景区影像数据上描绘新的矢量图层。根据采集的实际数据,设定缓冲区半径, 在新生成的矢量图层上建立点、线、面要素的缓冲区,代表景区所有的可通行区域。结合矢量图层,输出路径规划用的专题地图。

1.2 影像数字信息提取

A*算法是一种应用在格子环境中的启发式搜索算法,为了满足算法需要,需将输出的矢量专题地图离散化,转换为具有一定分辨率的栅格地图。栅格地图是按照一定的索引规则,将空间数据分割成有规律的网格,每一个网格称为一个像元,每个像元的位置由行列号来定义。像元也可以称为像素,表示图像的基本元素,是存储数字化影像的最小单元,像元的大小由图像分辨率的高低来决定:分辨率越高,像元所包含的信息就越抽象;分辨率越低,像元所包含的信息就越丰富[9-11]。

通过计算机程序,对栅格影像进行解译,将像元值存储在一个有序的二维数组中,数组行列号代表像元所在的行列号,数组存储的数值代表该像元的RGB值。在生成的专题地图中,景区道路网及多元性质的缓冲区域设有不同的RGB值,这是A*算法识别像元属性的关键。A*算法通过读取二维数组,对移动至每个像元的代价进行评估, 从而规划出最短路径。 图2是影像数字信息提取的一个实例。

图1 点、线、面缓冲区示意图Fig.1 Buffer schematic of point, line and surface

图2 影像数字信息提取实例Fig.2 Image digital information extraction example

2 基于A*算法的景区路径规划

A*算法的主体思想是在搜索下一个节点并选择该节点路径时加入与问题相关的启发性信息,指导搜索朝目标方向进行,用于搜索状态空间的最短路径[12-13]。A*算法是一种在静态格网状地图上求最佳路径的算法,为实现A*算法求解景区路径规划问题,需对景区影像进行信息提取。对于不同类型地物,设定不同的缓冲区半径及影响因子,生成不同属性缓冲区,创建包含多元空间信息的专题地图;对专题地图进行离散化处理,生成规则的格网状数字地图,供算法实现最优路径的计算;在A*算法启发式函数中添加缓冲区影响因子,实现缓冲区参与路径规划的思想。

2.1 A*算法思想

启发式搜索是在状态空间中对每一个搜索位置进行评估并得出最好的位置,然后从这个位置再次进行搜索评估,直至达到目标节点。启发式搜索可以省略大量无用的搜索路径,提高了效率。在启发式搜索中,对位置的评估十分重要[14]。

A*算法的估价函数可以表示为

F(n)=G(n)+H(n),

(1)

其中:F(n)为估价函数, 表示从起始点到目标点的估计代价;G(n)指在状态空间中从初始节点到节点n的实际代价;H(n)是节点n到目标节点最佳路径的估计代价。

最短路径(最优解)的关键在于H(n)的选取。

2.2 基本A*算法流程

2.3 基于景区缓冲区域的A*算法

在A*算法中,启发式函数H(n)对路径的生成速度和质量有重要的影响,常用的启发式函数计算方法有欧氏距离、曼哈顿距离和切比雪夫距离。本文采用曼哈顿距离作为启发式函数计算的基本方法,在此基础上,添加有关景区的影响因子,提高景区路径规划的精度。

曼哈顿距离是指在欧几里得空间的固定直角坐标系上,两点所形成的线段对坐标轴产生投影距离的总和。曼哈顿距离受坐标系统转度的影响,而非坐标轴的平移或者映射。

在二维平面两点a1(x1,y1) 与a2(x2,y2)间的曼哈顿距离

d12=|x1-x2|+|y1-y2|,

(2)

在原有的曼哈顿距离计算基础上, 添加景区影响因子。 景区影响因子是对景区原本道路网、 景点区域、 水域以及各要素生成的缓冲区域设定一个系数θ, 用来表示某一类区域的权重值,其中0<θ≤1或者θ=∞。 权重值越小, 代表该区域可通行优先级越高, 例如：景区道路网系数设定为1, 道路网缓冲区系数设定为0.8, 水域系数设定为∞。 计算公式为

d12=θ(|x1-x2|+|y1-y2|)，

(3)

因此, 面向景区路径规划的估价函数为

F(n)=G(n)+θ1H1(n)+θ2H2(n)+…+θmHm(n)，

(4)

式中:θmHm(n)表示某一类区域影响因子与该区域内曼哈顿距离的乘积。在路况复杂多变的景区,影响因子可以充分结合景区基本道路网和景区可通行区域,从而通过改进后的A*算法输出一条最优路径。基于景区缓冲区的A*算法流程见图3。

3 七星公园景区路径规划系统设计

以广西桂林市七星公园景区为例,验证基于A*算法的景区缓冲区路径规划的可行性。

3.1 数据准备及处理

数据源采用天地图发布的影像为基础底图,参考OpenStreetMap电子矢量地图,结合实地考察结果,对七星公园景区道路网、休息活动区域、景区保护区域、景点游览区域等进行重新勾绘。使用ArcGIS空间分析工具箱中Buffer工具,对绘制好的矢量多要素图层执行缓冲区操作,分别设立不同缓冲区半径的要素缓冲区域,结合原绘制好的矢量图层,设定不同区域色彩灰度值,生成A*算法所需的24位真彩色、JPG格式专题地图,专题地图见图4。

图3 基于景区缓冲区域的A*算法流程Fig.3 A* Algorithm flow chart based on buffer area of scenic area

本文使用ENVI 5.1自带的IDL编译器,自行编写了一套用于解译图像的脚本程序,遍历离散化图像的像元,将读取到的像元值按一定顺序存贮在二维数组中,生成供A*算法计算最优路径的“数组地图”。

图4 电子地图Fig.4 Electronic map

3.2 路径规划及显示

根据A*算法基本思想及改进后适用于景区缓冲区算法原理, 自主编写了一套景区路径规划系统。 系统读取已勾绘完成的专题地图,转换为对应的数组数据, 识别像元RGB值, 判定缓冲区区域性质, 创建不同性质缓冲区影响因子的A*算法。 基于缓冲区的A*算法根据各区域的影响因子, 计算每一次节点之间移动的代价, 输出一条由用户输入的起点及终点间的最佳路径。 将实验结果和执行传统A*算法规划路径进行对比分析, 验证了基于景区缓冲区的A*算法的有效性。 图5是执行传统A*算法的路径规划结果, 图6是经缓冲区处理后,执行改进后的A*算法最优路线。

图5 传统A*算法路径规划结果Fig.5 Traditional A* Algorithm path planning results

图6 基于缓冲区A*算法路径规划结果Fig.6 Path planning results based on buffer A* Algorithm

实验结果表明,对影像执行基本的绘制并作缓冲区处理后,景区内部多元化的区域信息以可视化的方式加载在影像上,影像信息更加丰富。较传统A*算法而言,添加缓冲区影响因子的A*算法,可有效结合景区道路网及多元区域的路况信息规划出一条最佳行进路线,为景区浏览提供参考信息。

4 结束语

地理信息系统是空间信息可视化的主要途径，可通过对影像的绘制及处理,将影像数据信息以数字或图像的方式呈现在计算机上,为影像使用者提供有力的空间决策支持。本文首先对景区影像进行信息挖掘,得到所需的专题地图;对专题地图进行离散化处理,生成A*算法所需的“数组地图”;针对景区道路网及缓冲区域的特性对A*算法进行改进,生成了一套适用于景区路径规划的软件系统,为景区观光提供参考信息。

本文分析了一种适用于缓冲区的路径规划方法的可行性,但在实际应用时,改进的A*算法中缓冲区影响因子设定需考虑多方面因素,没有一个统一的设定标准。因此，关于影响因子与缓冲区半径及缓冲区域性质之间的关系函数,还有待进一步研究。