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.