# How to recognize a STRIPS planning problem has no solution?

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 .

-

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