•
Sorted by Date •
Classified by Publication Type •
Classified by Topic •
Grouped by Student (current) •
Grouped by Former Students •

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

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.

### Download

[PDF]328.7kB

### 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.

### Additional Information

### BibTeX

@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
Thu Feb 22, 2024 11:36:58