Research On Key Technology Of Embedded Navigation Path Planning In Complex Environments

With the development of GPS, the vehicle navigation system has been widely used. As one of the key technologies in the vehicle navigation system, path planning has become a hot topic in the field of road traffic, the path planning based on the two-dimensional topology of road network has been widely used in car satellite navigation system. However, with the use of Beidou navigation satellite system, vehicles for military use and special vehicles may not only advance in wilderness without road, but also face the complex factors, such as weather, electromagnetic, roadblocks, trend information and real- time traffic information of various path planning. The effective path planning in such a complex environment becomes one of the difficulties in the current research in this field. Aiming at the application scene, this paper deeply analyzes relevant issues of two different environments based on network topology and the terrain modeling. And deeply study on the network data model, the weight distribution of dynamic traffic information, the terrain modeling and the problem of path search algorithm. The main work and achievements include:1. Proposes a multi-scale road network data model designed for dynamic navigation. According to the demand of navigation data content and scale of different tasks and the characteristic of slow storage speed of electronic disk, the display data and topology data for path planning were stratified into blocks. The display data and static road network data are stored in external storage of electronic hard disk, while the dynamic traffic information is stored in memory or an external database. Besides, linking relationships between dynamic traffic information and static road network is established. The model can not only reduce redundant data storage, it can also read different levels of sub-regional road network data according to the road grade features with a wide range of route planning to effectively reduce the amount of data path calculation. In this case, the dynamic traffic information can be effectively expressed and it provides a foundation for the realization of dynamic path planning.2. Investigates the path-planning algorithm based on multi- weight assignment for dynamic traffic information. Aiming at the problem that the path-planning is influenced by dynamic traffic information in the urban road network, the thesis includes a path planning method of dynamic traffic information weight distribution based on Fuzzy Rough sets. First of all, the dissertatio n establishes dynamic programming model, regarding travel time and traffic safety as the standard of the optimized path planning. Secondly, the method considers travel time factor and traffic safety factor separately, and generates attribute decision tables sooner after the two factors would be classified and quantized. The proposal adopts appropriate membership functions to compute the dependency between each attributes and planning principles, hence it determines the weight of each factors affecting. Fina lly, adopting stratified A* path planning algorithm, the method searches for optimized path in the domain of urban road network which is overlaid with dynamic traffic information. The simulation results demonstrate that the method can carry out path planning more reasonably for dynamic traffic information based road network in the precise of guaranteeing the real-time of the algorithm.3. Analyzes how to conduct path planning for vehicles running in the area where no path covered. Due to the particularity of tasks performed by certain special vehicles, actual terrain based path planning under off-road conditions needs to be considered. After getting into deep analysis of path planning algorithm under actual off-road conditions, the author puts forward path planning based on elevation-quadtree model and improved ant colony algorithm. The proposal divides actual off-road terrain in the basement of elevation difference, complying with quadtree partition principles, and cut down the amount of data largely while geographic information is fully stored. At the same time, the proposal improves storage efficiency and lower the number of calculations during the path planning process. O n the constructed model, the proposal analyzes terrain. To enable heuristic function in the Ant colony algorithm more accurate and effective, the author comes up with a new heuristic function representation comprehensively considering the distance, slope, roughness and other information, and optimize speed of pheromones update by adjusting volatilization factor adaptively. The experiment showed, contrasted with former algorithm, the proposal enhance the accuracy of path planning, accelerate the convergence rate, and effectively avoid precocity of algorithm.4. Synthesizing all the researches above, this chapter sets up an application frame of the embedded vehicle navigation system, and builds simulation development environment on Windows platform. Take certain city’s navigation road network data for example, the author construct multi-scale road network model adopting Map Info, then program the conversion process of road network format and path planning algorithm using VC++. The author design the data format conversion software to realize the conversion of multi-source road network data and elevation data. The proposal fulfills the implementation of path planning algorithm under the complicated environment, employs it into the embedded vehicle navigation system on the WinCE platform, and verifies the availability of the system.