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.

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.

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.

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.

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.

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.

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"

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