摘要
在多陷阱复杂环境下规划机器人导航路径,蚁群算法容易掉入陷阱而降低运算效率和路径质量,为了解决这一问题,提出了基于多种群蚁群算法的路径规划方法。使用栅格法建立了工作环境的(0~1)矩阵模型,使用路径长度和路径平滑度建立了路径评价函数。针对蚂蚁回退策略陷入陷阱时反复回退、标记、判断而降低算法运行效率,提出了陷阱深度标记策略,使蚂蚁能够跳跃出陷阱而提高效率;提出了多种群搜索策略,对不同的蚂蚁种群使用不同的启发信息,兼顾了算法随机性、目的性与收敛性。经仿真验证,在多障碍物复杂环境下,多种群蚁群算法规划的路径长度和平滑度明显优于基本蚁群算法;且多种群蚁群算法寻到最优路径的收敛次数也远少于基本蚁群算法。
When Planning robot navigation path in multi-trap complex environment,ant colony is easy to fall into trap so that computational efficiency and path quality may diminish.To solve the problem,path planning method based on multi-population ant colony algorithm is proposed.(0~1)matrix model of working environment is built by using grid method.Path evaluation function is built by synthesizing path length and evenness.When falling into trap,algorithm computational efficiency of ant backspacing strategy is low because of iterative backspacing,marking and judgement.Trap depth marking strategy is proposed,and ant can jump out of the trap when fall into it,so that algorithm efficiency can be advanced.Put forwarding multi-population searching strategy,different ant population uses different heuristic information,which balance the randomness,purposiveness and astringency.Clarified by simulation,under the multi-obstacle environment,length and smoothness of path planned by multi-population ant colony algorithm are superior to the path planned by basic algorithm.Besides,convergence times of multi-population algorithm is far less than basic ant colony algorithm when finding optimal path.
作者
王明超
WANG Ming-chao(Wuxi Institute of Arts&Technology,Jiangsu Yixing 214200,China)
出处
《机械设计与制造》
北大核心
2020年第9期296-300,共5页
Machinery Design & Manufacture
基金
江苏省教育厅十三五规划基金项目(52701704)。
关键词
机器人导航路径
多种群蚁群算法
陷阱深度标记策略
多种群搜索策略
Robot Navigation Path
Multi-Population Ant Colony Algorithm
Trap Depth Marking Strategy
Multi-population Searching Strategy
