Problem partitioning method and system

• US 20030120620A1
• Filed: 12/20/2001
• Published: 06/26/2003
• Est. Priority Date: 12/20/2001
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Reich, James E., Jackson, Warren B., Fromherz, Markus P.J.
• Granted Patent: US 6,922,681 B2
• Time in Patent Office: Days
• US Class Current: 706/45
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/043 Distributed expert systems; Blackboards

Abstract

In a problem partitioning method for problem solving in a computer system, a definition of a system to be controlled, a hierarchical control structure definition, problem definitions for a plurality of control nodes in the hierarchical control structure, and a structure evaluation function are used in partitioning the system problem. The partitioning method defines an instantiation of the hierarchical control structure by decomposing the system into a plurality of hierarchical control structure instances, with each control structure instance having a plurality of control levels. The performance of each of the hierarchical control structure instances is evaluated with the structure evaluation function and an optimal hierarchical control structure instance is selected.

Claims

1. A problem partitioning method for problem solving in a computer system, wherein the method comprises the steps of:

receiving the definition of a system to be controlled, wherein said system is controlled by a plurality of control elements;

receiving at least one hierarchical control structure definition including a plurality of structure parameters;

receiving problem definitions for a plurality of control nodes in said hierarchical control structure;

receiving a structure evaluation function; and

defining an instantiation of said hierarchical control structure comprising the steps of;

decomposing said system into a plurality of hierarchical control structure instances, wherein each of said hierarchical control structure instances includes a plurality of control levels, wherein each of said control levels includes at least one control node;

evaluating the performance of each of said hierarchical control structure instances with said structure evaluation function; and

selecting an optimal hierarchical control structure instance.

2. The problem partitioning method according to claim 1, wherein said plurality of structure parameters includes the number of nodes to be included at each level of said hierarchical control structure.

3. The problem partitioning method according to claim 1, wherein said plurality of structure parameters includes the number of levels to be included in said hierarchical control structure.

4. The problem partitioning method according to claim 1, further comprising the step of receiving a problem evaluation function for evaluating problem solving complexity for individual control nodes within said hierarchical structure.

5. The problem partitioning method according to claim 4, further comprising the steps of:

decomposing said hierarchical control structure from a first level by organizing said control elements into a plurality of hierarchical control structure configurations according to a grouping criterion, thereby forming a plurality of possible group configurations for said first level, wherein each said group configuration includes not less than one control node;

evaluating the performance of each of said group configuration with said problem evaluation function; and

selecting one said group configuration as optimal;

defining said selected group configuration as a second level;

determining whether each of said groups within said selected group configuration satisfies a decomposition criterion;

if said groups do not satisfy said decomposition criterion, decomposing said second level of control elements into a plurality of subgroups according to a grouping criterion, thereby forming a plurality of possible subgroup configurations;

evaluating the performance for each subgroup within each said subgroup configuration with said problem evaluation function;

selecting one said subgroup configuration as optimal, said subgroup configuration defining a next level;

determining whether each of said subgroups within said selected subgroup configuration satisfies said decomposition criterion;

repeating the steps of decomposing said next level of control elements into a plurality of subgroups to form a plurality of possible subgroup configurations, evaluating the performance for each subgroup within each said subgroup configuration, selecting one said subgroup configuration as optimal, and determining whether each of said subgroups within said selected subgroup configuration satisfies said decomposition criterion until the groups satisfy said decomposition criterion; and

discontinuing decomposition when said subgroups satisfy said decomposition criterion.

6. The problem partitioning method according to claim 1, wherein the step of selecting an optimal control structure configuration comprises creating groups of elements having equivalent properties.

7. The problem partitioning method according to claim 6, wherein said equivalent properties comprise one or more of identical position, identical direction, one identical position component, identical position, or identical force magnitude.

8. The problem partitioning method according to claim 1, wherein the step of selecting an optimal control structure configuration comprises using a fixed policy.

9. The problem solving method according to claim 8, wherein said fixed policy comprises grouping neighboring control elements.

10. The problem partitioning method according to claim 4, wherein said problem evaluation function is based on the structure of the problems to be partitioned.

11. The problem partitioning method according to claim 10, wherein said structure comprises a number of problem constraints in a problem to be partitioned and the number of expressions in said problem constraint terms.

12. The problem partitioning method according to claim 4, wherein said problem evaluation function is based on a performance model for solving problems with specific characteristics.

13. The problem partitioning method according to claim 12, wherein said specific characteristics comprise a number of problem constraints for the problem to be partitioned.

14. The problem partitioning method according to claim 12, wherein said specific characteristics comprise the number of variables in the problem to be partitioned

15. The problem partitioning method according to claim 1, wherein said structure evaluation function measures the time complexity of the problem to be solved.

