FAILURE DRIVEN DYNAMIC SEARCH CONTROL FOR PARTIAL ORDER PLANNERS - ANEXPLANATION-BASED APPROACH

Given the intractability of domain independent planning, the ability t o control the search of a planner is vitally important. One way of doi ng this involves learning from search failures. This paper describes S NLP + EBL, the first implementation of an explanation based search con trol rule learning framework for a partial order (plan-space) planner. We will start by describing the basic learning framework of SNLP + EB L. We will then concentrate on SNLP + EBL's ability to learn from fail ures, and describe the results of empirical studies which demonstrate the effectiveness of the search control rules SNLP + EBL learns using our method. We then demonstrate the generality of our learning methodo logy by extending it to UCPOP (Penberthy and Weld, 1992), a descendant of SNLP that allows for more expressive domain theories. The resultin g system, UCPOP + EBL, is used to analyze and understand the factors i nfluencing the effectiveness of EBL. Specifically, we analyze the effe ct of (i) expressive action representations, (ii) domain specific fail ure theories and (iii) sophisticated backtracking strategies on the ut ility of EBL. Through empirical studies, we demonstrate that expressiv e action representations allow for more explicit domain representation s which in turn increase the ability of EBL to learn from analytical f ailures, and obviate the need for domain specific failure theories. We also explore the strong affinity between dependency directed backtrac king and EBL in planning.