ON TRANSFORMATION OF STRIPS PLANNING PROBLEM

STRIPS planning is a difficult computational problem. One way to increase efficiency of searching for a solution may be a transformation of a problem to another problem and then search for a solution of the transformed problem. In this work a simple STRIPS problem has been transformed to two problems: linear programming and linear equalities and inequalities. The transformation from planning to Linear Programming is based on mapping of conditions and operators in each plan step to variables. Truth-values of conditions are mapped to 0 and 1 values. For linear programming the objective function reaches the maximum if the goal situation is true in last step of planning. For inequalities and equalities the goal situation is mapped to equality constraints. The efficiency and quality of this approach has been analyzed and compared.