Premium
Experimentation‐Driven Knowledge Acquisition for Planning
Author(s) -
Tae Kang Soo,
Cook Diane J.,
Holder Lawrence B.
Publication year - 1999
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/0824-7935.00093
Subject(s) - computer science , operator (biology) , artificial intelligence , state (computer science) , incremental heuristic search , tree (set theory) , theoretical computer science , heuristics , node (physics) , state space , machine learning , search algorithm , beam search , algorithm , mathematics , mathematical analysis , biochemistry , chemistry , statistics , structural engineering , repressor , transcription factor , engineering , gene , operating system
Knowledge engineering for planning is expensive and the resulting knowledge can be imperfect. To autonomously learn a plan operator definition from environmental feedback, our learning system WISER explores an instantiated literal 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 experiments with an operator at each node. The positive state, in which an operator can be successfully executed, constitutes initial preconditions of an operator. We analyze the number of required experiments as a function of the number of missing preconditions in a seed state. We introduce a naive domain assumption to test only a subset of the exponential state space. Since breadth‐first search is expensive, WISER introduces two search techniques to reorder literals at each level of the search tree. We demonstrate performance improvement using the naive domain assumption and literal‐ordering heuristics. To learn the effects of an operator, WISER computes the delta state, composed of the add list and the delete list, and parameterizes it. Unlike previous systems, WISER can handle unbound objects in the delta state. We show that machine‐generated effects definitions are often simpler in representation than expert‐provided definitions.