Method of optimizing component layout using a hierarchical series of models

• US 5,825,660 A
• Filed: 09/07/1995
• Issued: 10/20/1998
• Est. Priority Date: 09/07/1995
• Status: Expired due to Term

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Kolli, Ashish, Szykman, Simon, Rutenbar, Robin, Cagan, Jonathan
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): FREJD, RUSSELL WARREN
• Application Number:
  US08/524,091
• Time in Patent Office: 1,139 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 364/578
• US Class Current: 703/2
• CPC Class Codes: E21B 2200/22 Fuzzy logic, artificial intelligence, neural networks or the like
• 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

A method of optimizing a three-dimensional component layout in accordance with predetermined constraints is comprised of the steps of generating a plurality of models for each component. The plurality of models is arranged in a hierarchy from the model having the least resolution to the model having the most resolution. A starting layout is selected for the components. An iterative type of optimization routine is performed wherein each iteration is evaluated for satisfaction of the constraints using models for the components selected according to the level of resolution desired at that time in the iterative process. The optimization routine ends when a predetermined ending criterion is met.

Claims

1. A method of optimizing component layout in accordance with predetermined constraints, comprising:

generating a plurality of models for each said component of said layout, said plurality of models being arranged in a hierarchy from a simple approximation of said component shape to a more accurate approximation of said component shape;

selecting a starting layout for the said components;

performing an iterative type of optimization routine wherein each iteration includes moving at least one said component and evaluating the resulting layout for satisfaction of said predetermined constraints using a model for each said component selected from said plurality of models according to the level of approximation desired; and

ending the optimization routine when said predetermined constraint is met.

2. The method of claim 1 wherein the step of performing an iterative type of optimization routine includes the step of performing a simulated annealing routine, and wherein a temperature associated with the simulated annealing routine determines the level of approximation desired.

3. The method of claim 1 wherein the step of generating a plurality of models includes the step of generating a plurality of models using an octree representation.

4. The method of claim 2 wherein the level of approximation desired is determined based on the temperature and the magnitude of the move selected.

5. The method of claim 1 wherein the step of moving at least one of the components includes the step of selecting a move from a moveset.

6. The method of claim 5 wherein the step of moving at least one of the components includes the step of selecting a magnitude for the move selected from the moveset.

7. The method of claim 4 wherein the temperature has a level of approximation associated therewith and the magnitude of the move has a level of approximation associated therewith, and wherein the level of approximation desired is determined by the following ruleset:

if the temperature approximation level is less than the move approximation level, then the level of approximation desired is the temperature approximation level,

if the temperature approximation level is greater than or equal to the maximum approximation level, then the level of approximation desired is the maximum approximation level, and

if the temperature approximation level is greater than the move approximation level, then the level of approximation desired is a combination of the two approximation levels.

8. The method of claim 6, additionally comprising the step of incrementing a count associated with each magnitude of each move whenever that magnitude produces a layout which is accepted.

9. A method of optimizing component layout in accordance with predetermined constraints, comprising:

(a) generating a plurality of models for each said component, said plurality of models being arranged in a hierarchy from a simple approximation of said component shape to a more accurate approximation of said component shape;

(b) associating each level of approximation with the moves of a moveset;

(c) selecting a current layout for the said components;

(d) moving one of the said components to create a new current layout;

(e) selecting a model for each said component from said plurality of models based on the level of approximation desired and a move selected from the moveset;

(f) evaluating the new current layout using the selected models and the predetermined constraints;

(g) determining whether to accept the new current layout; and

(h) repeating steps (d) through (h) until said predetermined constraint is satisfied.

10. The method of claim 9 wherein the plurality of models is generated using an octree representation.

11. The method of claim 10 wherein the plurality of models is generated by converting all non-linear surfaces of each component into triangulated polyhedra, and wherein the highest approximation model of each component is generated from the polyhedral model, and wherein all the lower approximation models of each component are generated from the highest approximation model.

12. The method of claim 11 wherein the lower approximation models are generated from the higher approximation models by examining the children of each node at each level in the octree.

