王文霞

摘 要： 在静态三角网络的基础上设计实现了动态三角网络地图算法，通过改变三角网格地图障碍物变化过程中的网格节点代价值，设计相关算法模块并对新生成的网格地图实时获取更新信息，实现动态变化效果。结合搜索算法Anytime Replanning A*（ARA*）和D* Lite，实现在动态环境中的路径规划方法Anytime Dynamic A*（AD*），通过对网格地图中已扩展信息的保存和在有限时间内不断缩小膨胀因子，找到网格地图中代价值最小的节点，动态规划得到最优路径。在动态环境中，通过模拟动态场景图，并应用动态规划方法建立相应的数据搜索结构和方法，对仿真效果进行分析和对比。

关键词： 动态三角网格； AD*算法； 路径规划； 模拟仿真

中图分类号： TN911.1?34； TM417 文献标识码： A 文章编号： 1004?373X（2017）11?0103?04

Research on path planning based on dynamic triangular mesh

and heuristic search algorithm

WANG Wenxia

（Department of Computer Science and Technology， Yuncheng University， Yuncheng 044000， China）

Abstract： The dynamic triangular network map algorithm was designed and implemented on the basis of static triangular mesh to change the grid node cost value in the obstacle changing process of the triangular mesh map. The related algorithm was designed to acquire the updata information of the generated grid map in real time to realize the dynamic change effect. The search algorithm Anytime Replanning A*（ARA*） and D* Lite are combined to realize the path planning method A*（AD*） in dynamic environmet. The extended information in grid map is saved， and the expansion factor is reduced constantly in the finite time to find the node with minimum cost value in the grid map， and obtain the optimul path of dynamic planning. The dynamic scene graph is simulated in dynamic environment. The dynamic planning method is used to establish the corresponding data search structure and method to analyze and contrast the simulation results.

Keywords： dynamic triangular mesh； AD* algorithm； path planning； analog simulation

随着社会经济的发展，找到合适、优化而且适用于各种额外条件如动态环境、大规模人群、任意宽度路径等一系列需求成为路径规划算法的研究方向[1]。本文研究在动态地图网格中通过动态搜索算法，实时更新地图信息的同时采用更加高效的搜索算法记录当前群体信息并反馈出动态环境中的环境变化情况，如人群规模、路径宽度等相关信息，以便在较短时间内避免碰撞和到达目的地。

1 动态环境地图网格构建及生成

1.1 动态三角网格设计实现

在构建动态网格（Dynamic Local Clearance Triangulation，DLCT）[2]的过程中需要保持原有的LCT三角网格[3]中对路径宽度的要求，在动态化的过程中添加和删除障碍物时通过多边形障碍物ID进行操作，在添加算法中把所有障碍物的限制条件遍历直至找到需要添加障碍物的ID；……