Feedback control of problem solving

• US 7,089,221 B2
• Filed: 06/24/2003
• Issued: 08/08/2006
• Est. Priority Date: 06/24/2003
• Status: Expired due to Fees

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Crawford, Lara S., Fromherz, Markus P. J., Shang, Yi
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US10/602,193
• Publication Number:
  US 20040267680A1
• Time in Patent Office: 1,141 Days
• Field of Search: 706/13, 706/46, 706/19, 706/45, 706/60, 706/14, 370/216
• US Class Current: 706/46
• CPC Class Codes: G05B 13/021 in which a variable is automatically adjusted to optimise the performance

Abstract

A method for feedback control of cooperative problem solving for real-time applications in complex systems utilizes solvers parameterized by control variables. The method includes initializing the time setting and selecting at least one solver parameter value. The solver is operated with the selected solver parameter value or values for a specified interim and the operational conditions are reviewed. A solution is transmitted to the system if a solution quality condition is satisfied. The solver continues to operate if the solution quality condition is not satisfied and the performance differential is not greater than a specified threshold. If the solution quality condition is unsatisfied, but the performance differential exceeds the threshold, at least one alternate solver parameter value is selected and the solver is operated with the new solver parameter value for a specified interim. The solver continues to operate until the solution quality condition is satisfied.

Claims

1. A method of feedback control of cooperative problem solving for providing resolution of control problems within a computer controlled system having a plurality of subsystems, each having networked sensors and implementation units, with each subsystem having control, monitoring, and fault diagnosis capabilities, wherein the computer controlled system includes an applications module within which reside a control module and a problem solver, wherein the control module receives instructions as to resource constraints and system performance goals and current state data from the implementation units, wherein the problem solver utilizes a plurality of solvers to resolve system performance problems, and wherein the control module transmits commands to the subsystem controllers directing operation of the implementation units, the method comprising:

initializing the time setting;

defining a system performance problem to be solved utilizing the plurality of constraint problem solvers, wherein said problem statement includes system performance constraints, current state of the implementation units, system performance goals, a desired solution quality, and a time deadline for solving the said system performance problem;

selecting not less than one solver parameter value, wherein said solver parameter value satisfies said implementation unit usage constraints within a specified time bound, such that expected solution quality is optimal;

operating the solver with said not less than one selected solver parameter value for a specified interim;

reviewing solver operational conditions, wherein said operational conditions include a performance measure, comprising the difference between expected performance and actual performance, and solution quality;

transmitting a solution of the system performance problem to the control module for formulation of control signals to be transmitted to the subsystem controllers for the implementation units affected if said solution quality condition is satisfied;

continuing to operate the solver with said not less than one selected solver parameter value if said solution quality condition is not satisfied and said difference between expected performance and said actual performance is not above a specified threshold;

selecting not less than one alternate solver parameter value if said solution quality condition is not satisfied and said difference between expected performance and said actual performance is above a specified threshold;

operating the solver with said not less than one alternate solver parameter value for a specified interim; and

continuing to operate the solver with said not less than one alternate solver parameter values until said solution quality condition is satisfied.

2. The method for feedback control of cooperative problem solving according to claim 1, wherein said specified interim comprises a specified number of steps.

3. The method for feedback control of cooperative problem solving according to claim 1, wherein said specified interim comprises a specified amount of time.

4. The method for feedback control of cooperative problem solving according to claim 1, wherein said solution quality is defined as the value of the objective function.

5. The method for feedback control of cooperative problem solving according to claim 1, wherein said performance measure comprises the improvement in the value of the objective function.

6. The method for feedback control of cooperative problem solving according to claim 1, wherein said performance measure comprises the number of function evaluations required per iteration in a continuous solver.

7. The method for feedback control of cooperative problem solving according to claim 1, wherein said performance measure comprises the number of backtracks required per time unit in a depth-first search solver.

8. The method for feedback control of cooperative problem solving according to claim 1, wherein said operational conditions further include violation of resource constrains.

