A proactive route planning approach to navigation errors

ABSTRACT

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 the most 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.

KEYWORDS:

• Route planning
• navigation errors
• uncertainty
• spatial databases

Data and code availability statement

The code that supports the findings of this study is available at https://doi.org/10.6084/m9.figshare.12018201. The link also contains the database dump that is used for running the simulations. This Postgres database contains city network information. The scripts generate the data shown in Section 5 and are run as explained in its README file.

Data acknowledgements

Map data copyrighted OpenStreetMap contributors and available from https://www.openstreetmap.org.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

David Amores

David Amores is a PhD student at the University of Melbourne. He obtained a Master of Information Technology from the University of Melbourne in 2016. His research interests are spatial algorithms and location-based services, especially those that intercede with spatial cognition findings.

Egemen Tanin

Prof Tanin has finished his PhD at the University of Maryland at College Park before joining the University of Melbourne in 2003. His areas of interest are Spatial Databases and Mobile Data Management. He is an Associate Editor of ACM TSAS and served as a PC Chair for ACM SIGSPATIAL in 2011 and 2012. He was elected to serve as the Treasurer for ACM SIGSPATIAL and served in this role till 2017. Dr Tanin was also elected to be the Secretary of the SIG from 2017 till 2020 and recently re-elected to be the next Vice-Chair. Dr Tanin is also the co-founder of ACM SIGSPATIAL Australia as well as the founding editor for ACM SIGSPATIAL Special.

Maria Vasardani

Dr Maria Vasardani finished her PhD at the University of Maine prior to joining Dalhousie University in Canada, and then The University of Melbourne in 2011. Since late 2018 she is now member of the Geospatial Sciences staff group in RMIT University, as well as a Vice-Chancellor Research Fellow. She is currently serving as Chair of the ACM SIGSPATIAL Chapter in Australia for a second consecutive year. Her interests are in spatial information representation and reasoning, as well as spatial HCI.