|
| Title: |
Combining Progression and Regression in State-Space Heuristic Planning |
| Author(s): |
D. Vrakas, I. Vlahavas.
|
| Availability: |
Click here to download the PDF (Acrobat Reader) file (12 pages).
|
| Keywords: |
|
| Appeared in: |
Proc. 6th European Conference on Planning (ECP '01), 2001.
|
| Abstract: |
One of the most promising trends in Domain Independent AI
Planning, nowadays, is state-space heuristic planning. The planners of this
category construct general but efficient heuristic functions, which are used as a
guide to traverse the state space either in a forward or in a backward direction.
Although specific problems may favor one or the other direction, there is no
clear evidence why any of them should be generally preferred.
This paper proposes a hybrid search strategy that combines search in both
directions. The search begins from the Initial State in a forward direction and
proceeds with a weighted A* search until no further improving states can be
found. At that point, the algorithm changes direction and starts regressing the
Goals trying to reach the best state found at the previous search. The direction
of the search may change several times before a solution can be found. Two
domain-independent heuristic functions based on ASP/HSP planners enhanced
with a Goal Ordering technique have been implemented. The whole bidirectional
planning system, named BP, was tested on a variety of problems
adopted from the recent AIPS-00 planning competition with quite promising
results. The paper also discusses the subject of domain analysis for state-space
planning and proposes two methods for the elimination of redundant
information from the problem definition and for the identification of
independent sub-problems. |
| See also : |
|
|
|
