Developing logical approach to solving automated planning problems: an analytical review

Abstract

The article provides an analytical review of the application of methods based on a logical approach to solving classical Automated Planning problems, in which the determinism of the actions of performers is assumed, and the duration of actions is not analyzed and quantitative resources are not taken into account. In contrast to the Scheduling Theory, where the focus is almost always on solving problems of a specific type, Automated Planning develops general methods for solving a wide range of problems using their declarative description. Perhaps that is why the logical approach, which assumes a declarative representation of knowledge and unified inference engines, has gained such popularity in solving automated planning problems. The most recently researched planning systems based on the development of this approach include systems using Constraint Programming Technology. Recently, there has been an increased interest in table constraint inference procedures. In addition to typical tables, the table constraints include compressed tables, smart tables and etc. The table constraints are increasingly used in Automated Planning problems: in order to effectively solve high-dimensional problems, various kinds of graphs are translated into table constraints, with the help of which transitions from state to state and/or from one action to another are encoded. Therefore, a significant part of the presented analytical review deals with the application of table constraints in Automated Planning problems. In addition, such well-known methods as reducing planning problems to the search for proof of theorems, translating the planning graph into the Boolean satisfiability problem and constraint satisfaction problem are considered.