Newsgroups: comp.ai
Path: cantaloupe.srv.cs.cmu.edu!rochester!cornellcs!newsstand.cit.cornell.edu!portc01.blue.aol.com!portc02.blue.aol.com!howland.erols.net!cs.utexas.edu!ennfs.eas.asu.edu!ennews!news
From: rao@parichaalak.eas.asu.edu (Subbarao Kambhampati)
Subject: Re: What is non-interleaved planner?
Message-ID: <E1Hx6u.A7H@ennews.eas.asu.edu>
Sender: news@ennews.eas.asu.edu (USENET News System)
Organization: Dept. of Computer Science, Arizona State University, Tempe
Date: Tue, 26 Nov 1996 21:04:06 GMT
References: <56g90g$b5q@eng-ser1.erg.cuhk.hk> <57ckto$2m0@lyra.csx.cam.ac.uk>
X-Nntp-Posting-Host: parichaalak.eas.asu.edu
Lines: 65


[Lookee here! What do we have--an actual technical question on
Comp.ai? wonder of wonders, miracle of miracles...]

What is non-interleaved planner-- Here go my two nia-paise (tuppence...)

the answer depends upon the context in which "non-interleaving" is
used.

(non)interleaving might refer to the order in which the subgoals are
achieved by a (backward chaining, state-space or plan-space)
planner. STRIPS is a non-interleaving planner in that it completes one
top level goal and all its subgoals before it considers the next top
level goal. Prodigy is an interleaving planner in that it interleaves
the subgoals of several top level goals in achieving
them. Interleaving is necessary for ensuring completeness of a
backward chaining state-space planner, while it doesn't matter for the
plan-space (partial order) planners. Thus a planner like UCPOP or
Nonlin can either interleave or not interleave subgoals. In the case
of these partial order planners, the non-interleaving is referred to
as the LIFO goal order. Recently, some authors [Gereveni,
Schubert--see JAIR] suggested that non-interleaved operation leads to
better performance (although they are being disputed by other
authors).

(non)interleaving might refer to the order of planning and
execution--whehter planing is completed before execution is started or
whether they are interleaved. Pretty much any planner can be coaxed
into doing either interleaved or non-interleaved execution. A thorny
technical issue is that once you allow interleaved execution,
completeness is not guaranteed in general since the planner can
literally paint itself into a corner.  In some domains, interleaved
execution is "necessitated" because some of the information crucial to
the completion of the plan (e.g., the goal paint the table with a
color that is complementary to its present one-- this needs the
planner to sense the color of the table so it knows which color to use
in painting. Of course, even here sensing is not strictly required--we
can make a contingent or conditional plan which makes one plan for
each of the possible colors that the table might have and at the time
of execution, execute the right branch--but this approach can be quite
cumbersome given that there are many possible colors that the table
can have. Had the goal been "toggle the switch", such contingent
planning makes more sense.) Thankfully, most sensing actions tend not
to cause "causal change" to the environment (they instead change the
knowledge state of the agent), and thus don't affect completeness.

Finally, (non)interleaving might refere to the way different
refinements -- state space, plan-space and task-reduction-- 
are used by the planner (although it probably won't meant this outside
of the confines of ASU). Most classical planners pick and stick to one
single refinement. However, some planners (such as one called UCP that
we developed) allows interelaving of differnt refinements in a single
planning episode. This not only preserves completeness, but also can
be more efficient in some domains. 

Rao

ps: for this and other introductory issues about planning, you might
want to look at the on-line notes from ASU planning seminar 
(URL: http://rakaposhi.eas.asu.edu/planning-class.html)
----------
Subbarao Kambhampati Dept. of Comp Sci. and Engg. Arizona State University, 
Tempe, AZ 85287-5406  rao@asu.edu (email) 602-965-0113 (Phone)
602-965-2751 (FAX) 
WWW: http://rakaposhi.eas.asu.edu
