Flexible Paths: A Path Planning Approach to Dynamic Navigation
David Amores, Egemen Tanin, Maria Vasardani
Abstract
During navigation, people may deviate from an already planned path. Possible reasons include traffic congestion, difficulty in following instructions, or personal preferences, as evidenced by studies in human spatial cognition and transportation. Most path planning methods provide users with a single path, for example the shortest one, while a few give the user a set of paths to choose from. In the latter case, once a path from the given set is chosen, the rest are discarded. If the user were to deviate from the planned path, alternatives may not exist or may cause a significant delay to the user. Services such as Google Maps continuously monitor possible alternatives, but they may offer a path with no alternatives or few and lengthy ones. Taking a proactive approach to finding alternatives, we introduce the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">most flexible path</i> – a path that maximises the number of alternatives the user has along a given path. This way, users may choose to take a different path midway and be more likely to have alternative paths available to them. Straightforward approaches to obtaining such a path have a prohibitive computational complexity. We introduce a set of algorithms that yield exact and approximate solutions to this problem. We then showcase the most flexible path’s time-saving reroutes in a traffic congestion scenario.