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
.