Research On Path Planning Methods Based On Indoor MAP

Path planning is widely used in indoor navigation,urban planning and unmanned driving.It mainly consists of environment modeling and path finding.At present,the research on path planning at home and abroad mainly focuses on outdoor scenes and video games,while the research on real indoor scenes is in its infancy.The indoor environment has the characteristics of many kinds of feature points,large amount of information,complex topological structure,large number of obstacles and irregular distribution.The environment modeling method in the traditional path planning technology is difficult to describe it accurately.Indoor environment information is stored in indoor maps,so how to design indoor path planning methods based on indoor maps is of great research value.First of all,according to the characteristics of indoor environment,this paper proposes a three-level indoor environment modeling framework based on indoor maps,and models the indoor environment hierarchically according to the indoor environment information stored in the indoor map.The framework uses the corresponding environment modeling methods to model the indoor environment at every level,and generates a three-level indoor environment model to solve the problems that the traditional single environment model can not accurately represents the indoor environment information,the storage space is too high,and the modeling process can not be performed automatically.The first level is the floor level,this paper uses a hash table based approach to build the environment model.The second level is the regional level,this paper use the uniform grid method for environmental modeling.The third level is the indoor level,this paper uses triangulation algorithm for environmental modeling Compared with the traditional model,the three-level indoor environment model can represent the indoor complex environment more accurately and provide the model foundation for the indoor path finding.Secondly,according to the above-mentioned three-level indoor environment framework,the paper proposes a corresponding path search algorithm corresponding to each level of environment model.Specifically: 1)For the floor level hash model,this article uses the current common direct access method;2)For the regional level grid model,this paper presents a data-map based jump point search algorithm(Data-Map Based Jump Point Search,DMBJPS),which solves the problem of low search speed and high memory overhead that are common to the current path finding algorithms based on the grid method.Paper verifies that the algorithm can speed up the path search and reduce the memory overhead by exprimentation.3)For the indoor-level triangulation model,a Triangle-Node Based A *(TNBA *)algorithm based on triangular nodes is proposed in this paper.The algorithm solves the problem that the traditional path length of the conventional algorithm is long and does not consider the size of the moving object.The experiment results show that the proposed algorithm has a shorter path length than the traditional algorithm.And the algorithm can get a reasonable path to avoid obstacles considering the size of the moving object,and smooth the result when the pedestrian is considered.