9. The method for feedback control of cooperative problem solving according to claim 8, further comprising continuing to operate the solver with said not less than one selected solver parameter value if said solution quality condition is not satisfied, said difference between expected performance and said actual performance is not above a specified threshold, and said resource constraints arc not violated.

10. The method for feedback control of cooperative problem solving according to claim 8, further comprising selecting nor less than one alternate solver parameter value if said solution quality condition is not satisfied and said resource constraints are violated.

11. The method for feedback control of cooperative problem solving according to claim 1, wherein said operational conditions further include reaching a specified time bound.

12. The method for feedback control of cooperative problem solving according to claim 11, further comprising continuing to operate the solver with said not less than one selected solver parameter value if said solution quality condition is not satisfied, said time bound is not reached, and said difference between expected performance and said actual performance is not above a specified threshold.

13. The method for feedback control of cooperative problem solving according to claim 11, further comprising transmitting a solution to the system if said time bound is reached.

14. The method for feedback control of cooperative problem solving according to claim 11, further comprising selecting not less than one alternate solver parameter value if said solution quality condition is not satisfied, said time bound is not reached, and said difference between expected performance and said actual performance is above a specified threshold.

15. The method for feedback control of cooperative problem solving according to claim 1, wherein said operational conditions further include reaching a specified rime bound and violation of resource constraints.

16. The method for feedback control of cooperative problem solving according to claim 15, further comprising transmitting a solution to the system if said solution quality condition is satisfied or said time bound is reached.

17. The method for feedback control of cooperative problem solving according to claim 15, further comprising continuing to operate the solver with said not less than one selected solver parameter value if said solution quality condition is not satisfied, said time bound is not reached, said difference between expected performance and said actual performance is not above a specified threshold, and said resource constraints are not violated.

18. The method for feedback control of cooperative problem solving according to claim 15, further comprising selecting not less than one alternate solver parameter value if said solution quality condition is not satisfied, said time bound is not reached, and said resource constraints have been violated.

19. A system of feedback control of cooperative problem solving for providing resolution of control problems within a computer controlled system having a plurality of subsystems, each having networked sensors and implementation units, with each subsystem having control, monitoring, and fault diagnosis capabilities, wherein the computer controlled system includes an applications module within which reside a control module and a problem solver, wherein the control module receives instructions as to resource constraints and system performance goals and current state data from the implementation units, wherein the problem solver utilizes a plurality of solvers to resolve system performance problems, and wherein the control module transmits commands to the subsystem controllers directing operation of the implementation units, the system comprising:

means for initializing the time setting;

defining a system performance problem to be solved utilizing the plurality of constraint problem solvers, wherein said problem statement includes system performance constraints, current stare of the implementation units, system performance goals, a desired solution quality, and a time deadline for solving the said system performance problem;

means for selecting not less than one solver parameter value, wherein said solver parameter value satisfies said implementation unit usage constraints within a specified time bound, such that expected solution quality is optimal;

means for operating the solver with said not less than one selected solver parameter value for a specified interim;

means for reviewing solver operational conditions, wherein said operational conditions include a performance measure, comprising the difference between expected performance and actual performance, and solution quality;

means for transmitting a solution of the system performance problem to the control module for formulation of control signals to be transmitted to the subsystem controllers for the implementation units affected if said solution quality condition is satisfied;

means for continuing to operate the solver with said not less than one selected solver parameter value if said solution quality condition is not satisfied and said difference between expected performance and said actual performance is not above a specified threshold;

means for selecting not less than one alternate solver parameter value if said solution quality condition is not satisfied and said difference between expected performance and said actual performance is above a specified threshold;

means for operating the solver with said not less than one alternate solver parameter value for a specified interim; and

means for continuing to operate the solver with said not less than one alternate solver parameter values until said solution quality condition is satisfied.

20. The system for feedback control of cooperative problem solving according to claim 19, wherein said operational conditions further include violation of resource constraints.

