Adaptive search in a hierarchical problem-solving architecture

Abstract

The ability to solve novel problems is a distinguishing feature of human intelligence. This capacity has been replicated in both cognitive architectures and AI planning systems, but previous work has ignored its adaptive character. In this paper, we review HPS, a cognitive architecture that searches a space of hierarchical problem decompositions with parameters that support a variety of strategies. Moreover, decisions made by these strategic parameters may be conditioned on information available during search, such as the depth, branching factor, and progress toward the goal description. We examine three such parameters, one that decides whether to chain forward or backward when retrieving operator instances, one that determines how far to backtrack upon failure, and another that decides how deep to search before backtracking. In each case, we describe adaptive methods for making these decisions and report experiments which compare their performance with that for fixed strategies. In closing, we recount prior research on adaptive problem solving and propose some directions for future work in this understudied area.