Efficient Precondition Evaluation for Lifted Progression Planning

The popular approach in modern automated AI planning is to transform a given planning problem to a grounded transition system before attempting to solve it. This approach struggles on 'difficult-to-ground' planning problems which include a large number of objects and action schemas with many arguments since the transition system may not fit in memory. An alternative approach to planning from a theorem-proving perspective works directly with lifted action schemas during runtime to find which ground actions are possible in a given state. This alleviates issues with difficult-to-ground problems, but currently, evaluating action preconditions at runtime to find next possible actions is computationally expensive. In this thesis, I introduce two new methods for evaluating action preconditions more efficiently. These methods rely on algorithms for conjunctive query answering, namely the HashJoin and LFTJ algorithms developed in database management systems. They help alleviate a computational bottleneck faced by the theorem-proving approach at runtime. I also improve a domain-independent heuristic based on the 'planning graph' data structure which aids lifted planners in determining promising action sequences. All methods have been experimentally evaluated and compared on a large collection of planning benchmarks. I summarize experimentally determined division of work related to precondition evaluation that can be done offline vs computations that can be done at runtime. My thesis draws conclusions about the next steps in efficient evaluation of action preconditions.