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.
Algorithm: Goal Stack Planning
- Push the original goal on the stack.
- Repeat step
a to d until the stack becomes empty.
- If TOP is a compound goal, push its unfinished subgoals onto the stack.
- 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.
- If TOP is
an action,
- Pop the action
- Execute the action
- update the knowledge base with effects of the action
- 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