Methods and apparatus for heuristic search to optimize metrics in generating a plan having a series of actions

• US 7,533,073 B2
• Filed: 12/05/2006
• Issued: 05/12/2009
• Est. Priority Date: 12/05/2005
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Howard, Michael D., Huang, Eric
• Primary Examiner(s): Starks, Jr.; Wilbert L
• Application Number:
  US11/566,984
• Publication Number:
  US 20070129834A1
• Time in Patent Office: 889 Days
• Field of Search: 706/47, 706/45
• US Class Current: 706/47
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

Methods and apparatus to provide techniques for planners that records constraints over a set of numeric state variables for each fact and characterizes the set of states in which that fact is true to provide more information to reason about mutual exclusions among sets of states offering a tighter bound on the metric cost of a plan than existing planners currently attain. This more accurate estimate can avoid irrelevant states and decrease search times.

Claims

1. A method of generating a plan for a planner including tightening bounds on a metric cost of the plan, comprising:

tagging a fact with a compressed representation of relaxed states that can make the fact true;

generating, using a computer, the compressed representation as a range of possible values that a numeric variable for the relaxed states can possibly take on when the fact is true, where the range of the numeric variable includes a set of disjoint ranges;

computing a new range of values for the numeric variables as a combination of ranges of values tagged on each precondition of an action modified by effects of the action; and

outputting the plan in a format to enable display for a user to make decisions for reaching a plan goal.

2. The method according to claim 1, further including computing the new range of values for the numeric variables as a logical AND of ranges of values tagged on each precondition of an action modified by effects of the action.

3. The method according to claim 1, further including applying the effects of the action by shifting the range of numeric values in the state by an amount of the action'"'"'s effect on the numeric variable.

4. The method according to claim 3, further including a search termination criterion that is true when all actions have been applied without altering the ranges of numeric variables tagged to any fact.

5. A computer-implemented method of generating a plan, comprising:

associating with each fact in each state a compressed representation of all of the relaxed states that can make the each fact true, wherein the compressed representation is a range of possible values that each numeric variable can possibly take on when the fact is true; and

outputting the plan in a format to enable display for a user to make decisions for reaching a plan goal.

6. The method according to claim 5, wherein the range of each of the numeric variables can be a set of disjoint ranges.

7. The method according to claim 6, wherein each of the facts is tagged with a list of enabling actions, each of the actions associated with the set of bounds on numeric variables that represents the supporting subgraph through that action.

8. The method according to claim 7, further including using an update rule that describes when an action is applicable in a particular state of the numeric variables.

9. The method according to claim 8, wherein the numeric bounds of the variables associated with each precondition fact of the action are merged using a disjunction.

10. The method according to claim 8, further including, if there are any numeric preconditions to the action, conjoining the numeric preconditions with the merged numeric state, which can result in contraction of the range of the numeric bounds on one or more of the numeric variables.

11. A method of generating a plan for a planner that can produce tighter bounds on a metric cost of the plan, comprising:

for a first state, tagging a first fact with a first enabling action;

for a second state, tagging a second fact with a second enabling action;

for a third state, tagging the first and second facts with a joint action to generate a choice of actions to achieve planning goals;

computing, using a computer, a constrained metric from a range of numeric fluents associated with the first and second facts that represents the lowest cost way to achieve each precondition of an action, and can be used to select a first one of the choice of actions; and

outputting the plan in a format to enable display for a user to make decisions for reaching a plan goal.

12. The method according to claim 11, further including tagging the first fact with an action'"'"'s preconditions including a set of bounds on the numeric fluents of the first fact representing a compressed history of actions it required to establish the first fact.

13. The method according to claim 11, wherein computing the metric further includes shifting bounds for the numeric fluents, by the amount of the effects of each action.

14. The method according to claim 13, wherein the shifting bounds includes shifting downward.

15. The method according to claim 13, wherein the shifting bounds includes shifting downward or upward.

16. A system for generating a plan, comprising:

a first means for tagging facts with enabling actions; and

a second means for computing a metric to tighten bounds on a metric cost of the plan.

17. The system according to claim 16, wherein the second means can contract the bounds.