Development of a computationally-tractable design method for combined multi-physics optimization of packing and routing problems, at relevant scale, within compact packaging volumes, will offer benefits across several engineering domains. But for performing multi-physics packing and routing optimization, generation of spatially feasible initial layouts is essential. Three new and computationally efficient methods are demonstrated in this article to produce automatically interference-free 2D geometric layouts. First, a novel 2D force-directed layout method (FDLM) is proposed that implicitly ensures non-interference between components and/or the interconnect network by utilizing spring force theory without using explicit geometric constraints. Second, the A\* algorithm, a well-established 2D shortest path algorithm (SPA), has been modified significantly to perform efficient routing of complex interconnect systems. Third, a new geometric topology (GT) enumeration algorithm is presented that produces all unique interconnect routing configurations for given multi-component system architecture. These layout generation methods are then compared with respect to average computational efficiencies and average success rates in attaining feasible layouts for a restricted class of topologies, including evaluation of how the methods scale to problems with an increased number of components. Limitations and future work items for each method are discussed. These methods are presented as an important step toward solution strategies that are compatible with the currently unmet challenges of real-world 2D and 3D combined packing and routing problems, including efficient navigation of the space of discrete options for interconnect geometric topology, as well as scaling to more complex problems.


Automated Layout Generation Methods for 2D Spatial Packing

Division / Sponsors: 
Design Engineering Division and Computers & Information In Engineering Division


Paper Proceedings: https://asmedigitalcollection.asme.org/IDETC-CIE/IDETC-CIE2020/volume/83907

IDETC2020 - Virtual Conference

Supporting the need among researchers worldwide for additional online and multimedia content, ASME now offers the ASME Conference Video Collection. This platform will collect and provide long-term access to conference presentation videos, encompassing all technology areas within ASME's technical conference and events program. About 30,000-40,000 engineers across all mechanical engineering and related disciplines participate in ASME conferences each year. This includes authors of approximately 6,000 to 8,000 technical papers published by ASME, the majority of whom also submit video presentations for our virtual conferences. The video collection will be available as an add-on to existing product packages or as a separate subscription.