• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Eyal Weiss, Ariel Felner, and
Gal A. Kaminka. A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates. In
Proceedings of the European Conference on Artificial Intelligence (ECAI), pp. 2607–2614, 2023.
An earlier
version was published at the RDDPS workshop at ICAPS 2023 conference.
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.
@inproceedings{ecai23,
author = {Eyal Weiss and Ariel Felner and Gal A. Kaminka},
title = {A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates},
booktitle = ECAI,
year = {2023},
pages= {2607--2614},
wwwnote = {An earlier version was published at the RDDPS workshop at ICAPS 2023 conference.},
abstract = { 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.
},
}
Generated by bib2html.pl (written by Patrick Riley ) on Fri Aug 30, 2024 17:29:51