[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Thinking topic]: Completeness and minimality..
- To: "Rao Kambhampati" <email@example.com>
- Subject: [Thinking topic]: Completeness and minimality..
- From: "Subbarao Kambhampati" <firstname.lastname@example.org>
- Date: Mon, 21 Jan 2008 15:31:27 -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:mime-version:content-type:content-transfer-encoding:content-disposition:x-google-sender-auth; bh=gHbnGEw79FwB+69lcdKA3QuIkiQivuQav0u3fDKztoU=; b=puDSuWdbCep2/x7P39EwgQKuRmySkEzZNYu1QixgjFlxXl0PrMA+nyufYiTzhHbHQ3rBkfPMfqyoRW1xXpsdDtCjvGMRiYbhGU7o8TGSAT9c9SzL5gjAD4CVkEBL6COBGGpG2aYR10i7EJXsq0sJVJ9mZQUsCQgHhEDoU25rpv0=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:sender:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition:x-google-sender-auth; b=wn69Y3jdumr8YiCw/PAUwhQgJNpehPnWRREpViT0bWW/kg5PYbPwqcYWZ8p64XZjpuIdkRYbBj+hs7MfzPMKoQgbcXNZdBVHi0Cptc/qtcnActZlibIUQAYHH39LmxW2l1kxWI8tZ9QHJu8KqY27OjuMWJgTtl7+OjOfdy7sMUM=
- Sender: email@example.com
[Part of the required participation in the class involves taking part
in the blog discussions--and giving answers to thinking topics. Here
An interesting issue about planner completeness is whether or not the
planner is capable of finding *every plan* for the problem.
Let us get some terminology straight.
A sequence of actions a1...an is considered a solution to a problem
[I,G] if we can
execute the sequence starting in state I and G will hold in the final
state after executing an.
A solution plan P: a1...an is said to be minimal if it is not
possible to remove any subset of actions from P
without violating its solution-ness.
An example of a non-minimal plan for achieving On(A,B) when A, B and C
are all on table is:
put A on C, take A of C, put A on B.
Cleraly, we can cut the first two actions out and it will still be a
solution (so it is a non-minimal solution).
Consider the following questions:
0. Given a planning problem that is solvable, how many solutions
(minimal as well as non-minimal) are there?
1. Is progression planner complete for all plans (including minimal
and non-minimal plans)?
2. Is regression planner complete for all plans (including non-minimal)?
3. Will regression planner ever find any non-minimal plans?
4. Will progression planner ever find any non-minimal plans?
5. If a planner is capable of producing non-minimal plans, then will
sussman anomaly be non-serializable for such a planner?
6. Given a possibly non-minimal plan, how costly would it be to
"minimize" it (i.e., remove redundant actions from it)?
(Complexity-wise... is it polynomial?