Abstract
This paper explores the application of artificial intelligence state-space search techniques to large-scale combinatorial problems in engineering, specifically the partitioning of electronic circuits. By defining formal operators for state transitions and utilizing heuristic weights derived from element connectivity, the proposed method effectively navigates complex search spaces. Experimental results on synthetic and real-world datasets, including printed circuit board (PCB) layouts, demonstrate substantial improvements over random configurations, achieving nearly complete routability in practical applications.
Introduction
During the 1970s, the increasing complexity of electrical and mechanical systems led to a "combinatorial explosion" in design tasks. Problems such as partitioning a system into manageable modules or placing hundreds of components on a circuit board became too vast for manual intuition or exhaustive computational methods. This research addresses the challenge of rationalizing the design process by focusing on "decomposition problems"—splitting large sets into optimal subsets—and "selection problems"—choosing appropriate functional elements. The primary objective is to minimize a cost function, typically the number of interconnections between modules, while adhering to physical constraints.
Methodology: State-Space Search
The authors frame these engineering challenges as state-space search problems. This framework consists of three primary components: solution states, operators, and heuristic guidance.
Solution States and Operators
A "state" represents a specific configuration of the system, such as a particular partitioning of a circuit. Transitions between these states are governed by a set of defined operators ($O_1$ through $O_5$). These operators include moving a single element from one subset to another, joining subsets, or interchanging elements between subsets.
The research suggests a hierarchical approach: first generating an "admissible" object using simple grouping operators, and subsequently refining it through interchange operators to balance computational speed with solution quality.
Heuristic Weights
Given the impossibility of an exhaustive search, the algorithm employs heuristic weights ($\Delta$) to prioritize state transitions. These weights are calculated based on "binding strength," or the degree of connectivity between elements.
As shown in the cost function $g(x)$, the algorithm evaluates the local connectivity of an element $a_i$ relative to its subset $A_l$. If moving an element to a different subset significantly reduces external connections, that move is assigned a high weight. The search continues until a "break-off point" is reached, where no further improvements to the cost function are possible.
Experimental Evaluation
The methodology was tested on both synthetic and real-world datasets. Synthetic partitioning tasks involved sets of 24 and 72 elements to be partitioned into subsets of fixed sizes. Real-world engineering data included organizational structures and double-sided PCB layouts from the Academy of Sciences of the GDR.
Results and Discussion
The heuristic search consistently outperformed random assignments. For the 72-element test set, the algorithm achieved partition costs 10% lower than random configurations, while the 24-element set saw an 18% improvement.
In practical applications for double-sided PCBs, the efficiency of the resulting layouts was particularly notable. Subsequent routing programs were able to successfully connect 96% to 98% of all required electrical paths, demonstrating the method's effectiveness in preparing designs for physical implementation. Furthermore, the algorithm proved capable of identifying natural clusters within experimental data, suggesting its utility for broader system analysis.
Conclusion and Future Work
While the structural approach to combinatorial problems yielded significant gains, the authors acknowledge limitations. Current models focus primarily on structural interconnections, often neglecting the specific functional features of components. Future research aims to incorporate these functional constraints and develop better probabilistic estimates for reaching global optima. The ultimate goal remains the full automation of the synthesis process, transitioning directly from functional descriptions to physical layouts.
Summary updated