------------------------------------------------------------------------------------
Note on Jan 24 Class. Note taker: Minh Binh Do.
Topics: + About D.Smith paper.
       + Planning as Refirement.

Papers involved: 
1. D.Smith. "Bridging the gap between Planning and Scheduling"
2. Rao's paper: "Planning as Refinement". AI Magazine.
3. Rao's tutorial paper at IJCAI-99.
------------------------------------------------------------------------------------

First, Rao was talking about Smith's paper. He gave some comments on what's the main
motivation of the paper. Following are some of the general comment on section 1:

Overview of the paper: There are set of Planning problem that stand right between
what people has been thinking about Planning and Scheduling. There are some aspects
that future complicate those problems:
+ There are *choices* to make for a observation. Because which choice to make is pretty
much depend on the current state of instrument, we can't preprogram the solver to handle 
problem of this type.
+ There are setup costs for each action to be turned out. However, the setup costs not
only depend on which action we chose, but also on which instrument will be used to
carry out that action, and how that instrument has been used previously.
+ Each action to be carried out in this type of problem surpass the formal limitation of
classical plan, each action not only change the value of proposition, but also change
some metric resource associated with it. Moreover, they should be carried out in some
duration of time, which is not atomic.

It's not that those types of problems have never been address in the Planning community
before. There were some efforts to extend the classical planner to support discrete/metric
resource, but it's not been concentrated that much. On the other hand, there were some
efforts in the scheduling community to include action selections to there scheduler. But
there has not been any good planner/scheduler that address both problems effectively.

So, as the people in the planning community, what should we know about "resources". They
are:
+ Producable: There exist actions that increse its value.
+ Comsummable: There are actions that reduce its value.
+ Reusable: After we use it, there are action that "free" it, so we can use it later.
+ Shareable: It can be used by multiple tasks at the same time.
+ Nonshareable: When one task seize it, no other task can use that resource.
+ Limited-capacity: Has finite capacity, so there are some, but not infinite number of
task can use it at the same time. Shareable, and nonshareable are extreme case of
limited-capacity resource, when the capacity-limit is INFINITY or ZERO.

Note that not all resources have all those above aspect. Think about the "Truck" or
"Plane" in logistic domain, they are sharable and reusable. If we want to make it
more realistic by limit the number of package that one truck can carry, then we have the
limited-capacity resource. The example of Sharable/Non-reusable resource is the rocket
in the one-way rocket domain. In the serial-block world domain, the robot hand is 
Nonsharable resource. If we also consider "fuel" needed for truck to be running, then
we have "consumable" resource, and if we suppose that there are gas-station around 
the road, then fuel is producable. Actually, we can think of all kind of realistic
problem that resource have a subset of 6 aspects listed above.

Now, we may ask the question of what make the scheduling problems hard? Or what make
our planning community to only be able to concentrate on those STRIPS representation
in classical planning? According to Rao, the real problem here come from the
"limited-capacity". Rao said that in general problem, two easiest cases are when the
limit is 0 or infinite, and something in the middle always the harder one. People in 
Planning have been trying to extend classical planner to support the 
Shareable/Nonsharable, and the metric resources, but the limited-capacity sources
has not been addressed much.

After finish section 1, Rao started to talk about the issue in section 2. He mentioned
the 4 limitation of classical planning and its STRIPS representation in page 3 of Smith's
paper. He specially concentrate more in the second issue. He pointed out that there is
no clear resource "type" in classical plan. We treat "block" and "robot hand" quite the
similar ways. They are both objects in classical planning, other than of totally different
types. What happen if we increase the number of robot hand in the block problem, the
common sense tells us that we should be able to solve the problem much easier. However,
Graphplan and most of other classical planner can't realize that they are all of the same
type, which lead to the symmetry in using them for the same action. We can't realize that
the failure with one hand will happen again when we try the same action with other hand,
and we pay the price for not consider resource separately from objects. For the deeper
discussion on tearing resource apart from object, and treat them differently, there is
a good paper from Biplav in ECP99. Rao also mentioned about the difficult in dealing with
"goal of attainment" and "goal of maintenance" in planning. We can't do it in classical
planning, because there is no notion of time. What happen if we want to achieve some goal
by some deadline (e.g 4 PM). Some specific type of goal of maintenance can be achieved,
but goals involve time are the most difficult ones to deal with.

Aftter section 2.1.1, Rao concentrate more on the stuffs in the IJCAI-99 tutorial, because
it's more thorought and clearer than what's in section 2.1.2-?. First, Rao was more into
how to model the classical planning, he divide all current methods into two general types
Conjuntive Planning and Disjuntive Planning. In Conjuntive Planning, the set of 
constraints that we need to resolve to get a solution is only the conjuntion of 
primitive constraints, there is no disjuntive constraint in that set. In the disjuntive
planning, in addition to primitive constraint, we also have disjuntive constraints. The
second issue is how to repsesent the planning problems. We aldready know about the STRIPS
representation, which is discussed in section 2.1.1. The extended version of STRIPS is
called ADL, in which we allow the universal quantification (for both preconds, and effect)
and existence notation for effect. Note that we can't allow existence for the effects,
because then we won't be able to make the effect of action to be deterministic. The next
issue in the classical planning is how to check the correctness of the solutions. There
are two general ways:
+ State-based proof: Which is future separated into forward checking, and backward
checking.
+ Causal proof.

For causal proof, we have to make sure that for each condition, there exist preceeding
step that support it (Establishment condition), and no possible interventin step delete
it (Declobbered). There are some characteristics of causal proof as listed as following:
+ It;s local: We only try to resolve one condition at the time. There is no notation
of state (which is the conjuntion of proposition) in causal proof/causal encoding.
+ State-less: Action/Step doesn't need to know the state before each condition be 
established. Therefore, we dont' need to know actions in sequence, there are only partial
order between them. There is no "state sequence" established as the result of apply 
each action/step.
+ Incremental: With respect to the action insertion.

With all those partial ordering characteristics listed above, people have been arguing
that it's easier to extend causal planning (than state-based planning) to handle
resource.

Rao in his tutorial give a more generalized view for all three types of planner. He
argued that they are all special case of a refinement search in space of partial plan,
if we only put a actions cemented to the initial condition (prefix), then we will get
the forward state-space planner. On the other hand, if we only put them stick to the
goal end, then we will have backward state-space planner. The third option, if we allow
action to be anywhere in between, then we will have what people call plan-space planner.
Actually, Rao developped the Universal Planner, which combine the feature of all of
the three types of planner, he allow it to add actions prefix, suffix, or anywhere in
between. However, this planner needs more sophisticated heuristics in not only the problem
of which action to choose, but also on the decision on where to put the action in the
partial plan.