Cost-Algebraic Heuristic Search

Stefan Edelkamp, Shahid Jabbar, Alberto Lluch Lafuente

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Heuristic search is used to efficiently solve the single-node
shortest path problem in weighted graphs. In practice, however,
one is not only interested in finding a short path, but
an optimal path, according to a certain cost notion. We propose
an algebraic formalism that captures many cost notions,
like typical Quality of Service attributes. We thus generalize
A*, the popular heuristic search algorithm, for solving
optimal-path problem. The paper provides an answer to a
fundamental question for AI search, namely to which general
notion of cost, heuristic search algorithms can be applied. We
proof correctness of the algorithms and provide experimental
results that validate the feasibility of the approach.
Original languageEnglish
Title of host publicationAAAI-05, Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference
PublisherAAAI Press / The MIT Press
Publication date2005
Pages1362-1367
Article numberAAAI-05 / 1362
ISBN (Print)1-57735-236-X
Publication statusPublished - 2005
Externally publishedYes
Event20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference - Pittsburgh, PA, United States
Duration: 9 Jul 200513 Jul 2005

Conference

Conference20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference
CountryUnited States
CityPittsburgh, PA
Period09/07/200513/07/2005

Fingerprint Dive into the research topics of 'Cost-Algebraic Heuristic Search'. Together they form a unique fingerprint.

Cite this