Automated layout generation methods for 2D spatial packing

Satya R.T. Peddada, Samanta B. Rodriguez, Kai A. James, James T. Allison

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Development of a computationally-tractable design method for combined multi-physics optimization of packing and routing problems, at a relevant scale, within compact packaging volumes, will o er benefits across several engineering domains. But for performing multi-physics packing and routing optimization, the 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 noninterference 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.

Original languageEnglish (US)
Title of host publication46th Design Automation Conference (DAC)
PublisherAmerican Society of Mechanical Engineers (ASME)
ISBN (Electronic)9780791884010
StatePublished - 2020
EventASME 2020 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, IDETC-CIE 2020 - Virtual, Online
Duration: Aug 17 2020Aug 19 2020

Publication series

NameProceedings of the ASME Design Engineering Technical Conference


ConferenceASME 2020 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, IDETC-CIE 2020
CityVirtual, Online

ASJC Scopus subject areas

  • Mechanical Engineering
  • Computer Graphics and Computer-Aided Design
  • Computer Science Applications
  • Modeling and Simulation


Dive into the research topics of 'Automated layout generation methods for 2D spatial packing'. Together they form a unique fingerprint.

Cite this