One of the reasons state space search cannot exploit subgoal
independence is that from a given initial condition, once an operator,
O-1 is applied all plans that result from this path MUST have O-1 as
the first operator (in that direction).



What is needed is a method to decide which steps should be part of a
plan BEFORE deciding their exact position within the plan. 
State space methods can't do this since they need to fix the position
of oprators to fix the state. 

Instead, we have to organize our search in the space of plans

So consider a method that starts with a "NULL plan" and ends with the
desired plan:


	 _______		    ________
	| t(o)	| ---------------> | t(inf) |  on(A,B)
	 -------		    --------   on(B,C)
	 
As operators are selected for inclusion they must occur between t(o)
and t(inf).  t(o) can be thought of as an operator that has no
preconditions, only effects.  t(inf) can be thought of as an operator
with no effects, only preconditions.


Building a plan:
---------------------- SLIDE -------------------------------

	 _______		    ________
	| t(o)	| ---------------> | t(inf) |  on(A,B)
	 -------	|	    --------   on(B,C)
			|
			|
			V
	 _______       ________	     ________
	| t(o)	| --->|t1:     |--> | t(inf) | 
	 -------      |	puton  |     --------   on(B,C)
		 Cl(A)|(A,T,B) |=============>  on(A,B)
		 Cl(B) ________	 (clausal)
		on(A,T) |
			|	 
			V
	               ________	        ________
	    /-------->| t1:    |-----> | t(inf) | 
	   /   on(B,T)|	puton  |      / --------   
 _______  /	 Cl(B)|(A,T,B) |==============> on(B,C)
| t(o)	|/	 Cl(C) ________	    /	    ==>	on(A,B)
 ------- \			   /	   /	
 	  \			  /	  /
 	   \			 /	 /
 	    \	       _______  / 	/
	      ------->|t1:     |       /(clausal)	
	              |	puton  |      /	     
		 Cl(A)|(A,T,B) |======
		 Cl(B) ________	
		on(A,T) |
			|
			|
			V
			
			
	(O.K... that's enuff)			   		
---------------------------------------------------------

THe general idea is to work on the preconditions of each of the steps,
and establish them (with the help of effects of steps that are
currently in the plan, are those that are new steps in the step
library).


As each operation, for example puton(A,T,B) is inserted between t(o)
and t(inf) we know only that any successful plan must have
puton(A,T,B) in it. We are not restricting the position within the
plan.


It does not matter in what order you pick goals to be acheived.

Termination condition: Every precondition has a link supporting it.
None of the clausal links are violated.

When you are done the plan is a "topological sort" of the operations
added to the original null plan.

Next class will discuss the algorithm that performs this Plan Space Search.
(See slide below)

The search algorithm for building the plan is given below.

Note that a plan is a structure 
 < steps, orderings, links>

where link is a structure

 <step1, cond , step2> [with the meaning that the precondition cond of
                        step2 is being given by an effect of step1]

---------------------- SLIDE ------------------------------
Search:
0 - Pick a partial plan P from the search queue

1 - If all the preconditions of all the steps of P have causal links, and all
    are safe, terminate
    
2 - If P is order inconsistent, fail

3 - Pick SOME precondition "c" of some step "s" that is not supported.
	Add a new or old step s' to support it.
				c
	Plan <-- Plan + s' + s'---> s + (s'<s  a(o) < s' s'<a(inf) )

4 - If there is a link which is "threatened"
		c
	i.e. s'----> s where s'' can come between s' and a and delete c
	
      either
      	a) Promote s'' (i.e. Plan <--- Plan + s'<s'')
      	b) Demote s'' (i.e. Plan <--- Plan + S''<s')
      	
5 - Go back to step 0
------------------------------------------------------------

 

Plan Space Planning
	Also called 
		1) Partial order planning -- since as plans are created,
			the plans may not be fully ordered as compared
			with state space planning methods.
		2) Least commitment planning -- since actions are kept
			in mind for use, but there does not need to be
			a committed order.

--
 Each partial plan can be represented as a structure (tuple)
    < Steps, Orderings, Links > 
    Where the steps correspond to the various actions that comprise the 
    plan
    
    The orderings specify a (partial)ordering relation between the steps
    
    and the Links specify a set of causal dependencies between the 
      effects and preconditions of various steps
      
       A link can be seen as a structure 
         < Step1 , Condition, Step2>
           Where an effect of step1 is being used to satify the condition
            "Condition" of Step2.



Planning starts with a null plan that contains two dummy steps 
called t0 and tinfinity, corresponding to the beginning and end of the 
plan respectively. t0 is ordered to come before tinfinity. t0 is assumed 
to have as its effects all the conditions of the initial state of the 
problem, and tinifty is supposed to have as its precondtions all the 
conditions of the goal state.

Example (blocks world):
problem, where you have a A, B and C on table in the initial state, and 
we want On(A,B), and On(B,C) in the goal state. 

Given t(0) ------> t(infinity)

Where
	t(0) has  as its effects all the conditions that are true in the initial
	           state of the problem 
		on(A,T)
		on(B,T)
		on(C,T)
		cl(A)
		cl(B)
		cl(C)

	t(infinity) has as its preconditions all the conditions that are required
	             in the goal state.
		on(A,B)
		on(B,C)

Graphical representation:

                                                  |A|
                                                  |B|
  |A|  |B|  |C|                                   |C|
-----------------                           ---------------

      t(0) ----------------------------------> t(infinity)


----Planning process

The basic step in plan space planning is to pick a precondition C of some 
step S of the plan and considering ALL POSSIBLE WAYS OF ESTABLISHING IT 
(Making it true).

To establish a precondition C of a step S, we can 

 [1] either introduce a new 
step S', that has C as its effect, into the plan, and order S' to come 
before S (and after the intial step t0). 
TO remember the establishment, we also add a link <S' , C , S>

 [2] or take an existing step S'' in the plan, that has an effect C, and 
     use it to satisfy the precondition of S (if S'' is not currently 
     ordered to come before S, introduce  an ordering between S'' and S
     [remember that the ordering in the plan is
     partial--not total--so although S'' and S are both in the current 
     partial plan, they may not be ordered with respect to each other])
     To remember the establishment, we add the link <S'', C , S>
   

Once each precondition is established, and none of the establishments are 
violated, we terminate and return the partial plan. Any topological sort 
of that partial plan will be a sequence of actions that will take the 
agent from the initial state to the goal state.

For each way of establishing the condition, create a new partial plan and 
put them all in the search queue


	puton(A,T,B)    
	puton(A,C,B)

Either of these two can give on(A,B), so make two plans, each of them 
corresponding to using one of the actions


============================================================================

Graphically, we can represent each search node like the following:

                                     on(A,B)
                                 /-------------\
                  |----------------|            \
     t(0) ------> |  puton(A,T,B)  | --------> t(infinity)
                  |----------------|

where it is shown that t(0) precedes puton(A,T,B) which precedes
t(infinity), and that puton(A,T,B) yields the desired result of on(A,B)
that is a condition for t(infinity). There is a link <puton(a,t,b) , On 
(A,B), tinfity> 

============================================================================

What is the content of a search node?  A search node is a partial plan.
A partial plan is a structure (tuple) as follows:

	P: <steps, orderings, links, step-action mapping>

Where
	Each step has 
		1) Add list
		2) Delete list
		3) Precondition list
		(note that t(0) is a special case that only has an
			add list, and t(infinity) is a special case
			that only has a precondition list).

	Orderings may have such items as
		t(0) < t(infinity)
		t(0) < puton(A,T,B) < t(infinity)
		Note that orderings need not be complete until the end.
		Every ordering is either causal (to create desired
			results) or a safety ordering (to avoid 
			conflicts in preconditions).

	Links are a set of tuples that consist of
		link: <source, destination, conditions>
		Where source and destination are step names and the
			conditions are things like on(A,B) that must
			hold to get to the destination step (destination
			preconditions).

	Step-action mappings handle two identical action steps, such as
		puton(A,T,B) and puton(A,T,B).  These mappings assign a
		unique "step name," such as t5, to each discrete step.


Each search node contains one of these partial plans, which may look like
the following:

<
	(t(0), t(infinity), t(2)), 
	{t(0)<t(1), t(1)<t(infinity)}, 
	{<t(1), t(infinity), on(A,B)>}
	{t(2) --> puton(A,T,B)}, 
>

***Any condition not supported by a causal link is called an open condition.

============================================================================

An agenda lists those conditions that need to be satisfied, and is a set
of ordered pairs consisting of a precondition and a step, such as

{	
	(on(A,B), t(infinity)),
	(on(B,C), t(infinity)),
	(cl(A), t(1)),
	(cl(B), t(1)),
	(on(A,T), t(1))
}

The search has a solution when the agenda is empty and there are no conflicts
in the causal links.

-------------
CONFLICT
--A causal link <S', C, S> is said to have a conflict with another step 
S'' in the plan, if S'' can come between S' and S and can delete C. 

In such a case, the conflict is resolved by either ordering S'' to come 
before S' or after S. 
-------------
Note that if existing steps are used to get to multiple goals, the agenda
will not increase (the agenda increases whenever new steps are introduced).


============================================================================

To pick a good plan, use heuristics
	State space:  can use the difference between the current state and
		the goal state (number of conditions to be satisfied)
	Partial plans:  like f = g + h from A* search, g can be the current
		number of steps in the plan, and h can be the number
		of open conditions on the agenda.

Note that with partial plans, the order in which plans are created (which
agenda items are addressed first) is orthogonal (unrelated) to the order 
in which goals get achieved during execution.  

Each of the pieces of a partial plan is like a constraint, and a solution
is generated by taking a topological sort on the plan.

This is also called Refinement Planning, since a partial plan is
refined by adding constraints to it.

 [Another way of seeing it is that a partial plan is a stand-in for the 
 set of ground operator sequences that are consistent with its constraints.
 
  For example the plan t0 --> puton(A,T,B) --> tinfty is a shorthand 
  notation for ALL the operator sequences that have puton(A,T,B) as one 
  of their elements. 
  
  Adding further step, ordering, binding and link constraints ot the 
  partial plan reduces the number of ground operator sequneces that are
  consistent with it. Eventually, the number of sequences consistent with 
  it will become so low that we can pick one of them as the solutions for 
  the planning problem]]
  

============================================================================

WE CAN HANDLE GOALS OTHER THAN GOALS OF ACHIEVEMENT.

	Handling goals not associated with just the final state:
		1)  Maintaining goals across states
		2)  Preventing conditions from occurring.
		Example, when flying a plane, we always want to have gas
			in the tank, and we never want to run out of
			gas or crash. This is a goal of maintenance. 
			
			

		This can easily be handled by adding condition requirements,
			such as on(C,Table) in the blocks world.

============================================================================