Planning-Hierarchical Planning

Planning-Hierarchical Planning 

ABSTRIPS 

• It is a hierarchical planning system based on STRIPS rules 
• Criticality numbers are assigned by this system to every conjunct present in the precondition of STRIPS rule. 
• The criticality number is assigned based on the complexity of achieving the conjunct. If it is easier to achieve a conjunct a lower critically number is assigned to it. 
• The steps in ABSTRIPS planning are as follows, 

1. A threshold value is chosen such that the precondition which have their value less than threshold value are assumed to be true and a plan is developed based on assumption. The hardest conjuncts achievement is postponed here.
2. Now the criticality threshold is decremented by 1 and a plan is developed by taking the plan generated in step 1 as guide and assuming the precondition as true which have there criticality lower than threshold. 
3. And so on. 

• Example : Here the robot should go from one room to other. 
• The actions used in this example are, 

1. goto(r₁, d, r₂) - which represents the robot is going from rooms to room2 through door d.
2. open(d) - which specifies the door action schema of opening door.
3. In(R₁) - represents that robot is in room R₁

• The criticality numbers assigned, are represented by a circle above the literals in preconditions in Fig. 3.10.16.
• open(d) is considered as easy task and assigned a criticality value as 1.
• Let us consider all the preconditions which have their criticality 1 are true and an abstract plan is constructed.
• The goal here is In(R₃) that is the robot should be in room3. To achieve that the actions performed are,                 
• {goto(R₁, D₁, R₂), goto(R₂, D₁, R₃)} 
• Now, goto(R₁, D₁, R₂) have to be achieved first. To achieve this, its preconditions have to be achieved and after applying it the preconditions of goto (R₂, D₂, R₃) have to be achieved. 

Initial State : In(R₁) Open(D₁) Closed(D₂) 

Goal : In(R₃) 

STRIPS Rule : goto(r₁, d, r₂) 

                            (2)            (1)                (2)

Preconditions : In(R₁) ∧ Open(d) ∧ Connects(R₁, d, R₂). 

Delete List : In(R₁) 

Add List : In(R₂) 

Open(d) 

                                (1)

Preconditions: Closed(d) 

Delete List.: Closed(d) 

Add List : Open(d) 

Fig. 3.0..16 A Planning Problem for ABSTRIPS

• The operator's preconditions are known as islands.
• To have a detailed plan we decrement the threshold by 1, so in this case the preconditions of criticality 1 can also be achieved.
• It results in {goto(R₁, D₁, R₂), Open(D₂), goto(R₂, D₂, R₃)} which is the plan to be produced, open. (D₁) is given in initial state so, it is not included in the plan.
• This plan-development process is known as length first.
• In the length first method we first develop a complete plan at particular level and then we descend to other level, which is detailed, to develop the plan.
• The other methods for plan-development. 

Example: The process is, as follows,

STEP 1: In this step sequence of islands are identified in search space by developing a complete plan at top-level. 

These islands which are identified are preconditions of first-level operators. 

STEP 2: Now, the first part of the plan at next level is developed. 

The plan developed is complete just to the first island and this process continues till the lowest level complete plan is achieved for the first island at that level. 

This lowest level of detail achieved by first operator can be executed in the initial state. 

This is a type of depth-first planning and is more suitable in the cases where sense/ plan/act cycle is used. 

The entire process is, repeated after the first action is executed and its result is move used as guide in re-planning. 

• In hierarchical planning a simple problem is solved first to be used in actual problem.
• The level in a hierarchical planning is a detailed version of the level which is above it. 

Combining Hierarchical and Partial-Order Planning

• Partial-order and plan-space planning is combined with hierarchical planning by some planning systems like NOAH, SIPE and O-PLAN. 
• These planning systems helps in finding or describing the lower-level detail of abstract plans. 

Example: Consider move rule it just describes in move(P, Q, F) that, P which is on Q is moved to floor. These systems add the lower level rules like pickup and putdown 

to move rule. This can be seen in Fig. 3.10.17. 

Figure: Plan Articulation

• These lower-level rules may contain detailed pre-conditions which requires other lower level rules to be added, to complete the plan at that level. 
• The process continues until all operators consists of primitive rules that can be executed.