Goal Stack Planning

The reasoning strategy used by STRIPS is goal stack planning [13]. 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, and a database DB of logical formulas describing the current situation. The algorithm of 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 the top subgoal of GS by an appropriate action, and add its precondition to the top of GS.
2. Until the top element of GS is a subgoal that cannot be proved from the formulas in DB, do the following.
   1. If the top element of GS is a subgoal that can be proved from the formulas in DB, pop it from GS.
   2. If the top element of GS is an action, pop it from GS, apply it to DB, and append it to the end of .

3. If , check whether the formulas in the stack describing the goal configuration can be proved from DB. Add to GS the formulas that could not be proved from DB.