Initial State - ON(B,A) ∧ ONTABLE(A) ∧ ONTABLE(C) ∧ ONTABLE(D) ∧ CLEAR(B) ∧ CLEAR(C) ∧ CLEAR(D) ∧ ARMEMPTYįor example, to perform the STACK(X,Y) operation i.e. Using these predicates, we represent the Initial State and the Goal State in our example like this: Given below are the list of predicates as well as their intended meaning Predicates can be thought of as a statement which helps us convey the information about a configuration in Blocks World.

Representing the configurations as a list of “predicates” World State on the other hand starts off as the Initial State and ends up being transformed into the Goal state.Īt the end of this algorithm we are left with an empty stack and a set of actions which helps us navigate from the Initial State to the World State. Goal Stack uses this world state to work its way from Goal State to Initial State. We make use of a stack to hold these goals that need to be fulfilled as well the actions that we need to perform for the same.Īpart from the “Initial State” and the “Goal State”, we maintain a “World State” configuration as well. We keep solving these “goals” and “sub-goals” until we finally arrive at the Initial State. These preconditions in turn have their own set of preconditions, which are required to be satisfied first. We start at the goal state and we try fulfilling the preconditions required to achieve the initial state. Goal Stack Planning is one of the earliest methods in artificial intelligence in which we work backwards from the goal state to the initial state. Our aim is to change the configuration of the blocks from the Initial State to the Goal State, both of which have been specified in the diagram above. The robot arm can move only one block at a time, and no other block should be stacked on top of the block which is to be moved by the robot arm. We have a robot arm to pick up or put down the blocks. Some blocks may or may not be stacked on other blocks. This is how the problem goes - There is a table on which some blocks are placed. In this medium article, we will take look at the Blocks World Problem and implement Goal Stack Planning to solve the same. Blocks World Problem - Initial State and Goal State for this article P holds if a and b hold, or if a does not hold and c holds too Thereįor example, suppose that we need to write code to capture the following condition: Nonetheless, “generally” does not mean “always”. Nonetheless, it is an important programming construct: it is generally a better idea to try use negation as failure than to write code containing heavy use of red cuts. Summing up, we have seen that negation as failure is not logical negation, and that it has a procedural dimension that must be understood. In the new version (which goes wrong) we useīefore we have done this. In a nutshell, the crucial difference between the two programs is that in the original version (the one that works right) we use After all, the database contains the informationįails, and hence the original query does too. Holds, which means that it must check whetherįails. What’s going on? Well, in the modified database, the first thing that Prolog has to check is whether And indeed, this is the crucial generalisation: the cut-fail combination lets us define a form of negation called negation as failure.

That is, the cut-fail combination seems to be offering us some form of negation. The crucial observation is that the first clause is essentially a way of saying that Vincent doesĮnjoy X if X is a Big Kahuna burger. Something useful is clearly going on here, but it would be better if we could extract the useful part and package it in a more robust way.Īnd we can. In short, we’ve got two mutually dependent clauses that make intrinsic use of the procedural aspects of Prolog. Similarly, the cut is crucial: if we remove it, the program doesn’t behave in the same way (so this is aĬut). For a start, note that the ordering of the rules is crucial: if we reverse the first two lines, we This tries to force backtracking, but the cut blocks it, and so our query fails. This commits us to the choices we have made, and in particular, blocks access to the second rule. , the first rule applies, and we reach the cut. In the first line (this even has a name: it’s called the cut-fail combination). How does this work? The key is the combination of

Prolog code for block world problem