摘要
针对传统A^(*)算法在大型场景下AGV(automated guided vehicle)路径规划时遍历节点多、路径平滑性差和搜索时间长等问题,提出了三层结构的块搜索A^(*)(Blocks-A^(*))算法,并构建麦克纳姆轮AGV解决运动学约束问题。Blocks-A^(*)算法将地图分解为多个较大的区域(块),采用以块搜索代替节点搜索的方式。第一层,通过先验地图信息划分自由空间和限制空间,将自由空间分解成若干三角形,对三角形进行节点等效化并构建邻接矩阵;第二层,运用Blocks-A^(*)算法计算最优块通道,生成基于邻接三角形边界线中点的次优路径;第三层,根据不同场景应用线性规划或二次规划优化模型,生成最终的最优路径。实验结果表明,所提算法在大型场景下的遍历节点数明显减少,优化后的路径平滑度更符合AGV的运行要求,搜索效率得到显著提高,可专门应对大型场景下的路径规划问题。
To address the issues of excessive node traversal,poor path smoothness,and long search time in traditional A^(*)algorithms for automated guided vehicle(AGV)path planning in large-scale scenarios,this paper proposed a three-layer block search A^(*)algorithm(Blocks-A^(*))and developed a Mecanum-wheel AGV to resolve kinematic constraints.The Blocks-A^(*)algorithm decomposed the map into larger regions(blocks),replacing node-level searches with block-level operations.Firstly,it divided free space and restricted space based on prior map information,partitions free space into triangles,performed node equivalence for these triangles,and constructed adjacency matrices.Secondly,the Blocks-A^(*)algorithm calculated the optimal block channel to generate suboptimal paths using midpoints of adjacent triangle boundaries.Thirdly,it applied linear programming or quadratic programming optimization models according to specific scenarios to generate the final optimal path.Experimental results demonstrate that the proposed algorithm significantly reduces traversed nodes in large-scale environments,improves path smoothness to better meet AGV motion requirements,and enhances search efficiency.This method is specifically applicable to large-scale path planning problems.
作者
汪行
黄细霞
梁董
Wang Hang;Huang Xixia;Liang Dong(Institute of Logistics Science&Engineering,Shanghai Maritime University,Shanghai 201306,China;Key Laboratory of Transport Industry of Marine Technology&Control Engineering,Shanghai Maritime University,Shanghai 201306,China)
出处
《计算机应用研究》
北大核心
2025年第8期2355-2363,共9页
Application Research of Computers
基金
国家自然科学基金资助项目(52001197)。
