Abstract Automating "innovative design"—the process of creating physical systems from first principles rather than selecting from pre-defined templates—presents a significant computational challenge due to the combinatorial explosion of possible component connections. This paper introduces the Systematic Interaction Explorer (SIE), an algorithm that utilizes a simplified "interaction set" representation to prune the search space. By implementing a "Quick Test" for causal connectivity, SIE can eliminate up to 95% of invalid designs before expensive mathematical verification. Experimental results on cross-domain engineering benchmarks demonstrate that SIE is more systematic and complete than previous state-of-the-art systems.
Introduction
In the early 1990s, artificial intelligence research focused heavily on synthesis tasks like planning and design. Innovative design is particularly difficult because the number of ways to connect a set of components (e.g., valves, sensors, generators) grows exponentially with the number of parts. Previous systems, such as IBIS, attempted to guide this search using complex interaction topologies but often suffered from redundancy and required convoluted debugging phases to resolve inconsistent designs. The Systematic Interaction Explorer (SIE) was developed to provide a more robust, systematic approach to exploring the design space without these inefficiencies.
The SIE Algorithm
SIE treats design as a search problem over a component-connection graph. It assumes components are described by lumped parameter models, including terminals, variables, and equations (e.g., pressure, flow, voltage). The core innovation of SIE lies in its pruning mechanism:
- Interaction Sets: Instead of maintaining complex graphs, SIE uses a "union-find" approach to partition device parameters into equivalence classes. Two parameters belong to the same interaction set if a change in one can causally affect the other through a chain of equations.
- The Quick Test: Before performing rigorous mathematical verification on a candidate design, SIE checks if the parameters required for the target behavior are within the same interaction set. If there is no causal path between the relevant components, the design is discarded immediately.
- Systematic Search: SIE employs depth-first iterative deepening to explore concrete design topologies. This ensures the algorithm finds the simplest designs first and avoids redundant exploration of the same topology.
Experimental Evaluation
SIE was evaluated using several classic engineering benchmarks designed to test cross-domain synthesis:
- The Punchbowl Problem: A benchmark requiring the maintenance of a specific height difference between fluid containers.
- The Dynamo Problems (1-4): A series of increasingly complex designs spanning fluid (vats), mechanical (turbines), and electrical (generators, bulbs) domains. These tests specifically measure the algorithm's ability to handle connections across different physical technologies.
Results and Discussion
Implementation of SIE in Common Lisp on a SPARCstation-IPX yielded significant performance gains. The interaction-based focusing mechanism proved highly effective, particularly in cross-technology designs where interaction sets remain distinct for longer periods during the search.
As shown in Table 1, SIE successfully managed the combinatorial complexity of the Dynamo 4 test, exploring 2,786 possible devices and identifying 14 valid solutions in under 40 seconds. Notably, the "Satisfy I" column demonstrates the power of the Quick Test; for the Dynamo 4 problem, only 72 of the 2,786 candidates required full verification, representing a pruning rate of over 97%.
Conclusion
SIE demonstrates that searching a concrete space of component connections can be more efficient than abstract interaction searches, provided an effective pruning mechanism is used. While the combinatorial explosion remains a long-term threat for larger systems, SIE provides a complete and systematic foundation for first-principles design. Future work suggests combining this systematic search with case-based reasoning and geometric constraints to further scale the system's capabilities.
Summary updated