Planning for Solving Problems: 5 Steps | Artificial Intelligence

In order to solve any complex problem the following tasks need to be done step wise:

1. Choose the best rule to apply the next, based on the best available heuristic information.

2. Apply the chosen rule to complete the new problem state which arises from its application.

3. Detect when a solution has been found.

4. Detect dead-ends so as to avoid them and direct the system’s effort in more fruitful direction.

5. Detect when an almost correct solution has been found so as to employ special techniques to make it totally correct.

The first four tasks are required for all types of problem solving and the fifth one is needed for more complex system for which planning is needed.

Let’s discuss them one-by-one with the help of the Block-world example:

Step # 1. Choosing the Best Rule (Rules to Apply):

Isolate a set of differences between the desired goals state and the current state, and identify those rules which are relevant to reducing, differences. If several rules are available then by using other heuristic information the best one is selected. This technique is based on Means-End-Analysis.

Step # 2. Applying Rules:

Having selected the rules how do we apply them?

In most of the cases problems are simple so these rules can be applied in a straight forward manner since the problem can be reduced into many sub-problems and rules required to deal them are available. But some times available rules can tackle only a part of the problem! Then how to deal with such cases?

The problem is divided into many sub-problems and specific rules, which specify only a small part of the complete problem state are applied.

There are many methods, one such method is described below:

a. For each action, describe each of the changes it makes to the state’s description. Statement that everything else remains unchanged also need to be made. In Green’s formulation (1986) a given state in a system was described by a set of predicates presenting the facts which were true in that state. Each distinct state was represented explicitly as part of the predicate. Fig. 8.2, shows how a state, called S₀, of a given blocks world problem could be represented, according to Green’s formulation.

The manipulation of these state descriptions was done using resolution theorem. So, for example, the effect of the operator UNSTACK(x, y) could be described by the following axiom (variables are assumed universally quantified, unless expressed otherwise).

[CLEAR(x, s) ˄ ON(x, y, s)] →

[HOLDINGS, DO (UNSTA CK(x, y), s)) ˄

A CLEAR(y, DO(UNSTACK(x, y), s))].

Here, DO is a function which specifies the new state generated as a result of the action generated after the execution of the given operator in that given state.

The above axiom states that if the predicates CLEAR(x) and ON(x, y) both hold in state S₀, then the predicates HOLDING(x) and CLEAR(y) will hold good in the state S₁which results from Doing an action UNSTACK(x, y), starting in state S.

If we execute action UNSTACKC(A, B) in state S₀ as defined above, we get after the operation Unstacking in new state S₁

HOLDING(A, S₁) ˄ CLEAR(B, S₁)

What else do we know about the situation in S₁? Intuitively, we know that B is still on the table. But we cannot derive it so far from the database we have. To do so, we need to provide a set of rules called FRAME AXIOMS, which describe components of the state which are not affected by each operator.

So for example, we need to say that:

1. ONTABLE(z, s) → ONTABLE(z, DO(UNSTACK(x, y), s) that is the ONTABLE relation is never effected by the UN STACK operator.

2. ON relation is only affected by the UN STACK operator if the blocks involved in the ON relation are the same as ones involved in the UNSTACK, expressed in logic as-

[ON (m, n, s) ˄ ¬ EQUAL(m, x) → ON(m, n), DO(UNSTACK(x, y),s))].

The advantage of this approach is that a single mechanism, resolution, can perform all the operations which are required on state description. But the number of axioms which are required become very large if the problem state descriptions are complex. To handle complex problem domains we need a mechanism which does not require a large number of explicit frame axioms. One such mechanism is the one used by the early robot problem solving system STRIPS and its descendants. 

In this approach each operation is described by a list of new predicates which the operator causes to become true and a list of old predicates which it causes to become false, ADDLIST and DELETE LIST respectively.

A third list, PRECONDITION list (P), contains those predicates which must be true for the operator to be applied. The frame axioms of Green’s function are specified implicitly in STRIPS: any predicate not included on either the ADD (A) or DELETE (D) list of an operator is assumed to be unaffected by it.

This means that in specifying each operator, we need not consider aspects of the domains which are unrelated to it that is, the relationship of UN STACK to COLOUR need not be given, if specially not needed. This means that some mechanism other than simple theorem proving must be used to compute complete state descriptions after operations have been performed.

STRIPS-style operators corresponding to blocks world operation are shown in Fig. 8.3.

We may note that for simple rules such as these PRECONDITION list is identical to DELETE list. In order to pickup a block, the robot arm must be empty; as soon as it picks up a block, it is no longer empty.

But preconditions are not always deleted, for example, for the arm to pick up a block, the block must have no other block on the top of it. After it has been picked up it still has no blocks on the top of it. This is the reason that the P and D lists must be specified separately.

By making use of frame axioms implicit in STRIPS, the information which must be supplied for each operator is reduced considerably. This means that when a new attribute which the objects might possess is introduced into the system, it is not necessary to go back and add a new axiom for each of the existing operators. But how can it actually achieve the effect of the use of the frame axioms in computing complete state descriptions?

The first thing we notice is that for complex state descriptions most of the state remains unchanged after each operation. But if we represent the state as an explicit part of each predicate, as was done in Green’s system, then all that information must be deduced all over again for each state.

To avoid that, we can drop the explicit state indicator from the individual predicates and instead simply update a single database of predicates so that it always describes the current state of the world. To explain it let us once again refer to Fig. 8.2.

The initial state would be represented as:

