Abstract: Concerning the problems that traditional path planning of group animation needs long time for searching and is of poor optimization, the authors proposed a multi-threaded path planning algorithm based on group search optimization. Firstly, to solve the problem that the algorithm easily gets trapped in local optimum, metroplis rule was introduced in this search mode. Secondly, by using random path through the multi-threading and stitching techniques, the algorithm was applied to path planning. The simulation results show that the algorithm has better global convergence both in high-dimensional and low-dimensional cases, and the method is good enough to meet the requirements of path planning in complex animation environment.

Key words: swarm intelligence, group search optimization algorithm, simulated annealing algorithm, path planning, group animation

摘要： 针对群体动画中传统路径规划算法搜索时间长、寻优能力差等问题，提出一种利用群搜索算法进行多线程路径规划的方法。该方法首先将模拟退火算法引入到搜索模式中，克服算法易陷入局部最优的问题；其次，通过结合多线程和路径随机拼接技术，将算法应用到路径规划中。仿真实验表明该算法无论在高维还是低维情况下都具有较好的全局收敛性，能够很好地满足在复杂动画环境下路径规划的要求。

关键词: 群体智能, 群搜索优化算法, 模拟退火算法, 路径规划, 群体动画