Method of optimizing component layout using a pattern based search

• US 5,953,517 A
• Filed: 11/20/1997
• Issued: 09/14/1999
• Est. Priority Date: 11/20/1997
• Status: Expired due to Term

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Cagan, Jonathan, Yin, Su
• Primary Examiner(s): Grant, William
• Assistant Examiner(s): Rapp, Chad
• Application Number:
  US08/974,783
• Time in Patent Office: 663 Days
• Field of Search: 364/149, 364/488, 364/489, 364/500.1, 364/474.13
• US Class Current: 716/122
• CPC Class Codes: G06F 2113/20 Packaging, e.g. boxes or containers
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

The present invention is directed to a method of, and apparatus for, solving a packing or layout problem by applying a pattern based search technique to an initial component configuration. By interactively working through a series of new or "then current" configurations, an optimal component configuration is determined based on a predetermined criterion. According to one embodiment of the invention, at least one perturbation is introduced during the course of the search. The perturbation may be introduced by swapping component positions, increasing move size, or any other activity which breaks or interrupts the pattern of a normal pattern based search.

Claims

1. A method of solving one of a packing and layout problem comprising:

applying a pattern based search technique to each component in an initial component configuration to determine an optimal component configuration based on a predetermined criterion, wherein said each component is selected randomly from all available components; and

introducing at least one perturbation into the search, wherein the perturbation interrupts a pattern in the pattern based search technique.

2. The method of claim 1 wherein the pattern based search technique is applied to each available component and wherein said each component is selected randomly from a subset of all available components.

3. The method of claim 1 herein said pattern based search proceeds from said initial component configuration to said optimal component configuration through a series of then current component configurations, and wherein said step of introducing at least one perturbation into the search includes the step of randomly swapping the positions of certain of said components within one of said then current component configurations.

4. The method of claim 1 wherein said pattern based search proceeds from said initial component configuration to said optimal component configuration through a series of then current configurations produced by moving certain components within a configuration, said pattern based search including the step of periodically reducing the size of said movements, and wherein said step of introducing at least one perturbation into the system includes the step of increasing the size of said movements.

5. The method of claim 4 wherein said move size is increased randomly.

6. The method of claim 4 wherein said move size is increased according to a heuristic.

7. The method of claim 4 wherein said move size is increased periodically.

8. The method of claim 1 wherein said pattern based search includes the steps of selecting a level of resolution and evaluating each configuration of the components according to said selected level of resolution.

9. The method of claim 8 wherein said pattern based search includes the step of reducing the size of the movements of the components over time, and wherein said step of selecting a level of resolution is related to said move size.

10. A method, comprising:

initializing a plurality of components into an initial current component configuration;

performing a series of moves on each of said plurality of components in a current component configuration to produce a series of new current component configurations, wherein each of said plurality of components is selected randomly from all available components in said initial current component configuration;

evaluating each of said new current component configurations and saving certain of said new current component configurations;

reducing the size of the component moves over time;

repeating the steps of performing, evaluating, and reducing until a predetermined criterion is met; and

perturbing the method at least once before the predetermined criterion is met, wherein the perturbation interrupts a pattern of the series of moves.

11. The method of claim 10 wherein the series of moves is performed on each available component in a current component configuration and wherein said each component is selected randomly from a subset of all available components in said initial component configuration.

12. The method of claim 10 wherein said step of perturbing the method includes the step of randomly exchanging the positions of certain components to produce a new current component configuration.

13. The method of claim 10 wherein said step of perturbing the method includes the step of increasing the size of the component moves.

14. The method of claim 10 wherein said step of evaluating includes the step of selecting a level of resolution and wherein said step of evaluating is carried out using the selected level of resolution.

15. The method of claim 10 wherein said step of evaluating includes the step of evaluating according to two-dimensional layout criteria.

16. The method of claim 15 wherein said step of evaluating includes the step of evaluating according to functional criteria.

17. The method of claim 10 wherein said step of evaluating includes the step of evaluating according to three-dimensional layout criteria.

18. The method of claim 17 wherein said step of evaluating includes the step of evaluating according to functional criteria.

19. A method of determining component layout comprising the steps of:

establishing an initial component configuration;

performing a series of translational and rotational moves on each of said components according to a preselected order to produce a series of new component configurations, wherein each of said components is selected randomly from all available components;

scoring each of said new component configurations according to at least one of layout and functional constraints;

saving those configurations which produce a better score;

reducing the size of the component moves over time;

repeating the steps of performing, scoring, saving, and reducing until a predetermined criterion is met; and

perturbing the method at least once before the predetermined criterion is met, wherein the perturbation interrupts a pattern of the series of the translational and rotational moves.

20. The method of claim 19 wherein each of said components is selected randomly from a subset of all available components.

21. The method of claim 19 additionally comprising the step of prohibiting any translational and rotational moves that violate any layout and functional constraints.

22. An apparatus, comprising:

means for performing a pattern based search on each component in a plurality of components to determine an optimal configuration of said components, said components selected randomly from all available components; and

means for introducing at least one perturbation into the search, wherein the perturbation interrupts a pattern in the pattern based search.

23. The apparatus of claim 22 wherein said means for introducing at least one perturbation includes means for randomly exchanging the positions of certain components.

24. The apparatus of claim 22 wherein said means for performing a pattern based search includes means for reducing the size of the movements of the components, and wherein said means for introducing at least one perturbation into the search includes means for increasing the size of said movements.

25. The apparatus of claim 22 wherein said means for performing a pattern based search includes means for selecting a level of resolution and means for evaluating a plurality of component configurations according to the selected level of resolution.

26. The apparatus of claim 25 wherein said means for selecting a level of resolution also changes the size of the movements of the components.