• 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 ICAPS-23 Workshop on Reliable Data-Driven Planning and Scheduling (RDDPS), 2023. An improved version
appears in the European Conference on Artificial Intelligence (ECAI) 2023
(unavailable)
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{rddp23,
title = {A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates},
booktitle = {Proceedings of the ICAPS-23 Workshop on Reliable Data-Driven Planning and Scheduling ({RDDPS})},
year = {2023},
author = {Eyal Weiss and Ariel Felner and Gal A. Kaminka},
wwwnote = {},
note = {An improved version appears in the European Conference on Artificial Intelligence ({ECAI}) 2023},
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 Apr 19, 2024 19:01:33