A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
This work addresses a theoretical and practical limitation in AI applications where edge weight computation time is ignored, though it appears incremental as it builds on existing shortest path frameworks.
The paper tackles the shortest path problem in graphs by generalizing it to allow multiple edge-cost estimates with varying accuracy and computation time, and presents two complete algorithms that empirically demonstrate efficacy.
The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. We present a generalized framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. This raises several generalized variants of the shortest path problem. We introduce the problem of finding a path with the tightest lower-bound on the optimal cost. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy.