Tightest Admissible Shortest Path


  • Eyal Weiss Bar-Ilan University
  • Ariel Felner Ben-Gurion University
  • Gal A. Kaminka Bar-Ilan University




The shortest path problem in graphs is fundamental to AI. Nearly all variants of the problem and relevant algorithms that solve them ignore edge-weight computation time and its common relation to weight uncertainty. This implies that taking these factors into consideration can potentially lead to a performance boost in relevant applications. Recently, a generalized framework for weighted directed graphs was suggested, where edge-weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. We build on this framework to introduce the problem of finding the tightest admissible shortest path (TASP); a path with the tightest suboptimality bound on the optimal cost. This is a generalization of the shortest path problem to bounded uncertainty, where edge-weight uncertainty can be traded for computational cost. We present a complete algorithm for solving TASP, with guarantees on solution quality. Empirical evaluation supports the effectiveness of this approach.




How to Cite

Weiss, E., Felner, A., & Kaminka, G. A. (2024). Tightest Admissible Shortest Path. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1), 643-652. https://doi.org/10.1609/icaps.v34i1.31527