{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T12:49:21Z","timestamp":1753879761840,"version":"3.41.2"},"reference-count":33,"publisher":"ASME International","issue":"3","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,9,1]]},"abstract":"<jats:p>This paper presents a new search method that has been developed specifically for search trees defined by a generative grammar. Generative grammars are useful in design as a way to encapsulate the design decisions that lead to candidate solutions. Since the candidate solutions are not confined to a single configuration or topology and thus useful in conceptual design, they may be difficult to computationally analyze. Analysis is achieved in this method by querying the user. A formal definition of a rule-based interactive tree-search is presented in this paper. The user interaction is kept to 30 pair-wise comparisons of candidates. From the data gathered from the comparisons, a stochastic decision-making process infers what candidate solutions best match the known optimal. The method is implemented and applied to a grammar for tying neckties. It is shown through 21 user experiments and 4000 automated experiments that the method consistently finds solutions within the 99.8 percentile. The computational complexity of the proposed algorithm is also studied. The implications of this method for conceptual design are expounded on in the conclusions.<\/jats:p>","DOI":"10.1115\/1.4007153","type":"journal-article","created":{"date-parts":[[2012,8,9]],"date-time":"2012-08-09T18:02:41Z","timestamp":1344535361000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":6,"title":["A Stochastic Tree-Search Algorithm for Generative Grammars1"],"prefix":"10.1115","volume":"12","author":[{"given":"Matthew I.","family":"Campbell","sequence":"first","affiliation":[{"name":"Associate Professor Automated Design Laboratory, Department of Mechanical Engineering, University of Texas at Austin, Austin, TX 78712-0292 e-mail:"}]},{"given":"Rahul","family":"Rai","sequence":"additional","affiliation":[{"name":"Associate Professor Department of Mechanical and Aerospace Engineering, University at Buffalo (UB)-SUNY, Buffalo, NY 14260 e-mail:\u2002rahulrai@buffalo.edu"}]},{"given":"Tolga","family":"Kurtoglu","sequence":"additional","affiliation":[{"name":"Research Scientist Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA 94304 e-mail:"}]}],"member":"33","published-online":{"date-parts":[[2012,8,9]]},"reference":[{"article-title":"Engineering Shape Grammars","volume-title":"Formal Engineering Design Synthesis","year":"2001","key":"2019100517291963100_B1"},{"issue":"1","key":"2019100517291963100_B2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1080\/09544820701546165","article-title":"Automated Synthesis of Electromechanical Design Configurations From Empirical Analysis of Function to Form Mapping","volume":"20","year":"2009","journal-title":"J. Eng. Des."},{"key":"2019100517291963100_B3","unstructured":"Sridharan, P., and Campbell, M. I., 2004, \u201cA Grammar for Function Structures,\u201d Proceedings of ASME 2004 International Design Engineering and Technical Conference and Computers and Information in Engineering Conferences, Salt Lake City, UT, Sept. 28\u2013Oct. 2, DETC04\/DTM-57130."},{"issue":"4","key":"2019100517291963100_B4","first-page":"187","article-title":"Towards an Automated Approach to the Design of Sheet Metal Components","volume":"17","year":"2003","journal-title":"Artif. Intell. Eng. Des. Anal. Manuf."},{"issue":"1","key":"2019100517291963100_B5","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/s00163-008-0062-1","article-title":"An Evaluation Scheme for Assessing the Worth of Automatically Generated Design Alternatives","volume":"20","year":"2009","journal-title":"Res. Eng. Des."},{"issue":"1","key":"2019100517291963100_B6","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0304-3975(95)00202-2","article-title":"Probabilistic Hyperedge Replacement Grammar","volume":"159","year":"1996","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"2019100517291963100_B7","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1068\/b250205","article-title":"A Blend of Different Tastes: The Language of Coffee Makers","volume":"25","year":"1998","journal-title":"Environ. Plan. B: Plan. Des."},{"issue":"3","key":"2019100517291963100_B8","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1115\/1.2826360","article-title":"A Shape Annealing Approach to Optimal Truss Design With Dynamic Grouping of Members","volume":"119","year":"1997","journal-title":"ASME J. Mech. Des."},{"key":"2019100517291963100_B9","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1017\/S0890060400003140","article-title":"Optimized Process Planning by Generative Simulated Annealing","volume":"11","year":"1997","journal-title":"Artif. Intell. Eng. Des. Anal. Manuf."},{"issue":"2","key":"2019100517291963100_B10","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1007\/BF01606905","article-title":"Recursive Annealing: A Computational Model for Machine Design","volume":"7","year":"1995","journal-title":"Res. Eng. Des."},{"key":"2019100517291963100_B11","unstructured":"Starling, A. C., and Shea, K., 2003, \u201cA Grammatical Approach to Computational Generation of Mechanical Clock Designs,\u201d Proceedings of ICED\u201903 International Conference on Engineering Design, Stockholm, Sweden."},{"key":"2019100517291963100_B12","unstructured":"Starling, A. C., and Shea, K., 2005, \u201cVirtual Synthesizers for Mechanical Gear Systems,\u201d Proceedings of ICED\u201905 International Conference on Engineering Design, Melbourne, Australia."},{"volume-title":"Total Design: Integrated Methods for Successful Product Engineering","year":"1991","key":"2019100517291963100_B13"},{"volume-title":"The Mechanical Design Process","year":"1995","key":"2019100517291963100_B14"},{"volume-title":"The Analytic Hierarchy Process","year":"1980","key":"2019100517291963100_B15"},{"volume-title":"Decisions With Multiple Objectives: Preferences and Value Tradeoffs","year":"1976","key":"2019100517291963100_B16"},{"issue":"6","key":"2019100517291963100_B17","first-page":"397","article-title":"Quantifying Aesthetic Form Preference in a Utility Function","volume":"131","year":"2009","journal-title":"ASME J. Mech. Des."},{"year":"2002","key":"2019100517291963100_B18","article-title":"Interactive Evolutionary Computation: A Survey of Existing Theory"},{"key":"2019100517291963100_B19","doi-asserted-by":"crossref","unstructured":"Takagi, H., 2001, \u201cInteractive Evolutionary Computation: Fusion of the Capacities of EC Optimization and Human Evaluation,\u201d Proceedings of the IEEE 89, 9, pp. 1275\u20131296.","DOI":"10.1109\/5.949485"},{"key":"2019100517291963100_B20","first-page":"126","article-title":"A Stochastic Search Approach to Grammar Induction","volume-title":"Lecture Notes in Computer Science","year":"1998"},{"article-title":"Integrating Case-Based Reasoning and Qualitative Reasoning in Engineering Design","volume-title":"Artificial Intelligence in Engineering Design","year":"1989","key":"2019100517291963100_B21"},{"issue":"3","key":"2019100517291963100_B22","first-page":"207","article-title":"Engineering Design Synthesis: A Domain-Independent Representation","volume":"1","year":"1988","journal-title":"Artif. Intell. Eng. Des. Anal. Manuf."},{"key":"2019100517291963100_B23","first-page":"59","article-title":"Design Problem Solving: A Task Analysis","volume":"Winter","year":"1990","journal-title":"AI Mag."},{"year":"1989","key":"2019100517291963100_B24","article-title":"As Neckwear Goes, This Knot's News"},{"volume-title":"The 85 Ways to Tie a Tie: The Science and Aesthetics of Tie Knots","year":"2001","key":"2019100517291963100_B25"},{"year":"2006","key":"2019100517291963100_B26"},{"issue":"4","key":"2019100517291963100_B27","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1068\/b3015","article-title":"Functional Scalability Through Generative Representations: The Evolution of Table Designs","volume":"31","year":"2004","journal-title":"Environ. Plann. B"},{"issue":"1","key":"2019100517291963100_B28","doi-asserted-by":"crossref","first-page":"16","DOI":"10.2307\/3001663","article-title":"The Exploration and Exploitation of Response Surfaces: Some General Considerations and Examples","volume":"10","year":"1954","journal-title":"Biometrics"},{"key":"2019100517291963100_B29","first-page":"69","article-title":"A Comparative Analysis of Selection Schemes Used in Genetic Algorithms","volume":"1","year":"1991","journal-title":"Found. Genet. Algorithms"},{"volume-title":"Matrix Computations","year":"1996","key":"2019100517291963100_B30"},{"key":"2019100517291963100_B31","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by Simulated Annealing","volume":"220","year":"1983","journal-title":"Science"},{"volume-title":"Mass Customization: The New Frontier in Business Competition","year":"1992","key":"2019100517291963100_B32"},{"key":"2019100517291963100_B33","article-title":"Toward a Smarter Web","volume":"325","year":"2009","journal-title":"Science"}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4007153\/6098764\/031006_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4007153\/6098764\/031006_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T17:29:42Z","timestamp":1570296582000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/doi\/10.1115\/1.4007153\/370771\/A-Stochastic-TreeSearch-Algorithm-for-Generative"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,9]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,9,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4007153","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2012,8,9]]},"article-number":"031006"}}