W3C home > Mailing lists > Public > public-sws-ig@w3.org > December 2004

Re: Planning under Description Logic ?--an obstacle towards WSAC

From: Drew McDermott <drew.mcdermott@yale.edu>
Date: Wed, 8 Dec 2004 15:19:26 +0000 (GMT)
To: lmshill@gmail.com
CC: public-sws-ig@w3.org
Message-ID: <E1Cc3bk-0000Nc-8h@frink.w3.org>


> [Manshan Lin]
> I'm wondering these days about two questions:
> 1. In planning for WSAC, we have two choices: a) planning from 
> the initial state to the goal; b) planning from the goal to the initial 
> state. Because it is hard for us to establish a complete initial state 
> before planning (the user doesn't know what information he should
> privide in advance. For example, some plans generated to buy a 
> book may require the user to provide his address, while some may 
> require the user to provide both his address and phone number), 
> b) seems to be a good choice.

The way this distinction is drawn in AI textbooks must not be taken
too seriously.  Almost all planners search a space of _partial plans_.
A partial plan is a set of design choices tentatively made.  The hope
is that that set can be extended to a complete and workable plan.  If
not, then the planner must undo some of the design choices ---
backtrack --- and try something else.

Against that backdrop we usually see reasoning patterns that could be
characterized as "forward" and "backward," often both types in the
same planner.  For example, in a classic partial-order planner a
partial plan is a set of commitments to actions to achieve some of the
subgoals discovered so far, plus a set of ordering constraints adopted
to avoid deleting a subgoal too early, plus a set of open subgoals
that still need to be achieved.  A typical operation on such a plan is
to pick an open subgoal and choose a way of achieving it.  That's
"backward" reasoning, I suppose.  Another operation is to use a goal
achieved by an existing step to achieve an open subgoal.  "Forward"
reasoning?  Another is to postpone an action that threatens to delete
an achieved action.  Is that "forward" or "backward"?  At this point
this question starts to seem a bit irrelevant.


> 2. If we choose b), the following question must be answered:
> how to recognize an input of an operation that can be provided
> by the user? if the input is the user's private information, we can
> define these kind of information in the initial state; however, if the
> information is plan specific, such as "bookname", "ISBN" in bookstore
> example, how can we recognize it? Let's consider this situation:
> an operation "o1" needs "bookname" as input, another operation
> "o2" tranfers the input "isbn" to the corresponding output "bookname". 
> How can a planner make a decision on getting the "bookname" of "o1" 
> from the user or from the output of "o2"?

In principle this is just the standard action-selection problem
(or method-selection problem in an HTN planner).  The planner knows of
more than one way to achieve "I know the ISBN of the desired book."
Way 1 is "Ask the customer."  Way 2 is o2.  The planner can choose
between them by trying out both (in simulation) and seeing which is
best.  Of course, with N such choices the planner has 2^N partial
plans to think about.  That's what makes planning interesting.

Classically the quality of a plan was simply whether it achieved the
overall goal or not.  In realistic cases we have to think about the
probability of success and the resources used.  Asking the customer
might be likely to fail, and cost some "customer annoyance" points.
Using o2 might cost time or money.  More issues that make planning
interesting.

                                             -- Drew

-- 

                                         -- Drew McDermott
                                            Yale University
                                            Computer Science Department
Received on Wednesday, 8 December 2004 15:20:00 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Sunday, 16 March 2008 00:10:59 GMT