一种改进的移动机器人路径规划A*算法  

An Improved A*Algorithm of Path Planning of Mobile Robot

作　　者：洪昭斌 杨海杰 陈水宣 袁和平 HONG Zhaobin;YANG Haijie;CHEN Shuixuan;YUAN Heping(School of Mechanical&Automotive Engineering,Xiamen University of Technology,Xiamen 361024,China)

机构地区：[1]厦门理工学院机械与汽车工程学院,福建厦门361024

出　　处：《厦门理工学院学报》2023年第1期49-56,共8页Journal of Xiamen University of Technology

基　　金：福建省自然科学基金项目(2020J01277);福建省科技计划工业引导性项目(2019H0037);江西中烟工业有限责任公司科研项目(赣烟工科计2019-15)。

摘　　要：在路径规划中,针对传统的A*算法存在的搜索效率低、路径转向次数多及路径不平滑等问题,提出了一种改进的A*算法。该算法采用自适应搜索邻域并叠加跳点搜索策略来扩展子节点,以确保在不影响算法搜索效率的前提下缩短路径长度和减少路径转向次数;根据被扩展路径与最近障碍物的距离,进一步筛选子节点,以加强路径的安全性;对估价函数进行优化,以提高算法的搜索效率;对A*算法规划的路径使用引入虚拟控制点的3次B样条曲线进行平滑处理,以消除路径转折点处的尖峰,使路径更短、更平滑。仿真结果表明,改进算法在进行路径规划时,相比4邻域A*算法,搜索时间减少17.5%,路径长度减少8.1%,路径转向次数减少56.5%,转角总和减少76.2%;相比8邻域A*算法,搜索时间减少14.1%,路径长度和路径转向次数相近,转角总和减少57.4%,且lo,min增大,路径更安全。Aiming at solving the problems of low search efficiency,excessive path turns and uneven path of the traditional A*algorithm in path planning,an improved A*algorithm was proposed.An adaptive neighborhood search strategy and a hop search strategy were used to expand the child nodes so as to shorten the path length and reduce the number of path turns without affecting the search efficiency of the algorithm.The child nodes were further screened on the distance between the extended path and the nearest obstacle to enhance the security of the path,and the evaluation function optimized to improve the search efficiency of the algorithm.Finally,the path planned by A*algorithm was smoothed by using the cubic B-spline curve with the introduction of virtual control points so as to eliminate the sharp peaks at the turning points of the path and make it shorten and smoother.The simulation results show that,the improved algorithm reduces the search time by 17.5%,the path length by 8.1%,the number of path turns by 56.5%,and the sum of corners by 76.2%compared with the 4-neighborhood A*algorithm,and it reduces the search time by 14.1%,has the similar path length and number of path turns,reduces the sum of corners by 57.4%,and improved the shortest distance between the path and the obstacle(lo,min)and safer path,compared with the 8-neighborhood A*algorithm respectively.

关 键 词：移动机器人 路径规划 A*算法 扩展方式 估价函数 平滑处理 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]