13. The method of claim 9 wherein the step of evaluating the new current layout includes the step of determining the volume of overlap between components of the new current layout.

14. The method of claim 9 wherein steps (c) through (h) are part of a simulated annealing routine.

15. The method of claim 14 wherein the predetermined end criterion is satisfied when the layout has stabilized at a lowest temperature associated with the simulated annealing routine.

16. A method of optimizing a three-dimensional component layout in accordance with predetermined constraints, comprising the steps of:

generating a plurality of models for each said component using an octree representation of said layout said models arranged in a hierarchy from a simple approximation of said component shape to a more accurate approximation of said component shape, and wherein each approximation level is related to a temperature;

initializing the said components and a starting temperature; and

performing a simulated annealing optimization routine comprised of a series of iterations which reduce the starting temperature to a final temperature, and wherein the layout at each iteration is evaluated for satisfaction of said predetermined constrains according to models selected on the basis of the then current temperature.

17. The method of claim 16 wherein the models selected progress generally from low approximation models at the beginning of the optimization routine to high approximation models near the end of the optimization routine.

18. A method of optimizing component layout in accordance with predetermined constraints, comprising the steps of:

generating a plurality of models for each said component using an octree representation, said plurality of models being arranged in a hierarchy from a simple approximation of said component shape to a more accurate approximation of said component shape;

selecting a starting layout for the said components;

performing an iterative type of optimization routine wherein each iteration is evaluated for satisfaction of predetermined constraints using models for each said component selected according to the level of approximation desired; and

ending the optimization routine when a predetermined constraint is met.

19. The method of claim 18 wherein the step of performing an iterative type of optimization routine includes the step of performing a simulated annealing routine, and wherein the temperature determines the level of approximation desired.

20. The method of claim 19 wherein the step of performing a simulated annealing routine includes the step of moving at least one of the components per iteration, and wherein the level of approximation desired is determined based on the temperature and the move selected.

21. The method of claim 20 wherein the step of moving at least one of the components includes the step of selecting a move from a moveset.

22. The method of claim 21 wherein the step of moving at least one of the components includes the step of selecting a magnitude for the move selected from the moveset.

23. The method of claim 21 wherein the temperature has a level of approximation associated therewith and the magnitude of the move has a level of approximation associated therewith, and wherein the level of approximation desired is determined by the following ruleset:

if the temperature approximation level is less than the move approximation level, then the approximation desired is the temperature approximation level,

if the temperature approximation level is greater than or equal to the maximum approximation level, then the level of approximation desired is the maximum approximation level, and

if the temperature approximation level is greater than the move approximation level, then the level of approximation desired is a combination of the two approximation levels.

24. The method of claim 22, additionally comprising the step of incrementing a count associated with each magnitude of each move whenever that magnitude produces a layout which is accepted.

25. A method of optimizing component layout in accordance with predetermined constraints, comprising the steps of:

(a) generating a plurality of models for each said component of said layout using an octree representation, said plurality of models being arranged in a hierarchy ranging from a simple approximation of said component shape to a more accurate approximation of said component shape;

(b) selecting a current layout for the said components;

(c) moving one of the said components to create a new current layout;

(d) selecting a model for each said component from said plurality of models based on the level of approximation desired;

(e) evaluating the new current layout using the selected models and the predetermined constraints;

(f) determining whether to accept the new current layout; and

(g) repeating steps (c) through (g) until a predetermined constraint is satisfied.

26. The method of claim 25 wherein the plurality of models is generated by converting all non-linear surfaces of each component into triangulated polyhedra, and wherein the highest approximation model of each component is generated from the polyhedral model, and wherein all the lower approximation models of each component are generated from the highest approximation model.

27. The method of claim 26 wherein the lower approximation models are generated from the higher approximation models by examining the children of each node at each level in the octree.

28. The method of claim 25 wherein the step of evaluating the new current layout includes the step of determining the volume of overlap between components of the new current layout.

29. The method of claim 25 wherein steps (b) through (g) include being part of a simulated annealing routine.

30. The method of claim 29 wherein the predetermined constraint is satisfied when the layout has stabilized at the lowest temperature.