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.

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).

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.

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.

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.

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

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.

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