基于混合蛙跳算法的层次化群体路径规划  

HIERARCHICAL GROUP PATH PLANNING BASED ON SHUFFLED FROG LEAPING ALGORITHM

作　　者：庞乐[1,2] 刘弘[1,2] 吕蕾[1,2] 

机构地区：[1]山东师范大学信息科学与工程学院,济南250358 [2]山东省分布式计算机软件新技术重点实验室,济南250014

出　　处：《山东师范大学学报（自然科学版）》2015年第1期10-14,19,共6页Journal of Shandong Normal University(Natural Science)

基　　金：国家自然科学基金资助项目（61272094）．

摘　　要：在复杂的群体运动场景中，传统路径规划方法具有计算量大、耗时长、效果生硬等缺点。为此笔者提出了一种层次化路径规划方法，将群体路径规划问题分为两个层次，在底层使用A＊算法进行全局路径搜索，规划出一条从起始点到目标点的全局最优路径，使群智能算法进行上层局部路径规划时只考虑上层粒子间的碰撞；在上层采用混合蛙跳算法并结合多线程技术进行个体路径的动态规划。仿真实验结果表明：所提出的方法有效降低了群体路径规划中的算法复杂度和时间复杂度，在较为复杂场景下能够逼真和高效地进行群体运动仿真。In some complex scenes,traditional path planning methods have shortcomings such as largecomputation,time -consuming and the stiff effect.The hierarchical path planning method is used to solve thisproblem in this paper.The group path planning is divided into two hierarchies.The A＊ algorithm is used in lowerglobal path planning to find a path from the starting position to the target position.So that the upper swarmintelligence algorithm considered the collision between the particles in local path planning only;SFLA in the upperlocal path planning and combined multi -threading technology with dynamic group path planning are used.Thesimulation results show that this method effectively reduces the population path planning algorithm complexity andtime complexity and it is more realistic and efficient to achieve requirement of group sports simulation in complexscenes.

关 键 词：群体智能 混合蛙跳算法 群体路径规划 层次化 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]