# Tightest Admissible Shortest Path

arXiv: https://arxiv.org/abs/2308.08453 · HTML: https://mlsanity.com/paper/2308.08453/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 29 references that are in the map.
- First posted on arXiv 15 Aug 2023.

## Builds on (most cited first, 4 of 4)

- [Generalized Lazy Search for Robot Motion Planning: Interleaving Search and Edge Evaluation via Event-based Toggles](https://mlsanity.com/paper/1904.02795/) (2019)
- [A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors](https://mlsanity.com/paper/1603.03490/) (2016)
- [Lazy Receding Horizon A* for Efficient Path Planning in Graphs with Expensive-to-Evaluate Edges](https://mlsanity.com/paper/1803.04998/) (2018)
- [A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates](https://mlsanity.com/paper/2208.11489/) (2022)

## Abstract (arXiv)

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.