Fwd: Comments on Project 3 reports (continued)

[Subbarao Kambhampati <rao@asu.edu>]

Date: Mon, 19 May 2003 20:55:09 +0700
From: Nguyen Hong Hanh <nguyenhhanh@hn.vnn.vn>
Subject: Comments on Project 3 reports (continue)
To: "'Subbarao Kambhampati'" <rao@asu.edu>
Cc: binhminh@asu.edu
X-Mailer: Microsoft Outlook, Build 10.0.2616
Importance: Normal
X-Spam-Status: No, hits=2.3 required=5.0
        tests=HTML_40_50,HTML_FONT_FACE_ODD,HTML_MESSAGE
        version=2.53
X-Spam-Level: **
X-Spam-Checker-Version: SpamAssassin 2.53 (1.174.2.15-2003-03-30-exp)


Rao,

 

Here are my comments on the other 5 reports that I read today in between doing other things. Still two reports of Menkes and Mike that I havent read.

 

Minh

 

1. Xin:

Part I: I was surprised at the number of problems that you can solve with Sapa. As in her report, Monika (and myself with a less powerful laptop) was able to solve 19/20 problems in the Satellite domain but you solved only 12 so Im curious to know what exactly does search limit exceededmean in your table (time or memory?).

 

Part II: I was also surprise that while the numbers of actions in the solutions by Sapa and LPG for the same problems are basically the same, the makespans of solutions by Sapa is much better. I wonder if you check the solutions carefully to see if they actually composed by the same set of actions or not. Thus, Im curious to know if the different in makespan values are due to Sapas greedy partialization routine or not. I think that solutions in LPG is greedily partialized by default itself, but if its possible, please send me the set of solutions of both planners.

 

Another comment is that the complexity of your domain is virtually unchanged from its classical version. Therefore, Im a little curious about what happen if we run AltAlt to solve the classical version of this Dining Philosopher domain.

 

Your domain is similar to the Gripper domain in the first International Competition. Its harder in the sense that there is deadlock (which is not the case with the Gripper domain). You can consult the performance of different planners on this domain to see what type of planners could be best for your domain.

 

 

1. J.Benton:

You pointed out correctly that Sapa is ignoring the metric field in PDDL2.1 by now. You also pointed out correctly that PDDL2.1 lacks the power to model numerical goal, which I do think is nearly as important as True/False logical goals.

 

You made very interesting points at the end of the report J. In my opinion, its true that even for domain independent planners, we are looking at the techniques that are best suitable for a large set of benchmark domains. I remember Rao one time said that given any planner, he can create a domain that just kills that planner.

 

Im not so sure what is the weakness of LPG regarding the numerical goal, but following is the email I sent to J.Benton weeks ago regarding how Sapas struggle to deal with this type of problem involving numerical goals:

 

First, I would like to say that I found nothing wrong in your domain and it's very interesting. Sapa was not able to solve it because its heuristic is basically blind in this domain. So basically what you found is an Achilles's heel of relaxed plan that ignore resource.

 

The reason is that your goal is not really a logical goal, which is basically what normal planners have to concern about. In your domain, the only action that achieves the goal is "got-goal-amount". In this action, the only important precondition is: (>= (amount-money ?p) (final-goal ?p)). However, because it's numerical precondition, there is no action in the relaxed plan that achieve it. The resource-adjustment technique will add at most one more action (beg). Thus, the heuristic values for all the state will be 1 or 2, which are very far from the actual values. Actually, if the planner has the capability to deal with numerical goals directly and you don't have to go around by adding a new action 'got-goal-amount' then it would be interesting to see if this problem persists.

 

Because the heuristic guidance is very poor in this case, it will take the planner very long long time to recover even for a simple problem. I don't know how LPG will fare, but I believe Sapa is in big trouble.

 

What I need to do later is to improve the heuristic estimate regarding to the metric value like the amount-money in this case. Thanks for finding a domain exploiting that. I hope Rao will give you high mark on this.

 

 

