Compilation of Email Discussion on the topic of Graph Plan CSCE976 Spring'2002 ========================== From: "lin xu" Subject: amy 'sminus Date: Sun, 17 Feb 2002 15:02:01 -0600 Amy's minus comments 1. using different code and different machine can effect the result a lot. I still remember using C write a search code to solve some problem needs 3 s, but someone us java need 30 min. So, using different machine and coding language is not acceptable. 2. In a planning graph, there is a solution does not means there exist a valid plan. but if we can't make a planning graph with goals then there is no solution at all.After exclusion relations among planning graph nodes, we can reduce the search space. Then it will be easier to find a valid plan. And also I think there is infinite valid plans (since we can repeat some steps for ever). We can't find all valid plans. Lin ====================================== Date: Mon, 18 Feb 2002 10:32:26 -0600 From: Amy Davis To: cse976-ml@cse.unl.edu Subject: Amy's Minutes A few things that were in the comments turned in, but not included in the discussion: Graphplan is a high-commitment planner because it assigns time-stamps to an action immediatly. The paper contradicts the conventional wisdom that a least-commitment planner is the most effective. This actually enables GraphPlan to be faster. GraphPlan may suffer from scaleability problems because the size of the planning graph is O(p+mln^k) where k is the largest number of formal parameters in any operator. If k is large (operators have high arity), is could cause problems. Indeed, such problems were showed in the SATPlan paper to occur even when k was 4. The idea of "weakly complete" is used for the basic GraphPlan algorithm, which, at each step either discovers a plan or proves that no plan having that many steps or fewer is possible. The ideas of leveling-off and memoization make the algorithm more "complete" in the normal sense. One cannot judge the "sensible-ness" of a plan---it is quite subjective. However the authors claim to give empirical evidence that a plan is sensible. In the discussion we noted that the length of a plan determines its quality. This would hold for its sensible-ness as well. How were the optimizations that they implemented guided? Did they use a profiler, or just ad hoc improvements? (I doubt we can determine that from these papers). It may be possible to add heuristics that help us to focus on the goal and seek situations that are closer to the goal over ones that are far away from the goal. Because all plans are developed in the graph, this would not seem to have a large effect, but is interesting. GraphPLan employes both back-checking and forward-checking. The back-checking makes sure that the current action selected is not mutually exclusive to any of the actions taken so far, and the forward-checking checks to make sure that no future goal has been "cut-off". Has anyone implemented the ideas presented in the future-work section? If so, what have the results been? O __ || / \_ CH2 -O- C - CH2 - CH2 - CH3 \ __ / Stop and smell the Roses!