一种基于A*算法的图搜索路径优化平滑方法
2022-11-02陈子豪
现代制造技术与装备 2022年9期
关键词:优化
陈子豪
(杭州应用声学研究所,杭州 311499)
路径规划作为地图导航、无人平台运动控制等多种技术领域的关键环节,一直都是研究的热点。A*算法[1]、D*算法、人工势场、快速搜索随机树(Rapidexploration Random Tree,RRT)等经典算法,在路径搜索领域都有十分广泛的应用。但是,各算法自身均存在不同的短板,导致这些算法从发布至今仍在不断演变和衍生。例如,原始的A*算法生成路径可能存在过于紧贴障碍物、拐点较多等问题[2-4]。本文基于A*算法提出了一种基于二阶贝塞尔曲线的路径优化平滑方法。
1 A*算法
由于A*算法的原理涉及篇幅较长且已有大量发表资料可供参考,这里不对A*算法的原理进行赘述,仅对A*算法中的关键步骤加以说明。
基于图搜索的A*算法实现过程如下:
(1)读取原始图像进行灰度化,得到二值化图像;
(2)以像素点为单位,遍历整张图片,将图片中的点分类,白色点标志为可行域,黑色点标志为障碍;
(3)障碍物膨胀处理;
(4)设定起点和终点坐标,检查起点和终点是否为障碍,若是,终止搜索,若处于可行域上,执行步骤5;
(5)将起点作为openlist中第一个节点,开始路径搜索;
(6)将路径搜索最终得到的路径点保存在容器中;
(7)画出路径轨迹。
1.1 障碍物膨胀
对障碍物进行膨胀处理是由于初始算法规划的路径会出现紧贴障碍物的情况,需设置一定的危险半径,避免过于靠近障碍物发生碰撞。障碍物膨胀也可通过简单的图像腐蚀膨胀实现。但是,实际应用场景中局部地图的生成主要依靠激光或声呐等传感器测量到障碍物的实际距离,再选择合适的地图分辨率将探测到的障碍物映射到局部地图上。……
登录APP查看全文
