How to recognize a STRIPS planning problem has no solution?

Question

Strips –Stands for STanford Research Institute Problem Solver (1971).

STRIPS Pseudo code -

STRIPS(stateListstart, stateListgoals)
1.Set state = start
2.Set plan = []
3.Set stack = goals
4.while stack is not empty do
     1.STRIPS-Step()
5.Return plan

STRIPS-Step()
switch top of stack t:
1.case this a goal that matches state:
    1.pop stack
2.case this an unsatisfied conjunctive-goal:
    1.select an ordering for the sub-goals
    2.push the sub-goals into stack
3.case this a simple unsatisfied goal
    1.choose an operator op whose add-list matches t
    2.replace the twith op
    3.push preconditions of op to stack
4.case this an operator
    1.pop stack
    2.state = state + t.add-list -t.delete-list
    3.plan = [plan | t]

Some explanations -

state - is a list of predicates.

stack - is a stack which includes both predicates or operations.

[plan | t] - add the opreration t to list plan.

If the stack gets empty, it means that plan holds the solution plan.

Since the algorithm is running while stack is not empty do, how can I recognize that there is no solution (i.e plan) which led to the goal state ?

Those who are not familiar with this algorithm, you can see its running example here. Brief introduction: imagine a crane which picks boxes and put them each other , so operation can be put box A on box B and state can be box A is on box B .

Answer 1

Realize that STRIPS solves linear planning problems. By this I mean those planning tasks where the order in which the goals are satisfied is not relevant and these are, in practice, easier to solve than the non-linear planning problems ---be aware, however, that STRIPS is PSPACE-complete anyway and it is necessary to restrict it quite a lot to prove it to be NP-complete (though whether both classes are equal is still unknown but, ... may I say unlikely?)

Non-linearity is quite intriguing. It does not only mean that a particular planning task with, say, 3 goals $G=\{g_1, g_2, g_3\}$ can only be satisified in a particular ordering (such as: first $g_2$, then $g_1$ and finally $g_3$). It might also imply that while some goals are achieved simultaneously, others have to be satisified in a particular order. A good discussion on the subject can be found in Korf, Richard E. Planning as Search: A Quantitative Approach. Artificial Intelligence 33, pp. 65--88. 1987

From your pseudocode, realize that STRIPS commits to a particular order in line 2.1 of STRIPS-step and it never tries any other one. In fact, the ordering selected for the goals is strict after step 2.2. Thus, STRIPS explores the whole state space engendered by the definition of the planning task for a particular ordering of the subgoals If this ordering has not been properly chosen, then the problem is unsolvable for STRIPS.

In the end, all that STRIPS can say is that a problem is unsolvable for a particular ordering but not whether the planning task is solvable or not. Although it is not shown in your pseudocode, recall that STRIPS can discard a particular operator if its preconditions introduce goals that were considered before ---i.e., it avoids circular reasonings. And, in the end, it will have no available operator if the problem is unsolvable for the selected ordering.

PRODIGY was an attempt to solve this problem by explicitly enumerating all the different orderings of the subgoals which, however, might become very easily an unmanageable number. FF, Hoffmann, Joerg, Nebel, Bernhard. The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research 14, pp. 253--302. 2001, however, can detect that some planning tasks are unsolvable even if they are non-linear planning tasks just by verifying that the relaxed graphplan cannot achieve them. Nevertheless, this procedure is sound but incomplete ---i.e., some unsolvable planning tasks can seem solvable fooling FF.