Finally discovered a bug that was preventing plan being formed on Logistics Domain. The bug was that the object of derived classes in a condition were not used (objects of only the class in the condition were being used) in action instantiation. For example, to move from depot to depot, a truck would never go to an airport since airport is not of depotType, but of the derived class airportType. Fixed in svn revision 404.
I am finding out that I need to write even more, not less before starting to code. It will shorten the total time spent in implementation.
Another problem left to fix now is that if there is a long lasting action like FlyAirplane of duration 100 (other actions are of length about 10-20), the action never gets an interval to get inserted. This is because there is no heuristic that takes care to create space for inserting an action.
Thursday, April 16, 2009
Wednesday, April 15, 2009
GUI Design
http://stackoverflow.com/questions/42793/gui-design-techniques-to-enhance-user-experience
A figure like http://www.adaptive-planning.com/images/mpp.jpg would be quite explanatory about the functionality of the GUI.
Audacity is an open source GUI using wxWidgets. The source can be useful in constructing our GUI.
PAC + MVC + Mid-way Pull-Push model.
For visualization, can use force-directed layout. VTK. has vtkGraphLayoutView. The excellent Boost.Graph library provides a wide range of algorithms, among which a few layout algorithms. I'd recommend using either Kamada-Kawai spring layout or Fruchterman-Reingold force-directed layout. neato from graphviz also implements force-dir layout. This guide includes using the fdp layout algorithm, which appears to be exactly what you want. All of graphviz falls under the Common Public License.
A figure like http://www.adaptive-planning.com/images/mpp.jpg would be quite explanatory about the functionality of the GUI.
Audacity is an open source GUI using wxWidgets. The source can be useful in constructing our GUI.
PAC + MVC + Mid-way Pull-Push model.
For visualization, can use force-directed layout. VTK. has vtkGraphLayoutView. The excellent Boost.Graph library provides a wide range of algorithms, among which a few layout algorithms. I'd recommend using either Kamada-Kawai spring layout or Fruchterman-Reingold force-directed layout. neato from graphviz also implements force-dir layout. This guide includes using the fdp layout algorithm, which appears to be exactly what you want. All of graphviz falls under the Common Public License.
Tuesday, April 14, 2009
Contract Algorithms for Cost Repair
The following is based on planning group discussion on 14th April 2009. The text is copied from Eric's email.
We discussed possible approaches to solve the problem of selecting a heuristic among a group of heuristics given certain constraints. In this case, we want to solve the problem of Anytime planning -- producing a plan given a certain amount of time.
One approach is: each heuristic exposes certain parameters to aid in the selection. For example, if there are three heuristics available, and their parameters given are as follows:
Time Quality
Heuristic 1 1 5
Heuristic 2 5 30
Heuristic 3 10 70
Given infinite amounts of time, one trivially selects Heuristic 3 to attain the highest quality every time. However, given a time constraint (say, the planner asks for a quick replanning to be done in 5 time units only), we certainly have to choose Heuristic 2.
Another tactic (suggested by Eric) is to simply ask the heuristic for a quality rating, given that the planner has to produce a plan in n time units. The quality reported would be 0 for those heuristics that cannot finish within n time units.
Other parameters that may be inserted in the future include a reliability rating of the time/quality estimates that each heuristic exposes, or how many processors are needed by a heuristic to perform its task. Amit said this is non-trivial but not so important, and we can set this aside for later. It is noted that the reliability rating might be needed for times when the quality of a heuristic is not yet proven -- in which case, given 5 time units and Heuristic 2 has a reliability rating of 0 while Heuristic 1 has a reliability rating of 100, then Heuristic 1 would still be chosen because, given the limited amount of time, we might need some assurance that the heuristic will complete (and Heuristic 2 has not been proven yet, so it would be too risky to choose it).
For future expandability, Eric suggests that we can probably design a contract system where the planner gives n parameter restrictions given m possible parameters, and the heuristics report on actual estimates on all m parameters. For example, the contract may be to "produce the highest quality solution in maximum x time" or "produce the quickest solution with the least amount of processors involved" or "produce the best quality solution with no time restrictions" (in the latter case, we would obviously still choose the heuristic that performs fastest, and so each heuristic must still provide estimates on all available parameters).
The problem with all these approaches is that quality is not clearly defined. Sima points out that we cannot assign "quality" parameters in this way alone because the quality of a given heuristic may vary over the current state of the plan. Amit points out that determining which parts of the plan have an effect on the state may be problematic to define -- there might be certain attributes common to all plans that correspond to this state, and some that are domain-dependent.
Also, the actual amounts of time each heuristic will take are estimations only. Amit suggested that we keep historical data on the amount of time a heuristic took to execute previously.
Would also like to point out our discussion that instead of passing just Time as an additional parameter to the contract call to heuristics, it would be better to abstract the additional parameter one level up. Time and quality are about the cost-benefit of using the heuristic. So better pass a CostBenefitParameters object that contains information about time the heuristic takes, expected solution quality improvement and so on. The benefit is that we may use few or many of these parameters (for example, just time, or alternatively, time and solution quality) under the same class name.
We discussed possible approaches to solve the problem of selecting a heuristic among a group of heuristics given certain constraints. In this case, we want to solve the problem of Anytime planning -- producing a plan given a certain amount of time.
One approach is: each heuristic exposes certain parameters to aid in the selection. For example, if there are three heuristics available, and their parameters given are as follows:
Time Quality
Heuristic 1 1 5
Heuristic 2 5 30
Heuristic 3 10 70
Given infinite amounts of time, one trivially selects Heuristic 3 to attain the highest quality every time. However, given a time constraint (say, the planner asks for a quick replanning to be done in 5 time units only), we certainly have to choose Heuristic 2.
Another tactic (suggested by Eric) is to simply ask the heuristic for a quality rating, given that the planner has to produce a plan in n time units. The quality reported would be 0 for those heuristics that cannot finish within n time units.
Other parameters that may be inserted in the future include a reliability rating of the time/quality estimates that each heuristic exposes, or how many processors are needed by a heuristic to perform its task. Amit said this is non-trivial but not so important, and we can set this aside for later. It is noted that the reliability rating might be needed for times when the quality of a heuristic is not yet proven -- in which case, given 5 time units and Heuristic 2 has a reliability rating of 0 while Heuristic 1 has a reliability rating of 100, then Heuristic 1 would still be chosen because, given the limited amount of time, we might need some assurance that the heuristic will complete (and Heuristic 2 has not been proven yet, so it would be too risky to choose it).
For future expandability, Eric suggests that we can probably design a contract system where the planner gives n parameter restrictions given m possible parameters, and the heuristics report on actual estimates on all m parameters. For example, the contract may be to "produce the highest quality solution in maximum x time" or "produce the quickest solution with the least amount of processors involved" or "produce the best quality solution with no time restrictions" (in the latter case, we would obviously still choose the heuristic that performs fastest, and so each heuristic must still provide estimates on all available parameters).
The problem with all these approaches is that quality is not clearly defined. Sima points out that we cannot assign "quality" parameters in this way alone because the quality of a given heuristic may vary over the current state of the plan. Amit points out that determining which parts of the plan have an effect on the state may be problematic to define -- there might be certain attributes common to all plans that correspond to this state, and some that are domain-dependent.
Also, the actual amounts of time each heuristic will take are estimations only. Amit suggested that we keep historical data on the amount of time a heuristic took to execute previously.
Would also like to point out our discussion that instead of passing just Time as an additional parameter to the contract call to heuristics, it would be better to abstract the additional parameter one level up. Time and quality are about the cost-benefit of using the heuristic. So better pass a CostBenefitParameters object that contains information about time the heuristic takes, expected solution quality improvement and so on. The benefit is that we may use few or many of these parameters (for example, just time, or alternatively, time and solution quality) under the same class name.
Sunday, April 12, 2009
Implementation Diary: April 13, 2009
Recently I performed experiments for a paper I submitted to MIC 2009 conference. More on this later. There are still issues with solving problems in Logistics domain. The simpler cases are already done: like shipping packages within the city.
To further investigate why plan was not being formed for 4 packages, I simplified the problem to involve just one package: this is shipped from one city to another. Yesterday, after changes, the plan to ship package to the airport in another city was able to be produced. (The change was to avoid stuckness of search into one configuration that resulted in no change in plan after a certain number of iterations - the stuckness occurred in case of goal condition when none of the heuristics were left applicable).
Still, plan is not being formed in case when a package is to be transferred to a depot (not airport) in another city.
To further investigate why plan was not being formed for 4 packages, I simplified the problem to involve just one package: this is shipped from one city to another. Yesterday, after changes, the plan to ship package to the airport in another city was able to be produced. (The change was to avoid stuckness of search into one configuration that resulted in no change in plan after a certain number of iterations - the stuckness occurred in case of goal condition when none of the heuristics were left applicable).
Still, plan is not being formed in case when a package is to be transferred to a depot (not airport) in another city.
Subscribe to:
Posts (Atom)