Grahplan an regression and IDA*

[Subbarao Kambhampati <rao@asu.edu>]

At 12:19 PM 10/9/2004, you wrote:

> Dear
> Dr. Rao,
>     I have a question about planning graph. This question
> was originally asked by William Cushing in the class. 
> The planning graphs level off, but does this happens before the entire
> state space is expanded? 
> My thinking says that the planning graph will expand the entire search
> space before it levels  off? Am I correct?

Yes, I remember this question.

First off, I think you want to ask about what happens when PG
_terminates_ (i.e., has no new memos between
two consecutive levels) not when it levels off. 

What we can say is that the  planning graph will not terminate
terminate without expanding the entire search space that is both
reachable
from initial state and relevant from goal state. 

To see what is going on you need to realize that

   1. A progression search will cover the entire reachable
space
   2. A regression search will cover the entire relevant space
(i.e., space reacable from _goal state_)
   3. Graphplan is doing  an iterative deepening
regression search (IDA* regression), were the iterations are generated in
the forward direction and search is done in the backward direction. [In
IDA* terms, the planing graph construction phase is giving us the equi-f
contour; regression  is used t search it]

 In the forward phase, the PG is finding envelopes for states that
are reachable in k steps from the init 
state. In the backward phase, the graphplan is doing regression search
within this k-envelope. If the search fails, he 
envelope is extended to k+1 and regression is done again. 

Given this, it is possible for graphplan to terminate without expanding a
node that is reachable but is not relevant (which still does not
affect
completeness). 


[You can get a more elaborate explanation of this in the paper 
http://rakaposhi.eas.asu.edu/SKambhampati00.pdf 
(read from the seventh page first column bottom---from the para
starting "In fact, it is
easy to see that modifying the Graphplan algorithm
in the following ways gets us a Graphplan-variant that
is essentially isomorphic to a state-space regression planner
using dis-based heuristics:"  }

You can also look at
section 2.2 alone in
http://rakaposhi.eas.asu.edu/pegg-jair-latest.pdf


>  
> I also wanted to say something about additional constraints for planning
> problem. 
> I feel additional constraints can be useful if they decrease the search
> space more then decreasing the feasible solution space.

Yes. In particular, the "deductive closure" constraints (of the
kind we get by constraint propagation)
 have the property that they do not rule out any solutions, and just
tighten the search space. 

>  
> But, in those circumstances calling them constraints is subjective and
> highly debatable!
>