cicyt UNIZAR
Full-text links:

Download:

Current browse context:

cs.AI

Change to browse by:

cs

References & Citations

DBLP - CS Bibliography

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo ScienceWISE logo

Computer Science > Artificial Intelligence

Title: A New Result on the Complexity of Heuristic Estimates for the A* Algorithm

Abstract: Relaxed models are abstract problem descriptions generated by ignoring constraints that are present in base-level problems. They play an important role in planning and search algorithms, as it has been shown that the length of an optimal solution to a relaxed model yields a monotone heuristic for an A? search of a base-level problem. Optimal solutions to a relaxed model may be computed algorithmically or by search in a further relaxed model, leading to a search that explores a hierarchy of relaxed models. In this paper, we review the traditional definition of problem relaxation and show that searching in the abstraction hierarchy created by problem relaxation will not reduce the computational effort required to find optimal solutions to the base- level problem, unless the relaxed problem found in the hierarchy can be transformed by some optimization (e.g., subproblem factoring). Specifically, we prove that any A* search of the base-level using a heuristic h2 will largely dominate an A* search of the base-level using a heuristic h1, if h1 must be computed by an A* search of the relaxed model using h2.
Subjects: Artificial Intelligence (cs.AI)
Journal reference: Artificial Intelligence, 55, 1 (May 1992), 129-143
Cite as: arXiv:1803.06422 [cs.AI]
  (or arXiv:1803.06422v1 [cs.AI] for this version)

Submission history

From: Marco Valtorta [view email]
[v1] Fri, 16 Mar 2018 22:57:32 GMT (22kb)