Automated plan synthesizer and plan execution method

• US 5,392,382 A
• Filed: 12/01/1992
• Issued: 02/21/1995
• Est. Priority Date: 12/01/1992
• Status: Expired due to Fees

• Current Assignee: Marcel J. Schoppers
• Original Assignee: Marcel J. Schoppers
• Inventors: Schoppers, Marcel J.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): HAFIZ, TARIQ R
• Application Number:
  US07/983,836
• Time in Patent Office: 812 Days
• Field of Search: 395/10, 395/11, 395/22, 395/81, 395/82, 395/85
• US Class Current: 706/62
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

A reactive planning system automatically generates a universal plan for achieving specified goals. The universal plan is derived from a set of primitive and deductive rules governing operation of one or more actuators, and the specified goals. The universal plan contains tree structure defining predicates, actions and subplans for achieving the specified goals, and subgoals of those goals. Also included in the universal plan generated by the system are a set of confinement rules which determine the proper order for achieving unmet goals. During operation of the system, after the universal plan has been formulated, a plan interpreter or executer determines the subgoals that have yet to be met, and then selects one or more subgoals as being the appropriate ones to be worked on at the current time. More particularly, to select a goal or subgoal for processing, the plan executer first determines the set of goals that are currently achievable, which is the set of goals for which all preconditions and subgoals have been met. Then all the confinement rules in the universal plan are scanned to determine which of those rules are applicable to the goals that are currently achievable. Application of the confinement rules evaluates all interactions between subplans and determines what goals are protectable and thus can be achieved without causing a conflict between subplans.

Claims

1. A reactive planning and plan execution method for accomplishing a specified set of goals with a predefined set of actuators in a physical system, the steps of the method comprising:

storing a specified set of primitives that define said physical system, primitive actions that can be performed by said actuators, and changes in the defined physical system effected by said primitive actions;

said set of primitives including primitives that specify goals and subgoals with respect to each primitive action that can be performed by said actuators;

generating and storing in said computer memory, based on said stored set of primitives and without regard to said specified set of goals, a set of confinement rules for ordering achievement of combinations of said goals and subgoals, each confinement rule containing both a single first goal (the rule'"'"'s First-Goal) to be achieved and a set of goals (the rule'"'"'s Conflict-Goals-Set), such that at least one goal in said Conflict-Goals-Set cannot be kept true when said First-Goal is being achieved;

wherein a first plurality of said confinement rules have at least two goals in their respective Conflict-Goals-Sets and constrain order of achievement of at least three goals without constraining order of achievement of any pair of said at least three goals;

generating and storing in a computer memory, based on said set of primitives and said predefined set of goals, a universal plan tree comprising a hierarchy of plans for accomplishing defined goals, said defined goals including said specified set of goals and subgoals thereof, wherein each plan in said hierarchy of plans specifies an action for accomplishing one of said defined goals, preconditions for taking said specified action and a set of subgoals that must be met before performing said specified action;

selecting and performing actions specified in said universal plan tree, said actions being performed using said predefined set of actuators in sequences consistent with said confinement rules, and repeating said selecting and performing steps until said specified set of goals is achieved.

2. The reactive planning and plan execution method of claim 1, wherein said selecting and performing steps include repeatedly performing the steps of:

determining which goals in said universal plan tree are currently achievable, applying said confinement rules to select from the currently achievable goals those which should be achieved first, and then performing the actions specified in said universal plan tree for accomplishing the selected goals.

3. The reactive planning and plan execution method of claim 1, wherein said performing actions step includes:

(A) evaluating the preconditions and defined goals in said universal plan tree so as to determine which of said defined goals in said universal plan tree are currently achievable goals;

(B) selecting one or more goals from among said currently achievable goals by determining which of said confinement rules are applicable thereto and selecting at least one currently achievable goal for which there is no confinement rule requiring another defined goal to be accomplished prior to achieving said selected goal;

(C) performing the action specified in said universal plan tree to accomplish said selected one or more goals;

(D) repeating steps A-C until all of said specified goals have been achieved.

4. The method of claim 3, wherein

a second plurality of said confinement rules include a qualifier such that said confinement rule is applicable only when said qualifier represents a condition that is true, and all other confinement rules include an implied qualifier that is always true;

