Research On Indoor Path Planning Based On Improved A* Algorithm

With the advent of the Internet age and the ever-expanding scale of cities,outdoor navigation systems have been widely used.However,indoor navigation systems have not been ideally designed.The core of indoor navigation research is indoor positioning,indoor map construction and indoor path planning algorithms.Among them,indoor positioning has not yet formed a universally applicable method,and the construction standards of indoor maps have not been unified.At the same time,the indoor path planning algorithm still needs to be specifically designed for specific situations.These are issues that need to be further studied and solved.This paper mainly studies the related problems of indoor path planning.Compared with the static path planning algorithm under the known environment,selects the heuristic A* search algorithm as the core research algorithm,compares it with the improved algorithm,and carries out the relevant simulation experiments,verify the effectiveness of the improved A* algorithm.The main work of this paper is as follows:Firstly,aiming at the problem that the A* algorithm search path leads to repeated traversal of the OPEN table,this paper chooses the minimum heap to storage OPEN table node so that keep the node with the smallest F value at the vertex position always,which is convenient for searching for access during the comparison process,thereby improving efficiency.At the same time,the Hash table is used to optimize the OPEN table index,so that the membership judg ment time complexity of the OPEN table member is reduced.Secondly,for the problem of multiple useless nodes encountered in the A* algorithm path-finding process,this paper uses the cosine function as an added value to improve the traditional heuristic function.The new heuristic function is formed to avoid repeated search problems and achieve the goal of effectively reducing the number of accessing useless nodes.Thirdly,in order to verify the effectiveness of the improved A* algorithm,the improvement A* algorithm is compared with the before by simulation experiments in this paper.The time-consuming consumption and the number of search nodes of the improvement algorithm are counted after multiple sets of experimental tests,evaluate the effectiveness of the improved algorithm by using the chart generated.