Risk-averse autonomous route guidance by a constrained A* search

In this article, the authors propose an efficient algorithm for finding a risk-averse path for use in autonomous vehicle navigation systems. When no dynamic traffic information is available, a risk-averse path can be found by a constrained A* search. The accuracy of navigation on the basis of static network data is improved by taking travel-time uncertainty into account. When dynamic traffic information in the form of broadcast traffic messages is available, rerouting is achieved by a constrained A* search, which takes congestion propagation into account. By making use of information computed at the start of the trip, the authors propose a responsive version of the constrained A* search, which reduces the on-demand response time. An experimental performance analysis of the proposed methods on grid graphs demonstrates their efficiency.