and a third plurality of said confinement rules include subgoals that must be accomplished prior to achievement of said First-Goal and prior to achievement of the goals in said Conflict-Goals-Set;

said step of selecting one or more goals includes determining whether each currently achievable goal P is protectable, and selecting protectable ones of said currently achievable goals, if any, wherein a goal P is defined to be protectable when there is no confinement rule C in said set of confinement rules such that of the following criteria, (a) through (e) below are all true and one or both of criteria (f) and (g) are true;

(a) rule C'"'"'s first-goal has not yet been achieved or is a subgoal of a goal that has not yet been achieved;

(b) all the members of rule C'"'"'s conflict-goals-set have not yet been achieved or are subgoals of a goal that has not yet been achieved;

(c) rule C'"'"'s qualifier is true;

(d) the truth of P implies the truth of some member M of C'"'"'s conflict-goals-set;

(e) except for M, all other members of rule C'"'"'s conflict-goals-set, if any, are equivalent to, or are implied by, true and protectable subgoals in said plan tree;

(f) rule C'"'"'s first-goal is not both true and protectable; and

(g) rule C has a subgoal that is not both true and protectable; and

when no said confinement rule in said set of confinement rules meets said criteria with respect to goal P, goal P is denoted as being achievable and protectable.

5. The reactive planning and plan execution method of claim 1, wherein said step of generating and storing confinement rules includes

determining from said primitives whether each said goal for which confinement rules are being generated can be achieved when each potentially conflicting goal and each potential combination of potentially conflicting goals have been previously achieved, and

generating said confinement rules with each rule'"'"'s Conflict-Goals-Set equal to one of (A) a conflicting goal whose prior achievement and maintenance would prevent achievement of said each goal, and (B) a combination of conflicting goals whose prior achievement and maintenance would prevent achievement of said each goal.

6. The reactive planning and plan execution method of claim 5, wherein said step of generating confinement rules includes automatically generating subgoals for ones of said confinement rules by searching, with respect to each one confinement rule, for a chain of other confinement rules in said set of confinement rules which specify that achievement and maintenance of said one confinement rule'"'"'s First-Goal could prevent achievement of any goal in said one confinement rule'"'"'s Conflict-Goal-Set, and then adding a subgoal to said one confinement rule for each condition that would break said chain of other confinement rules so as to enable achievement of said goal in said one confinement rule'"'"'s Conflict-Goal-Set.

7. The reactive planning and plan execution method of claim 1, wherein said step of generating and storing confinement rules includes comparing confinement pairs of confinement rules having overlapping Conflict-Goal-Sets, and adding a qualifier to the one of said pair of confinement rules having the larger Conflict-Goal-Set to limit said one confinement rule'"'"'s applicability, wherein said added qualifier represents shared goals in said overlapping Conflict-Goal-Sets and such that said one confinement rule is applicable only when said added qualifier represents a condition that is true.

8. The reactive planning and plan execution method of claim 1, wherein a second plurality of said confinement rules each include a qualifier such that said each confinement rule is applicable only when said qualifier represents a condition that is true, and all other confinement rules include an implied qualifier that is always true.

9. The reactive planning and plan execution method of claim 1, wherein a second plurality of said confinement rules each include a qualifier such that said each confinement rule is applicable only when said qualifier represents a condition that is true and include subgoals that must be accomplished prior to achievement of said First-Goal and prior to achievement of the goals in said Conflict-Goals-Set.

10. A reactive planning and plan execution method for accomplishing a specified set of goals with a predefined set of actuators in a physical system, the steps of the method comprising:

storing a specified set of primitives that define said physical system, primitive actions that can be performed by said actuators, and changes in the defined physical system effected by said primitive actions;

said set of primitives including primitives that specify goals and subgoals with respect to each primitive action that can be performed by said actuators;

generating and storing in said computer memory, based on said stored set of primitives, a set of confinement rules for ordering said specified set of goals and all goals and subgoals of said primitive actions, each confinement rule containing both a single first goal (the rule'"'"'s First-Goal) to be achieved and a set of goals (the rule'"'"'s Conflict-Goals-Set), such that at least one goal in said Conflict-Goals-Set cannot all be kept true when said First-Goal is being achieved;

wherein a first plurality of said confinement rules have at least two goals in their respective Conflict-Goals-Sets and constrain order of achievement of at least three goals without constraining order of achievement of any pair of said at least three goals; and

