Journal of Computer Applications ›› 2012, Vol. 32 ›› Issue (08): 2223-2226.DOI: 10.3724/SP.J.1087.2012.02223

• Artificial intelligence • Previous Articles     Next Articles

Group path planning method based on improved group search optimization algorithm

ZHENG Hui-jie1,2,LIU Hong1,2,ZHENG Xiang-wei1,2   

  1. 1. School of Information Science and Engineering, Shandong Normal University, Jinan Shandong 250014, China
    2. Shandong Provincial Key Laboratory for Distributed Computer Software Novel Technology (Shandong Normal University), Jinan Shandong 250014, China
  • Received:2012-01-09 Revised:2012-03-01 Online:2012-08-28 Published:2012-08-01
  • Contact: ZHENG Hui-jie

基于改进群搜索优化算法的群体路径规划方法

郑慧杰1,2,刘弘1,2,郑向伟1,2   

  1. 1. 山东省分布式计算机软件新技术重点实验室(山东师范大学),济南 250014
    2. 山东师范大学 信息科学与工程学院,济南 250014
  • 通讯作者: 郑慧杰
  • 作者简介:郑慧杰(1987-),女,山东泰安人,硕士研究生,主要研究方向:进化计算、计算机辅助设计;
    刘弘(1955-),女,山东济南人,教授,博士生导师,主要研究方向:计算机辅助设计、人工智能;
    郑向伟(1971-),男,山东济南人,副教授,博士,主要研究方向:进化计算、人工智能。
  • 基金资助:
    国家自然科学基金资助项目(60970004);教育部博士点基金资助项目(20093704110002);山东省自然科学基金资助项目(ZR2010QL01)

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

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

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

CLC Number: