Reliable Optimal Path for Pedestrian Navigation

Pedestrians are not constrained by road networks (for example, lanes, turn restrictions, one-way streets), unlike vehicle drivers. An optimal route for pedestrians might involve many intersections that are difficult to navigate, because they offer more than one alternative to turn left or right or go ahead. This makes it much easier for pedestrians to lose their way, even having turn-by turn-direction assistance. After analyzing related work on the problem, we find there are two aspects that need to be improved. One is that current solutions have high computational time complexity (most of them are O (|V|⁴). The other is that the turn weight/turn unreliability models are either inaccurate or unreasonable. We propose a general solution to both of the aspects to provide a more reliable optimal route for pedestrians. The first part of the solution presents a reliable path algorithm that minimizes the number of complex intersections with turn ambiguities between two locations along a path by giving an improved burning algorithm with its own definition of intersection weight standard. The improved algorithm reduces the regular computational time complexity of the reliable optimal route to O (|V|). The second part of the solution focuses on improving the accuracy of the turn unreliability function by building an improved model based on information entropy. Both parts of the solution can be implemented separately or altogether. Examples are given to demonstrate the solution, and they show that the solution is feasible for better pedestrian navigation services with a more reliable optimal path.