Goal Stack Planning

The reasoning strategy used by STRIPS is goal stack planning. In goal stack planning, the problem solver makes use of a goal stack GS that contains both subgoals and actions that have been proposed to satisfy those subgoals. It also relies on a database DB that describes the current situation, and a set of actions described by precondition, add and delete lists.

At each succeeding step of the problem solving process, a subgoal of the stack is pursued. An action that could cause it to be true is sought. If an appropriate action is found, its precondition is established as the top subgoal of the stack in order for that action to be applicable. When a sequence of actions that satisfies a subgoal is found, that sequence is applied to the current situation, yielding a new current situation. Then, all the subgoals that are satisfied by the new current situation are popped off the stack. Next, another subgoal of the stack is explored and an attempt is made to satisfy it, starting from the situation that was produced as a result of satisfying the first subgoal.

This process continues until the goal stack is empty. Then, as one last check, the original goal is compared to the final situation derived from the application of the chosen actions. If any conditions on the goal are not satisfied in that situation (which they might not be if they were achieved at one point and then undone later), then those unsolved subgoals are reinserted onto the stack and the process resumed (Rich and Knight 91).

The algorithm used by goal stack planning can be summarized as follows: repeat the cycle below until the goal stack is empty, otherwise return the plan associated with the database describing the current situation as a solution.

1. Replace top subgoal of GS by an appropriate action, and add its precondition to the top of GS.
2. If the top element of GS is a subgoal that can be proved from the formulas in DB, pop it off from GS, and consider the next element of GS. If the top element of GS is an action, apply it to DB, pop it off from GS, add it to , and consider the next element of GS.
3. If go to step 1. If check whether the formulas in the stack describing the goal configuration can be proved from DB. Reinsert in GS the formulas that cannot be proved, and go to step 1.