ECAI 2004 Conference Paper

[full paper]

Variants of A* for Planning

Minh Tang, Amol Mali

Significant advances have occurred in plan synthesis in the last nine years. Many of the recently developed efficient planners use a variation of A* search algorithm called weighted A*. In this paper we report on three sound and complete classical planners AWA*-PD, AWA*-AC and AWA*-AC-LE. AWA*-AC is adjusted weighted A* with action conflict-based adjustment. AWA*-PD is adjusted weighted A* with deleted preconditions-based adjustment. AWA*-AC-LE is a variant of AWA*-AC which performs lazy evaluation (LE). The novel ideas in these planners are (i) node-dependent weighting for g(n) and h(n) terms in the path cost equation of A*, (ii) conditional two-phase heuristic evaluation, and (iii) lazy heuristic evaluation which does not construct relaxed plans to compute heuristic values for all nodes. We report on an empirical evaluation of the planners on several challenging new domains containing dead ends. We also report on an empirical comparison of the planners with planners HSP-2 and FF. The variants of A* solve several problems from these domains faster than HSP-2 and FF.

Keywords: Planning

Citation: Minh Tang, Amol Mali: Variants of A* for Planning. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.1095-1096.