System and method for automatic design of components in libraries

• US 7,711,674 B2
• Filed: 11/01/2005
• Issued: 05/04/2010
• Est. Priority Date: 11/01/2005
• Status: Expired due to Fees

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Polak, Wolfgang H., Arthur, W. Brian
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): Tran; Mai T
• Application Number:
  US11/264,219
• Publication Number:
  US 20070100784A1
• Time in Patent Office: 1,645 Days
• Field of Search: 706/62, 706/13, 717/120, 717/107, 717/126, 235/382
• US Class Current: 706/62
• CPC Class Codes: G06F 2111/20 Configuration CAD, e.g. designing by assembling or positioning modules selected from libraries of predesigned modules
• CPC Class Codes: G06F 8/36 Software reuse

Abstract

Embodiments of the present invention introduce a novel recursive assembly process to automatically create a library of components. It starts with simple components used as building blocks and proceeds by repeatedly combining these randomly into more complex ones. The utility and quality of these random combinations of components are measured against a set of functional goals. Useful combinations then become new components in the library that can be used as building blocks for further random combination. This description is not intended to be a complete description of, or limit the scope of, the invention. Other features, aspects, and objects of the invention can be obtained from a review of the specification, the figures, and the claims.

Claims

1. A system for automatically generating at least one new component, the system comprising:

a plurality of components, wherein each of the plurality of components performs a certain function;

a component library to store the plurality of components;

a processing device; and

a persistent storage device coupled to the processing device for storing an executable component generation module, wherein the component generation module when executed causes the system to create the at least one new component, wherein the component generation module when executed further causes the system to;

select a subset of the plurality of components in the component library;

generate a combination by randomly combining the subset of the plurality of components;

evaluate the combination against a plurality of goals, wherein the plurality of goals are formal specifications of a function of a desired component defined by a user;

encapsulate the combination into the at least one new component, designate an observable interface for the at least one new component, and store the at least one new component in the component library if the combination meets one or more criteria, wherein each of the plurality of components is associated with a cost, wherein the cost comprises the number of subcomponents needed to build the combination.

2. The system according to claim 1,

each of the plurality of components is composed hierarchically, represented and manipulated in a computer system.

3. The system according to claim 1, wherein:

the plurality of goals are specified by the user via a formal logical language.

4. The system according to claim 1, wherein:

the component generation module initializes the component library with a plurality of primitive components.

5. The system according to claim 1, wherein:

the component generation module replaces a component in the plurality of components that either is subsumed by the combination or does not match the goal as well as the combination.

6. The system according to claim 1, wherein:

the component generation module prefers a certain component over another in the subset of the plurality of components when generating the combination.

7. The system according to claim 1, wherein:

the combination is more complex than any of the components in the subset of the plurality of components.

8. The system according to claim 1, wherein:

each of the one or more criteria are one of;

the combination has a valid function;

the combination has a cheaper cost than any of the plurality of components; and

the combination relates to the goal better than any of the plurality of components.

9. The system of claim 1, wherein the plurality of goals are vectors of logic functions.

10. The system of claim 9, wherein the vectors of logic functions are represented as vectors of binary decision diagrams.

11. The system of claim 1, wherein the combination is generated by wiring the subset of the plurality of components together.

12. A computer-implemented method to support automatic component library design comprising:

storing a plurality of components in a component library, wherein each of the plurality of components performs a certain function;

selecting a subset of the plurality of components in the component library;

generating, by a component generation module executable on one or more computing devices, a combination by randomly combining the subset of the plurality of components;

evaluating the combination against a plurality of goals, wherein the plurality of goals are formal specifications of a function of a desired component defined by a user;

encapsulating the combination into a new component, designating an observable interface for the new component, and storing the new component into the component library if the combination meets one or more criteria, wherein each of the plurality of components is associated with a cost, wherein the cost comprises the number of subcomponents needed to build the combination; and

generating at least one new component.

13. The computer-implemented method according to claim 12, further comprising:

specifying one or more of the plurality of goals by the user via a formal logical language.

14. The computer-implemented method according to claim 12, further comprising:

initializing the component library with a plurality of primitive components.

15. The computer-implemented method according to claim 12, further comprising:

replacing a component in the plurality of components that either is subsumed by the combination or does not match the goal as well as the combination.

16. The computer-implemented method according to claim 12, further comprising:

preferring certain component over another in the subset of the plurality of components when generating the combination.

17. The computer-implemented method according to claim 12, further comprising:

generating the combination to be more complex than any of the components in the subset of the plurality of components.

18. The computer-implemented method according to claim 12, wherein:

each of the one or more criteria are one of;

the combination has a valid function;

the combination has a cheaper cost than any of the plurality of components, wherein the cost is distinct from the function; and

the combination relates to the goal better than any of the plurality of components.

19. A machine readable medium having instructions stored thereon that when executed cause a system to:

store a plurality of components in a component library, wherein each of the plurality of components performs a certain function;

select a subset of the plurality of components in the component library;

generate, by a component generation module executable on one or more computing devices, a combination by randomly combining the subset of the plurality of components;

evaluate the combination against a goal, wherein the plurality of goals are formal specifications of a function of a desired component defined by a user;

encapsulate the combination into a new component, designate an observable interface for the new component, and store the new component into the component library if the combination meets one or more criteria, wherein each of the plurality of components is associated with a cost, wherein the cost comprises the number of subcomponents needed to build the combination; and

generate at least one new component.