[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Fwd: A little more on white-knight clause..
- To: "Rao Kambhampati" <rao@asu.edu>
- Subject: Fwd: A little more on white-knight clause..
- From: "Subbarao Kambhampati" <rao@asu.edu>
- Date: Tue, 22 Jan 2008 22:44:30 -0700
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; bh=OwAmvKXD+jL/xWZwDhuswRmKQjRI4f9/LNox5aSHW50=; b=PHR4hmlVA4OV38TS84yXYajuPcI4TktcwXrB8G4sqN5t2+mKAqTLwaqNm4BpnXEfSNwJ3sYr2L6rRs+9ul8tQAcJi9LCsLKon12baMbFG1tD1lKHOtf1SP+WvegwhxE7GkKuJWjdBMFrEk90rzMi08wxlOyFnl+ZqSqXg94lfXk=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:sender:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; b=XPRIcsJmJCvzovPcolvj/AavDHELktcdVjc9tnRmggDvWKNITrmRcm1F3zzDDiP7u+FyDslRdR3h2aATtAjgSHBB5yNT7W6Pgz8jwGaI4PYys152moHbnibSh/ioTpNy1udAunDr8rUS/aOtK5YUqv4vrAX9oWG4ok4udrhhvRw=
- In-reply-to: <8d80847a0801222143y4dede89fy9168660a8aa9db04@mail.gmail.com>
- References: <8d80847a0801222143y4dede89fy9168660a8aa9db04@mail.gmail.com>
- Sender: subbarao2z2@gmail.com
After class, Tuan and Kartik had a ton of questions on the infamous
white-knight clause. Here is a gist of that discussion for general
edification. (Tuan--you can copy this over to your scribe notes as
necessary).
The term white-knight comes from the "White knights in shining armor
rescuing damsels in distress".. The white-knight step intervenes
between the threatening step and the step needing the condition and
re-establishes the condition.
*NOTE* that while white-knight clause is needed to prove correctness
of arbitrary partial order plans, it is *NOT* needed to ensure
completeness of plan-space planning (which, like progression and
regression, only needs to generate all action sequences that can solve
the problem). While the plan-space planner I discussed in the class
will never be able to terminate with the white-knight example plan
(because there is no way to come up with an un-threatened causal link
for that plan), it is able to terminate with two different
specializations (refinements) of that plan--such that every action
sequence that is a top-sort of the white-knight plan is also a
top-sort of one of these refinements.
*IF* for some strange reason, you do want your plan-space (partial
order) planner to terminate with the white-knight plan, then you need
to generalize the semantics of causal links such that you have three
ways of resolving a threat. Specifically, if a causal link s1--p--s2
is threatened by a step s3 (which has effect ~p), then, we have three
resolution possibilities:
1. Promotion: put s3<s1
2. Demotion: put s2<s3
3. White-knight "de-clobbering"
Find a step s4 (either existing in the plan, or from the library)
such that s4 has effect p.
Introduce ordering s3<s4<s2
(so s4 comes between s3 and s2)
As mentioned above, the white-knight declobbering is unnecessary for
completeness in the space of action sequences.
It is also worth noting that when you allow white-knight declobbering,
you are essentially changing the semantics of the causal-link
constraint. Without declobbering, we in essence say that once
established, the causal link condition *CANNOT BE VIOLATED EVEN
TEMPORARILY*. Allowing declobbering means you can allow it to be
temporarily violated.
[Maintenance goals] Sometimes, plan-space planners use causal links to
model *Maintenance* goals. (The normal goals we saw until now are
goals of attainment--i.e., the conditions must be true at the end.
Sometimes, you also have goals of maintenance--all through the
execution of the plan, a certain condition must hold true. For
example, if you want to walk through a dark basement garage to the
fuse box to reset the fuse, then you need light to help you navigate
the garage. This light must be on pretty much all through the
execution of the plan. This kind of semantics will not be respected by
white-knight declobbering.
[White-knight and Chapmans Modal Truth Criterion;] White-knights
entered planning vocabulary through an (unfortunately) influential
paper from 1987 by David Chapman.
I stored a copy at http://rakaposhi.eas.asu.edu/cse574/notes/chapman-mtc.pdf
for your edification
This paper was unfortunate in that it (1) confused plan-space planning
with the need for being complete in the space of partial plans (which
as I pointed out is *NOT needed*) and (2) consequently assumed that
per-node complexity in plan-space planning will be influenced by the
cost of checking correctness of a partially ordered plan. Another
wrong assumption that Chapman made was that plan-space planners *MUST*
deal with partially instantiated partial order plans (this is the
*lifted planning* I started talking about).
Since a PO Plan can have an exponential topoligical sorts, and many
more ground topological sorts, it is not surprising that checking the
correctness of all those topological sorts can potentially be
exponential.
Chapman's +ve result was that *if* actions have no conditional
effects, and all variables are considered to have *infinite* domains
(which is a bogus assumption), then correctness can be checked in poly
time (note that this requires the white-knight clause). His negative
result was that once you have conditional effects, the correctness
check will be NP-complete. He somehow made this sound as if it was
the end of the world (and the planning community, for its part, went
along with it). On scholar.google.com, you see that Chapman's paper
has had 845 citations--most before 1991..
http://scholar.google.com/scholar?q=chapman+modal+truth+criterion&hl=en&lr=
The third paper in that page--written some 7 years after Chapman's
paper--brings up some of these critiques.
Rao
ps: What is wierd about Chapman's paper is that Chapman should have
known better. 10 years before his work, the planner "Nonlin" was
developed by Austin Tate and it saw farther (the plan-space planner we
discussed today is closer to 1977 paper by Tate than anything in
Chapman's 1987 paper). Apparently Chapman did talk to Tate but somehow
Tate's work is not cited prominently. Checkout
http://rakaposhi.eas.asu.edu/nonlin-review.txt
for an opinionated review of this whole episode..