PABLO is a nonlinear planner that reasons hierarchically by generating abstract predicates. PABLO’s abstract search spaces are generated automatically using predicate relaxation, a new technique for defining hierarchies of abstract predicates. For some domains, this mechanism generates hierarchies that are more useful than those created by previous techniques. Using abstractions can lead to substantial savings in computation time. Furthermore, PABLO can achieve a limited form of reactivity when reasoning with relaxed predicates. These abstractions can be viewed as small reactive plans, and our method as an approach to dynamically combining these into useful nonlinear plans.