融合改进A*和DWA算法的物流机器人自主导航及路径规划研究
- 来源:互联网周刊
- 关键字:DWA算法,自主导航,路径规划
- 发布时间:2024-08-23 11:55
文/黄以成 同方威视技术股份有限公司
摘要：本文提出了一种融合改进A*算法和DWA算法的物流机器人自主导航及路径规划方法。改进A*算法引入航向角策略和Floyd算法优化，生成平滑高效的全局路径；改进DWA算法引入全局路径因素和自适应窗口机制，实现实时避障与全局引导。实验结果表明，这种融合改进算法相比传统A*和DWA算法，任务完成率提高8.2%，平均用时缩短14.4%，平均能耗降低21.7%，显著提升了物流机器人在复杂动态环境中的导航性能。
关键词：物流机器人；A*算法；DWA算法；自主导航；路径规划
引言
随着物流行业的快速发展，物流机器人在仓储、配送等环节发挥着越来越重要的作用。然而，复杂多变的物流环境对物流机器人的自主导航和路径规划能力提出了更高要求。传统算法在动态未知环境中适应性不足，智能优化算法的实时性和收敛性有待提高。本文旨在解决上述问题，提出一种融合改进A*和DWA算法的路径规划方法，以提高物流机器人导航的安全性和效率。
1. 现阶段物流机器人自主导航与路径规划算法存在的问题
物流机器人需要在复杂、动态的环境中实现高效、安全的导航与路径规划，相关要求对其自主性和智能化水平提出了一些挑战。传统算法和采样算法对动态未知环境的适应性不强，实时避障能力有限；智能优化算法的实时性和收敛性还有待提高，参数调试较为复杂；大部分研究对算法改进后的计算效率和路径质量缺乏定量分析与对比[1]。针对上述问题，本文从提高物流机器人导航规划的安全性与高效性出发，提出了改进A*和DWA算法相结合的路径规划策略。
2. 融合改进A*与DWA算法的路径规划方法
2.1 A*算法改进
2.1.1 引入航向角策略
传统A*算法在搜索最优路径时，只考虑了当前节点到目标节点的估计代价，而忽略了节点间连接路径的方向变化，导致生成的路径往往存在大量冗余节点，路径平滑度差。针对上述问题，研究在A*算法中引入航向角的概念，通过评估相邻节点间的夹角来优化路径的生成过程。
设当前节点为ni，其父节点为ni-1，可扩展的子节点为。定义航向角为连接和的夹角，如图1所示。
航向角可通过计算得到公式1：
（1）
引入航向角后，子节点的估计代价可表示为公式2：
（2）
其中，为起点到的实际代价，为到目标点的估计代价，w为航向角权重因子。通过合理设置权重因子w，可以控制航向角对节点扩展的影响程度。w值越大，算法越倾向于选择与当前运动方向一致的节点，生成的路径越平滑；w值越小，算法越倾向于选择距离目标点最近的节点，生成的路径越短。因此，w值的选取需要在路径长度和平滑度之间进行权衡[2]。
2.1.2 Floyd算法优化路径
尽管引入航向角策略后，A*算法生成的路径得到了一定程度的平滑，但仍然存在一些冗余节点，导致路径长度不够理想。为了进一步优化路径，研究在A*算法的基础上，采用Floyd算法对生成的路径进行二次处理。
Floyd算法是一种基于动态规划的多源最短路径算法，可以在O(n3)的时间复杂度内求出任意两点之间的最短路径。设改进A*算法生成的初始路径为P0={n0,n1,…,nm}，其中n0为起点，nm为终点，m为路径节点数。首先，根据路径P0构建一个(m+1)×(m+1)的邻接矩阵D，矩阵元素dij表示路径节点ni和nj之间的欧几里得距离，当ni和nj不直接相连时，dij=∞。
Floyd算法对于路径上的任意两个节点ni和nj，如果经过中间节点nk（i
2.2 DWA算法改进
在动态环境下，单纯依靠全局路径规划难以应对突发障碍，容易导致机器人碰撞等危险情况。为了使机器人能够在局部动态环境中灵活避障，同时兼顾全局路径的引导，研究在DWA算法的基础上进行了针对性的改进和优化。
传统DWA算法通过在机器人速度空间中采样获得一系列可行速度，并评价每个采样速度的效用，从中选取最优速度作为下一时刻的控制指令。评价函数通常包含方向、速度和距离三个因素，分别表示为(ν)、和，则采样速度的效用如公式3所示：
（3）
其中，为三个因素的权重系数。然而，传统DWA算法在评价速度时，只考虑了局部信息，容易使机器人偏离全局最优路径。为了增强DWA算法的全局引导能力，研究在评价函数中引入全局路径因素，表示采样速度下机器人预测位置距离全局路径的偏离程度，偏离越小，该项得分越高[4]。同时为了提高避障的安全性，还对距离因素进行了细化，考虑了机器人与障碍物的相对速度，引入碰撞时间项Tc。改进后的DWA评价函数如公式4所示：
（4）
其中，为四个因素的权重系数。在速度采样时，传统DWA算法采用等间隔的网格采样方式，采样粒度较粗，导致控制输出不够平滑。研究采用了基于概率分布的非均匀采样策略，在局部最优速度附近进行细粒度采样，在其他区域进行粗粒度采样，从而在保证实时性的同时提高了速度选择的精度。
2.3 融合改进算法设计实现
为实现物流机器人在复杂环境中的自主导航，本文提出了一种融合改进A*算法和改进DWA算法的路径规划方法。该方法以改进A*算法为核心，生成全局最优路径，并结合改进DWA算法进行局部动态避障，实现了全局路径引导下的实时避障，算法融合策略如图2所示。
融合策略分为五个步骤：
（1）离线阶段，利用改进A*算法在静态地图中规划出起点到目标点的全局最优路径。引入航向角因素，评估相邻节点间的夹角，优先选择与当前节点方向一致的节点，生成平滑路径，然后采用Floyd算法对路径进行二次优化，压缩冗余节点，缩短路径长度。
（2）机器人开始执行任务后，进入在线导航阶段。利用传感器实时获取周围环境信息，并与静态地图进行融合，构建局部代价地图。代价地图中包含静态障碍物信息和动态障碍物信息，用于DWA算法的碰撞检测。
（3）根据当前机器人位置和局部代价地图，在改进DWA算法框架下进行速度采样和评价。评价函数包括方向、速度、距离和全局路径四个因素，其中全局路径因素用于衡量采样速度下机器人的预测位置与全局路径的偏离程度。
（4）评价函数为每个采样速度赋予效用值，选取效用最高的速度作为下一控制周期的速度指令，输出到机器人底层控制器执行。机器人在局部路径上运动的同时，实时进行障碍物检测和避障决策。
（5）随着机器人不断运动，更新当前位置和局部代价地图，重复步骤（3）和步骤（4，直到到达目标点或出现无法避障的情况。如果出现无法避障，则须返回步骤（1，重新规划全局路径。
为加快算法的收敛速度，减少无效搜索，研究在改进DWA算法的基础上，设计了自适应窗口调整机制[5]。根据机器人与最近障碍物的距离，动态调整速度空间的搜索范围，距离障碍物越近，搜索窗口越小，反之则越大。同时，在窗口内采用非均匀采样，提高局部最优速度附近的采样密度，自适应窗口示意如图3所示。
3. 融合改进算法的物流机器人导航规划实验分析
为验证融合改进A*和DWA算法的路径规划方法的有效性和优越性，本文在物流机器人平台上开展了导航规划实验。实验在完整的物流场景中进行，包含多个拣货点和配送站，机器人需要根据订单依次经过各个目标点，同时避开动态障碍。实验对比了融合改进算法与传统A*+DWA算法在任务完成率、平均用时和平均能耗三个指标上的差异。其中，平均用时反映了路径的时间优化程度，平均能耗反映了路径的平滑度和速度变化的剧烈程度，两种算法的综合导航实验结果对比如表1所示。
从表1可以看出，融合改进算法相比传统算法，任务完成率提高了8.2%，平均用时缩短了约14.4%，平均能耗降低了约21.7%，整体导航性能大幅提升。这得益于全局路径的持续优化和局部路径的自适应调整，使得机器人能够在动态环境中高效、灵活地完成导航任务。结果证明，融合改进A*和DWA算法的路径规划方法在综合导航性能上显著优于传统算法，该方法能够使物流机器人在复杂动态环境中实现高效、平滑、安全的自主导航，显著提高了物流作业效率和智能化水平。
结语
本文提出的融合改进A*和DWA算法的物流机器人自主导航及路径规划方法，有效解决了传统算法在复杂动态环境中的局限性。未来研究可进一步探索算法在更复杂环境下的适应性，如多机器人协同导航、动态目标追踪等场景。此外，还可结合深度学习等人工智能技术，提高算法的环境感知和决策能力。本研究为物流机器人在复杂动态环境中实现高效、安全、智能的自主导航提供了新的技术支持，对推动物流行业智能化升级具有重要意义。
参考文献：
[1]薛光辉,刘爽,王梓杰,等.基于改进概率路线图算法的煤矿机器人路径规划方法[J].工矿自动化,2023,49(6):175-181.
[2]郭志军,尹亚昆,李亦轩,等.融合改进A～*和TEB算法的移动机器人路径规划[J].河南科技大学学报(自然科学版),2023,44(4):57-65,7.
[3]常见,任雁.基于改进遗传算法的机器人路径规划[J].组合机床与自动化加工技术,2023(2):23-27.
[4]赵倩楠,黄宜庆.融合A～*蚁群和动态窗口法的机器人路径规划[J].电子测量与仪器学报,2023,37(2):28-38.
[5]王鹤静,王丽娜.机器人路径规划算法综述[J].桂林理工大学学报,2023,43(1):137-147.
作者简介：黄以成，硕士研究生，工程师，研究方向：自动控制、项目管理。
关注读览天下微信，
100万篇深度好文，
等你来看……
