一种基于改进A*算法的室内导航路径规划方法

叶小艳，钟华钧，邓可儿

(广州软件学院 网络技术系，广东 广州 510990)

0 引 言

室内导航是指在各种室内空间中采用不同技术来实现人员室内导航以及对人员、物体的定位与跟踪。其关键技术主要涉及三个方面：室内导航定位技术、室内路径规划技术和室内地图构建。路径规划是室内导航的关键技术之一，按照某一性能指标(如距离、时间、目标等)搜索一条从起始状态到目标状态的最优或次优路径。目前，已有多种算法和方案的研究用于解决室内导航路径规划问题。文献[3]提出了一种改进启发式飘逸消除算法，消除室内环境中行人导航定位算法中的漂移误差。文献[4]结合室内导航的鲁棒特征跟踪要求，提出了一种基于图形处理器的加速策略，在实时导航时减少误匹配机会。文献[5]描述了一种新的地图辅助模糊决策树(FDT)，减少累积误差，提高生成能力和最小化基础设施的使用。文献[6]改进地图匹配算法，提高商场室内导航地图定位引擎的定位精度。谢民提出一种改进的蚁群算法来解决道路交通导航系统中以加权路径网的以路径长度与通行时间的线性组合为目标函数的优化问题。王中玉提出了一种基于A*算法改进的高效路径规划算法，解决规划路径存在的冗余点和拐点的问题。赵柯柯研究了室内停车场的路径规划算法与导航，陶文瀚构建了基于改进型蜻蜓算法的物流配送过程中的车辆路径模型。王文东、周嵘针对机器人室内路径规划算法，开展了A*算法的室内路径规划研究。很明显，A *算法是解决路径规划最优问题的一种比较常用并且高效的算法。在大型建筑体内环境(如大型商场、大型购物中心、复杂写字楼、展览馆等)，运用A*算法按切身需求来规划最佳路径，尤其遇到紧急情况时，科学的路径规划方法可以根据出入口的人流量和通过权限做出调整。目前A*算法在解决室内导航问题上，从起点开始，以一定的步长扩展节点，选择路径长度最小的节点作为扩展节点，然后逐步扩展，直至到达终点。在数值优化算法方面，当区域的点数量较少时，效率是非常高的。但是如果路径点的规模较大，当使用数值优化算法求解最佳路径时，难度将会急剧增加，从而导致规划时间所需时间过长，明显不符合实时性要求。

因此，为提高路径规划方法中的效率和稳定性，达到加速导航算法的目的，采用分层计算的思想对普通A*算法进行优化，提出了一种改进型A*算法优化的方案。经过算法效率测试，改进型A*算法在室内导航路径规划的效率和稳定性比较优。

1 A*算法

作为一种常见的全局路径规划算法，A*算法在静态路网中运用广泛，对于找寻最优路径是最有效的直接搜索方法。目前在A*算法运用方面，很多相关的解决方案都是在A*算法的基础上进行优化和使用的。如微软硅谷研究院提出的Crp算法(customizable route planning，可定制路线规划)，与传统的A-star(即A*算法)，基本支撑了目前工业界地图产品的路径规划服务。Bian等提出了一种用户偏好建模和获取的方法，考虑用户偏好对传统的A*算法进行了改进，并通过实例说明了个性化A*算法的优越性。邱磊提出将跳点搜索算法的思想融入传统的A*算法，通过在栅格地图中定义关键节点来保证获得最优路径的同时提高寻路速度，有效减少了内存开销。但传统的A*算法在室内导航规划寻径过程中，出现大量无用节点，重复搜寻，导致寻径耗时过长，搜索节点数量过多，搜索效果不佳。

1.1 A*算法的基本思想与实现步骤

A*算法的基本思想主要是在规划最优路径的前提下运用启发函数引导搜索，A*算法的启发函数为

F

()=

G

()+

H

()，其中

F

()表示节点

n

从初始点到目标点的函数，

H

()表示从当前节点到目标节点的估计代价，

G

()表示从起始节点到当前节点的距离。每一次选择最小代价的节点作为下一个处理节点。

其实现步骤用伪代码表示如下：

创建开启列表、关闭列表

将起始点加入开放列表中

弹出开启列表的第一个节点，将该元素作为当前节点

