Abstract
This disclosure describes techniques to determine a diversity of navigational routes in a digital map application, inspired by electrical circuit simulators. The graph of the road (or transport) network is modeled as a linear electrical circuit whose edges’ (roads’) costs are replaced by conductances with values proportional to the capacity of the road. A simulated voltage is applied between the source and the destination, and the resulting current flow (decomposition) is determined using linear algebra techniques. The current decomposition represents possible navigational routes. The electrical circuit is recursively represented at multiple levels of granularity, such that current flow simulation and decomposition results in a further diversity of routes. For example, an initial route can be computed between waypoints at a low granularity, and diverse routes can be computed between pairs of waypoints at a high granularity. Compared to conventional graph-theoretic, path-searching techniques for alternative-route generation, the described techniques produce substantially larger numbers of diverse alternative routes with low latency.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Recommended Citation
Manifold, Allison and Sinop, Ali, "Generating Navigational Routes Using Techniques of Electrical Flow Computation", Technical Disclosure Commons, (August 30, 2024)
https://www.tdcommons.org/dpubs_series/7317