Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-05T16:20:20.677Z Has data issue: false hasContentIssue false

An intelligent design machine: architecture and search strategies

Published online by Cambridge University Press:  27 February 2009

Michael A. Gray
Affiliation:
Artificial Intelligence Laboratory, Advanced Computer Architecture, Microelectronics and Computer Technology Corporation, Austin, TX 78759, U.S.A.

Abstract

In this report the architecture of an intelligent design machine capable of performing routine design in different design domains is described. This machine is crafted to operate as a part of a larger system driven by a human designer. Notable features are its use of best-first search strategies for problem-solving control and its ability to adjust problem-solving control strategies, perform automated redesign following specification changes, and resolve constraint violations using domain knowledge. The claims made for this machine are analyzed and it is argued that these claims are founded on established principles of design for intelligent systems. An implementation of this architecture in a rule-based system named Proteus is discussed and its operation is examined using as an example the domain of register-transfer-level computer design.

Type
Research Article
Copyright
Copyright © Cambridge University Press 1988

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Acosta, R. D., Huhns, M. N. and Liuh, S. 1986. Analogical reasoning for digital system synthesis. In IEEE International Conference on Computer-Aided Design, Santa Clara, CA, pp. 173176.Google Scholar
Adelson, B. and Soloway, E. 1984. A model of software design, YALE/CSD/RR #342. Department of Computer Science, Yale University, New Haven, CT.Google Scholar
Arora, J. S. and Baenziger, G. 1986. Uses of artificial intelligence in design optimization. Computer Methods in Applied Mechanics and Engineering 54, 303323.CrossRefGoogle Scholar
Barbuceanu, M. 1985. An object-centered framework for expert systems in computer-aided design. In Gero, J. S. (ed.), Knowledge Engineering in Computer-Aided Design. Amsterdam: North-Holland, pp. 223253.Google Scholar
Bell, C. G. and Newell, A. 1971. Computer Structures: Readings and Examples. New York: McGraw-Hill.Google Scholar
Brown, D. C. 1984. Expert systems for design problem-solving using design refinement with plan selection and redesign. PhD thesis. Department of Computer and Information Science, Ohio State University, Columbus, OH.Google Scholar
Brown, D. C. 1985. Failure handling in a design expert system. Computer-Aided Design 17(9), 436442.CrossRefGoogle Scholar
Brown, D. C. and Chandrasekaran, B. 1985 a. Expert systems for a class of mechanical design activity. In Gero, J. S. (ed.), Knowledge Engineering in Computer-Aided Design Amsterdam: North-Holland, pp. 259282.Google Scholar
Brown, D. C. and Chandrasekaran, B. 1985 b. Plan selection in design problem-solving. Technical Report, Department of Computer and Information Science, Laboratory for Artificial Intelligence Research, Ohio State University, Columbus, OH.Google Scholar
Brown, D. C. and Chandrasekaran, B. 1986. Knowledge and control for a mechanical design expert system. Computer 19(7), 92100.CrossRefGoogle Scholar
Brown, D. E. and White III, C. C. 1987. An expert system approach to boiler design. IEEE Transactions on Systems, Man, and Cybernetics SMC-17(2), 293297.CrossRefGoogle Scholar
Brownston, L., Farrell, R., Kant, E. and Martin, N. 1986. Programming Expert Systems in OPS5: Introduction to Rule-Based Programming. Reading, MA: Addison-Wesley.Google Scholar
Denning, P. J., Dennis, J. B. and Qualitz, J. E. 1978. Machines, Languages, and Computation. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
Doyle, J. A. 1979. Truth maintenance system. Artificial Intelligence 12(3), 231272.CrossRefGoogle Scholar
Erman, L. D., Hayes-Roth, F., Lesser, V. R. and Reddy, D. R. 1980. The Hearsay-II speech-understanding system: integrating knowledge to resolve uncertainty. Computing Surveys 12(2), 213253.CrossRefGoogle Scholar
Ernst, G. W. and Newell, A. 1969. GPS: A Case Study in Generality and Problem Solving. New York: Academic Press.Google Scholar
Ersoz, A. 1986. Towards an expert system for automating digital circuit design. CRC Technical Report 86–9, Center for Reliable Computing, Computer Systems Laboratory, Department of Electrical Engineering and Computer Science, Stanford University, Stanford, CA.Google Scholar
Feinstein, J. L., Siems, F., Popolizio, J., Bailey, D. and Wang, A. 1987. XTEL: an expert system for designing theater-wide telecommunications architectures. In 7th International Workshop Expert Systems and their Applications, Avignon, France, pp. 313333.Google Scholar
Fisher, E. L. 1986. An Al-based methodology for factory design. Al Magazine 7(4), 7285.Google Scholar
Furuta, H., Tu, K. and Yao, J. T. P. 1985. Structural engineering applications of expert systems. Computer-aided Design 17(9), 410419.CrossRefGoogle Scholar
Gray, M. A. 1987. Implementing an intelligent design machine in a TMS-based inferencing system. In Proceedings of the 1987 IEEE Conference on Systems, Man, and Cybernetics, Alexandria, VA, pp. 163172.Google Scholar
Hanks, S. and McDermott, D. 1986. Default reasoning, nonmonotonic logics, and the frame problem. In Proceedings AAAI-86, Philadelphia, PA, pp. 320333.Google Scholar
Hayes, P. J. 1977. In defense of logic. In IJCAI-77, Cambridge, MA, pp. 559565.Google Scholar
Hayes-Roth, B., Garvey, A., Johnson, M. V. Jr and Hewett, M. 1986. A layered environment for reasoning about action. Knowledge Systems Laboratory Report No. KSL 86–38, Knowledge Systems Laboratory, Computer Science Department, Stanford University, Palo Alto, CA.Google Scholar
Hogger, C. J. 1984. Introduction to Logic Programming. New York: Academic Press.Google Scholar
Jansen, J. J. and Puttgen, H. B. 1987. ASDEP: an expert system for electric power plant design IEEE Expert 2(1), 5666.CrossRefGoogle Scholar
Joobbani, R. and Siewiorek, D. P. 1985. WEAVER: a knowledge-based routing expert. In Proceedings of the 22nd Design Automation Conference, Las Vegas, NV, pp. 266272.Google Scholar
Kant, E. and Newell, A. 1982. Problem solving techniques for the design of algorithms. CMU-CS-82–145, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA.Google Scholar
Keen, J. S. and Seviora, R. E. 1987. Expert system for VLSI design: a survey and a perspective. In 7th International Workshop Expert System and their Applications, Avignon, France, pp. 14471458.Google Scholar
Lagrana, N. A., Mitchell, T. M. and Ramachandran, N. 1986. Progress toward a knowledge-based aid for mechanical design. In Proceedings of the Symposium on Integrated and Intelligent Manufacturing. Anaheim, California, 1986 ASME Winter Annual Meeting.Google Scholar
Laird, J. E., Newell, A. and Rosenbloom, P. S. 1987. Soar: an architecture for general intelligence. Artificial Intelligence 33(1), 164.CrossRefGoogle Scholar
Levi, G. and Sirovich, F. 1976. Generalized and/or graphs. Artificial Intelligence 7(3), 243259.CrossRefGoogle Scholar
Li, H. L. and Papalambros, P. 1985. A production system for use of global optimization knowledge. Journal of Mechanisms, Transmissions, and Automation in Design 107, 277284.CrossRefGoogle Scholar
Liuh, S. and Huhns, M. N. 1986. Using a TMS for EBG. Technical Report AI-445–86, Microelectronics and Computer Technology Corporation, Austin, TX.Google Scholar
Lowther, D. A., Saldanha, C. M. and Choy, G. 1985. The application of expert systems to CAD in electromagnetics. IEEE Transactions on Magnetics MAG-21(6), 25592562.CrossRefGoogle Scholar
Maher, M. L., Sriram, D. and Fenves, S. J. 1984. Tools and techniques for knowledge based expert systems for engineering design. Advanced Engineering Software 6(4), 178188.CrossRefGoogle Scholar
McCarthy, J. 1987. Generality in artificial intelligence. Communications of the ACM 30(12), 10301035.CrossRefGoogle Scholar
McDermott, D. V. 1977. Flexibility and efficiency in a computer program for designing circuits. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology.Google Scholar
McDermott, J. 1982. Rl: a rule-based configurer of computer systems. Artificial Intelligence 19(1), 3988.CrossRefGoogle Scholar
Mitchell, T. M., Keller, R. M. and Kedar-Cabelli, S. T. 1986. Explanation-based generalization: a unifying view. Machine Learning 1(1), 4780.CrossRefGoogle Scholar
Mitchell, T. M., Steinberg, L. I. and Shulman, J S. 1985. A knowledge-based approach to design. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-7(5), 502510.CrossRefGoogle Scholar
Mittal, S. and Araya, A. 1986. A knowledge-based framework for design. In Proceedings of the 5th National Conference on Artificial Intelligence, Vol. II, Philadelphia, PA, pp. 856865.Google Scholar
Mittal, S., Dyn, C. L. and Morjaria, M. 1986. PRIDE: an expert system for the design of paper handling systems. Computer 19(7), 102114.CrossRefGoogle Scholar
Mostow, J. 1985. Toward better models of the design process. AI Magazine 6(1), 4457.Google Scholar
Newell, A. 1962. Some problems of the basic organization in problem-solving programs. In Proceedings of the 2nd Conference on Self-Organizing Systems, Chicago, Illinois.Google Scholar
Newell, A. and Simon, H. A. 1972. Human Problem Solving. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
Nilsson, N. J. 1980. Principles of Artificial Intelligence. Palo Alto, CA: Tioga.Google Scholar
Odawara, G., Iijima, K. and Wakabayashi, K. 1985. Knowledgebased placement technique for printed wiring boards. In Proceedings of the 22nd Design Automation Conference, Las Vegas, NV, pp. 616622.Google Scholar
Oxman, R. and Gero, J. S. 1987. Using an expert system for design diagnosis and design synthesis. Expert Systems 4(1), 415.CrossRefGoogle Scholar
Pearl, J., Leal, A. and Saleh, J. 1982. GODDESS: a goal-directed decision structuring system. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-4(3), 250262.CrossRefGoogle Scholar
Pearl, J. 1984. HEURISTICS Intelligent Search Strategies for Computer Problem Solving. Reading, MA: Addison-Wesley.Google Scholar
Petrie, C. J. Jr 1987. Revised dependency-directed backtracking for default reasoning. Technical Report AI-002–87, Microelectronics and Computer Technology Corporation, Austin, TX.Google Scholar
Petrie, C. J., Russinoff, D. M. and Steiner, D. D. 1986. Proteus: a default reasoning perspective. In Proceedings of the 5th Generation Conference, Washington, DC.Google Scholar
Pitts, S. and Virdhagriswaran, S. 1987. PLEX phase II: a truth maintenance system (TMS)-based placement program for printed wire boards using dependency-directed backtracking and human-aided machine design. SPIE 786, Applications of Artificial Intelligence V, pp. 327331.Google Scholar
Radford, A. D. and Gero, J. S. 1985. Towards generative expert systems for architectural detailing. Computer-Aided Design 17(9), 428435.CrossRefGoogle Scholar
Reddy, S. D., Tyle, N., Maher, M. L., Banares, R., Rychener, M. D. and Fenves, S. J. 1983. Knowledge-based expert systems for engineering applications. In Proceedings of the IEEE International Conference on Man, Systems, and Cybernetics, pp. 364368.Google Scholar
Rehak, D. R., Howard, H. C. and Sriram, D. 1985. Architecture of an integrated knowledge based environment for structural engineering applications. In Gero, J. S. (ed.), Knowledge Engineering in Computer-Aided Design. Amsterdam: North-Holland, pp. 89117.Google Scholar
Saucier, G., Crastes de Paulet, M. and Hannat, S. 1987. ASYL: A rule-based synthesis tool. In 7th International Workshop Expert Systems and Their Applications, Avignon, France, pp. 14591485.Google Scholar
Simon, H. A. 1973. The structure of Ill structured problems. Artificial Intelligence 4(3,4), 181201.CrossRefGoogle Scholar
Simon, H. A. 1983. Search and reasoning in problem solving. Artificial Intelligence 21(1,2), 729.CrossRefGoogle Scholar
Sriram, D. 1986. DESTINY: a model for integrated structural design. International Journal for Artificial Intelligence in Engineering 1(2), 109116.Google Scholar
Sriram, D., Maher, M. L. and Fenves, S. J. 1983. Applications of expert systems in structural engineering. In Proceedings of the Conference on Artificial Intelligence, Rochester, MI, pp. 379394.Google Scholar
Stefik, M. J. 1980. Planning with constraints. PhD thesis, Department of Computer Science, Stanford University.Google Scholar
Subrahmanyam, P. A. 1986. Synapse: an expert system for VLSI design. Computer 19(7), 7889CrossRefGoogle Scholar
Tong, C. H. 1988. Knowledge-based circuit design. Technical Report LCSR-TR-108, Department of Computer Science, Laboratory for Computer Science Research, Rutgers University, New Brunswick, NJ.Google Scholar
Virdhagriswaran, S. and Afshartous, N. 1987. MINC: a deniable expert system that reasons with simplying assumptions. SPIE 786, Applications of Artificial Intelligence V, pp. 3840.Google Scholar
Wiilograd, T. 1980. Non-monotonic logic I. Artificial Intelligence 13(1,2), 526.Google Scholar