Gal A. Kaminka: Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped 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 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

Download

(unavailable)

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{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 Aug 30, 2024 17:29:52