Note taker:     Tuan Chi Le (lctuan@asu.edu)
Date:           2 Feb 2000
Subject:        Cont'd on CONJUNTIVE REFINMENT PLANNERS
In exchange with Eric <dimperio@asu.edu>.

                Pls. comment. Thanks!
----------------------------------------------------------------------------------

Started from the slide: "Plan Space Refinement: Example 2"
Ended with the slide: "Interleaving refinements"
Recommended reading: PAGES 78-84 of Dr. Rao's paper 
        "Refinement planning as a Unifying framework for plan synthesis"

----------------------------------------------------------------------------------

Plan-Space Refinement (PSR) gives the flexibility in easing the choice of
exact position of actions as required in Forward & Backward state-space 
refinement strategy. This way of flexibility brings to the PSR the benefit of
least
commitment but it will loose the advantage of predicting the states of the
real 
world, smaller candidate set size that are inherent in state-space refinement
strategy.

The PSR strategy will start by taking any precondition of any step in the
plan and introducing constraints to ESTABLISH a commitment that the
preconditions must provided by some steps. This is not enough, the
establishment will need to be preserved by intervening steps after
establishment (preservation preconditions). This process of enforcement is
called de-clobbering. The
de-clobbering can be done thru 3 ways of Promotion, Demotion and
Confrontation. The first slide (PSR: example 2) is an example of doing both
establishment and de-clobbering taking from the rocket domain. Book-keeping in
PSR can be optional. The question is that book-keeping can increase the speed
of planning. The answer is unnecessary.

As the second slide "Position, Relevance and commitment" described, the
state-space strategy requires both position and relevance of actions due to
the knowledge of the evolution of states of the world, hence reduce branching
factors by eliminating unnecessary branching. The plan space allows
more possibility in positioning. But this will lead to a trade-off paying
more on plan-handling cost due to the candidate set size increasing.

The 3rd slide "Generating Conjunctive Refinement Planners" gives a general
algorithm of refinement. This will use 1 among 3 categories of tractability
refinements: attempting to make all linearization safe with respect to
auxiliary constraints (pre-satisfaction refinement). Here we make an
assumption
that (for conjunctive planers) planners will solve a conjunctive goal problem
by solving individual sub-goals serially. By using this category of
tractability refinement, if we know safe linearization, we can know minimal
candidates, and hence we can know solutions.

Tractability refinement: As mentioned above, there are three categories of
tractability refinement: 1) Reduce the number of linearization by using
pre-ordering
or pre-positioning; 2) Make all linearization safe by using pre-satisfaction;
and 3)
reduce uncertainty in action identify (e.g. pre-reduction refinement as in
HTN planning). In de-clobbering promotion and demotion could be not safe!


UCPOP: open conditions are ones that do not appear at the end of causal links
Open condition can destroy planing constraints. Unsafe IPCs can kill
causal links. UCPOP is an example of conjunctive planners using incremental
solution check and tractability refinement. In UCPOP, plan refinement, that
corresponding to steps 2.1 & 2.2 can be independently implemented with
removing unsafe IPS (step 2").

Many variations on the theme: This table provides options (book keeping),
categories of tractability refinement strategy and termination conditions and
the way goal is selected in various planners. The readers can find more
details in [Kambhampati, Knoblock, Yang. 1995].


Interleaving Refinement: One interesting point of unifying view of planning
is that, different refinement strategies can be included in a planner,
possibly for different planning problems that can bring more efficiency than
in the case of using only using any single refinement strategy (each
refinement strategy corresponds to different way of narrowing down candidate
sets). This is a still open question how to implement a planner with this
interleaving refinement strategies. The criteria for selection of refinement
strategies for different phase in refinement period of a planer can be based
on the number of components produced by each refinement, or the progress
factor that each refinement strategy at each phase affords.

Next issues: heuristics for conjunctive planners, disjunctive planners