ONLINE CONTINUAL AUTOMATED PLANNING FRAMEWORK BASED ON TIMELINES

• US 20120185286A1
• Filed: 01/17/2011
• Published: 07/19/2012
• Est. Priority Date: 01/17/2011
• Status: Abandoned Application

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Do, Minh Binh
• Application Number:
  US13/007,790
• Publication Number:
  US 20120185286A1
• Time in Patent Office: Days
• US Class Current: 705/7.12
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations

Abstract

An online planning system and method represents variables in an environment for which a plan is being developed in the form of timelines. The timelines are continually maintained by capturing how different ones of the variables change their values over time. The plan being a consistent plan built and maintained by adding tokens to affected timelines, wherein each token represents different types of actions affecting the variable represented by that timeline.

Claims

1. An online planning method comprising:

representing variables in an environment for which a plan is being developed in the form of a sequence of actions and the corresponding timelines representing the plan'"'"'s effects on the world state;

continually maintaining the timelines that capture how different ones of the variables change their values over time; and

building and maintaining consistent plans by adding tokens to affected timelines, wherein each token represents different types of cosnstraints and effects actions affecting the variable represented by that timeline.

2. The method of claim 1 wherein each timeline represents at least a distinct variable of the variables.

3. The method according to claim 1 wherein each variable has a state that changes over time.

4. The method according to claim 1 wherein the state is represented by a set of variables

5. The method according to claim 1 wherein each timeline comprises the current value of the variable it is representing and a set of tokens representing constraints and changes on variable value at different times.

6. The method according to claim 1 wherein each token represents an action'"'"'s condition or effect affecting the associated variable and each token is added to the associated timeline due to actions in the plan that affect the value of the variable.

7. The method according to claim 1 wherein each token has an earliest time point and a latest time point that the action can occur.

8. The method according to claim 1 wherein the plan is formed using as an input a goal set and a consistent set of timelines representing all operations occurring after a current wall-clock time that affects any state of the variables.

9. The method of claim 1 wherein the plan is defined by a sequence of actions.

10. A timeline-based continual on-line planning and scheduling method for determination of a sequence of actions that when executed from a known initial state achieves all pre-defined goals, the method being performed by a planner residing within a computer control system having a memory storage, the method comprising:

building and maintains a consistent valid plan by adding tokens to affected timelines, wherein;

the plan is defined by a sequence of actions;

each timeline represents a variable;

each variable has a value that changes over time;

each timeline comprises the current value of the variable and a set of tokens, each token representing an condition or effect of an action affecting the variable and the adding of tokens to timelines due to actions in the plan that affect the value of the variable.

11. The method of claim 10, wherein each token has an earliest time point and a latest time point.

12. The method of claim 10, wherein the planner takes as an input a goal set and a consistent set of timelines representing all operations occurring after the current wall-clock time that affect any state variables.

13. The method of claim 10, wherein the plan is valid if:

the plan achieves the desired goal or set of goals, wherein;

the plan represented by the set of timelines achieves the desired goal if at the end the timelines the end value of the last token matches the goal; and

the set of goals is achieved when for all goals in the goal set the end value of the last token of a timeline representing the goal variable satisfies the goal;

all tokens caused by the actions in the plan are able to start after the wall-clock time when the plan is found; and

adding all tokens caused by the plan does not cause any inconsistencies, wherein the plan is consistent if the set of timelines for all variables are;

value consistent, wherein the timeline is value consistent if consecutive tokens on the same timeline make up a consistent sequence of changes, wherein the end value of a given token matches with the start value of the next token; and

temporal consistent, wherein the timeline is temporal consistent if all tokens that are added to the timeline do not cause the value of a variable to conflict the value of the same variable in another timeline.

14. The method of claim 13, wherein:

each token is represented by a start time point and an end time point, a start value of the variable for discrete or continuous variables or an upper and lower bounds on the start value for continuous variables, and a change operation specifying how the variable value changes during the token duration;

there is a temporal relation between tokens that represent a condition to or effect of the same action or represent a condition to or effect of actions that are related to one another, wherein related actions are actions that are dependent upon the results of one another.

15. The method of claim 13, wherein the planner determines a plan by starting with an empty plan, the empty plan is inputted into the core planning component, wherein the core planning component:

adds or replace actions to the inputted plan to create the set of plans;

generates and maintains the state for each plan in the set of plans, wherein each state is composed of the actions of the plan and the timelines resulting from adding tokens caused by the actions to the original timelines;

removing inconsistent plans;

choosing the best plan from the set of states and associated plan;

checking the best plan and associated state space for validity;

if the best plan is invalid, the best plan and associated state space is inputted into the core planning component and the process repeated until a valid plan is reached;

if the best plan is valid, then the best plan is executed and its effects are incorporated into the continually maintained timelines.

16. An apparatus comprising:

a digital processing device configured to perform a timeline-based continual on-line planning and scheduling method for determination of a sequence of actions that when executed from a known initial state achieves all pre-defined goals, wherein the method is performed by a planner residing within a computer control system having a memory storage, wherein the planner builds and maintains a consistent valid plan by adding tokens to affected timelines, wherein;

the plan is defined by a sequence of actions;

each timeline represents a variable;

each variable has state that change over time;

each timeline comprises the current value of the variable and a set of tokens;

wherein a token represents an action affecting the variable and tokens are added to timelines due to actions in the plan that affect he value of the variable;

each token has an earliest time point and a latest time point that the action can occur; and

the planner takes as an input a goal set and a consistent set of timelines representing all operations occurring after the current wall-clock time that affect any state variables.

17. The method of claim 16, wherein the plan is valid if:

the plan achieves the desired goal or set of goals, wherein;

the plan represented by the set of timelines achieves the desired goal if at the end the timelines the end value of the last token matches the goal; and

the set of goals is achieved when for all goals in the goal set the end value of the last token of a consistent timeline representing that goal satisfies the goal;

all tokens caused by the actions in the plan are able to start after the wall-clock time when the plan is found; and

adding all tokens caused by the plan does not cause any inconsistencies, wherein the plan is consistent if the set of timelines for all variables in the plan are;

value consistent, wherein the timeline is value consistent if consecutive tokens on the same timeline make up a consistent sequence of changes, wherein the end value of a given token matches with the start value of the next token; and

temporal consistent, wherein the timeline is temporal consistent if all tokens that are added to the timeline do not cause the value of a variable to conflict the value of the same variable in another timeline.

18. The method of claim 17, wherein:

each token is represented by a start time point and an end time point, a start value of the variable for discrete or continuous variables or an upper and lower bounds on the start value for continuous variables, and a change operation specifying how the variable value changes during the token duration ;

there is a temporal relation between tokens that represent a condition to or effect of the same action or represent a condition to or effect of actions that are related to one another, wherein related actions are actions that are dependent upon the results of one another.

19. The method of claim 17, wherein the planner determines a plan by starting with an empty plan, the empty plan is inputted into the core planning component, wherein the core planning component:

adds actions to the inputted plan to create the set of plans;

generates and maintains the state for each plan in the set of plans, wherein each state is composed of the actions of the plan and the timelines resulting from adding tokens caused by the actions to the original timelines;

removing inconsistent plans;

choosing the best plan from the set of states and associated plan;

checking the best plan and associated state space for validity;

if the best plan is invalid, the best plan and associated state space is inputted into the core planning component and the process repeated until a valid plan is reached;

if the best plan is valid, then the best plan is executed and its effects are incorporated into the continually maintained timelines.