1. Corey Miller:

Part I: Regarding your comment that LPG got speedup by avoid building multiple lengthy relaxed planning graph. In my opinion, I dont think its the case. I think the main reason is in the implementation and datastructures used in the two planners. LPG mentioned that they developed very efficient way of managing the action graph. Note that FF using efficient implementation out-speed LPG in classical and numerical domains even though it has to build (non-temporal) planning graph for each state too. The temporal action graph in LPG is not significantly different from the non-temporal action graph it uses for the classical domains because it just put the temporal annotation on each action in the classical AG to make it temporal AG.

 

Part II: To go around the shortcoming of PDDL2.1 in supporting disjunctive goals, you can create several dummy actions that take each disjunctive goal and give the one and only ultimate goal. I doubt it myself that the original PDDL may support disjunctive goals, and if so, then does PDDL2.1.

 

For the memory shortfall, you may try to run Sapa with Javas Xmx option. I do agree that LPG is much faster by now. They have a team working on it for a long time.

 

 

1. Dan Bryce:

Part I: In other studentsreport, while Sapa return shorter solutions in term of number of actions, LPG tends to be better in term of makespan. In your report, Sapa returns better makespan value. Im not sure if students run planners with different options or not.

 

Part II: Your domain seems to be very interesting, especially regarding the plan metric. I will sure to look at it more closely later. This domain also gives troubles to Sapa and those domains are always more helpful than the ones that can be solved rather easily ;)

 

Regarding the problems of parsing error for predicates with no variable, you did receive my mail with fixed source code, didnt you?

 

1. Josh:

Part I: I think that Josh, like Dan, is a little over-generalized the comparison between Sapa and LPG into the comparison between systematic and local search approaches. One important issue is the implementation details and datastructure, which can greatly affect the running time. As mentioned above, FF in classical domains out-speed LPG. I think AltAlt can out-speed or comparable to LPG in classical setting also. Its true that the temporal setting leads to more time-consuming in building the temporal planning graph and manage the search state. However, one time I talked with Jorg Hoffman (the author of FF planner) and we kind of agree that the datastructures in Sapa can be improved greatly. The fact is that for many problems in which the numbers of search states for Sapa and FF are the same, FF is several orders faster. Until now, I have been concentrated on making everything right and had little time to make it more efficient. It will surely be one of the future works besides making it more expressive and better heuristics etc. On the other hand, the quality of solutions by LPG can be improved with its qualitysetting.

 

Part II: I mentioned above one way to overcome the predefined amount of memory by Java. For the solution analysis, I can give some insight on how LPG find solutions with dogs are fed at different locations and Sapa has dogs are fed at the same locations (I did not look at the solutions, but I guess that Sapa will feed a dog, then clean the place and then feed another dog). The reason is that both planners consider two fed-dogactions that occur at the same place to be mutex and not being able to execute parallel. I believe that in your mind, those actions are not mutex and can be executed concurrently. Because LPG consider them to be mutex, and if you recall the LPG search framework, it will limit the number of level and do limited search over that fixed AG before extending the graph. Because the only solution according to LPG with the number of level restricted is to feed dogs at different places, it will return those solutions. If you modify the action description so that those actions can be executed concurrently by LPG, I think that it may find your desired solution.

 

For Sapa, things happen differently, I think that applying actions feed(dogX,locationY)will have  similar, if not the same heuristic value for a given dogX and any locationY. Thus, it will try to feed all dogs at locationY and Y will be the first location in your problem file (if all the locations appear the same in your problem). After applying feed(dogX,locationY). Sapa may try to clean the place and feed another dog.

 

You are right that if the post-processing phase is improved (in this case, you would need to add the capability of removing irrelevant sweepactions) then the plans by Sapa can be very close to optimal.

 

1. Menkes:

 

 

1. Mike: