A proactive route planning approach to navigation errors

摘要

Online navigation systems assume a person can follow a given route from origin to destination. Nonetheless, spatial cognition studies show that wayfinding is a complex, highly adaptive process and that route planning is incremental rather than prescriptive. Indeed, people may deviate from their originally chosen route for a number of reasons including navigation errors, especially when the environment is unfamiliar. Even in familiar places, certainty in wayfinding is highly unlikely to be completely achieved. Consequently, when people make a wrong turn or miss an exit, even the best reroute to the destination may add several minutes to the originally planned travel time. This work formally defines the novel problem of finding a path such that, when navigation errors occur, recovering is not as costly. We call this approach themost recoverable path. This subtle change in the route planning problem - i.e., considering error recovery costs - invalidates using dynamic programming, such as in shortest path algorithm solutions. We therefore introduce a novel, readily applicable, fast heuristic to this NP-hard problem. The benefits of the most recoverable path are manifold: long detours are avoided, actual travel time is reduced, and it is comparable to its shortest counterpart in terms of length.