Acting and Learning with Goal and Task Decomposition

Abstract

Two central problems of creating artificial intelligent agents that can operate in the human world are learning the necessary knowledge to achieve routine tasks, and using that knowledge effectively in a complex and unpredictable domain. The thesis argues that an important part of this domain knowledge should be represented in the form of decomposition rules that decompose tasks into subgoals. The thesis presents HOPPER, an implemented planning system that uses decomposition rules and a least-commitment decomposition strategy that strikes a balance between reactive and deliberative planning. Like reactive planners, HOPPER is able to robustly handle and recover from unexpected events with minimal disruption to its plan. Like deliberative planners, it is also able to plan ahead to take advantage of opportunities to interleave and shorten its sub-plans. The thesis also presents TADPOLE, an implemented learning system that learns both the structure and preconditions of new decomposition rules from a small number of lessons demonstrated by a teacher. It learns by parsing and interpreting the teacher’s behaviour in terms of decomposition rules it already knows. It extends its rule set by filling in the holes in its parses of the teacher’s lessons. Both HOPPER and TADPOLE have been evaluated together in two different domains: a kitchen domain that emphasizes complexity, and a logistics domain that emphasizes plan efficiency. Every rule used by HOPPER was learned by TADPOLE and every rule learned by TADPOLE was successfully used by HOPPER to achieve various tasks, showing that TADPOLE is able to learn effective decomposition rules from minimal lessons from a teacher, and that HOPPER is able to robustly make use of them even in the face of unexpected events.