Dynamic Real-time Navigation Research Based On Region Partitioning Strategy

With the complexity of urban traffic and number of vehicles surge dramatically,it is causing serious traffic congestion. Hence, vehicle navigation systems arebecoming increasingly important. Research on navigation algorithms for vehicles isindeed a popular topic world-wide. Vehicle navigation systems can be largelycategorized into static and dynamic route navigating approaches. Static routenavigation takes no significance of the real-time traffic conditions, while dynamicroute guidance does, and it would be the main research context in this work. A majorchallenge with dynamic route guidance is the requirement to constantly process alarge volume of real-time data, how to appropriately reduce the volume of data inputfor an algorithm is thus a critical problem that needs solving.The main topics covered by this thesis are explained in the following points.Firstly, this work requires the construction of an urban traffic network model. Thetraffic network model is established based on level division strategy, which can freelysupport to what level of details should the traffic conditions be analyzed. Secondly,according to historical statistics of different time periods and traffic signalinformation, this work analyzed the corresponding traffic conditions and their effectson vehicle navigation, and hence deduce better navigation results at the globallyoptimized level. Finally, detail analysis of nearby area can ensure that vehicle isavoiding congestions and always actively search for the optimal path in thecorresponding local area. This approach ensures that only nearby traffic conditioninformation is analyzed, and thus greatly reducing the costs on calculating andmemory resources.In this way, it has an advantage over global analysis, which is hindered bycomputing a large number of data including nodes and traffic information. Hence, forregional analysis, optimal routes can be supplied to vehicle drivers in time. Applyingthe region partitioning strategy to reduce the number of nodes in the search space andreduce the volume of traffic conditions is the key merit of this study. This maincontribution also means more factors can be considered simultaneously to ensureroutes suggested by the algorithm is better customized for the actual traffic condition. This work simulates a RSU (Road Side Unit) based traffic communicationnetwork topology. RSUs are used to collect traffic signals and nearby vehicleinformation. When the vehicle reaches RSU coverage, information is collated todetermine the actual traffic condition on the corresponding intersection, thisinformation is feed to the navigation system, and taken into account whiledetermining the optimal routes. The system is implemented on the Android platform,and Baidu maps API is used for obtaining the maps required.