Goal Stack Planning-Python Code

Planning is one on the basic tasks in Artificial Intelligence. It is an essential component of applications like Robotic Control or Goal achieving applications of AI. It is basically the task of decision making in such applications. Goal Stack Planning is one such algorithm that is implemented in AI applications to evaluate the likelihood of completion of a specific task.

The STanford Research Institute Problem Solver(STRIPS) specifically used the Goal Stack Planning algorithm  for its action-centric representation.

Key features of its representation are-

  • Stack to maintain the action and satisfy the goal.  
  • Knowledge base to maintain the current state, actions.

Goal stack planning resembles a node in a search tree. Starting from a specific node the branches is created only when there is a possibility of taking a further action.

Goal Stack Planning

Algorithm: Goal Stack Planning

  1. Push the original goal on the stack.
  2. Repeat step a to d until the stack becomes empty.
    1. If TOP is a compound goal, push its unfinished subgoals onto the stack. 
    1. If TOP is a single unfinished goal then, replace it with an action and push the action’s precondition on the stack to satisfy the condition.
    1. If TOP is an action,
      1. Pop the action
      1. Execute the action
      1. update the knowledge base with effects of the action
    1. If TOP is a satisfied goal, pop it.
tab = []
result = []
goalList = ["a", "b", "c", "d", "e"]


def parSolution(N):
    for i in range(N):
        if goalList[i] != result[i]:
            return False
    return True


def Onblock(index, count):

    # break point of recursive call
    if count == len(goalList)+1:
        return True
    # copy tab of index value to result
    block = tab[index]
    # stack block
    result.append(block)
    print(result)
    if parSolution(count):
        print("Pushed a result solution ")
        # remove block from tab
        tab.remove(block)
        Onblock(0, count + 1)
    else:
        print("result solution not possible, back to the tab")
        # pop out if no partial solution
        result.pop()
        Onblock(index+1, count)


def Ontab(problem):
    # check if everything in stack is on the tab
    if len(problem) != 0:
        tab.append(problem.pop())
        Ontab(problem)
    # if everything is on the tab the we return true
    else:
        return True


def goal_stack_planing(problem):
    # pop problem and put in tab
    Ontab(problem)
    # print index and number of blocks on result stack
    if Onblock(0, 1):
        print(result)


if __name__ == "__main__":
    problem = ["c", "a", "e", "d", "b"]
    print("Goal Problem")
    for k, j in zip(goalList, problem):
        print(k+"    "+j)
    goal_stack_planing(problem)
    print("result Solution")
    print(result)

The advantage of this technique is that the generated plans display complete sequence of operations. It starts from original unfinished goal and at each step complete set of sequential operations for the next incomplete goal are generated. A database that describes the current situation. Use of stack in this code allow to backtrack and follow an unfinished task – part of the current subgoal.

Other Artificial Intelligence techniques like heuristics or A* can also be used to find finished goals. Using these it becomes easier to discard paths that do not promise reaching the goal.

Be First to Comment

Leave a Reply

Your email address will not be published.