Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Weighted A* search - unifying view and application
 
research article

Weighted A* search - unifying view and application

Ebendt, Ruediger
•
Drechsler, Rolf
2009
Artificial Intelligence

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. With 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 epsilon > 0. this bound is (1 + epsilon) (left perpendicularN/2right perpendicular) where N is an upper bound on an optimal solution length.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.artint.2009.06.004
Author(s)
Ebendt, Ruediger
Drechsler, Rolf
Date Issued

2009

Published in
Artificial Intelligence
Volume

173

Start page

1310

End page

1342

Subjects

Planning

•

Search

•

Heuristic search

•

A*

•

Weighted A*

•

Bdd

•

Strips

•

Binary Decision Diagrams

•

Exact Bdd Minimization

•

Heuristic-Search

•

Best-1St Search

•

Algorithm

•

Obdds

•

Graphs

•

DLR

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
NEARCTIS
Available on Infoscience
November 24, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/58284
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés