An important form of learning involves acquiring skills that let an agent achieve its goals. Although there has been considerable work on learning in planning, most approaches have been sensitive to representations of background knowledge, which hinders their generality. A mechanism that acquires skills effectively across different representations would support more robust behavior. In this paper, we present a novel approach to constructing hierarchical task networks that acquires conceptual predicates as learning proceeds, making it less dependent on carefully crafted background knowledge. This procedure for representation acquisition expands the system’s knowledge about the world and leads to more rapid learning. We demonstrate the mechanism’s effectiveness by comparing its behavior with that of a similar learner that does not extend its representation.