Situation-space Planning Algorithms

Situation-Space Planning Algorithms: There are 2 approaches to situation-space planning:

1. Progression situation-space planning
2. Regression situation-space planning

Progression Planning:

• Forward-chaining from initial state to goal state
• Looks just like a state-space search except STRIPS operators are specified instead of a set of next-move functions
• You can use any search method you like (i.e. BFS, DFS, A*)
• Disadvantage: huge search space to explore, so usually very inefficient

Algorithm:

1. Start from initial state
2. Find all operators whose preconditions are true in the initial state
3. Compute effects of operators to generate successor states
4. Repeat steps #2-#3 until a new state satisfies the goal conditions

The work through of the progression algorithm for the Blocks World example is shown below: