×

The downward refinement property. (English) Zbl 0747.68063

Artificial intelligence, IJCAI-91, Proc. 12th Int. Conf., Sydney/Australia 1991, 286-292 (1991).
[For the entire collection see Zbl 0741.68016.]
The paper is a new step towards understanding abstract problem-solving in general. It is known that having a good abstraction hierarchy, the average time complexity of planning search can be reduced from exponential to linear. However, abstraction in planning does not guarantee by itself an improvement in search efficiency. The authors’ analysis and experiments proved that good abstraction hierarchies have, or are close to having, the downward refinement property (DRP). It states that if a non-abstract, concrete level solution to the planning problem exists, then any abstract solution can be refined to a concrete solution without backtracking across abstraction levels. In other words, once a solution is found at the abstract level it need never be reconsidered, just refined. The paper provide a semantics for ABSTRIPS-style abstraction, using it to give a definition of the DRP. The DRP effect on search efficiency is examined, a general semantic condition that is sufficient to ensure the DRP is given, and a number of syntactic conditions that are sufficient to guarantee the DRP presence is derived. It can be demonstrated that these conditions can be checked in polynomial time, allowing a specification of a domain hierarchy to be checked quickly for the DRP.
Reviewer: N.Curteanu (Iaşi)

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68P10 Searching and sorting

Citations:

Zbl 0741.68016
PDFBibTeX XMLCite