基于理论最短距离变权重A~*算法的路径规划  

Path Planning Based on Theoretical Minimum Distance of A~* Algorithm

作　　者：刘源[1] 王海泉[2] Liu Yuan;Wang Haiquan(School of Mechanotronics Engineering,Zhengzhou University of Aeronautical Industry,Zhengzhou 450015,China;School of Electric and Information Engineering,Zhongyuan University of Technology,Zhengzhou 450015,China)

机构地区：[1]郑州航空工业管理学院机电工程学院,郑州450015 [2]中原工学院电子信息学院,郑州450015

出　　处：《计算机测量与控制》2018年第4期175-178,共4页Computer Measurement &Control

基　　金：河南省科技攻关项目(172102210076)

摘　　要：在栅格化的障碍物地图中,将简单高效的A~*算法引入解决路径规划问题;为了提高路径规划效率,减少搜索节点数量,提出了一种在规定的椭圆区域内,基于理论最短距离动态改变A~*算法中估价函数权重的最短路径算法;该算法将搜索范围限定在规定的椭圆区域内,椭圆以起点和终点为焦点,利用统计分析与路径中障碍物尺寸相结合的方法计算长轴参数;将各节点实际代价权重赋予动态变化的权值,以实际代价与起点O到终点D的直线距离的比值为该点权重,且规定了上下限以保证搜索精度;同时,对节点估计代价赋予惩罚函数,远离理论最短路径距离的节点将获得较大的惩罚值,使最终路径靠近理论最短路径;通过仿真实验证明,该算法在保证搜索精度的前提下,大大提高了搜索效率。The paper introduces a simple and efficient A*algorithm into the path planning problem in a grid map.In order to improve the efficiency of path planning,this paper proposes a shortest path algorithm based on theoretical minimum distance,characterized by dynamically changing valuation function weights of A star algorithm with limited ellipse area.The start point and end point are two focal points of ellipse area,and the long axis of ellipse is calculated by statistical analysis and obstacle size between start point and end point.Actual cost of each node is given weight which dynamic change between upper and lower limits.The penalty cost is given to the penalty function which the farther away from the line,the greater the penalty.The final path is close to the shortest path in theory through penalty factor acting on estimated cost.The penalty factor is proportional to the shortest distance to the theory.The simulation results show that the shortest path algorithm can improve search efficiency greatly and ensure search accuracy.

关 键 词：理论最短距离 路径规划 椭圆搜索区域 惩罚函数 栅格法 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]