[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: "Rao Kambhampati" <rao@asu.edu>*Subject*: [Thinking topic]: Completeness and minimality..*From*: "Subbarao Kambhampati" <rao@asu.edu>*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*: subbarao2z2@gmail.com

[Part of the required participation in the class involves taking part in the blog discussions--and giving answers to thinking topics. Here is one] 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? exponential? etc)

- Prev by Date:
**Mailing list and class blog set up..** - Next by Date:
**Policies on scribing..** - Previous by thread:
**Mailing list and class blog set up..** - Next by thread:
**Policies on scribing..** - Index(es):