On The Optimal Path Planning In Vehicle Navigation System

With the developing of economy and the extensive popularization of vehicle, the phenomenon of jam traffic become serious. It makes people's travel discommodity and blocks the development of society economy. To resolve this problem, the Intelligent Transportation System (ITS) was brought forward by some experts. It has been realized by some different modes. What is called ITS is an integrated and omnidirectional traffic system that unite the satellite, the control center of ground, the measure device of crossing, the computer in the car , the control system of the roads and so on. Recent years, the ITS in China developed quickly, but some technical problems haven't been resolved. Experimental unit is local, application hasn't been cosmically.The Navigation of vehicle is an important subsystem of ITS. The main function contains the orientation of the car; map matching, path planning and traffic guide. Path planning is the key technology, the quality of the system is based on the optimization and the real-time of planned path .The relation technologies contain the storage of the data of map, static path planning, the gather and disposal of the real-time information of traffic, dynamic path planning and so on.The storage of digital map, designing the arithmetic static path planning and compare with the performance of different arithmetic, the path planning of single vehicle and the path planning of multi vehicle are researched in this paper. The main content will be introduced as follows:1. The storage of digital map. First of all, construct the mathematical model to describe the road net; based on the map theory of computer, disport the map into node class and road class., stored in neighboring matrix and neighboring list, discuss the complexity of the two structures. Add a turning class in neighboring list to describe the limited turning for the crossing. To multi layers map, stored the data in the different layer, and construct the relevancy with different layer. To big map, partition the map into grid or administration area, loaded dynamically. 2. Arithmetic of static path planning. Firstly, The Arithmetic of static path planning in common use are described, the complexity and applicability are compared and discussed. Bidirectional search and layered search as improved strategies are adopted. The improvement of the Arithmetic is analyzed; Fit together the different storage strict of the map and the different arithmetic of path planning, compare the result and the cost of search in the experiment, analyze the warp between theory and experiment, and get the reason. Finally, the conclusion can be gotten: if the map is a single layer map, the map should be stored in the neighboring list, the arithmetic should be A star; if the map is multi layers map, when the distance between start node and the destination node is near, the arithmetic should be A star arithmetic, when the distance between start node and the destination node is far, the arithmetic should be layered search based on A star arithmetic should be adopted.3. Dynamic path planning of single vehicle. Firstly, analyzing which arithmetic of path planning should be adopted for different type of navigation system. Construct the mathematical model of single vehicle path planning. To advance the real time performance of the planned path, the traffic information of real time should be use in the dynamic path planning. Based on the place and the time of path planning, single vehicle dynamic path planning can be divided into single vehicle dynamic path planning based on node and single vehicle dynamic path planning based on some period. The target functions of the arithmetic are brought out, and then the resolutions of the model are given. The arithmetic is designed, the flow charts of the arithmetic are drawn, and the complexities of arithmetic are analyzed. The result of the experiment indicates that the real time performance of optimization is advanced in evidence, prove the arithmetic can effectively dodge the jam road and the road happen accident. Finally, the advantage and disadvantage are evaluated; the way of improvement is discussed.4. Dynamic path planning of Multi vehicle. Firstly, analyze the different between the path planning of single vehicle and path planning of multi vehicle. Then construct the model based on the model suppose.,give the resolve of the model. Arithmetic is designed, the flow chart is drawn, and the method of calculating the period is given. The experiment proves the arithmetic can effectively plan the path steering clear of the jam road and street no entry. At the target function of user optimization, compare the arithmetic of multi vehicle with the arithmetic of single vehicle, the conclusion can be gotten: the arithmetic of multi vehicle can decrease the number of jam road, reduce the average cost of the travel. Considering the system optimization, mending the target function, accommodate the proportion of the user optimization and the system optimization, the number of jam road can be less, but the cost of travel will be increase. In actual system, the proportion should be accommodated as the traffic information.From the research of this paper and the experiments, getting the conclusion: To independent navigation system without any traffic information, the A star arithmetic and the layered search based on A star arithmetic matching different type of map. To independent navigation system that can get the real time traffic information, the dynamic path planning arithmetic of single vehicle is researched, this arithmetic make sure that the vehicle is on the road of optimization real time, steer clear of the jam roads. To centre-decided navigation system, dynamic path planning arithmetic of multi vehicle is researched; accommodate the target function with user optimization and system optimization, realize the effective control of the number of jam roads and the average cost of travel.