A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates (Student Abstract)

Authors

  • Eyal Weiss Bar-Ilan University

DOI:

https://doi.org/10.1609/socs.v16i1.27316

Keywords:

Foundations Of Search & Optimization, Combinatorial Search With Uncertainty, Shortest Path

Abstract

The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. In this paper 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 a generalized shortest path problem that optimizes different aspects of path cost and its uncertainty. We describe in high-level a complete anytime algorithm for the generalized problem and discuss possible future extensions.

Downloads

Published

2023-07-02