ARTIFICIAL INTELLIGENT PART 3

Planning

The task of coming up with a sequence of action that will achieve a goal is called planning.

§  One technique of problem-solving, like searching

§  More complicated problems are divided into small pieces to work separately

§  Without division, it becomes too large to handle in the amount of time available.

Two ways of decomposition of a problem

a) Avoid having to recomputed the entire problem state when we move from one state to other eg. If we move from one room to another, this does not effect the locations of the doors and the windows in the two rooms.

b) Divide a single hard problem into several hopefully easier problems.

Planning:

Planning is the use of methods which do these two kinds of decomposition on the original problem into appropriate subparts and interaction between these subparts.

Components of a Planning System

Elementary techniques in problem solving:

1) Choose the best rule to apply based on available heuristic information

§   Most widely used technique for selecting apprpriate rules t apply is : “First isolate a set of difference between desired goal state and the current state and then to identify those rules to reducing their differences.

§  If several rules are found, a variety of other heuristic information can be exploited to choose among them.

§  This technique is based on ‘Mean end analysis’.

2) Apply the chosen rule

§  To compute the new problem state that arises from its application

§  each rule simply specified the problem state that would result from its application

§  state is described by a set of predicates

§  Manipulation of these state descriptions was done using a resolution theorem prover

§  preconditions to apply the rule, adding and deleting the state description are made in STRIPS; problem solving system

3) Detecting the solution

§  Can we reach by applying the sequence of operators that are applicable?

§  Yes implies that planning system has succeed

§  Many reasoning mechanism like predicate calculus can be used to deduce

§  If we cannot get the targeted state, some initial state description should be added or sequence of operator  should be revised.

4) Detecting the dead end

§  Like searching for a sequence of operators to solve a particular problem, the planning system must be able to detect the path that can never be lead to a solution.

§  Reasoning process are used to detect them.

5) Repairing an almost correct solution

§   used for more complex systems e.g. nearly decomposable problems

§  One can assume the nearly decomposable problems as completely decomposable problem and proceed to solve the sub problems separately

§  Many repairing strategies are available

Problems Related to Planning

1) Frame Problem

§  The problem of how to determine which things change and which do not in a problem domain is known as the frame problem.

§  The problem becomes increasingly important as the complexity of the problem state increases

§  It is snot possible to represent individual objects and facts in the world. In the world, some facts change where some others remains the same

§  Thus a different mechanism is required that odes’nt6 require a large number of explicit frame axioms to be stated. This is don with STRIPS planning mechanism.

2) Qualification Problem

§  The problem of representing special cases or more precise conditions is known as the qualification problem. For example: only light objects can be moved.

3) Ramification Problem

§  The process of keeping track of which derived formulas survives subsequent transitions. E.g. Robot picks up a package in room R1 and later moves to R2. How do we present the frame axioms form asserting that the package is still in room R1.

STRIPS Planning

§  Stanford Research Institute Planning System

§  The STRIPS was used for planning actions of the robot SHAKEY

§  In this planning system each operation is described by a list of new predicates as follows:

i)ADD list: It is a list of new predicates that the operator causes to become true.

ii) DELETE list: It is a list of old predicates that it causes to become false.

iii) PRECONDITION list : It is a list of predicates that must be true for the operator to be applied

Basic Approach of STRIPS

i) Find a difference between current state and goal state

ii) Find a relevant operator ‘f’ for reducing the difference

iii) Achieve precondition of ‘f’ apply ‘f’ from the result state : achieve goal ‘G’.