21. The system for feedback control of cooperative problem solving according to claim 20, further comprising means for continuing to operate the solver with said not less than one selected solver parameter value if said solution quality condition is not satisfied, said difference between expected performance and said actual performance is not above a specified threshold, and said resource constraints are not violated.

22. The system for feedback control of cooperative problem solving according to claim 20, further comprising means for selecting not less than one alternate solver parameter value if said solution quality condition is not satisfied and said resource constraints are violated.

23. The system for feedback control of cooperative problem solving according to claim 19, wherein said operational conditions further include reaching a specified time bound.

24. The system for feedback control of cooperative problem solving according to claim 23, further comprising means for continuing to operate the solver with said got less than one selected solver parameter value if said solution quality condition is not satisfied, said time bound is not reached, and said difference between expected performance and said actual performance is not above a specified threshold.

25. The system for feedback control of cooperative problem solving according to claim 23, further comprising means for transmitting a solution to the system if said time bound is reached.

26. The system for feedback control of cooperative problem solving according to claim 23, further comprising means for selecting not less than one alternate solver parameter value if said solution quality condition is not satisfied, said time bound is not reached, and said difference between expected performance and said actual performance is above a specified threshold.

27. The system for feedback control of cooperative problem solving according to claim 19, wherein said operational conditions further include reaching a specified time bound and violation of resource constraints.

28. The system for feedback control of cooperative problem solving according to claim 27, further comprising means for transmitting a solution to the system if said solution quality condition is satisfied or said time bound is reached.

29. The system for feedback control of cooperative problem solving according to claim 27, further comprising means for continuing to operate the solver with said not less than one selected solver parameter value if said solution quality condition is not satisfied, said time bound is not reacted, said difference between expected performance and said actual performance is not above a specified threshold, and said resource constraints are not violated.

30. The system for feedback control of cooperative problem solving according to claim 27, further comprising means for selecting not less than one alternate solver parameter value if said solution quality condition is not satisfied, said time bound is not reached, and said resource constraints have been violated.

31. An article of manufacture comprising a computer usable medium having computer readable program code embodied in said medium which, when said program code is executed by said computer causes said computer to perform method steps for of feedback control of cooperative problem solving for providing resolution of control problems within a computer controlled system having a plurality of subsystems, each having networked sensors and implementation units, with each subsystem having control, monitoring, and fault diagnosis capabilities, wherein the computer controlled system includes an applications module within which reside a control module and a problem solver, wherein the control module receives instructions as to resource constraints and system performance goals and current state data from the implementation units, wherein the problem solver utilizes a plurality of solvers to resolve system performance problems, and wherein the control module transmits commands to the subsystem controllers directing operation of the implementation units, the method comprising:

initializing the time setting;

defining a system performance problem to be solved utilizing the plurality of constraint problem solvers, wherein said problem statement includes system performance constraints, current state of the implementation unit, system performance goals, a desired solution quality, and a time deadline for solving the said system performance problem;

selecting not less than one solver parameter value, wherein said solver parameter value satisfies said implementation unit usage constraints within a specified time bound, such that expected solution quality is optimal;

operating the solver with said not less than one selected solver parameter value for a specified interim;

reviewing solver operational conditions, wherein said operational conditions include a performance measure, comprising the difference between expected performance and actual performance, and solution quality;

transmitting a solution of the system performance problem to the control module for formulation of control signals to be transmitted to the subsystem controllers for the implementation units affected if said solution quality condition is satisfied;

continuing to operate the solver with said not less than one selected solver parameter value if said solution quality condition is not satisfied and said difference between expected performance and said actual performance is not above a specified threshold;

selecting not less than one alternate solver parameter value if said solution quality condition is not satisfied and said difference between expected performance and said actual performance is above a specified threshold;

operating the solver with said not less than one alternate solver parameter value for a specified interim; and

continuing to operate the solver with said not less than one alternate solver parameter values until said solution quality condition is satisfied.