wherein a second plurality of said confinement rules each include (A) a qualifier such that said each confinement rule is applicable only when said qualifier represents a condition that is true and (B) subgoals that must be accomplished prior to achievement of said First-Goal and prior to achievement of the goals in said Conflict-Goals-Set;

selecting and performing actions to achieve said specified set of goals and subgoals thereof, said actions being performed using said predefined set of actuators in sequences consistent with said confinement rules, and repeating said selecting and performing steps until said specified set of goals is achieved.

11. The reactive planning and plan execution method of claim 10, wherein said selecting and performing steps include repeatedly performing the steps of:

determining which of said specified set of goals and subgoals thereof am currently achievable, applying said confinement rules to select from the currently achievable goals those which should be achieved first, and then performing the actions specified by said primitive for accomplishing the selected goals.

12. The reactive planning and plan execution method of claim 10, wherein said performing actions step includes:

(A) evaluating the specified set of goals and subgoals of the primitive actions related thereto so as to determine which of said goals and subgoals are currently achievable goals;

(B) selecting one or more goals from among said currently achievable goals by determining which of said confinement rules are applicable thereto and selecting at least one currently achievable goal for which there is no confinement rule requiring another defined goal to be accomplished prior to achieving said selected goal;

(C) performing the action specified by said primitives to accomplish said selected one or more goals;

(D) repeating steps A-C until all of said specified goals have been achieved.

13. The method of claim 12, wherein

any confinement rules in said set of confinement rules that do not include said qualifier include an implied qualifier that is always true;

said step of selecting one or more goals includes determining whether each currently achievable goal P is protectable, and selecting protectable ones of said currently achievable goals, if any, wherein a goal P is defined to be protectable when there is no confinement rule C in said set of confinement rules such that of the following criteria, (a) through (e) below are all true and one or both of criteria (f) and (g) are true;

(a) rule C'"'"'s first-goal has not yet been achieved or is a subgoal of a goal that has not yet been achieved;

(b) all the members of rule C'"'"'s conflict-goals-set have not yet been achieved or are subgoals of a goal that has not yet been achieved;

(c) rule C'"'"'s qualifier is true;

(d) the truth of P implies the truth of some member M of C'"'"'s conflict-goals-set;

(e) except for M, all other members of rule C'"'"'s conflict-goals-set, if any, are equivalent to, or are implied by, true and protectable conditions;

(f) rule C'"'"'s first-goal is not both true and protectable; and

(g) rule C has a subgoal that is not both true and protectable; and

when no said confinement rule in said set of confinement rules meets said criteria with respect to goal P, goal P is denoted as being achievable and protectable.

14. The reactive planning and plan execution method of claim 10, wherein said step of generating and storing confinement rules includes

determining from said primitives whether each said goal for which confinement rules are being generated can be achieved when each potentially conflicting goal and each potential combination of potentially conflicting goals have been previously achieved, and

generating said confinement rules with each rule'"'"'s Conflict-Goals-Set equal to one of (A) a conflicting goal whose prior achievement and maintenance would prevent achievement of said each goal, and (B) a combination of conflicting goals whose prior achievement and maintenance would prevent achievement of said each goal.

15. The reactive planning and plan execution method of claim 14, wherein said step of generating confinement rules includes automatically generating subgoals for ones of said confinement rules by searching, with respect to each one confinement rule, for a chain of other confinement rules in said set of confinement rules which specify that achievement and maintenance of said one confinement rule'"'"'s First-Goal could prevent achievement of any goal in said one confinement rule'"'"'s Conflict-Goal-Set, and then adding a subgoal to said one confinement rule for each condition that would break said chain of other confinement rules so as to enable achievement of said goal in said one confinement rule'"'"'s Conflict-Goal-Set.

16. The reactive planning and plan execution method of claim 10, wherein said step of generating and storing confinement rules includes comparing confinement pairs of confinement rules having overlapping Conflict-Goal-Sets, and adding said qualifier to the one of said pair of confinement rules having the larger Conflict-Goal-Set to limit said one confinement rule'"'"'s applicability, wherein said added qualifier represents shared goals in said overlapping Conflict-Goal-Sets and such that said one confinement rule is applicable only when said added qualifier represents a condition that is true.