# A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 36 references that are in the map.
- First posted on arXiv 22 Aug 2022.

## 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)
- [Position Paper: Online Modeling for Offline Planning](https://mlsanity.com/paper/2206.03356/) (2022)

## Built on by (most cited first, 1 of 1)

- [Tightest Admissible Shortest Path](https://mlsanity.com/paper/2308.08453/) (2023)

## Abstract (arXiv)

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.