Study On The Method Of Multi-objective Path Planning Based On Grid

The path planning means that in the environment of obstacles, in accordance with certain evaluation criteria, the collision free path is sought from the starting state to the target state. There are a lot of evaluations of the path planning problem, such as safety, energy consumption, path length. The application of path planning is very extensive, mainly in the field of VLSI design, robot path planning and geographic information system. The main content is also related to a number of subjects, such as environmental expression, planning methods, path search and so on.The research target of this paper is to design a high-efficient path-searching algorithm, basing on A* algorithm and further proper optimization, and apply it in a dynamic virtual environment to enable a non-collision, non-conflict concurrent movement for several virtual roles, whose paths' length is as short as possible and turning angle as small as possible.A* is a heuristic search algorithm, which is widely used in the path search and graph traversal. But, it also has some defects and shortcomings. Firstly, the performance of the algorithm is related to the design of the heuristic function. Heuristic function is based on the experience, so it is influenced by subjective factors; Secondly, A* algorithm will frequently visit two static table. So, it is important to design an appropriate data structure to improve the efficiency of accessing state table; At last, the path which is calculated by the algorithm is a section of the line with large turning angle, which seems not true.Improvement measures in addressing the deficiency of A* algorithm mainly include: optimize the searching speed for Open table, design another new heuristic function as the evaluation function, smooth the path, design collision-solving strategies for multi sports body.Through the simulation experiment, the improved A* algorithm is more efficient. It is applied to a dynamic virtual scene.