Planning with Regression Analysis in Transaction Logic

Heuristic search is arguably the most successful paradigm in Automated Planning, which greatly improves the performance of planning strategies. However, adding heuristics usually leads to very complicated planning algorithms. In order to study different properties (e.g. completeness) of those complicated planning algorithms, it is important to use an appropriate formal language and framework. In this paper, we argue that Transaction Logic is just such a specification language, which lets one formally specify both the heuristics, the planning algorithm, and also facilitates the discovery of more general and more efficient algorithms. To illustrate, we take the well-known regression analysis mechanism and show that Transaction Logic lets one specify the concept of regression analysis easily and thus express \(\textit{RSTRIPS}\), a classical and very complicated planning algorithm based on regression analysis. Moreover, we show that extensions to that algorithm that allow indirect effects and action ramification are obtained almost for free. Finally, a compact and clear logical formulation of the algorithm lets us prove the completeness of \(\textit{RSTRIPS}\)—a result that, to the best of our knowledge, has not been known before.