基于新的粒子群算法的虚拟角色路径规划仿真系统

New particle swarm optimization algorithm for path planning simulation of virtual character

针对标准粒子群算法(SPSO)中粒子在避障时易陷入局部最优而无法继续行走的问题,提出一种将局部最优粒子的位置后退至其历史最优位置,在此位置进行8-邻域局部搜索最优可行解的方法。该方法找到离目标最近的非障碍点,让粒子行走至该位置;同时找出当代群体的全局最优位置,并将各粒子位置设定为此位置,继续迭代。通过在栅格地图中的避障实验发现,传统算法粒子遇到障碍物时会陷入局部最优而无法行走,而改进后的算法粒子能够成功避开障碍到达终点。将改进的算法引入三维视景仿真系统,仿真结果表明在大地图、多障碍场景下粒子陷入局部最优而导致寻路失败的概率高达50%;通过给障碍物添加圆形坡度对算法进一步改进,粒子成功规划出路径的概率提高至83%。实验结果表明改进后算法搜索能力增强,能在复杂场景中有效地规划出路径。

For the problem of that the particle easily falls into local optimum when avoiding obstacles and cannot walk forward, the method of retreating the position of the local optimal particle to its historical best position and searching the feasible and optimal location in the 8-neighborhood of this position was proposed. The position which is nearest to the target and is not a barrier could be found by this method, then the particle was moved to it. Meanwhile, the global optimal position of current generation particle swarm could be found, and the location of each particle was set for this position to continue iteration. In the experiments for obstacle avoidance in grid map, the fact was found that when encountering obstacles, the particles fell into local optimum by the traditional methods, but particles could successfully avoid obstacles and arrive the end by using the improved algorithm. The improved algorithm was introduced into the 3D visual simulation system, in large map with many obstacles scenarios, the probability of falling into local optimum of the particle was reached to 50% which resulted in routing failure. After adding a circular slope to the obstacles for the further improvement of the algorithm, the probability of successful path-finding of the particle was increased to 83%. The experimental results show that the search ability of the improved algorithm is increased and it can effectively plan path in a complex scene.