A novel path planning to provide real-time backup paths for vehicle navigation systems

The rapid progress of wireless technologies has made the information of real-time traffic available to vehicles. In this paper, the authors propose a dynamic path planning algorithm for vehicle navigation system which can adapt to changeable traffic and replan a better path with good travelling time for drivers within a reasonable computation time for large-scale road networks. Based on the hierarchical model of road networks, we use source-directed A* to save the path planning time, to create a good travelling time path, and to construct a backup path tree. When a traffic condition of a link in the driving path becomes worse, the replanning of a new partial path for a certain part of the backup path tree reflected by the link is calculated. The system has been tested on Taiwan road network. Through experiment results, the system presents a good efficiency for planning/replanning a path in terms of planning time and travelling time.