Experimentation-driven knowledge acquisition for planning

Knowledge engineering for planning is expensive and the resulting knowledge can be imperfect. To autonomously learn a plan operator definition from en vironmental feedback, our learning system WISER explores an instantiated li teral space using a breadth-first search technique. Each node of the search tree represents a state, a unique subset of the instantiated literal space . A state at the root node is called a seed state. WISER can generate seed states with or without utilizing imperfect expert knowledge. WISER experime nts with an operator at each node. The positive state, in which an operator can be successfully executed, constitutes initial preconditions of an oper ator. We analyze the number of required experiments as a function of the nu mber of missing preconditions in a seed state. We introduce a naive domain assumption to test only a subset of the exponential state space. Since brea dth-first search is expensive, WISER introduces two search techniques to re order literals at each level of the search tree. We demonstrate performance improvement using the naive domain assumption and literal-ordering heurist ics. To learn the effects of an operator, WISER computes the delta state, c omposed of the add list and the delete list, and parameterizes it. Unlike p revious systems, WISER can handle unbound objects in the delta state. We sh ow that machine-generated effects definitions are often simpler in represen tation than expert-provided definitions.