Bi-Directional Heuristic Planning in State-Spaces

D. Vrakas, I. Vlahavas, “Bi-Directional Heuristic Planning in State-Spaces”, Proc. 8th Panhellenic Conference on Informatics, Vol. 1, pp. 511-520, 2001.

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 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 step. 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 bi-directional planning system, named BP, was tested on a variety of problems adopted from the recent AIPS-00 planning competition with quite promising results.