ON(A, B) ˄ ONTABLE(B)˄ CLEAR(A)

After applying the operator UNSTACK (A, B), the description of the world would become (by making use of the ADD and DELETE lists of the operator UNSTACK):

ONTABLE (B) ˄ CLEAR(A) ˄ CLEAR (B)˄ HOLDING(A) …………. (8.1)

So far, so good for a single state description. But how does the sequence of operators affect the searching process when a number of operators are used for searching? In such a case when an incorrect sequence is explored, it must be possible to return to the original state by trying a different operator.

But this is possible even if the global database describes the problem state at the current node of the search graph. All we need to do is to record at each node the changes which need to be made to the global database as we passed through the node. Then, if we backtrack through that node we can undo the changes.

But the changes are described exactly in the ADD and DELETE lists of the operators which have been applied to move from one node to another. So we need only record, along each arc of the search graph, the operator which was applied. Fig. 8.4, shows a small example of such a search tree and the corresponding global database.

The initial state is the same as shown in Fig. 8.2. In view of the reasoning given above we must mention the operator (UNSTACK) as also its arguments in order to be able to undo the changes later.

Now suppose we want to explore a path different from the one just considered. First we back track through node 3 by adding each of the predicates in PUTDOWNs DELETE list to the global database and deleting each of the elements of PUTDOWN’s ADD list. After doing that, the database contains.

ONTABLE (B) ˄ CLEAR (A) ˄ CLEAR (B) ˄ HOLDING (A) …… (8.2) 

The reader should verify this description to be identical, as expected, to the one we previously computed description 8.1, as a result of applying UN STACK to the initial state.

If we repeat this process with which using the ADD and DELETE lists, of UNSTACK we get the description:

ONTABLE (B) ˄ CLEAR (A) ˄ ON (A, B) ˄ ARMEPTY

Which is the same as shown in Fig. 8.2, and with which we started. Because of the importance of implicit statement of frame axioms in STRIPS most of the operators used in planning make use of this style of representation.

Step # 3. Detecting a Solution:

A planning system has succeeded in finding a solution to a problem when it has found a sequence of operators which transforms the initial problem state into the goal state. How will it be known that it has been done so? In simple problem solving systems this question is easily answered by matching the state descriptions with the goal.

In a complex problem, the entire states are not represented explicitly but rather are described by a set of relevant properties. So, the solution depends on the way which state descriptions are represented. For any representational scheme which is used, it must be possible to reason with representation to discover whether one matches another.

Any knowledge representation, and reasoning method or combination of available methods can be used to discover when a solution has been found. Predicate logic because of its deductive mechanism proves to be a useful representable technique. A triangular table is another representable scheme.

Step # 4. Detecting Dead Ends:

A planning scheme is searching for a sequence of operators to solve a particular problem, it must be able to detect when it is exploring a path which can never lead to a solution (or appears unlikely to lead to one). The same reasoning mechanism which can be used to detect a solution can often be used for detecting a dead end.

If the search process is reasoning forward from the initial state, it can prune any path which leads to a state from which the goal state cannot be reached. If the search process is reasoning backward from the goal state, it can also terminate a path either because it is sure that the initial state cannot be reached or because little progress is being made towards that end.

In reasoning backward, each goal is decomposed into sub-goals. Each of them, in turn, may lead to a set of additional sub-goals. Sometimes, it is easy to detect that there is no way that all the sub-goals in a given set can be satisfied at once.

For example, a robot arm cannot both be empty and holding a block. Any path which is attempting to make both of these goals true simultaneously can be pruned immediately. Other paths can be pruned because they lead to nowhere. For example, if in trying to satisfy goal A, the program eventually reduces its problem to satisfying goal A, B and C, it has made little progress. It has produced a problem even harder than its original one such a path leading to this problem should be abandoned.

Step # 5. Repairing an Almost Correct Solution:

In the simple cases, the problems can be decomposable or a nearly so. If the problem is assumed to be the decomposable proceed to solve the sub-problems separately, combine the sub-solutions and then check for the solution. When sub-solutions are combined they yield a solution to the original problem. If they do not, the best solution is to throw them away – which is of course wastage of efforts.

A slightly better approach is when the sequence of operations corresponding to the proposed solution is executed and compared that situation with the desired goal. In most cases, the difference between two will be smaller than the difference between the initial state and the goal. The problem solving system is called again and again iteratively till the differences between the desired solution and iterative solution is eliminated.

An even better way to patch up an almost correct solution is to appeal to specific knowledge about what went wrong and then apply direct patch. For example, suppose that the reason of the proposed solution being inadequate is that one of its operators cannot be applied because at the point it should have been invoked its precondition were not satisfied. This might occur if the operator had two preconditions and the sequence of operations which makes the second one true made the first one untrue. But perhaps if the condition were satisfied in the opposite order the problem could have not cropped up.

A still better approach could be: not to patch up the incomplete solutions at all but rather leave them incompletely specified until the last possible moment. Then, when as much information as possible is available, complete the specification in such a way that no conflicts arises. This approach is called as LEAST-COMMITMENT strategy. It can be applied in a variety of ways. One is to defer deciding on the order in which operations will be performed.

In our above example of block-world, instead of arbitrarily choosing on order in which to satisfy a set of preconditions, we could leave the order unspecified until the very end. Then we would look at the effects of each of the substitutions to determine the dependencies exist among them. At that point an ordering can be chosen. In various methods available ordering of the parameters plays a crucial role.