Admissible Pruning Strategies Based on Plan Minimality for Plan-Space Planning

Abstract

Although plan space planners have been shown to be flexible and efficient in plan generation, they do suffer from the problem of "looping '- that is they may spend an inordinate amount of time. doing locally seemingly useful but globally useless refinements In this paper I review the anatomy of looping and argue that looping is intimately tied to the production of non minimal solutions I then propose two classes of admissible pruning techniques based on the notion of plan minimality I show that the first one is admissible for planners which do not protect their establishments but allow a precondition to be reestablished any number of times The second one is admissible for planners which protect their establishments through causal links I also discuss the complexity of the proposed pruning strategies and then potential applications 1