软件工程与应用|引入动态加权地图的混合A*算法

点击蓝字，关注我们

导读

在汉斯出版社《软件工程与应用》期刊上，有文章围绕多机器人路径规划中的前端搜索问题展开研究。

基本信息

引入动态加权地图的混合A*算法

Hybrid A* Algorithm Incorporating a Dynamic Weighted Map

作者：

刘滨珲, 贾丹平*, 康晓琦, 刘振宇：沈阳工业大学信息科学与工程学院，辽宁沈阳

关键词：

多机器人；路径规划；混合A*算法；动态加权地图

基金项目：

辽宁省科技创新团队领军人才项目(LJ222410142060)：基于多模态多传感器融合导航的复合机器人系统研究

doi：

https://doi.org/10.12677/sea.2026.152033

论文详情

上下滑动阅读更多内容

混合 A*算法

混合 A*算法是一种面向非完整约束移动平台的路径搜索方法。与传统 A*算法仅在二维离散栅格空间中进行状态扩展不同，该方法在状态描述中进一步引入了航向角信息，使搜索过程能够在同时包含位置与姿态的状态空间内开展。节点扩展阶段不再局限于固定邻域遍历，而是结合车辆运动学模型构造可执行的运动原语，从而能够在搜索过程中直接体现最小转弯半径、航向连续性等运动约束。

混合 A*算法兼顾了离散搜索的高效性与连续运动学模型的可执行性，因此被广泛应用于移动机器人路径规划问题中。

引入动态加权地图的混合 A*算法

混合 A*算法在进行搜索时，通常依赖离散栅格地图描述的环境信息。本文引入了动态加权地图，将其他机器人已规划路径所对应的潜在冲突风险映射为环境附加代价，从而引导机器人在路径规划阶段尽量避开拥堵区域。

动态加权地图更新方法如下图 1 所示。

为了避免地图权重在各机器人规划过程中频繁变化而影响搜索的稳定性，系统以 t 为周期对地图各栅格单元权重进行更新。当达到周期时，再统一利用集合 R 对地图权重进行更新来生成下一周期所使用的动态加权地图，并在生成新的地图权重后清空集合 R 。该权重旨在动态表征当前道路的拥挤状况及未来机器人流量的演变趋势。通过将此权重引入混合 A*算法，能够有效实现道路交通流量的全局均衡，从而显著降低因局部拥堵而引发的机器人排队等待现象。

在动态加权地图上使用传统混合 A*算法和改进后混合 A*算法，所规划出的路径如图 2 所示。

仿真验证

通过随机生成障碍物地图并对随机起始和终止位置的 25 个机器人分别使用混合 A*算法和引入动态加权地图的混合 A*算法进行对比实验，实验结果如下图 3 和图 4 所示。

如表 1 所示，机器人使用混合 A*算法规划出的路径会比使用动态加权地图后的混合 A*算法更短，而机器人移动最大时间、平均等待时间，由于改进算法在路径规划阶段就考虑到其他机器人的路径，提前避开了交通拥堵的路段，因此使用动态加权地图后的改进算法的移动最大时间、平均等待时间比原始算法的时间更短。

总结

总体而言，本文的研究提升了前端路径规划结果的质量与实用性，也为后续速度规划和轨迹优化提供了更加可靠的初始条件。后续研究可以考虑在现有二维动态加权地图的基础上进一步引入时间维度，构建时空权重模型，以刻画不同机器人在未来时段内对局部区域的动态占用情况。该方法有望降低二维权重对潜在冲突的保守估计，并提升通行效率。

期刊详情