[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publication: [PUBLink])

Refinement search is a stepwise narrowing process alternating between commitment and propagation. In each refinement, a subset of states (or plans) is chosen for further investigation until a solution is found. The choice of a subset is made by a commitment to a special plan property. Many potentially chosen but unsatisfactory states can be excluded from further investigation as a consequence of the commitment's decisions. This cutback is performed by propagation methods.

Traditionally, refinement techniques apply a complete search. Because of the infinite number of possible states/plans, completeness can only be achieved if the choice of an infinite subset presumes investigation parallel to the rest of the set, provided the rest is not already under investigation or definitely does not contain solutions. If an investigated finite set lacks a solution, another set has to be chosen (usually by backtracking). Furthermore, the union of all potentially investigated finite sets must include all solutions.

For refinement planning, logic programming with its unification and backtracking provides a very expressive framework. Many approaches, such as the language A [PUBLink] or the language E [PUBLink], make use of it.

Typical instances of refinement planning are total-order, partial-order and hierarchical planning. Other approaches use maximal plan structures to attain an improved propagation behavior.

• Total-Order Planning
• Partial-Order Planning
• Hierarchical Planning
• Refinement Using Maximal Graphs

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek