Abstract: Aiming at the problems of U-shaped traps,large number of iterations and disorderly search of in the traditional ant colony algorithm in the initial path planning of Automated Guided Vehicles（AGVs）,an improved ant colony algorithm based on the combination of heuristic search strategy and U-shaped trap filling strategy was proposed,and a reward and punishment mechanism was introduced.Advance judgment filling was made for the four-neighbor characteristics of U-shaped traps.A search strategy based on guided heuristics was designed to help ant colonies overcome the disorderly search state in the early stage.The reward and punishment mechanism was introduced to accelerate the convergence of the algorithm,and the redundant inflection points were eliminated through the greedy algorithm.Through experimental simulation,the improved algorithm could enhance the iterative efficiency by more than 30% in different sizes of raster maps,eliminate a large number of redundant inflection points and save algorithm time.

Key words: ant colony algorithm, heuristic search strategy, U-shaped trap filling strategy, greedy algorithm, automated guided vehicles, reward and punishment mechanisms

摘要： 针对传统蚁群算法在自动导引车（AGV）初期路径规划中存在U型陷阱、无序搜索、迭代次数较多等问题,提出一种基于启发式搜索策略与U型陷阱填充策略相结合的改进蚁群算法,并引入奖惩机制。针对U型陷阱的四邻域特性进行事先判断填充;设计一种基于引导式启发的搜索策略,协助蚁群渡过前期无序搜索状态;引入奖惩机制加快算法收敛,通过贪心算法将冗余拐点进行剔除。通过实验仿真验证,在不同大小的栅格地图中,改进算法均提高了30%以上的迭代效率,剔除了大量冗余拐点,节省了算法时间。

关键词: 蚁群算法, 启发式搜索策略, U型陷阱填充策略, 贪心算法, 自动导引车, 奖惩机制