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"