This entry does not have to do with Planning, but some softwares we are using.
Users of svn know that "svn merge" is often troublesome. Recently I was trying to merge some code from branches using the reintegrate option. I understand this makes use of some new feature introduced in svn 1.5. However, when I tried using "svn merge --reintegrate" it failed complaining that the server does not have mergeinfo. The sourceforge repositories have to be manually upgraded using "svnadmin upgrade" as described here.
Saturday, May 15, 2010
Wednesday, October 7, 2009
With What Probability Should a Change be Selected?
A change is a modification of the plan. Suppose we have $n$ candidate changes $c_1, c_2, ..., c_n$. Each change $c_i$ has an associated measure of distance $d_i$ from the ideal fit.
The question is to design a function $f(x)$ such that the selection of change $c_i$ with probability weight $f(d_i)$ is a "good selection strategy" [1]. An example of a "not-so-good strategy" is $f(x) = 1/x$ -- if $n$ is large and there are several "poor" $c_i$s each with large $d_i$, the cumulative sum of $f(d_i)$ corresponding to these poor $c_i$s is still large. This means that there is a large probability that a poor change will be selected.
$f(x) = 1/x^a$, $a = 3$ for example, is expected to perform better. Another candidate is $f(x) = 1/(1+a)^x$, $a = 0.25$ for example. [2] Empirically the last $f(x)$ seems to perform well in practice. Still better we would like that when some $d_i = 0$ then one of such $c_i$ is definitely selected. For this we can modify $f(x)$ to be $1/(x*(1+a)^x)$.
However more work is need to precisely discover the invariants of the good selection strategy.
[1] Due to stochastic nature of selection and the complexity of changes it is difficult to define "good selection strategy". One way to define it is to state specific examples, and expected weight ranges from the $c_i$. More work is needed to define it.
[2] The appropriate value of a depends on the scaling of distances and how greedy we want the selection to be.
The question is to design a function $f(x)$ such that the selection of change $c_i$ with probability weight $f(d_i)$ is a "good selection strategy" [1]. An example of a "not-so-good strategy" is $f(x) = 1/x$ -- if $n$ is large and there are several "poor" $c_i$s each with large $d_i$, the cumulative sum of $f(d_i)$ corresponding to these poor $c_i$s is still large. This means that there is a large probability that a poor change will be selected.
$f(x) = 1/x^a$, $a = 3$ for example, is expected to perform better. Another candidate is $f(x) = 1/(1+a)^x$, $a = 0.25$ for example. [2] Empirically the last $f(x)$ seems to perform well in practice. Still better we would like that when some $d_i = 0$ then one of such $c_i$ is definitely selected. For this we can modify $f(x)$ to be $1/(x*(1+a)^x)$.
However more work is need to precisely discover the invariants of the good selection strategy.
[1] Due to stochastic nature of selection and the complexity of changes it is difficult to define "good selection strategy". One way to define it is to state specific examples, and expected weight ranges from the $c_i$. More work is needed to define it.
[2] The appropriate value of a depends on the scaling of distances and how greedy we want the selection to be.
Thursday, September 3, 2009
Some Thoughts on Refactoring
Recently I refactored the Crackpot code to replace all shared_ptrs by auto_ptrs and pointer containers (see here for a list of changes). There were about 2500 occurrences of shared_ptrs in the code. This was a relatively large refactoring as many memory management issues had to be fixed; basically every allocated object had to be responsibility of some other object (previously these objects had shared ownership, or we can say "don't care" ownership). The refactoring took about a month to complete. In this article I share some lessons:
there are only poor c++ refactoring tools
There are no good c++ refactoring tools. Often in the middle of refactoring, the code does not compile (although it is not a good idea to let the code go too much "out of" compilation), and any refactoring tool dependent on a compiled code would not work.
Perhaps some time in the future, one can create a syntax-based tool for c++ refactoring. The main task was to replace every shared_ptr by a reference(&), and every -> operator by (.). It was a little complex task, but an "intelligent"/machine learning tool could "learn" the changes I was making. Meanwhile, I used the unix sed tool effectively.
The main reason for poor refactoring tools for c++, I consider, is because 1) c++ does not have reflection and 2) it is a quite complicated language. Java, for example, has much more productive refactoring tools. But these too require compiled code.
the code of the unit test of a class is worth the code of 9 classes
Some unexpected bugs cropped up when the refactoring was done. You know how I easily found them? By running the unit tests. If there were no unit tests, probably these bugs would have stayed hidden till much longer. It would have been much more difficult to find which part of the system has a problem. There have been no more bugs (touch wood) related to refactoring after all the unit tests passed (and I hope to see not many more).
PS: There are some aspects of refactoring still incomplete (and there may be some memory leaks) but this incompleteness is not too important for the purposes of this article.
there are only poor c++ refactoring tools
There are no good c++ refactoring tools. Often in the middle of refactoring, the code does not compile (although it is not a good idea to let the code go too much "out of" compilation), and any refactoring tool dependent on a compiled code would not work.
Perhaps some time in the future, one can create a syntax-based tool for c++ refactoring. The main task was to replace every shared_ptr by a reference(&), and every -> operator by (.). It was a little complex task, but an "intelligent"/machine learning tool could "learn" the changes I was making. Meanwhile, I used the unix sed tool effectively.
The main reason for poor refactoring tools for c++, I consider, is because 1) c++ does not have reflection and 2) it is a quite complicated language. Java, for example, has much more productive refactoring tools. But these too require compiled code.
the code of the unit test of a class is worth the code of 9 classes
Some unexpected bugs cropped up when the refactoring was done. You know how I easily found them? By running the unit tests. If there were no unit tests, probably these bugs would have stayed hidden till much longer. It would have been much more difficult to find which part of the system has a problem. There have been no more bugs (touch wood) related to refactoring after all the unit tests passed (and I hope to see not many more).
PS: There are some aspects of refactoring still incomplete (and there may be some memory leaks) but this incompleteness is not too important for the purposes of this article.
Wednesday, August 5, 2009
Meeting with Prof Alex - 5 August 2009
We discussed the following areas of work/PhD theses for the future research in planning:
1. Action Component Relations -- templates of the kinds of constraints between structures related to actions
2. Existence of Objects - new and delete objects
3. From Domain Input, figuring distance structures between objects
4. Higher level projection for multiple objects - for example, all the trees grow every moment.
5. Real-time aspects - telling the low-level cost structures the current priorities -- intensification or diversification. Also, returning robust solutions since there is an impending change.
1. Action Component Relations -- templates of the kinds of constraints between structures related to actions
2. Existence of Objects - new and delete objects
3. From Domain Input, figuring distance structures between objects
4. Higher level projection for multiple objects - for example, all the trees grow every moment.
5. Real-time aspects - telling the low-level cost structures the current priorities -- intensification or diversification. Also, returning robust solutions since there is an impending change.
Tuesday, June 2, 2009
Merging Code from FYP Branch into Old-Trunk Branch
Last academic year we had 3 Final Year Student projects related to Crackpot. I have started with merging code of these FYP projects from branches/FYP0809 into branches/oldtrunk (finally all these will be merged with the current trunk which has a refactored directory structure).
For merging, Eclipse editor is a good tool. I can compare any two directories using eclipse, merge each separate change from left to right or right to left (left and right are the two documents being compared).
Using CMake
CMake can be used for both generating multiple project files for multiple tests (GUI/Metaplanning/Logistics domain/whatever), as also cross-compilation with linux. I downloaded and installed cmake. After this, I followed the steps listed here in our context. Everything worked as expected. I also got separate project files for each unit test. This is good, and we should continue with CMake.
For merging, Eclipse editor is a good tool. I can compare any two directories using eclipse, merge each separate change from left to right or right to left (left and right are the two documents being compared).
Using CMake
CMake can be used for both generating multiple project files for multiple tests (GUI/Metaplanning/Logistics domain/whatever), as also cross-compilation with linux. I downloaded and installed cmake. After this, I followed the steps listed here in our context. Everything worked as expected. I also got separate project files for each unit test. This is good, and we should continue with CMake.
Thursday, May 21, 2009
The Notion of Subplan
A subplan is a subset of actions of a plan. A subplan S is composable with a plan A to yield another plan B. All plan-related data structures should be in the context of some plan - this is different from our notion of always having a single plan.
What are the opportunities enabled by including subplans? As we noted in the last paragraph, it helps us work efficiently with multiple plans at a time.
Case Based Reasoning
Further, a case in case-based-planning is a subplan. Along with notions like "Conditions in the Plan as a Tree Structure", the subplan may be used to compose into a plan to yield another (hopefully lower-cost) plan (this is discussed under "Plan Merging" in the topic "Conditions in the Plan as a Tree Structure").
Parallel Search
Having subplans enables us to search multiple options in parallel, and then select the best option.
What are the opportunities enabled by including subplans? As we noted in the last paragraph, it helps us work efficiently with multiple plans at a time.
Case Based Reasoning
Further, a case in case-based-planning is a subplan. Along with notions like "Conditions in the Plan as a Tree Structure", the subplan may be used to compose into a plan to yield another (hopefully lower-cost) plan (this is discussed under "Plan Merging" in the topic "Conditions in the Plan as a Tree Structure").
Parallel Search
Having subplans enables us to search multiple options in parallel, and then select the best option.
Thursday, May 7, 2009
Long Time No See
I had been off on a short vacation to India. BTW my research paper has been accepted in a conference. I am particularly excited because this is my first time. More on this soon!
Thursday, April 16, 2009
Implementation Diary - April 16, 2009
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.
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.
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.
Monday, March 23, 2009
CostStructure & CostMapping
This article is based on planning group discussion on March 17, 2009.
Each Cost belongs to a certain CostType. Each Attribute has costs of multiple CostTypes. The CostManager maintains multiple CostCollections, each containing some costs. One example: 2 CostCollections - 1 containing optimization costs, and the other containing satisfaction costs.
The CostManager also has a CostMapping that transforms a CostValue provided by Actuator into another CostValue that it uses to prioritize and schedule costs. One example of scheduling: First, satisfaction costs are handled, then optimization (which might lead to non-satisfaction of some costs), then satisfaction, and so on.
Each Cost belongs to a certain CostType. Each Attribute has costs of multiple CostTypes. The CostManager maintains multiple CostCollections, each containing some costs. One example: 2 CostCollections - 1 containing optimization costs, and the other containing satisfaction costs.
The CostManager also has a CostMapping that transforms a CostValue provided by Actuator into another CostValue that it uses to prioritize and schedule costs. One example of scheduling: First, satisfaction costs are handled, then optimization (which might lead to non-satisfaction of some costs), then satisfaction, and so on.
Friday, March 20, 2009
A Quick Introduction to C++
Update: Please refer to Crackpot wiki documentation for an updated version of this piece.
This article was copied from Crackpot wiki on Mar 21, 2009, as the sourceforge wiki is not public, and due to bugs in sourceforge, the wiki links are broken (atleast for private wikis).
Wikipedia entry at http://en.wikipedia.org/wiki/Cplusplus is a good place to start for people who have never programmed in C++. A note for C programmers – although C++ has almost all features of C, programming in C++ involves a completely different way of thinking. Compared to Java, C++ is more powerful and much more complex.
C++ has evolved a lot in the last 5-10 years. For example compiler implementations of certain parts of STL were known to be buggy 5 years ago, but most of such issues have been fixed in the latest versions of the compilers. The date of any reference is important to judge its relevance with the current C++ version. In deed the way of designing in C++ has been evolving with confirmation of new features – for example what was done using inheritance five years back may be done using template traits today with tradeoffs.
Here is a partial list of software domains primarily running on C++: databases, operating systems, web browsers, computer games. C++ is most useful for evolving domains and can form the base for a higher level language like Java, Ruby or Python. At the same time, it is possible to efficiently implement systems without getting too low level.
People: Bjarne Stroustrup (primary author of C++), Herb Sutter (C++ guru, concurrency), Doug Lea (co-writer of GNU C++ library, middleware, Java Concurrency), Scott Meyers (C++ guru), Andrei Alexandrescu (C++ guru), Doug Schmidt (middleware, patterns), Andrew Koenig (C++ standards committee, C++ guru).
Some illustrative C++ libraries: STL (standard template library – has several implementations), Boost (has many libraries that are candidates to be included into language standard), Blitz++ (fast numeric library), ACE (middleware, concurrency patterns), STL port (a portable implementation of STL), Loki (design based on modern C++ features like templates), OpenMPI & Intel Thread Building Blocks (parallel programming)
To start, "Thinking in C++" by Bruce Eckel is a good resource available both online and in print. "Accelerated C++" by Andrew Koenig and Barbara Moo has a top-down approach to teaching the language. "The C++ Programming Language" by Bjarne Stroustrup is a comprehensive book but slightly advanced for the beginner. Also interesting is his FAQs at http://www.research.att.com/ ~bs/bs_faq2.html. Check out Doug Schmidt's take on an Overview of C++ at http://www.cs.wustl.edu/ ~schmidt/PDF/C++-overview4.pdf, the "practical" tutorial at http://www.ge.infn.it/geant4/training/ornl_2008/c++_oop.pdf, and the "practical programming methodology" course at http://www.cs.ualberta.ca/~mburo/courses/201.w2006/ (just some links I found, you can find other better ones).
Once you have made a start and are raring to get to the next level, check out C++ FAQ Lite at http://www.parashift.com/c++ -faq-lite/. It discusses several caveats of the language. "Effective C++" and "More Effective C++" by Scott Meyers discuss ways to write good code and bad code. "Effective STL" also by Meyers discusses the same for the standard library. "C++ Guru of the Week (GoTW)" is an online list of interesting questions and answers by Herb Sutter. This list was printed into books "Exceptional C++" and "More Exceptional C++". "C++ Coding Standards" by Sutter and Alexandrescu is a summarization of many of the caveats of C++ contained in the previous references, and is highly recommended. "Design Patterns" book by "Gang of Four" is the bible for design patterns used in industry and contains many examples in C++.
Getting to the next, advanced level definitely needs an in-depth understanding of C++ Templates. Some good resources for this are "C++ Templates" by David Vandevoorde and Nicolai M. Josuttis, "Modern C++ Design" by Andrei Alexandrescu and "C++ Template Metaprogramming" by David Abrahams and Aleksey Gurtovoy.
After I wrote this article, I found this excellent site by Comeau Computing which cover the topic well. Another exhaustive resource list is here.
Please let me know if you find useful resources. I will then link to them.
This article was copied from Crackpot wiki on Mar 21, 2009, as the sourceforge wiki is not public, and due to bugs in sourceforge, the wiki links are broken (atleast for private wikis).
Introduction to C++
C++ is a large language, supports a large variety of programming paradigms and a large number of libraries have been written in C++. The language is designed to make programming more enjoyable for the serious programmer. There are hundreds of caveats that a C++ programmer has to understand. Most of the caveats arise from backward compatibility and practical issues in standardization.Wikipedia entry at http://en.wikipedia.org/wiki/Cplusplus is a good place to start for people who have never programmed in C++. A note for C programmers – although C++ has almost all features of C, programming in C++ involves a completely different way of thinking. Compared to Java, C++ is more powerful and much more complex.
C++ has evolved a lot in the last 5-10 years. For example compiler implementations of certain parts of STL were known to be buggy 5 years ago, but most of such issues have been fixed in the latest versions of the compilers. The date of any reference is important to judge its relevance with the current C++ version. In deed the way of designing in C++ has been evolving with confirmation of new features – for example what was done using inheritance five years back may be done using template traits today with tradeoffs.
Here is a partial list of software domains primarily running on C++: databases, operating systems, web browsers, computer games. C++ is most useful for evolving domains and can form the base for a higher level language like Java, Ruby or Python. At the same time, it is possible to efficiently implement systems without getting too low level.
Some Quick Lists Related to C++
Compilers: Microsoft's Visual Studio cl.exe (most popular), GNU GCC g++ (most popular), Intel C++ compiler.People: Bjarne Stroustrup (primary author of C++), Herb Sutter (C++ guru, concurrency), Doug Lea (co-writer of GNU C++ library, middleware, Java Concurrency), Scott Meyers (C++ guru), Andrei Alexandrescu (C++ guru), Doug Schmidt (middleware, patterns), Andrew Koenig (C++ standards committee, C++ guru).
Some illustrative C++ libraries: STL (standard template library – has several implementations), Boost (has many libraries that are candidates to be included into language standard), Blitz++ (fast numeric library), ACE (middleware, concurrency patterns), STL port (a portable implementation of STL), Loki (design based on modern C++ features like templates), OpenMPI & Intel Thread Building Blocks (parallel programming)
C++ Resources
There are several books and you have to choose the ones that fit your taste.To start, "Thinking in C++" by Bruce Eckel is a good resource available both online and in print. "Accelerated C++" by Andrew Koenig and Barbara Moo has a top-down approach to teaching the language. "The C++ Programming Language" by Bjarne Stroustrup is a comprehensive book but slightly advanced for the beginner. Also interesting is his FAQs at http://www.research.att.com/ ~bs/bs_faq2.html. Check out Doug Schmidt's take on an Overview of C++ at http://www.cs.wustl.edu/ ~schmidt/PDF/C++-overview4.pdf, the "practical" tutorial at http://www.ge.infn.it/geant4/training/ornl_2008/c++_oop.pdf, and the "practical programming methodology" course at http://www.cs.ualberta.ca/~mburo/courses/201.w2006/ (just some links I found, you can find other better ones).
Once you have made a start and are raring to get to the next level, check out C++ FAQ Lite at http://www.parashift.com/c++ -faq-lite/. It discusses several caveats of the language. "Effective C++" and "More Effective C++" by Scott Meyers discuss ways to write good code and bad code. "Effective STL" also by Meyers discusses the same for the standard library. "C++ Guru of the Week (GoTW)" is an online list of interesting questions and answers by Herb Sutter. This list was printed into books "Exceptional C++" and "More Exceptional C++". "C++ Coding Standards" by Sutter and Alexandrescu is a summarization of many of the caveats of C++ contained in the previous references, and is highly recommended. "Design Patterns" book by "Gang of Four" is the bible for design patterns used in industry and contains many examples in C++.
Getting to the next, advanced level definitely needs an in-depth understanding of C++ Templates. Some good resources for this are "C++ Templates" by David Vandevoorde and Nicolai M. Josuttis, "Modern C++ Design" by Andrei Alexandrescu and "C++ Template Metaprogramming" by David Abrahams and Aleksey Gurtovoy.
Future Developments
C++ is working towards a new standard named C++0x. It has several new and powerful features. See http://stackoverflow.com/questions/226061/c0x-when#229072. Current versions under discussion by Standardizing Committee are called Tr1, Tr2; see http://www.open-std.org/JTC1 /SC22/WG21/After I wrote this article, I found this excellent site by Comeau Computing which cover the topic well. Another exhaustive resource list is here.
Please let me know if you find useful resources. I will then link to them.
Wednesday, March 11, 2009
Implementation Diary - March 11 2009
Planning in the Logistics Domain still does not reduce the cost to 0. Meanwhile I moved on to other things, which require attention too.
Today I separated the domain definition from problem instance definition. Also, I created a large problem instance for logistics domain (copied from http://www.cs.colostate.edu/meps/aips2000data/2000-tests/logistics/probLOGISTICS-20-0.pddl) needed for my performance tests.
Today I separated the domain definition from problem instance definition. Also, I created a large problem instance for logistics domain (copied from http://www.cs.colostate.edu/meps/aips2000data/2000-tests/logistics/probLOGISTICS-20-0.pddl) needed for my performance tests.
Friday, March 6, 2009
Implementation Diary - 6 March 2009
I am still struggling with Logistics Domain. As the closeness to finishing the goal reduces, the amount of effort needed increases. I played with several parameters in the past 1-2 days - distances between various objects, weights for selection of action, weightage given to conditions violated versus the fulfilment of cost while adding an action, and so on.
I have been unable to make many conclusive observations. Till now I have been able to obtain "3 non-zero costs" (previously I got to "2 non-zero costs" as well, but now seem to have lost it). These three costs are due to some conditions on locations of package_4 and package_6 - these packages have to be shipped from one city to another. I still have to find why these costs never get satisfied. However I have realized that since we gave a 1/d^3 weight to actions, tuning the distances used in cost computation play an important role. Finding appropriate weights needs research. Right now all of this seems so murky and having no correct answer.
I performed a little experiment with the 1/d^3 weight to actions: replaced 3 with e=.5, 0.75, 1, 1.5, 2 etc. Contrary to what I thought, e < 1 didn't work well at all. Best value was achieved near e = 1.5. This experiment does not mean much though and I would hate to bet anything on it.
During the day I also ran the cost performance profile tool. It generates a graph for "number of non-zero costs" with a large number of ups and downs:
Putting filters on selection of action instances (like do not select actions that lead to more cost value on the cost being fixed) reduce the number of times "3 non-zero costs" is achieved.
I have been unable to make many conclusive observations. Till now I have been able to obtain "3 non-zero costs" (previously I got to "2 non-zero costs" as well, but now seem to have lost it). These three costs are due to some conditions on locations of package_4 and package_6 - these packages have to be shipped from one city to another. I still have to find why these costs never get satisfied. However I have realized that since we gave a 1/d^3 weight to actions, tuning the distances used in cost computation play an important role. Finding appropriate weights needs research. Right now all of this seems so murky and having no correct answer.
I performed a little experiment with the 1/d^3 weight to actions: replaced 3 with e=.5, 0.75, 1, 1.5, 2 etc. Contrary to what I thought, e < 1 didn't work well at all. Best value was achieved near e = 1.5. This experiment does not mean much though and I would hate to bet anything on it.
During the day I also ran the cost performance profile tool. It generates a graph for "number of non-zero costs" with a large number of ups and downs:
Putting filters on selection of action instances (like do not select actions that lead to more cost value on the cost being fixed) reduce the number of times "3 non-zero costs" is achieved.
Thursday, March 5, 2009
Logging
Logging is quite useful for debugging. Today I found a nice article on logging [1]. Besides describing what to log at system startup, I also found the concept of ring buffer for logging useful (The method is covered in more detail in [2]). Here, logs are not written into file, but into memory in a ring fashion. At the time the program crashes, the last few logs exist in memory and can be debugged.
In this context, google coredumper [3] might also be useful. The core file contains the complete state of the program at a point of time. A strategy can be that after an assertion fails and before crashing the program, the program dumps core using coredumper. This can help to find the bug that caused the assertion failure.
[1] About Log Files: Parts 1 and 2. http://www.ddj.com/cpp/212902973 and http://www.ddj.com/cpp/214502427
[2] Logging in multi-threaded applications efficiently with ring buffer http://www.ibm.com/developerworks/aix/library/au-buffer/index.html
[3] http://stackoverflow.com/questions/318647/what-is-a-good-way-to-dump-a-linux-core-file-from-inside-a-process
In this context, google coredumper [3] might also be useful. The core file contains the complete state of the program at a point of time. A strategy can be that after an assertion fails and before crashing the program, the program dumps core using coredumper. This can help to find the bug that caused the assertion failure.
[1] About Log Files: Parts 1 and 2. http://www.ddj.com/cpp/212902973 and http://www.ddj.com/cpp/214502427
[2] Logging in multi-threaded applications efficiently with ring buffer http://www.ibm.com/developerworks/aix/library/au-buffer/index.html
[3] http://stackoverflow.com/questions/318647/what-is-a-good-way-to-dump-a-linux-core-file-from-inside-a-process
Wednesday, March 4, 2009
Implementation Diary - March 5, 2009
I am still struggling with logistics domain. Need to finish it quickly and move on to more important work of performing parallelization experiments.
Distance between Object References
One of the questions we face in logistics domain is the distance between objects. Some attributes contain object references - for example, the location of a package is a subtype of "PackageLocationPlace". Truck, Airport, Depot, Airplane all are derived from PackageLocationPlace.
One question is how to compute the distance between two objects.
Example 10. the goal is to get package_1 to depot_1a, and currently it is at depot_2a. What is the distance between depot_1a and depot_2a?
Domain Independent Heuristics for Computing Distance Between Objects
To compute distance between two objects A and B, we compute the distance between each attribute a_i of A and B, and combine (for example, add) these distances.
1) if A and B are of same type t, compute distance for each attribute of type t.
2) if A is a subtype of B, compute distance for each attribute of type of B.
3) vice versa of 2)
4) compute distance between the type t1 of the needed type. For example, in Example 10, only attributes of packageLocationPlace objectType would be computed and combined.
Overall Picture
The above means that the distance between values of an attribute depends on the distance between objects. The distance between objects depends on the distance between attributes of the objects. This is a recursive relation.
Complex Interactions
Here is an example of the kind of interaction we have to deal with for computing distances: In logistics domain, we are interested in computing the difficulty of changing the attribute "package1.packageLocation" from "truck1" into "depot1". For this, we look for actions that change the value of package1.packageLocation from truck1 into depot1. We find one such action is "UnloadPackageFromTruck", which contains the contribution "package1.location <- truck1.truckInDepotType". Ok so now which actions transform the value of "truck1.truckInDepotType" from its current value to "depot1"? The difficulty of this action would also contribute to our answer.
More complex interactions will arise in other domains. We should develop a logic for making these computations. It would probably be based on description logic.
Distance between Object References
One of the questions we face in logistics domain is the distance between objects. Some attributes contain object references - for example, the location of a package is a subtype of "PackageLocationPlace". Truck, Airport, Depot, Airplane all are derived from PackageLocationPlace.
One question is how to compute the distance between two objects.
Example 10. the goal is to get package_1 to depot_1a, and currently it is at depot_2a. What is the distance between depot_1a and depot_2a?
Domain Independent Heuristics for Computing Distance Between Objects
To compute distance between two objects A and B, we compute the distance between each attribute a_i of A and B, and combine (for example, add) these distances.
1) if A and B are of same type t, compute distance for each attribute of type t.
2) if A is a subtype of B, compute distance for each attribute of type of B.
3) vice versa of 2)
4) compute distance between the type t1 of the needed type. For example, in Example 10, only attributes of packageLocationPlace objectType would be computed and combined.
Overall Picture
The above means that the distance between values of an attribute depends on the distance between objects. The distance between objects depends on the distance between attributes of the objects. This is a recursive relation.
Complex Interactions
Here is an example of the kind of interaction we have to deal with for computing distances: In logistics domain, we are interested in computing the difficulty of changing the attribute "package1.packageLocation" from "truck1" into "depot1". For this, we look for actions that change the value of package1.packageLocation from truck1 into depot1. We find one such action is "UnloadPackageFromTruck", which contains the contribution "package1.location <- truck1.truckInDepotType". Ok so now which actions transform the value of "truck1.truckInDepotType" from its current value to "depot1"? The difficulty of this action would also contribute to our answer.
More complex interactions will arise in other domains. We should develop a logic for making these computations. It would probably be based on description logic.
Tuesday, March 3, 2009
Executable Size, Memory Footprint etc
I tend to think these are not important right now for Crackpot executable. However a few links that I just went through:
[1] http://wiki.wxwidgets.org/Reducing_Executable_Size
[2] http://stackoverflow.com/questions/200292/process-for-reducing-the-size-of-a-executable
[3] http://www.gamedev.net/community/forums/topic.asp?topic_id=290430
[1] http://wiki.wxwidgets.org/Reducing_Executable_Size
[2] http://stackoverflow.com/questions/200292/process-for-reducing-the-size-of-a-executable
[3] http://www.gamedev.net/community/forums/topic.asp?topic_id=290430
Tuesday, February 24, 2009
Implementation Diary - Feb 25, 2009
I have been struggling with making Crackpot work with Logistics Domain. One recent observation here: This is the plot of number of costs in one run of the planner in Logistics Domain. As we can see there is a jump in number of costs suddenly from 10 to 200 within iterations from 175 to 300. The number of costs however always stays within 300, in 2000 iterations.
What is the cause of this sudden jump in number of costs? After investigation I found several costs fixed at that time were goal costs. For goals costs, we have only one heuristic that adds action into plan: addAction. There was one goal "Package 6 should be in depot 1b" and there was one action that pushed Package 6 to depot 1a near 278 time point. It seems actions were added one after another, but all not after 278, but before 278, which did not do anything to improve the cost of goal.
Monday, February 23, 2009
Thoughts on an Adaptive Local Search for Planning
Non-stationary Decision Making
The basic question discussed in this article is
Out of a set of possible choices (of heuristics, for example), which choice should be made?Markov Decision Processes (MDPs) are an often used mechanism for this problem. The model for MDP requires a set of states {s}, and a set of actions {a} which take from one state to another with certain probability P(s_(t+1)|s_(t), a). An immediate reward R_a(s_(t+1), s_t) is received on this transition. The solution of MDP is a policy to take some action a in each state s.
Our problem of making choice is complicated by the following factors:
1. Uncertainty in the real world introduces non-determinism in MDP. This is commonly studied under Partially Observable MDP (POMDP) - the idea is that the underlying states are not observable to the agent, but the agent must infer the underlying state from the observations. Only approximate solutions of POMDP may be determined.
2. There are efficient solutions for solving POMDPs. [2] presents a point-based anytime algorithm for POMDP, for example. However, for really quick responses such as is needed for selecting small actions within local search, they are still too slow. Solving POMDPs would be good for long term learning. For short-term, non-stationary learning low-cost approaches such as in [1] are suitable.
3. MDP does not incorporate change in state structure with time. For example, in local search, usually many more local minima are found as the search progresses, compared to near the start of search. So the policy must evolve as time goes on. One example of such is squeaky wheel optimization in local search.
However, the simple approach for non-stationary learning described in [1] can be augmented with a model to make it more efficient. The idea is that probably more time can be allocated to making a larger decision.
For this purpose, each heuristic contains the following:
- goodness of the heuristic (goodness = the difficulty level that can be improved by application of the heuristic)
- confidence of goodness of the heuristic
- time needed to execute the heuristic
- resources needed to execute the heuristic
Incorporating Short-Term Goal Aspects
We will have two systems - one that handles long term aspects (like difficulty of a goal, priority of a goal), and another that handles short-term aspects (like remaining time, available resources).
Every choice considers both short-term and long-term aspects of the choice.
Making a Choice
Decisions taken when there is sufficient time available are usually different from when little time is available before execution must start. For example, exploration of other/untried options will take a back seat when time available is little.
One question is whether, if confidence in goodness is low (which means there is a huge standard deviation of goodness), should be choice maker assume an optimistic stance or a pessimistic stance? This may be a research question.
General Observation
In general, we note that more sophisticated and resource intensive approaches are more applicable when a large decision is being made, or when the granularity of decision is high, that is, all choices will take a long time and resources to implement. Therefore, effective profiling of time and resource usage is important.
[1] Alexander Nareyek. Choosing heuristics by non-stationary reinforcement learning.
[2] Pineau, Gordon, Thrun. Point-based value iteration: An anytime algorithm for POMDPs.
Saturday, February 14, 2009
Implementation Diary - 14 Feb 2009 - 2
1. There was a bug introduced recently in PlannerImpl code due to which the heuristics were not selected based on their currentPreference. This led to non-convergence of plan in Apple Domain. Fixed.
2. Also, I wrote a small python script to plot the evolution of costs with iterations. For Apple domain there wasn't much interesting pattern of evolution of costs. The red one is total costs, and blue one is number of costs:
In Logistics domain the graphs were interesting, but in the wrong sense. I hope soon the graphs will be upside down of what they are now.
2. Also, I wrote a small python script to plot the evolution of costs with iterations. For Apple domain there wasn't much interesting pattern of evolution of costs. The red one is total costs, and blue one is number of costs:
In Logistics domain the graphs were interesting, but in the wrong sense. I hope soon the graphs will be upside down of what they are now.
Friday, February 13, 2009
Consistency of Input: Domain Definition and Initial and Goal States
Consistency of Domain Definition
Rules of thumb:
1. Every action type should use an actuator
Consistency of Initial State
1. Every attribute and actuator should have a present initial state
Rules of thumb:
1. Every action type should use an actuator
Consistency of Initial State
1. Every attribute and actuator should have a present initial state
Implementation Diary - 14 Feb 2009
One problem that often occurs in planning in Crackpot is two same actions (needing same preconditions) occurring concurrently. For example, two LoadPackageIntoTruckAtDepot(package_3, into: Truck1) actions occurring at time 6 and 12.
At 6: of type: LoadPackageIntoTruckAtDepot
: Duration: 10
ConditionInstances: [
@[6,7): Package_3 of type: package.packageLocation == Truck_1 of type: truck.truckInDepot
]
ContributionInstances: [
@[16,2147483647): Package_3 of type: package.packageLocation <- Truck_1 of type: truck (type OBJECT_REFERENCE)
]
ActionTaskInstances: [
]
At 12: of type: LoadPackageIntoTruckAtDepot
: Duration: 10
ConditionInstances: [
@[12,13): Package_3 of type: package.packageLocation == Truck_1 of type: truck.truckInDepot
]
ContributionInstances: [
@[22,2147483647): Package_3 of type: package.packageLocation <- Truck_1 of type: truck (type OBJECT_REFERENCE)
]
ActionTaskInstances: [
]
The way to eliminate this error is to introduce an Actuator "TruckBusy" within each truck that gets used when it is being loaded. The same Actuator is used when the truck is running and unloaded. This is one thing I did today.
Note that here we introduced the Actuator as an afterthought of observing a plan. This happened because Actuators are somewhat unobvious in actions.
It usually does not make sense that the same action (instantiated with the same parameters) are carried out again concurrently. For example, "opening the same door twice simultaneously" is non-sense. All such actions should contain Actuators.
At 6: of type: LoadPackageIntoTruckAtDepot
: Duration: 10
ConditionInstances: [
@[6,7): Package_3 of type: package.packageLocation == Truck_1 of type: truck.truckInDepot
]
ContributionInstances: [
@[16,2147483647): Package_3 of type: package.packageLocation <- Truck_1 of type: truck (type OBJECT_REFERENCE)
]
ActionTaskInstances: [
]
At 12: of type: LoadPackageIntoTruckAtDepot
: Duration: 10
ConditionInstances: [
@[12,13): Package_3 of type: package.packageLocation == Truck_1 of type: truck.truckInDepot
]
ContributionInstances: [
@[22,2147483647): Package_3 of type: package.packageLocation <- Truck_1 of type: truck (type OBJECT_REFERENCE)
]
ActionTaskInstances: [
]
The way to eliminate this error is to introduce an Actuator "TruckBusy" within each truck that gets used when it is being loaded. The same Actuator is used when the truck is running and unloaded. This is one thing I did today.
Note that here we introduced the Actuator as an afterthought of observing a plan. This happened because Actuators are somewhat unobvious in actions.
It usually does not make sense that the same action (instantiated with the same parameters) are carried out again concurrently. For example, "opening the same door twice simultaneously" is non-sense. All such actions should contain Actuators.
Tuesday, February 10, 2009
Implementation Diary - 10 Feb 2009 - Inheritance in Crackpot
One of the requirements in Logistics Domain is inheritance of object types. For example, the airports are also depots (trucks travel from depot to depot). Therefore airport is a derived class of depot.
Updated on 15 April 2009:
Inheritance (Is-a) and Containment (Has-a) relations between ObjectType s are implemented in Crackpot.
Inheritance
An example of inheritance in Logistics Domain is: Trucks travel from depot to depot. The airports are also depots as trucks travel to airports too. Therefore airport is a derived class of depot.
Changes made for implementation of inheritance:
1. Added a class called ObjectTypeRelationsContainer for containing the "directly" derived types. This class contains a 2-column table with each row containing a base and derived class. This class has a wrapper interface to find all directly derived object types called getDirectlyDerivedObjectTypeRange and a class to find all derived types of a type called getAllDerivedObjectTypes.
2. Added into interface of DomainPackage: functions to find all "directly" derived types of a type called getDirectlyDerivedObjectTypeRange, and inherited attributes of a type called getInheritedAttributeTypesOfObjectType (another function getAttributeTypesOfObjectType returns attributes but not inherited attributes). After the domain definition is read, the DomainPackage::postInitialize function is called. Inside this function, all attributes of base classes are inserted as attributes of derived classes too. In DomainPackageUtils class: added function getGroundObjectInstancesOfAllDerivedObjectTypes which returns all ground object instances of derived object types of a base type.
During planning, when an object parameter is instantiated, the planner uses getGroundObjectInstancesOfAllDerivedObjectTypes as the starting point to find an appropriate object instance.
Inheritance from multiple ObjectTypes are allowed (but not tested till now). No error checks like same attribute names in base classes etc is implemented.
Containment
Containment is implemented through object references. The value of an attribute which refers to another object in the domain is called an ObjectReferenceAttributeValueInstance.
Idea: Unlike our other interfaces, getAllDerivedObjectTypes returns a set, and not a range of iterators. A range class should be defined so that it also contains a pointer to its container. Then the range can be returned, and no need to returning the set explicitly.
Observations: the DomainPackage class is growing bigger everyday. This is not scalable. It needs to be broken down. It should delegate tasks to smaller classes - for objects and attributes, another for actions, and so on.
Updated on 15 April 2009:
Inheritance (Is-a) and Containment (Has-a) relations between ObjectType s are implemented in Crackpot.
Inheritance
An example of inheritance in Logistics Domain is: Trucks travel from depot to depot. The airports are also depots as trucks travel to airports too. Therefore airport is a derived class of depot.
Changes made for implementation of inheritance:
1. Added a class called ObjectTypeRelationsContainer for containing the "directly" derived types. This class contains a 2-column table with each row containing a base and derived class. This class has a wrapper interface to find all directly derived object types called getDirectlyDerivedObjectTypeRange and a class to find all derived types of a type called getAllDerivedObjectTypes.
2. Added into interface of DomainPackage: functions to find all "directly" derived types of a type called getDirectlyDerivedObjectTypeRange, and inherited attributes of a type called getInheritedAttributeTypesOfObjectType (another function getAttributeTypesOfObjectType returns attributes but not inherited attributes). After the domain definition is read, the DomainPackage::postInitialize function is called. Inside this function, all attributes of base classes are inserted as attributes of derived classes too. In DomainPackageUtils class: added function getGroundObjectInstancesOfAllDerivedObjectTypes which returns all ground object instances of derived object types of a base type.
During planning, when an object parameter is instantiated, the planner uses getGroundObjectInstancesOfAllDerivedObjectTypes as the starting point to find an appropriate object instance.
Inheritance from multiple ObjectTypes are allowed (but not tested till now). No error checks like same attribute names in base classes etc is implemented.
Containment
Containment is implemented through object references. The value of an attribute which refers to another object in the domain is called an ObjectReferenceAttributeValueInstance.
Idea: Unlike our other interfaces, getAllDerivedObjectTypes returns a set, and not a range of iterators. A range class should be defined so that it also contains a pointer to its container. Then the range can be returned, and no need to returning the set explicitly.
Observations: the DomainPackage class is growing bigger everyday. This is not scalable. It needs to be broken down. It should delegate tasks to smaller classes - for objects and attributes, another for actions, and so on.
Tuesday, February 3, 2009
Distance between Attribute Values
We use some kind of heuristic distance computation between different values of an attribute. One often used (and also used by us) heuristic is to define distance between two values A and B to be the number of actions it takes to go from A to B, ignoring any other preconditions and contributions of the actions.
Distance between Object References
In some cases the distance between object references are important. This is considered in detail in the post http://crackpotplanner.blogspot.com/2009/03/implementation-diary-march-5-2009.html
Modelling Uncertainty in Heuristic Distance Computation of AttributeInstances
We can extend this model of heuristic distance to include uncertainty in the distance. If there is a series of actions that really take from A to B, and has no other preconditions and contributions, then there is no uncertainty for this path from A to B. If there is a series of actions from A to B having many other preconditions, then the uncertainty would be large.
The original context that lead to this (small) idea was justifying a statement in Alex's paper "Local Search Heuristics for Generative Planning" - an action is inserted in proportion to 1/d^3, where d is the distance between the desired value and the resultant value after inserting the action. Why 1/d^3?
In case there is no uncertainty, the better action should be greedily selected (with probability 1). Suppose there are two actions A1 and A2 with distance d1 and d2 and uncertainty of distances u1 and u2, and u1 <> u2. This is a tricky case.
If there is no action that can convert from one value to another, then the distance would be infinite.
Distance between Object References
In some cases the distance between object references are important. This is considered in detail in the post http://crackpotplanner.blogspot.com/2009/03/implementation-diary-march-5-2009.html
Modelling Uncertainty in Heuristic Distance Computation of AttributeInstances
We can extend this model of heuristic distance to include uncertainty in the distance. If there is a series of actions that really take from A to B, and has no other preconditions and contributions, then there is no uncertainty for this path from A to B. If there is a series of actions from A to B having many other preconditions, then the uncertainty would be large.
The original context that lead to this (small) idea was justifying a statement in Alex's paper "Local Search Heuristics for Generative Planning" - an action is inserted in proportion to 1/d^3, where d is the distance between the desired value and the resultant value after inserting the action. Why 1/d^3?
In case there is no uncertainty, the better action should be greedily selected (with probability 1). Suppose there are two actions A1 and A2 with distance d1 and d2 and uncertainty of distances u1 and u2, and u1 <> u2. This is a tricky case.
If there is no action that can convert from one value to another, then the distance would be infinite.
Thursday, January 29, 2009
Distribution of AttributeInstances on Hardware
Important Factors for Distribution:
* amount of communication needed with other AttributeInstances
* close neighbours with which frequently interact
* workload - number of requests
* amount of communication needed with other AttributeInstances
* close neighbours with which frequently interact
* workload - number of requests
Tuesday, January 27, 2009
Conditions in a Plan as a Tree Structure
goal -> action + condition*
condition -> action + condition*
In Crackpot, we store each attribute and all conditions on an attribute. This means it is possible to infer: a particular condition c is satisfied by which actions, and these actions have in turn what conditions.
Visualizing conditions as a Tree structure is helpful:
1) Condition: If a condition c is no longer needed due to change in situation, the whole "subtree" of c (containing actions and conditions) should be removed, unless a certain action participates in achievement of another goal.
The queries from the Tree structure in the above scenario are:
a. get all action instances needed to satisfy a condition instance
b. get condition instances of an action instance
c. get all condition instances satisfied by an action instance
2) Cases (for the case base) - which heuristic helped achieve which condition in what scenario. In scenario, we can probably store: the condition that was satisfied and the existing states of the attributed participating in the condition. In the case, we also need to store what change was produced by the heuristic.
If the case base stores the whole tree of a condition, the tree can be copied and applied in another situation.
3) Infer goodness of a heuristic - How to update the goodness of a heuristic? If a heuristic participated in satisfying a condition of an action that was executed and yielded reward R, the heuristic should be awarded its share of R. How to determine the share?
As I earlier mentioned, the Cost value of a condition should store not just the difficulty of achieving the cost, but also the priority of the goal. A heuristic is best if it reduces the difficulty of a high priority goal using quite minimal resources and time. Once a heuristic is classified as better, the difficulty of the goal reduces. So within a closed-loop, the difficulty measures should be updated as well.
4) Plan Merging - In plan merging we are interested in reducing the size of merge(A, B) from size(A) and size(B). Plan merging is useful in parallelization of planning as well as in case-based planning. If A and B share a condition c such that the plans can be moved and adjusted to need to achieve c only once, all actions needed to achieve c need not be duplicated.
condition -> action + condition*
In Crackpot, we store each attribute and all conditions on an attribute. This means it is possible to infer: a particular condition c is satisfied by which actions, and these actions have in turn what conditions.
Visualizing conditions as a Tree structure is helpful:
1) Condition: If a condition c is no longer needed due to change in situation, the whole "subtree" of c (containing actions and conditions) should be removed, unless a certain action participates in achievement of another goal.
The queries from the Tree structure in the above scenario are:
a. get all action instances needed to satisfy a condition instance
b. get condition instances of an action instance
c. get all condition instances satisfied by an action instance
2) Cases (for the case base) - which heuristic helped achieve which condition in what scenario. In scenario, we can probably store: the condition that was satisfied and the existing states of the attributed participating in the condition. In the case, we also need to store what change was produced by the heuristic.
If the case base stores the whole tree of a condition, the tree can be copied and applied in another situation.
3) Infer goodness of a heuristic - How to update the goodness of a heuristic? If a heuristic participated in satisfying a condition of an action that was executed and yielded reward R, the heuristic should be awarded its share of R. How to determine the share?
As I earlier mentioned, the Cost value of a condition should store not just the difficulty of achieving the cost, but also the priority of the goal. A heuristic is best if it reduces the difficulty of a high priority goal using quite minimal resources and time. Once a heuristic is classified as better, the difficulty of the goal reduces. So within a closed-loop, the difficulty measures should be updated as well.
4) Plan Merging - In plan merging we are interested in reducing the size of merge(A, B) from size(A) and size(B). Plan merging is useful in parallelization of planning as well as in case-based planning. If A and B share a condition c such that the plans can be moved and adjusted to need to achieve c only once, all actions needed to achieve c need not be duplicated.
Friday, January 23, 2009
Using SQLite Database for Crackpot
Case for Database
There are several places where database can be useful in Crackpot. Storing and retrieving plans. Storing data from GUI for replay. Storing information for long term, learning etc. In summary, any place which is not in the critical performance path.
SQLite
The use of a database can simplify the work needed for storing and retrieving information. Some candidate databases are: BerkeleyDB, SQLite, MySQL, PostgresQL. Out of these, SQLite is a high performance and simple database with an open license. SQLite seems fit for our purposes.
In-memory databases
There are some databases which can be used to store and query information within the main memory (RAM). SQLite also supports in-memory databasing.
SQLite with C++
A good C++ wrapper for SQL in general is seems to be SOCI. Unfortunately using it for SQLite might need some work. But still seems to be a productive choice.
There are several places where database can be useful in Crackpot. Storing and retrieving plans. Storing data from GUI for replay. Storing information for long term, learning etc. In summary, any place which is not in the critical performance path.
SQLite
The use of a database can simplify the work needed for storing and retrieving information. Some candidate databases are: BerkeleyDB, SQLite, MySQL, PostgresQL. Out of these, SQLite is a high performance and simple database with an open license. SQLite seems fit for our purposes.
In-memory databases
There are some databases which can be used to store and query information within the main memory (RAM). SQLite also supports in-memory databasing.
SQLite with C++
A good C++ wrapper for SQL in general is seems to be SOCI. Unfortunately using it for SQLite might need some work. But still seems to be a productive choice.
Monday, January 19, 2009
Crackpot FAQs
Planning System
- Why do we need a class ObjectType and another called ObjectInstance? Why not just one class Object (refering to ObjectInstance)?
The information about the ObjectType is available only at runtime. If we have just one class Object, we won't be able to "tag" apple objects as of "apple" type. We want to store types of objects. You can think of ObjectTypes as tags to ObjectInstances.
- What is ground and formal ObjectInstance?
In the ActionType "OpenDoor(d: DoorType, p: personType)", d is be an "Object Variable" or a placeholder for an ObjectInstance. In ActionInstance, it becomes "OpenDoor(door0, person0)". Here door0 and person0 are actual objects in the world. The "Object Variables" are currently called Formal ObjectInstances and "actual objects in the world" are called Ground Object Instances.C++/Programming General
- I have a particular technical question. Where can I get help?
Besides the usual means, you can also search or ask on online forums. Before asking there, make sure you have done a good research on it on google (and include your research done along with the question). In particular I like stackoverflow.comC++ - Beginner Level
- Good resources?
See the article "A Quick Introduction to C++"
- How do I handle cyclic dependencies in C++? For example, class A uses class B, and class B uses class A?
See http://www.eventhelix.com/realtimemantra/HeaderFileIncludePatterns.htm
Friday, January 9, 2009
How it is and How it Should be
Changes and refactoring are an intrinsive part of evolution of any software. There is a lot of changes needed in Crackpot (code in trunk). Some of the changes are small - like renaming certain classes/functions and others are large - like architecture changes. Also see another list of needed changes in (crackpot_directory)/TODO.txt.
I am labelling the changes with severity labels of low, medium and high.
Objects and Attributes
Severity: Medium
Each ObjectType can have a "self" attribute which refers to the object itself. This will allow the existing framework of attributes to extend to include object references. For example, to refer to ObjectInstance a1, we can say "a1.self". (In the current implementation, a1 will be a ValueInstance. This is more of a hack.).
Severity: Medium
Formal ObjectInstance should be renamed as ObjectInstancePlaceHolder.
Actions
Severity: Medium
Right now contributions and conditions are connected with ActionType, while actually they should be connected to ActionTaskType.
Domain definition
Severity: Low
Right now all the information about the domain are read into a class called DomainPackage, which maintains repositories or objecttypes, objectinstances, attributetypes, actiontypes and so on. This has made DomainPackage class too large to the extent that it is exploding now.
In the future, we should have separate classes ObjectTypeRepository, ActionTypeRepository, and ObjectInstanceRepository. These repositories should handle name-based queries also like getObjectInstanceWithNameOfType(). ObjectTypes can contain its list of AttributeTypes and ActionResourceTypes. (Optional) Small factories like ObjectTypeFactory can be introduced; this has the logic to build ObjectTypes. ObjectInstanceRepository can contain the map from ObjectType to its ObjectInstances.
Finally, all the queries regarding the domain (and asked by heuristics) will be handled by PlanStructure class. So it can be something like:
class DomainQueryHandler
{
// all get and set functions related to domain
// implements facade that hides the various domain related repositories
};
class PlanStructure: public DomainQueryHandler {
// ...
};
Directory Structure
Update: Our colleague, Sima, completed the refactoring into the new directory structure.
Severity: Medium
As per Planning Group meetings, the directory structure has to evolve into something like this (this structure is not finalized, but will be soon):
PlanManager
PlanStructure
|- Object
|- Action
CostManager
CostStructure
CostCenter
|- Heuristics
Types and Instances
We can form a convention that functions to create instance will be a member function of type. For example, a ConditionType has a member to create ConditionInstance.
Complex Actions
Sometimes the further course of plan depends on result of performing an action. For example, try to open the door. If door is locked, it won't open. Then the agent must look for the key. This can be encoded as a monitoring ActionTask in the OpenDoor action: [If (monitor(door) == door-locked) insert look-for-key action into plan]. We need to develop/reuse a logic for this purpose. Further there may be monitoring loops within actions, like [ while (monitor(water-boiling) == false) {}].
Using Description Logic
Our rich-world description should be based on a formalized logic. This helps in interfacing with other tools, communication with other groups and reusability in other situations. Description Logic is one such logic. Description Logic is the basis for several semantic web constructs. We can use Description Logic constructs for objects, actions, plans and goals.
Implementation of More Examples
Both domain independent and domain dependent techniques can be used, for example for Settlers domain: http://planning.cis.strath.ac.uk/competition/ .
Implementation: Build Related
We need to normalize the build process across compile time options, include directories, etc. See http://stackoverflow.com/questions/222827/how-do-you-organize-your-version-control-repository/304036#304036 for a good build strategy.
Use of Templates
We should move to using templates in a greater manner - namely for all types that do not need run-time polymorphis
- policy-based class design helps to prepare more reusable components
- being purely syntactic entities they are also minimally intrusive to other class
I'm sure there is more to come. I expect this entry to be updated frequently.
I am labelling the changes with severity labels of low, medium and high.
Objects and Attributes
Severity: Medium
Each ObjectType can have a "self" attribute which refers to the object itself. This will allow the existing framework of attributes to extend to include object references. For example, to refer to ObjectInstance a1, we can say "a1.self". (In the current implementation, a1 will be a ValueInstance. This is more of a hack.).
Severity: Medium
Formal ObjectInstance should be renamed as ObjectInstancePlaceHolder.
Actions
Severity: Medium
Right now contributions and conditions are connected with ActionType, while actually they should be connected to ActionTaskType.
Domain definition
Severity: Low
Right now all the information about the domain are read into a class called DomainPackage, which maintains repositories or objecttypes, objectinstances, attributetypes, actiontypes and so on. This has made DomainPackage class too large to the extent that it is exploding now.
In the future, we should have separate classes ObjectTypeRepository, ActionTypeRepository, and ObjectInstanceRepository. These repositories should handle name-based queries also like getObjectInstanceWithNameOfType(). ObjectTypes can contain its list of AttributeTypes and ActionResourceTypes. (Optional) Small factories like ObjectTypeFactory can be introduced; this has the logic to build ObjectTypes. ObjectInstanceRepository can contain the map from ObjectType to its ObjectInstances.
Finally, all the queries regarding the domain (and asked by heuristics) will be handled by PlanStructure class. So it can be something like:
class DomainQueryHandler
{
// all get and set functions related to domain
// implements facade that hides the various domain related repositories
};
class PlanStructure: public DomainQueryHandler {
// ...
};
Directory Structure
Update: Our colleague, Sima, completed the refactoring into the new directory structure.
Severity: Medium
As per Planning Group meetings, the directory structure has to evolve into something like this (this structure is not finalized, but will be soon):
PlanManager
PlanStructure
|- Object
|- Action
CostManager
CostStructure
CostCenter
|- Heuristics
Types and Instances
We can form a convention that functions to create instance will be a member function of type. For example, a ConditionType has a member to create ConditionInstance.
Complex Actions
Using Description Logic
Our rich-world description should be based on a formalized logic. This helps in interfacing with other tools, communication with other groups and reusability in other situations. Description Logic is one such logic. Description Logic is the basis for several semantic web constructs. We can use Description Logic constructs for objects, actions, plans and goals.
Implementation of More Examples
Both domain independent and domain dependent techniques can be used, for example for Settlers domain: http://planning.cis.strath.ac.uk/competition/ .
Implementation: Build Related
We need to normalize the build process across compile time options, include directories, etc. See http://stackoverflow.com/questions/222827/how-do-you-organize-your-version-control-repository/304036#304036
Use of Templates
We should move to using templates in a greater manner - namely for all types that do not need run-time polymorphis
- policy-based class design helps to prepare more reusable components
- being purely syntactic entities they are also minimally intrusive to other class
I'm sure there is more to come. I expect this entry to be updated frequently.
Thursday, January 8, 2009
Cost Repair Guidance
In this entry we list some good heuristics for Cost Repair. These can be used by CostManager to select appropriate Costs to fix.
Do Something Now
Since limited time is available before execution starts, actions that need to be taken early on should be decided first, locked and sent for execution. Suppose there are two actions that could be executed under the current environment, a1 and a2. But executing one of the two actions is important right now to be able to succeed within time.
This is a question related to deliberation versus reaction. Should an agent think more or start execution? How much should the agent think, and how much execute?
To fix an action early on, there may be a way to measure the difficulty of reaching the goals from the states s1 and s2, reached when a1 and a2 respectively are executed in plan. Once the CostCenter has computed, for example, that s1 is much farther from goal than s2, a2 may be locked for execution.
Difficulty versus Priority: Note that difficulty of reaching a goal is a separate concern from the priority or urgency of reaching the goal. Each Cost should contain information both about difficulty and priority.
Estimating difficulty of reaching goal: How to estimate the difficulty of reaching the goal? Estimation should not consume so much time that it offsets the benefit of finer approximation of estimate. Depending on the situation, finer estimation may be more useful or not. One question in this regard is whether the estimate should be an admissible (link) estimate or not? If there are dead-ends in the topology of the search space, it is better to estimate their possibility of existence on our selected path.
Soundness: The plan formed before the execution should make sense. In a robot-doors domain, it does not make sense to "open the door" if the precondition that the robot is close to the door is not satisfied (the robot actually is 10m away from the door - in this case, the robot actuators might try to "open the door" in thin air). It is important that the plan sent for execution is sound, and does not cause a catastrophic effect (such as malfunctioning of robot actuators).
Most Constraining Choice First
Another heuristic for cost repair guidance is that the most constraining action should be fixed first. If there is some action that must be carried out (and there is no other choice), then it should be locked. This is similar to the fail-first principle used in CSP (see the tutorial on CSP by Bartak in ICAPS 2008). A good paper that significantly advances the idea of constraining choices is [2].
Most Likely Choice First
The instantiation value of a choice should be so that it makes the likelihood of production of plan the easiest/fastest. This is similar to the succeed-first principle used in CSP.
Case Based Reasoning
From the previous applications of heuristics, idea about 1) goodness of application of each heuristic, 2) time the heuristic took, 3) resources that were used by the heuristic, 4) how uncertain we are of the goodness of the heuristic, in the respective state may be stored. Next time the better heuristics for the purpose may be used.
Criteria for Scheduling Repairs
Some criteria for decision making for scheduling repairs are: 1) Available time to complete planning for the goal, 2) available resources, 3) Difficulty of the goal and 4) Priority of the goal.
Avoiding Interference Between Goals
If there are two goals that need mutual exclusive conditions to achieve the two goals, the two goals cannot be simultaneously achieved. This means one of the goals must be abandoned if there is not sufficient time available to achieve both of them [3].
I am sure there are more meta/hyper-heuristics for search guidance. I will write later on those.
References
[1] "Planning by Rewriting - Efficiently Generating High-Quality Plans" Ambite and Knoblock. They identified some transformation rules - collapse, expand, reorder, parallelize - to alter the plan within one iteration. May be somewhat useful reference for metaplanning.
[2] "Finding Crucial Subproblems to Focus Global Search" Susan L. Epstein, Richard J. Wallace. ICTAI 2006.
[3] "Detecting and Avoiding Interference Between Goals in Intelligent Agents"
Do Something Now
Since limited time is available before execution starts, actions that need to be taken early on should be decided first, locked and sent for execution. Suppose there are two actions that could be executed under the current environment, a1 and a2. But executing one of the two actions is important right now to be able to succeed within time.
This is a question related to deliberation versus reaction. Should an agent think more or start execution? How much should the agent think, and how much execute?
To fix an action early on, there may be a way to measure the difficulty of reaching the goals from the states s1 and s2, reached when a1 and a2 respectively are executed in plan. Once the CostCenter has computed, for example, that s1 is much farther from goal than s2, a2 may be locked for execution.
Difficulty versus Priority: Note that difficulty of reaching a goal is a separate concern from the priority or urgency of reaching the goal. Each Cost should contain information both about difficulty and priority.
Estimating difficulty of reaching goal: How to estimate the difficulty of reaching the goal? Estimation should not consume so much time that it offsets the benefit of finer approximation of estimate. Depending on the situation, finer estimation may be more useful or not. One question in this regard is whether the estimate should be an admissible (link) estimate or not? If there are dead-ends in the topology of the search space, it is better to estimate their possibility of existence on our selected path.
Soundness: The plan formed before the execution should make sense. In a robot-doors domain, it does not make sense to "open the door" if the precondition that the robot is close to the door is not satisfied (the robot actually is 10m away from the door - in this case, the robot actuators might try to "open the door" in thin air). It is important that the plan sent for execution is sound, and does not cause a catastrophic effect (such as malfunctioning of robot actuators).
Most Constraining Choice First
Another heuristic for cost repair guidance is that the most constraining action should be fixed first. If there is some action that must be carried out (and there is no other choice), then it should be locked. This is similar to the fail-first principle used in CSP (see the tutorial on CSP by Bartak in ICAPS 2008). A good paper that significantly advances the idea of constraining choices is [2].
Most Likely Choice First
The instantiation value of a choice should be so that it makes the likelihood of production of plan the easiest/fastest. This is similar to the succeed-first principle used in CSP.
Case Based Reasoning
From the previous applications of heuristics, idea about 1) goodness of application of each heuristic, 2) time the heuristic took, 3) resources that were used by the heuristic, 4) how uncertain we are of the goodness of the heuristic, in the respective state may be stored. Next time the better heuristics for the purpose may be used.
Criteria for Scheduling Repairs
Some criteria for decision making for scheduling repairs are: 1) Available time to complete planning for the goal, 2) available resources, 3) Difficulty of the goal and 4) Priority of the goal.
Avoiding Interference Between Goals
If there are two goals that need mutual exclusive conditions to achieve the two goals, the two goals cannot be simultaneously achieved. This means one of the goals must be abandoned if there is not sufficient time available to achieve both of them [3].
I am sure there are more meta/hyper-heuristics for search guidance. I will write later on those.
References
[1] "Planning by Rewriting - Efficiently Generating High-Quality Plans" Ambite and Knoblock. They identified some transformation rules - collapse, expand, reorder, parallelize - to alter the plan within one iteration. May be somewhat useful reference for metaplanning.
[2] "Finding Crucial Subproblems to Focus Global Search" Susan L. Epstein, Richard J. Wallace. ICTAI 2006.
[3] "Detecting and Avoiding Interference Between Goals in Intelligent Agents"
Heuristics Selection - Context Matching or Probabilistic Selection? Careful or Faster?
We target the problem of selecting proper heuristics for repair of a particular cost. The following things are important here: 1) What features of the current situation are important in selection of heuristic (and need to be stored)?, 2) How to measure the goodness of various heuristics in this situation?, 3) Given the features and goodness of various heuristics, how to select a good heuristic for application?
Availability of limited memory implies only limited number of features of a situation can be stored. Availability of limited computational resources implies only a little computation can be used to match the current situation with the features stored and to evaluate the goodness of various heuristics for updation of heuristic preferences. Also only limited time can be used for selecting good heuristic for application.
Features
A heuristic internally has several choice points. For example, a heuristic to add an action has internally the choices: which action to insert, which parameters to use to instantiate the action, which start time of action to use. Each choice point needs to store:
1) The context of the choice (for example, the current state and the desired state)
2) Evaluated goodness in the context. It may be noted that there may be defined a distance function between contexts.
Goodness
The goodness of a heuristic may be measured using a machine learning technique like Q-Learning.
Selection
The two extremes of implementation of heuristics selection are:
1) We store nothing, only a few simple choices for selection of appropriate class of heuristics. This is close to the current implementation. We choose an appropriate heuristic more or less randomly (actually it is not completely randomly but guided by the past experiences of heuristic selection (link to Alex's paper on this)). In this case, we expect fast reaction (due to simple heuristic selection), but will perform well only in domains where mistakes are tolerable and/or correctable. This is a less careful approach, but faster.
2) We store many features of each situation. Then the investigation of which heuristic to apply in a particular case takes more time. This is a more careful approach, but slower.
It may be argued that the faster approach may not be preferable for huge (exponential) search spaces with non-trivial structure. Randomly and quickly assigning some values for search may not work well when there is a huge space to search.
Indeed one way to approach the problem is to try something trivial. If it works then good, else try more time-taking more careful techniques. The preference values of what do not work may be temporarily reduced.
Availability of limited memory implies only limited number of features of a situation can be stored. Availability of limited computational resources implies only a little computation can be used to match the current situation with the features stored and to evaluate the goodness of various heuristics for updation of heuristic preferences. Also only limited time can be used for selecting good heuristic for application.
Features
A heuristic internally has several choice points. For example, a heuristic to add an action has internally the choices: which action to insert, which parameters to use to instantiate the action, which start time of action to use. Each choice point needs to store:
1) The context of the choice (for example, the current state and the desired state)
2) Evaluated goodness in the context. It may be noted that there may be defined a distance function between contexts.
Goodness
The goodness of a heuristic may be measured using a machine learning technique like Q-Learning.
Selection
The two extremes of implementation of heuristics selection are:
1) We store nothing, only a few simple choices for selection of appropriate class of heuristics. This is close to the current implementation. We choose an appropriate heuristic more or less randomly (actually it is not completely randomly but guided by the past experiences of heuristic selection (link to Alex's paper on this)). In this case, we expect fast reaction (due to simple heuristic selection), but will perform well only in domains where mistakes are tolerable and/or correctable. This is a less careful approach, but faster.
2) We store many features of each situation. Then the investigation of which heuristic to apply in a particular case takes more time. This is a more careful approach, but slower.
It may be argued that the faster approach may not be preferable for huge (exponential) search spaces with non-trivial structure. Randomly and quickly assigning some values for search may not work well when there is a huge space to search.
Indeed one way to approach the problem is to try something trivial. If it works then good, else try more time-taking more careful techniques. The preference values of what do not work may be temporarily reduced.
Tuesday, January 6, 2009
Should Heuristics refer to PlanManager?
We decided earlier that each Cost is fixed by one particular CostCenter - this mapping is statically defined. While this decision simplifies the workflow of Cost Repair, it creates new problems.
Take the case of Logistics domain. We have actions of LoadTruck, UnloadTruck and MoveTruck that modify the location of a packet. We have a goal to move a certain packet_1 from one location to another. According to our decision, this goal is a Cost to be repaired by the location attribute of packet_1.
The location attribute of packet_1 knows about the actions that alter its value. The actions LoadTruck and UnloadTruck do. However, for repair of the Cost, a truck is needed (on which the packet will be loaded). Now the location attribute of packet_1 does not know anything about a good truck to instantiate LoadTruck.
There are two options here: 1) the location attribute instantiates LoadTruck with a random truck (in the hope that the resultant cost will be fixed later), or 2) the location attribute asks the PlanManager about a good truck.
In the first option, we need to introduce a heuristic changeParameter to change a parameter of the LoadTruck action later. Also, probably it is better for the PlanManager to remember (and not lose the information) that a random truck was used to instantiate the LoadTruck action and fix the associated cost in this manner. One simple way to implement this is by using a dummy truck (which is a placeholder for a real truck) to instantiate LoadTruck. Cost due to dummy truck will be fixed by a new changeParameter heuristic.
The second option is quite intrusive change, more unpredictable and thus more difficult to parallelize. It is more unpredictable because the PlanManager may be busy with other tasks when the request for a good truck came, in which case the requesting location attribute would have to wait. However, it is noted that the second option may be needed to be used in more complex repairs, but not in the simple case we are dealing with right now.
Another thing: Note that in the first option, we would like to call changeParameter heuristic (and no other heuristic) whenever the Cost is on the dummy object. Therefore, in general a CostCenter must perform some pre-inspection to select an appropriate class of heuristics to fix a particular cost (this pre-inspection right now includes looking at the type of cost - whether it is a goal cost of condition cost).
Take the case of Logistics domain. We have actions of LoadTruck, UnloadTruck and MoveTruck that modify the location of a packet. We have a goal to move a certain packet_1 from one location to another. According to our decision, this goal is a Cost to be repaired by the location attribute of packet_1.
The location attribute of packet_1 knows about the actions that alter its value. The actions LoadTruck and UnloadTruck do. However, for repair of the Cost, a truck is needed (on which the packet will be loaded). Now the location attribute of packet_1 does not know anything about a good truck to instantiate LoadTruck.
There are two options here: 1) the location attribute instantiates LoadTruck with a random truck (in the hope that the resultant cost will be fixed later), or 2) the location attribute asks the PlanManager about a good truck.
In the first option, we need to introduce a heuristic changeParameter to change a parameter of the LoadTruck action later. Also, probably it is better for the PlanManager to remember (and not lose the information) that a random truck was used to instantiate the LoadTruck action and fix the associated cost in this manner. One simple way to implement this is by using a dummy truck (which is a placeholder for a real truck) to instantiate LoadTruck. Cost due to dummy truck will be fixed by a new changeParameter heuristic.
The second option is quite intrusive change, more unpredictable and thus more difficult to parallelize. It is more unpredictable because the PlanManager may be busy with other tasks when the request for a good truck came, in which case the requesting location attribute would have to wait. However, it is noted that the second option may be needed to be used in more complex repairs, but not in the simple case we are dealing with right now.
Another thing: Note that in the first option, we would like to call changeParameter heuristic (and no other heuristic) whenever the Cost is on the dummy object. Therefore, in general a CostCenter must perform some pre-inspection to select an appropriate class of heuristics to fix a particular cost (this pre-inspection right now includes looking at the type of cost - whether it is a goal cost of condition cost).
Subscribe to:
Posts (Atom)