Cost-Algebraic Heuristic Search

Stefan Edelkamp; Shahid Jabbar; Alberto Lluch Lafuente

Cost-Algebraic Heuristic Search

Stefan Edelkamp, Shahid Jabbar, Alberto Lluch Lafuente

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language	English
Title of host publication	AAAI-05, Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference
Publisher	AAAI Press / The MIT Press
Publication date	2005
Pages	1362-1367
Article number	AAAI-05 / 1362
ISBN (Print)	1-57735-236-X
Publication status	Published - 2005
Externally published	Yes
Event	20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference - Pittsburgh, United States Duration: 9 Jul 2005 → 13 Jul 2005

Conference

Conference	20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference
Country/Territory	United States
City	Pittsburgh
Period	09/07/2005 → 13/07/2005

OpenUrl availability

Full text

Cite this

@inproceedings{5d6da572381f49bc879011459317cc35,

title = "Cost-Algebraic Heuristic Search",

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.",

author = "Stefan Edelkamp and Shahid Jabbar and {Lluch Lafuente}, Alberto",

year = "2005",

language = "English",

isbn = "1-57735-236-X",

pages = "1362--1367",

booktitle = "AAAI-05, Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference",

publisher = "AAAI Press / The MIT Press",

note = "20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference ; Conference date: 09-07-2005 Through 13-07-2005",

}

Edelkamp, S, Jabbar, S & Lluch Lafuente, A 2005, Cost-Algebraic Heuristic Search. in AAAI-05, Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference., AAAI-05 / 1362, AAAI Press / The MIT Press, pp. 1362-1367, 20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference, Pittsburgh, Pennsylvania, United States, 09/07/2005.

Cost-Algebraic Heuristic Search. / Edelkamp, Stefan; Jabbar, Shahid; Lluch Lafuente, Alberto.
AAAI-05, Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference. AAAI Press / The MIT Press, 2005. p. 1362-1367 AAAI-05 / 1362.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Cost-Algebraic Heuristic Search

AU - Edelkamp, Stefan

AU - Jabbar, Shahid

AU - Lluch Lafuente, Alberto

PY - 2005

Y1 - 2005

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

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

M3 - Article in proceedings

SN - 1-57735-236-X

SP - 1362

EP - 1367

BT - AAAI-05, Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference

PB - AAAI Press / The MIT Press

T2 - 20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference

Y2 - 9 July 2005 through 13 July 2005

ER -

Cost-Algebraic Heuristic Search

Abstract

Conference

OpenUrl availability

Fingerprint

Cite this