A Research On Path Planning Algorithm Based On Strokes

The efficiency of the path planning function needs to be improved in vehicle navigation equipments to adapt to the complex,especially the ultra-large-scale road network.According to the study on the habits of choosing the path in human bings,found that people prefer the path with less turns,even if the path is more remote but can be acceptted.So this thesis focus on 1)improving the efficiency of path planning,2)reducing the number of turns in the path,balance in the path length and the number of turns.The concept ‘stroke' is a natural road in the road network.There are less elements in the road topology constructed by the strokes.Therefore,the path planning algorithm based on road topology constructed by strokes is more efficient.The planned path constructed by strokes or part of strokes,so the path has fewer turns.Based on the analysis above,the main study in this thesis includes 1)building the topology based on strokes,2)designing path planning algorithms for stroke topology.This thesis takes the static road network as the application secene to complete the following two pasts.In the first part,an algorithm on construct road topology based on strokes and a storage structure of road topology based on the stroke are proposed.The second part is the path planning algorithm based on the stroke.Firstly,a heuristic path planning algorithm based on the stroke is proposed,which is more efficient than traditional A-Star algorithm.The algorithm reduce the number of turns and make the increasement of path length in a reasonable range.Secondly,two kinds of stroke-based breadth-first path planning algorithms are proposed that ensure the path has the fewest turns.One algorithm is a bi-directional breadth-first path planning algorithm based on the stroke,which can efficiently find the path with the fewest turns.The other algorithm is the shortest path planning algorithm based on the optimal number of turns,which can find the shortest one in the paths with the fewest turns.