A Heuristic for Planning based on Action Evaluation

D. Vrakas, I. Vlahavas, “A Heuristic for Planning based on Action Evaluation”, Proc. 10th International Conference on Artificial Intelligence: Methodology, Systems, Applications (AIMSA '02), Springer-Verlag, LNAI 2443, pp. 61-70, 2002.

Proc. 10th International Conference on Artificial Intelligence: Methodology, Systems, Applications (AIMSA '02), Springer-Verlag, LNAI 2443, pp. 61-70, 2002.

This paper proposes a domain independent heuristic for state space planning, which is based on action evaluation. The heuristic obtains estimates for the cost of applying each action of the domain by performing a forward search in a relaxed version of the initial problem. The estimates for the actions are then utilized in a backward search on the original problem. The heuristic, which has been further refined by a goal-ordering technique, has been implemented in AcE (Action Evaluation), a state space heuristic planner, and thoroughly tested on a variety of toy problems.