while(当前节点不为终点时)：

获取并处理当前节点的周围可通过的节点，

为这些节点设置

G

值、

H

值，

添加当前节点为这些可通过节点的父节点

遍历当前节点的周围节点

if(该节点可通过且不在关闭列表):

if(该节点在开启列表):

根据 估价函数

F

()进行比较

if(开启列表的节点的估价函数大于该节点的估价函数):

将开启列表的节点进行覆盖

else:

将该节点加入开启列表

将当前节点添加到关闭列表中

对开启列表进行排序

当前节点<-获得开启列表的第一个元素

创建一个路径结果集

while(当前节点的父节点不为空):

获得当前节点的索引，存入路径结果集中

当前节点<-当前节点的父节点

返回路径结果集

结束

1.2 室内导航中A*路径算法存在的问题

A*路径算法在路径搜索过程中，删除了大量的节点，导致产生的结果可能不是最优路径。但由于该算法是用于室内导航的，所以这种可能的发生率非常小。

另一方面在大型建筑体内导航中，由于室内建筑体复杂加深，有些建筑(如大型商场等)经营面积巨大，且可利用空间非常多，再加上商城导航中一层地图如果节点划分越细，那么导航代价就越高，所以每一次利用A*算法时，都需要进行大量的搜索和估价。需要处理的节点非常多，当节点数量增加时，算法需要的时间成指数增长，严重影响了路径规划的效率和成本。传统的A*算法将规划目标视为质点，规划出的路径实际很可能会触碰到障碍物，使得规划路径较长。

2 室内导航中A*算法的改进

2.1 改进的A*算法的基本思想

如上所述，在商城导航中，需要处理的节点数量庞大，因此在室内导航中对A*算法的改进迫在眉睫。以大型商场为例对A*算法进行改进。通过对大量商城布局设计以及其他A*算法优化的方案进行研究后，对其在商城导航中的A*算法进行优化。具体思路为：对A*算法的地图数据进行划分，获取有效的且可支持完成导航的地图数据。

步骤1：假设在商城某一层里进行起点A到终点B的导航，如图1(a)，其中阴影部分是不可通过的节点。

步骤2：进行地图划分。以节点A为圆心，以节点A到节点B的距离为半径得到一个圆，如下：

dis_r向上取整，得到

r

，如下：

r

=dis_r

获得圆方程，如下：

(

x

-startx)+(

y

-starty)=

r

根据上面的圆获取外切正方形，同时也减少了一定数量的节点，得到图1(b)，即是新的地图数据。

图1 算法步骤

步骤3：再次划分地图数据。在商城导航中，节点往往是很多的。当从起点到达终点时，往往不会出现“以退为进”的选择。对步骤2中得到的新的地图数据进行再次划分，根据起点的

x

坐标与终点的

x

坐标的相对位置，如图1(c)。

步骤4：备用机制。当存在个例无法通过步骤3得到的地图数据获得导航规划路径时，会将步骤2的地图数据作为A*算法处理的地图数据。同样道理，当无法通过步骤2得到地图数据时，会将原地图数据作为A*算法处理的地图数据。那么商城布局以及商城使用的导航算法也相应地需要修改。

2.2 改进的A*算法

传统A*算法的启发函数通常只考虑距离启发信息且均采用单次计算，其应用主要为二维平面的寻路，改进后的A*算法采用分层计算的思想，实现了室内三维空间跨楼层的最优路径寻路。在路线规划方法函数中加入相关限制，有效保证了最优路径的唯一性，同时实现了复杂室内地图环境下用户步行路线最短的个性化需求，进一步增强了算法对复杂室内地图环境的适应性。综合室内复杂地图环境下用户对最短距离和直行路程的需求，在位置计算中，引入同时考虑方向和距离启发信息的启发函数，把POI点与寻路节点分开处理，以映射的方式建立联系，有效避免了直接搜寻POI节点数据量大、速率低的问题。

将该方案应用于室内导航中A*算法实现伪代码，如下所示：

创建一个地图数据列表

将原地图数据存入列表尾部

r

<-获得终点和起点的相对距离

r

<-对

r

进行向上取整以起点为圆心，

r

为半径

获取该圆的最小外接正方形，如下处理：

以起点的横坐标-

r

或者0作为正方形的上边界以起点的横坐标+

