Technological Research On Path Planning In Vehicle Navigation System

Path planning algorithm is the core function and key technology for the vehicle navigation system (VNS). The research and application of the algorithm are important parts in the intelligence transportation system (ITS). The path planning algorithm in the application of embedded systems is widely used with the increasing of the private car ownership in China. But for resource limitation of the embedded system and large road networks, it has some problems,such as running slowly, the unreasonable result and re-guide tardy.This thesis aims at above problems. At first we study the NDS standard, one of the road networks data model, explain how to split the data to blocks and explore the inherent hierarchical structure of road networks. Then take a look at the shortest path algorithms which are widely used in navigation, and also study several kinds of widespread and extensible algorithms based on the Dijkstra algorithms. On the basis of above theories, we propose a new bidirectional heuristic algorithm which searches in a hierarchical way. In fact, the new algorithm not only visits (or settles) the links in base level meshes, but also visits the nodes among the base level meshes and the national meshes, which mixes all three patterns in one Priority Queue. By using this new idea, we solve the problems of running slowly in embedded systems, getting unreasonable results occasionally, and the shortest path question with turn prohibitions. In addition, this algorithm also reduces the computing complexity of re-guiding.At the end, this thesis discusses mainly about a realworld application on the path planning techniques ---"Anyway vehicle navigation system". The construction of the system needs the requirement analysis of the path planning module, the interface definition and the design/implementation process. Our main idea of the application consists of the link filter, the shortest path searching and the route making, which depends on the specialization of the designing purpose, the algorithm and the program flowchart. Actual measurement is carried out on the path planning module, which supports that the new algorithm is realizable, highly effective, and satisfactory for the embedded applications.