Using regression-match graphs to control search in planning

摘要

Classical planning is the problem of finding a sequence of actions to achieve a goal given an exact characterization of a domain. An algorithm to solve this problem is presented, which searches a space of plan prefixes, trying to extend one of them to a complete sequence of actions. It is guided by a heuristic estimator based on regression-match graphs, which attempt to characterize the entire subgoal structure of the remaining part of the problem. These graphs simplify the structure by neglecting goal interactions and by assuming that variables in goal conjunctions should be bound in such a way as to make as many conjuncts as possible true without further work. In some domains, these approximations work very well, and experiments show that many classical planning problems can be solved with very little search.