16. The problem partitioning method according to claim 1, wherein said structure evaluation function measures the quality of solutions for the problem to be solved.

17. The problem partitioning method according to claim 1, wherein said structure evaluation function measures both the time complexity and the quality of solutions of the problem to be solved.

18. The problem partitioning method according to claim 1, wherein said system further comprises a plurality of hierarchical control structures, wherein each one of said plurality of hierarchical control structures includes its associated problem definitions and structure evaluation function.

19. The problem partitioning method according to claim 18, further comprising:

decomposing said system by decomposing each one of said plurality of hierarchical control structures; and

evaluating said system by evaluating each control structure configuration for each one said plurality of hierarchical control structures with said associated structure evaluation function.

20. The problem partitioning method according to claim 1, wherein said partitioning is performed on-line.

21. The problem partitioning method according to claim 5, wherein only group configurations at selected levels are repartitioned.

22. The problem partitioning method according to claim 5, wherein said decomposition criterion comprises specifying a maximum number of control elements.

23. The problem partitioning method according to claim 5, wherein said decomposition criterion comprises specifying a level of complexity determined by the problem evaluation function.

24. The problem partitioning method according to claim 1, wherein said structure evaluation function measures the memory use complexity of the problem to be solved.

25. A computer system for problem solving wherein the improvement is a problem partitioner, comprising:

an application controller for providing a definition of a system to be controlled to a solver distribution module, said system to be controlled having a plurality of actuators;

a decomposition module within said solver distribution module for decomposing said system into a plurality of hierarchical control structure instances;

an evaluation module for evaluating the performance of each of said hierarchical control structure instances; and

a control allocation module for grouping the actuators into modules for hierarchical allocation.

26. A computer system for problem solving according to claim 25, wherein said applications controller further provides a hierarchical control structure definition including a plurality of structure parameters to said solver distribution module.

27. A computer system for problem solving according to claim 25, wherein said applications controller further provides problem definitions for a plurality of nodes in said hierarchical control structure.

28. A computer system for problem solving according to claim 25, wherein said evaluation module select s an optimal hierarchical control structure instance.

29. A computer program product comprising:

a computer usable medium having computer readable program code means embedded in said medium for causing the partitioning of a problem to be solved by a computer, the computer readable code comprising;

computer readable program code means for causing said computer to decompose the control elements of a system to be controlled into a plurality of hierarchical control structure instances;

computer readable program code means for causing said computer to evaluate the performance of each of said hierarchical control structure instances; and

computer readable program code means for selecting an optimal hierarchical control structure instance.

30. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for solving a problem by partitioning the control elements of a system to be controlled, said method steps comprising:

receiving problem definitions;

receiving a structure evaluation function; and

defining an instantiation for a hierarchical control structure comprising the steps of;

decomposing said system into a plurality of hierarchical control structure instances, wherein each of said hierarchical control structure instances includes a plurality of control levels, wherein each of said control levels includes at least one control node;

evaluating the performance of each of said hierarchical control structure instances with said structure evaluation function; and

selecting an optimal hierarchical control structure instance.

31. The program storage device according to claim 30, wherein said problem definitions includes a hierarchical control structure having a plurality of structure parameters.

32. The program storage device according to claim 31, wherein said plurality of structure parameters includes the number of levels to be included in said hierarchical control structure.

33. The program storage device according to claim 30, further comprising the step of receiving a problem evaluation function for evaluating problem solving complexity for individual control nodes within said hierarchical structure.

34. The program storage device according to claim 33, further comprising the steps of:

decomposing said hierarchical control structure from a first level by organizing said control elements into a plurality of hierarchical control structure configurations according to a grouping criterion, thereby forming a plurality of possible group configurations for said first level, wherein each said group configuration includes not less than one control node;

evaluating the performance of each of said group configuration with said problem evaluation function; and

selecting one said group configuration as optimal;

defining said selected group configuration as a second level;

determining whether each of said groups within said selected group configuration satisfies a decomposition criterion;

if said groups do not satisfy said decomposition criterion, decomposing said second level of control elements into a plurality of subgroups according to a grouping criterion, thereby forming a plurality of possible subgroup configurations;

evaluating the performance for each subgroup within each said subgroup configuration with said problem evaluation function;

selecting one said subgroup configuration as optimal, said subgroup configuration defining a next level;

determining whether each of said subgroups within said selected subgroup configuration satisfies said decomposition criterion;

repeating the steps of decomposing said next level of control elements into a plurality of subgroups to form a plurality of possible subgroup configurations, evaluating the performance for each subgroup within each said subgroup configuration, selecting one said subgroup configuration as optimal, and determining whether each of said subgroups within said selected subgroup configuration satisfies said decomposition criterion until the groups satisfy said decomposition criterion; and

discontinuing decomposition when said subgroups satisfy said decomposition criterion.