Planning

Planning refers to the process of computing several steps of a problem solving before executing any of them.Planning is useful as a problem solving technique for  non decomposable problem.

Components of Planning System:

In any general problem solving systems, elementary techniques to perform following functions are required

• Choose the best rule (based on heuristics) to be applied
• Apply the chosen rule to get new problem state
• Detect when a solution has been found
• Detect dead ends so that new directions are explored.

To choose the rules ,

• first isolate a set of differences between the desired goal state and current state,
• identify those rules that are relevant to reducing these difference,
• if more rules are found then apply heuristic information to choose out of them.

To apply rules,

 

In simple problem solving system, 

• applying rules was easy as each rule specifies the problem state that would result from its application.
• In complex problem we deal with rules that specify only a small part of the complete problem state.

Let us consider the famous problem name as Block World Problem ,which helps to understand the importance of planning in artificial intelligent system.

The block world environment has ,

• Square blocks of same size
• Blocks can be stacked one upon another.
• Flat surface (table) on which blocks can be placed.
• Robot arm that can manipulate the blocks. It can hold only one block at a time.

In block world problem, the state is described by a set of predicates representing the facts that were true in that state.One must describe for every action, each of the changes it makes to the state description.In addition, some statements that everything else remains unchanged is also necessary.We are having four types of operations done by robot in block world environment .They are

UNSTACK (X, Y) : [US (X, Y)]

• Pick up X from its current position on block Y. The arm must be empty and X has no block on top of it.

STACK (X, Y):  [S (X, Y)] 

• Place block X on block Y. Arm must holding X and the top of  Y is clear. 

PICKUP (X):  [PU (X) ]

• Pick up X from the table and hold it. Initially the arm must be empty and top of X is clear.

PUTDOWN (X):  [PD (X)]

• Put block X down on the table. The arm must have been holding block X.

Along with the operations ,some predicates to be used to describe an environment clearly.Those predicates are,

• ON(X, Y)               -              Block X on block Y.
• ONT()                    -              Block X on the table.
• CL(X)                     -              Top of X clear.
• HOLD(X)               -              Robot-Arm holding X.
• AE                           -              Robot-arm empty.

Logical statements true in this block world.

X Holding X means, arm is not empty     

 

                                ($ X) HOLD (X) ® ~ AE

X is on a table means that X is not on the top of any block

                                (" X) ONT (X) ® ~  ($ Y) ON (X, Y)

Any block with no block on has clear top

                                (" X) (~  ($ Y) ON (Y,X)) ®  CL (X)

Initial State

 

Armempty

clear(block2)

ontable(block2)

ontable(block1)

clear(block1)

Goal State

 

 

Armempty

ontable(block2)

on(block1, block2)

clear(block1)

We have to generate a plan to reach goal state from initial state given.In this example the initial state has two blocks Block1 and Block 2.Both is placed on table.To reach the goal state first we have to

 PICKUP(Block 1) 

 

We need to check whether we reach goal state or not ,after completion of each and every operation.Here the environment looks like,

Hold(block1)

Clear(Block2)

OnTable(Block2)

This is not the goal state .so ,we have to continue the process. Next the block 1 needs to be place on block 2,to achieve this do the operation STACK(Block1,Block2). After this operation the environment looks like,

 

ArmEmpty,on(Block1,Block2),Clear(Block1),OnTable(Block2)

We reach the goal state,the plan for reaching goal state is 

PICKUP(Block1) and Stack(Block1,Block2)