A new result on the complexity of heuristic estimates for the A★ algorithm

✍ Scribed by Othar Hansson; Andrew Mayer; Marco Valtorta

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 736 KB
• Volume: 55
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(92)90045-y

✦ Synopsis

Hansson, O., A. Mayer and M. Valtorta, A new result on the complexity of heuristic estimates for the A * algorithm, Artificial Intelligence 55 (1992) 129-143.

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