摘要
针对障碍环境中路径规划存在的运算效率低、最短路径遗失问题,根据凸包边界在构建空间网络模型过程中具有快速高效的特点,结合路径与障碍物的相对位置关系,提出了一种基于双侧凸包扩张模型的路径快速规划算法。该算法在对凸包边界算法进行改进的基础上,提取左右侧关联障碍物的凸包边界作为网络模型,利用最短路径算法搜寻目标路径,并在ArcGIS Engine环境对密集不规则障碍物进行了仿真实验。实验结果表明,与凸包边界算法和航路二叉树算法相比,所提出的算法具有构建空间网络模型效率高、实际最短路径不丢失等优点。
There are the problems of low efficiency and losing the shortest path in path planning in the circumstance of obstacles.In addition,the boundary of convex-hull is characterized by its high efficiency in constructing the spatial network model.Enlightened by this,combining the relative position of paths and obstacles,a path planning method based on the bilateral convex-hull expanding model are proposed.Combining the high efficiency in the algorithm of the convex-hull boundary and the veracity in the route binary tree algorithm,a rapid path planning algorithm based on bilateral convex-hull expanding model is proposed.First,according to the relative position of path and obstacle,the obstacles that are relative to the path are grouped into the left obstacles and right obstacles.Then the path and its left and right obstacles are used to obtain its boundary of the convex-hull,which is regarded as the new path.Finally,the spatial network model are constructed by paths,and Dijkstra algorithm is used to solve the shortest path.Under the condition of ArcGIS Engine,three sets of comparative experiments are set up to analyze and compare the algorithm of convex-hull boundary,route binary tree and our proposed algorithm,respectively in terms of the accuracy of the spatial network model and the efficiency of the spatial network model construction.The result of simulation experiments show that our proposed algorithm is characterized by high efficiency in constructing the special network model and maintaining shortest paths.
作者
李改肖
吕程
彭认灿
董箭
LI Gaixiao;Lü Cheng;PENG Rencan;DONG Jian(Department of Military Oceanography and Hydrography and Cartography,Dalian Naval Academy,Dalian 116018,China;Key Laboratory of Hydrographic Surveying and Mapping,Dalian Naval Academy,Dalian 116018,China;Troops 91937,Zhoushan 316000,China)
出处
《武汉大学学报（信息科学版）》
EI
CSCD
北大核心
2021年第1期58-64,共7页
Geomatics and Information Science of Wuhan University
基金
国家重点研发计划(2017YFC1405505)
国家自然科学基金(41601498)。
关键词
凸包扩张模型
快速路径规划
最短路径
不规则障碍
convex-hull expanding model
rapid path planning
the shortest path
irregular obstacle