r

或者横坐标的最大值作为正方形的下边界以起点的纵坐标-

r

或者0作为正方形的左边界以起点的纵坐标+

r

或者纵坐标的最大值作为正方形的右边界

将新的地图数据(即正方形区域)存入地图数据列表尾部

if(终点在起点的下方):

将起点的横坐标作为正方形的上边界

else:

将起点的横坐标作为正方形的下边界

将新的地图数据(即正方形区域)存入地图数据列表尾部

当前地图数据<-弹出地图数据列表尾部元素

设置一个时间值

该时间值内无法通过A*算法获得结果,跳出

当前地图数据<-弹出地图数据列表尾部元素

结束

3 仿真实验

通过仿真实验对A*算法与改进的A*算法进行比较。首先，使用网格模拟路网，网格由多个正方形组成，每一个正方形区域可存储数字0或数字1，其中数字0表示障碍，具有不可通过的性质；数字1表示通路，顾名思义，通路是可通过的。接下来，模拟路网，并在网格中设置起点和终点，且起点和终点必然存在可到达的性质。最后，在同一个网格数据中，分别使用A*算法和改进的A*算法进行模拟导航。在使用算法模拟导航中，有以下两点前提：

(1)存储数字1的是可通过点；其中具有浅黑色阴影且存储数字1的正方形区域是A*算法在网格数据中的扫描点；

(2)存储数字0的正方形区域模拟的是路网中的障碍，并且使用黑色阴影进行了标记。

仿真效果如图2(a)和图2(b)所示。

图2 仿真效果

图2(a)显示A*算法对路网的大部分地图数据进行了扫描；图2(b)显示只扫描了重要区域。由仿真实验结果可知，在同一组网格数据中，改进的A*算法完成导航的时间远小于A*算法。

4 算法效率测试

实验中随机生成地图数据，随机选择起点和终点，对算法改进前后进行算法效率测试。每个节点10组数据，对10组数据求平均值，单位为毫秒，得到的数据见表1。

表1 A*算法优化前后效率比较 ms

图3为A*算法优化前后效率对比，可以明显地看到，优化后A*算法的整体效率提升了近50%。

图3 A*算法改进前后效率对比

下面以位置定位导航测试、活动详情的跳转测试、搜索并导航至商铺测试为例进行系统测试。

(1)位置定位导航测试。当用户设置好起点与终点位置后，测试在不同位置设定起点，系统是否能设计出最优路径给用户。结果显示：设定相同终点，不同起点时，根据当前所在位置与终点的距离，提供最优路径给用户行走；设置相同终点，相同起点时，反馈的最优路径都是一致的；设定相同起点，不同终点时，根据所距路程远近提供最优路径。

(2)活动详情的跳转测试。当用户在发现界面点击当前有最新产品促销活动的心仪商铺时，测试在浏览商铺时跳转到其相应的产品促销活动界面。结果显示：用户点击心仪商铺，点击最新活动链接时，跳转到活动详情界面；用户点击心仪商铺，接着没有点击最新活动，而点击了取消按钮时，没有跳转到活动详情界面。

(3)搜索并导航至商铺测试。当用户点击搜索栏进行商铺的搜索，测试是否能查找并导航至该商铺。结果显示：用户在搜索栏输入商铺名称，并确定起始位置，进行导航时，用户根据导航到达目的地；用户在搜索栏输入商铺名称，搜索到店铺后点击取消按钮时，用户没有导航至目的地；用户在搜索栏输入商铺名称，并没有确定起始位置，点击“到这去”按钮时，小程序提示起始点并未确立，用户没有导航至目的地。

最终测试结果显示，改进的A*算法运用在室内导航小程序符合室内导航目标的需求预期。在室内导航上实现了最优路线规划和导航，解决了用户在室内环境无法快速准确到达目的地的问题。

5 结束语

提出将改进的A*算法运用于室内导航，可以明显提高算法的效率，在实际运用方面，由于自主改造使用，所以接入成本低，定制性强。对A*算法进行自主改造与使用，一方面带来了很多好处，但另一方面，也存在许多问题。方案落地代价高，需要花费时间进行研发落地，整合进实际应用项目中；改进空间大，即使进行了优化，但是A*算法还是存在多种优化方案。