Substructure Discovery in Executed Action Sequences

Abstract

Abstract : This thesis describes a system, PLAND (Plan Discovery) for discovering substructures in observed action sequences. The goal of this thesis is to show how a system can learn useful macro operators by observing a task being performed. An intelligent robot using this system can learn how to perform new tasks by watching tasks being performed by someone else, even if the robot does not possess a complete understanding for the actions being observed. There may be more than one hypothesis of how an action (or macro operator) contributes to the completion of a task and PLAND allows for these various meanings to be pursued simultaneously. Macro operators are discovered within a specific context that provides the types of generalizations allowed in the discovery process and uses the previously proposed macro operators to build new ones. Background knowledge is used to determine which generalizations are appropriate and to control search. Although the system can discover simple syntactic structures (regular grammars) without background knowledge more meaningful and useful structures are discovered when background knowledge is incorporated into the process.