elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

Weighted A* Search - Unifying View and Application

Ebendt, Rüdiger und Drechsler, Rolf (2009) Weighted A* Search - Unifying View and Application. Artificial Intelligence, 173 (14), Seiten 1310-1342. Elsevier. doi: 10.1016/j.artint.2009.06.004. ISSN 0004-3702.

[img] PDF - Nur DLR-intern zugänglich
748kB

Offizielle URL: http://dx.doi.org/10.1016/j.artint.2009.06.004

Kurzfassung

The A* algorithm is a well-known heuristic best-first search method. Several performance-accelerated extensions of the exact A* approach are known. Interesting examples are approximate algorithms where the heuristic function used is inflated by a weight (often referred to as weighted A*). These methods guarantee a bounded suboptimality. As a technical contribution, this paper presents the previous results related to weighted A* from authors like Pohl, Pearl, Kim, Likhachev and others in a more condensed and unifying form. By use of this unified view, a novel general bound on suboptimality of the result is derived: in the case of avoiding any reopening of expanded states, for �µ>0, this bound is (1+�µ)^â��N/2â�� where N is (an upper bound on) the maximum depth of the search. Binary Decision Diagrams (BDDs) are well-known to AI, e.g. from set-based exploration of sparse-memory and symbolic manipulation of state spaces. The problem of exact or approximate BDD minimization is introduced as a possible new challenge for heuristic search. Like many classical AI domains, this problem is motivated by real-world applications. Several variants of weighted A* search are applied to problems of BDD minimization and the more classical domains like blockworlds and sliding-tile puzzles. For BDD minimization, the comparison of the evaluated methods also includes previous heuristic and simulation-based methods such as Rudell's hill-climbing based sifting algorithm, Simulated Annealing and Evolutionary Algorithms. A discussion of the results obtained in the different problem domains gives our experiences with weighted A*, which is of value for the AI practitioner.

elib-URL des Eintrags:https://elib.dlr.de/59485/
Dokumentart:Zeitschriftenbeitrag
Zusätzliche Informationen:Eine Kopie der Arbeit im PDF-Format kann per Email an Ruediger.Ebendt@dlr.de angefordert werden. A copy of the paper (PDF) can be requested by email to Ruediger.Ebendt@dlr.de.
Titel:Weighted A* Search - Unifying View and Application
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Ebendt, RüdigerNICHT SPEZIFIZIERTNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Drechsler, RolfUniversität BremenNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:August 2009
Erschienen in:Artificial Intelligence
Referierte Publikation:Ja
Open Access:Nein
Gold Open Access:Nein
In SCOPUS:Ja
In ISI Web of Science:Ja
Band:173
DOI:10.1016/j.artint.2009.06.004
Seitenbereich:Seiten 1310-1342
Verlag:Elsevier
ISSN:0004-3702
Status:veröffentlicht
Stichwörter:Shortest-Path, Dijkstra, A*, heuristic search
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Verkehr
HGF - Programmthema:Verkehrssystem
DLR - Schwerpunkt:Verkehr
DLR - Forschungsgebiet:V VS - Verkehrssystem
DLR - Teilgebiet (Projekt, Vorhaben):V - Mittel- und langfristige Entwicklung der Personenverkehrsnachfrage (alt)
Standort: Berlin-Adlershof
Institute & Einrichtungen:Institut für Verkehrssystemtechnik > Verkehrsmanagement
Hinterlegt von: Ebendt, Dr.rer.nat. Rüdiger
Hinterlegt am:17 Aug 2009 14:31
Letzte Änderung:06 Sep 2019 15:17

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.