The Research Of CGF Parallel Pathplanning Method

Pathplanning is the most foundation of simulation system for it is basic of the behavior of entities in simulation. The efficect of pathplanning has a direct effect on the performance of simulation system. Training simulation has been astricted by poor real-time pathplanning algorithm heavily. So real-time pathplanning under the dynamic environments has become a focus of the area of AI and simulation.With more and more popularity of multi-core CPU, parallel technology is quite potential to improve the computation efficiency. Parallelism of algorithm has been a major aspect to improve the performance of the algorithm. This dissertation aims to explore how to use the parallel technology in pathplanning to meet the need of simulation system.The final goal is to research how to improve the performance of real-time algorithm.To solve the problem of real-time pathplanning in training simulation. The thesis studies the pathplanning in static large scale environment dynamic and complex environment respectively. The main works are as follows:For the static and lager scale scene, PSO can find a feasible path rapidly for the easily astringency. Then combined with the parallel technology, we proposed a parallel PSO pathplanning algorithm. The parallel algorithm process the particles by assigning them to multi-cores averagely and will increase the efficiency extremly. At last, we analysis advantages and disadvantages of the algorithm. and then proposed hierarchy parallelism to improve the scalability of the parallel algorithm.For dynamic and complex environment, the thesis studies space representation with quadtree firstly which is adaptive for dynamic environment. Then introduce an pathplanning algorithm based on quadtree and analysis the characteristics of it. At last, the parallel bidirectional Quad* is proposed, PB-Quad* sereaches from each path extremity to the other using two cores, which can reduce the total number of searching nodes and improve the performance observably,Simulation results demonstrate that PSO can find a feasible route rapidly, and parallel PSO can obtain a favorable scalability. The quadtree could represent the space accurately with little quadnodes, and it can update promptly according local modified when the environment changes. At last, the experiment shows that PB-Quad* can reduce the search time markedly compared with Quad*.