Feedback control of problem solving

• US 20040267680A1
• Filed: 06/24/2003
• Published: 12/30/2004
• Est. Priority Date: 06/24/2003
• Status: Active Grant

• 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
• Granted Patent: US 7,089,221 B2
• Time in Patent Office: Days
• US Class Current: 706/19
• 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 for feedback control of cooperative problem solving for real-time applications in complex systems, wherein the method utilizes a plurality of solvers parameterized by control variables, the method comprising:

initializing the time setting;

selecting not less than one solver parameter value, 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 to the system 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 constraints.

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 are not violated.

10. The method for feedback control of cooperative problem solving according to claim 8, further comprising selecting not 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 time 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 for feedback control of cooperative problem solving for real-time applications in complex systems, wherein the system utilizes a plurality of solvers parameterized by control variables, the system comprising:

means for initializing the time setting;

means for selecting not less than one solver parameter value, 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 to the system 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 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.

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 reached, 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 feedback control of cooperative problem solving for real-time applications in complex systems, wherein each node includes a plurality of attributes having attribute values, the method comprising:

initializing the time setting;

selecting not less than one solver parameter value, 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 to the system 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.