基于动态三角网格和启发式搜索算法路径规划研究

《基于动态三角网格和启发式搜索算法路径规划研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于动态三角网格和启发式搜索算法路径规划研究摘要：在静态三角网络的基础上设计实现了动态三角网络地图算法，通过改变三角网格地图障碍物变化过程中的网格节点代价值，设计相关算法模块并对新生成的网格地图实时获取更新信息，实现动态变化效果。结合搜索算法AnytimeReplanningA*(ARA*)和D*Lite，实现在动态环境中的路径规划方法AnytimeDynamicA*(AI)*)，通过对网格地图中匕扩展信息的保存和在存限时间内不断缩小膨胀因子，找到网格地图中代价值最小的节点，动态规划得到最优路径。在动态环境中，通过模拟动态场景图，并应用动态规划方法建立相应的数据搜索结构和方法，对仿

2、真效果进行分析和对比。本文采集自网络，本站发布的论文均是优质论文，供学习和研究使用，文中立场与本网站无关，版权和著作权归原作者所有，如有不愿意被转载的情况，请通知我们删除己转载的信息，如果需要分享，请保留本段说明。关键词：动态三角网格；AD*算法；路径规划；模拟仿真中图分类号：TN911.1?34；TM417文献标识码：A文章编号：10047373X(2017)11?0103?04ResearchonpathplanningbasedondynamictriangularmeshandheuristicsearchalgorithmWANGWenxia(DepartmentofCo

3、mputerScienceandTechnology,YunchcngUniversity,Yuncheng044000,China)Abstract：Thedynamictriangularnetworkmapalgorithmwasdesignedandimplementedonthebasisofstatictriangularmeshtochangethegridnodecostvalueintheobstaclechangingprocessofthetriangularmeshmap.Therelatedalgorithmwasdesignedtoacquiretheu

4、pdatainformationofthegeneratedgridmapinrealtimetorealizethedynamicchangeeffect.ThesearchalgorithmAnytimeReplanningA*(ARA*)andD*LitearecombinedtorealizethepathplanningmethodA氺(AD*)indynamicenvironmet.Theextendedinformationingridmapissaved,andtheexpansionfactorisreducedconstantlyinthefinitetimet

5、ofindthenodewithminimumcostvalueinthegridmap,andobtaintheoptimulpathofdynamicplanning.Thedynamicscenegraphissimulatedindynamicenvironment.Thedynamicplanningmethodisusedtoestablishthecorrespondingdatasearchstructureandmethodtoanalyzeandcontrastthesimulationresults.Keywords：dynamictriangularmesh

6、；AD氺algorithm；pathplanning；analogsimulation随着社会经济的发展，找到合适、优化而且适用于各种额外条件如动态环境、大规模人群、任意宽度路径等一系列需求成为路径规划算法的研究方向［1］。本文研究在动态地图网格中通过动态搜索算法，实时更新地图信息的同时采用更加高效的搜索算法记录当前群体信息并反馈出动态环境中的环境变化情况，如人群规模、路径宽度等相关信息，以便在较短时间内避免碰撞和到达H的地。1动态环境地图网格构建及生成1.1动态三角网格设计实现在构建动态网格(DynamicLocalClearanceTriangulation,DLCT)［2］的

7、过程中需要保持原有的LCT三角网格［3］中对路径宽度的要求，在动态化的过程中添加和删除障碍物时通过多边形障碍物ID进行操作，在添加算法中把所有障碍物的限制条件遍历立至找到需要添加障碍物的ID;在之后的删除算法中会把与找到的障碍物ID相关的限制条件同时删除。由于在地图中障碍物之间可以相互覆盖，因此每个II)可能关联相互覆盖的限制条件。1.1.1障碍物插入模块该模块在原有LCT(S)的存储单元中插入新的多边形障碍物，在插入过程中，给障碍物设置新的ID。S设置为现在LCT(