Electrical Design: A Problem for Artificial Intelligence Research

Introduction:

Engineers combine, analyze, debug, and explain atructures in the course of design. They decide how simple structures may be combined to achieve perticular goals. They cen predict the behavior of complex structures by combining the beheviors of the substructures out of which they were formed. This anelysis is critical for debu11ing plausible designs which do not quite work, for constraining the possible design decisions, end for ruling out unfeesible plens. Finally, an engineer must be eble to explain the devices which he has designed. An e)Cplenation is often a description of how the behavior of the composite device can be ettributed to the combined behaviors of its parts. The ebility to explain is crucial to analysis and design. It is much easier to anelyze a system If we know the intended operation of the parts.

This paper outlines our project to construct an eleCtricel circuit designer progrem 11 part of an effort to understand the fundamental mechanisms involved in reasoning ebout complex, deliberately constructed systems. Perts of this progrem already exist, other perts are being developed and others ere still in the planning stage. Essentiel ideas from the recent theses of Allen Brown on the localizetion of feilures In radio circuits <Brown 1975> and Drew t.AcDermott one rule­ besed system of hlerarchicel design <t.AcDermott 1976> ere being lncorporeted Into this project.

A Theory of the Engineering Design Process:

Innumerable hours can be spent trecking down a ·bug· in e computer program, an electronic device, or a mathematical proof. At such times it may seem that a bug is at best e nuisance end at worst e disaster. We believ.e thet many buss ere just manifestations of powerful strategies of creative thinking -- that creation and removal of bugs are necessary steps in the normel process of solving a complex problem. Following the work of Polya <Polya 1962>, recent research <Fehlman 1973> <Sussmen 1973> <Goldstein 1974> predicated on this belief hes resulted in the development of a paredigm for problem solving which we call Problem Solvin& by Debunin& Almost-Risht Plens (PSBOARP). We believe that the PSBDARP theory Is a good foundation for building expert problem-solving systems for such diverse kinds of engineering aa circuit design and computer programming.

The PSBOARP Theory:

Figure 1 displays the structure of a PSBOARP problem solver. When the problem solver Is given a problem it first checks its Answer Library to determine if there is an answer available whose pattern of applicability matches the problem statement. If so, the proposed answer is tested ml.ke sure that it really works and if it passes the test it is returned as the answer to the problem posed. But suppose the answer is not immediately available. The problem solver next examines a set of problem decompositions to see if any are appropriate for breaking the problem into more manageable chunks. If so, the problem solver remembers the decomposition rule chosen and recursively calls itself to solve each subproblem separately. If this is possible, the solutions returned are combined according to the decomposition rule used to break the problem up and the resulting proposal is sent off to be tested. If there are no decomposition rules available which match the problem statement, the problem solver next checks to see if there are any changes of representation which can be applied to the problem statement to put it into a form more amenable to solution. If so, the problem is considered in terms of the alternate representation. If no representation changes are appropriate, the problem solver has failed on this problem and reports its failure. A failure may cause backtracking and search.

Suppose that a composite solution is eventually proposed and tested. If it is found to work it is returned as the answer, but often the proposal has a bug. A bug may manifest by a contradiction among the constraints of the modules which are the solutions to the subproblems. The composite solution is also analyzed to see if it actually achieves the goal. If there is a bug the next step is to localize the cause of the failure. Since the solution is a composite of correct solutions to subproblems, the bug must be the result of some unanticipated interaction between the parts of the proposed solution. In any case the problem solver must construct a subproblem whose solution would fix the bug. This problem is then solved (by a recursive call to the problem solver) and the resulting patch is installed in the proposed solution. The corrected solution must then be retested against the original criteria.

Why are there bugs?

One mi&ht imagine a problem-solver based on Figure 1 which produced only correct solutions to problems -- that is, one In which the question "Does it work?· is always answered "Yes·. The problem with this idea is that a crucial part of the problem­ solving strategy is the decomposition of problems into presumably independent subproblems. There is no guarantee that this is possible in general, but even when it is not possible, there are often general strategies for approximating a solution to a problem by composing the solutions to almost independent subproblems. Often one can make progress on the solution to a hard problem by considering the solution of a simplified version of the problem which is similar in some essential aspect to the original one but which differs from it in detail. But even in those cases where a decomposition into completely independent subproblems is possible, it is not always feasible. In order to be sure that the solutions to the subproblems are really independent it is necessary to understand the problem and the possible implementations of subsolutions so completely that one must effectively solve the entire problem before choosing the correct decomposition. This compromises the decomposition strategy. Another difficulty is that in order to allow ·perfect· solutions, the decompositions and possible answers to problems must be specified more precisely. This leads to a proliferation of stored answers and decompositions which differ in only some minor aspect and thus hide the power of generalization.

Superficially. PSBDARP is a kind of Means-Ends analysis <Ernst & Newell 1969> but it is not profitable to merge the concepts. In Means-Ends analysis the problem solver considers the current state of the problem solution and the goal being approached and attempts to apply an operator which will move the solution in the direction of the goal. Often the operator will decompose the problem into subproblems which can be achieved separately, to be combined into a solution of the overall problem. At this point the PSBDARP philosophy diverges. In Means-Ends analysis the process is now iterated. In debugging, the original goal may be ignored because many bugs manifest in terms of destructive interactions among the solutions of subproblems.

In PSBOARP there is a apecific phase of the solution process where debug&ing knowled&e is applied. This knowledge Ia relatively domain independent and ia concerned with notions of causality, teleology and simultaneous constraints. The debu11ing phase is far more concerned with the structure of the plan produced by the decompositioll,. phase than it is with the &Qal that evoked the plan. For example, localization of a bu& in an electrical circuit or in a computer program may Involve such strategies as ·tracing· -- examination of the conditions at various module boundaries to determine how the expected conditions compare with those that actually occur.

An Example of Synthesis:

Consider a concrete problem of enaineering synthesis. Suppose we want an electrical network with a specified system functloll! perhaps a network having a volta&e-transfer ratio whose magnitude varies with frequency as follows:

We recognize that the encodina of these requirements is not obvious -- part of the research is to determine appropriate languages for such description. The designer first checks the baa of tricks for a plan fragment (an answer or decomposition) whose pattern of applicability matches the goal. (An expert en&ineer would probably have an answer on tap for so simple a problem.) . "Matches· is a rather complex idea -- features must be extracted such as the ·flat response· between wl and w2, the fall off at frequencies above w2 and below wl, the positions of the ·elbows·, etc. In this case we assume that the designer does not have a plan fragment for synthesis of the required network, so it has to look for 1 transformation of the problem. (In McDermott's · terminology, we enter the "Rephrasing Protocol·.) In this case, there is a aood transformation available -- from a maanitude araph to a pole - zero plot. (This Ia an alaorithmic transformation which requires careful measurement of the parameters of the magnitude plot.) We get:

Thia repreuntatlon Is the same 11 the 11sumptlon that the system function h11 the algebraic form:

This alaebraic expresalon matches the pattern of applicability of one of our plan fragments -- the c11cede plan:

Ita pettern of eppllceblllty Ia:

Notice that this plen frqment is more aenerally epplicabie than just in the domein of eiectricel circuits. It is eppropriete to eny domein in which the ·stun- beina manlpuleted (in this cue sianel represented 11 volteaes) ·flows· from process to process. Note thet this plen frqment essumes thet the flow is unileterel; we will see thet this ceuses 1 bual The system h11 other aenerellzed decomposition rules 11 well. For exemple, if the system function hid been · sum of terms, we could use 1 different plen for decomposition:

In feet, if our ·bea of tricks· includes some techniques of elaebreic menlpulatlon we can turn our product into 1 sum by 1 partlal-frectlon expansion.

W. next try to expand end instentiete the plen freament's perts. W. ere forced to solve 2 subproblems:

(How will our system know to break It up this wey? -- It won't pertlcularly, in thet this depends upon how the elgebreic expression melcher works. But In eny case, If one decomposition fells to be reelizeble we cen expect to beck up end try enother.)

We also see that we have conveniently foraotten ebout K, which wes deferred for later because it is not a constreint. We know thet it is elweys eesy to make 1 se~ler If the problem speclflcetlon does not require thet the result be pessive.

Next, we recursively attempt to instenliete the aubproblems. In this cue, we have (et leest) two metches In the enswer librery. The voltege transfer retlos with one reel pole or with one reel pole end a zero et the oriain can be reelized 11 reslstor-cepecltor vo1t11· dividers.

The problem solver must now check the proposed result. Here circuit lnalysls is employed. If the problem were one of proaram design, we mlaht run the proposed program in CAREFUL mode <Sussman 1973>) or we might try to Meta­ eveluate the proaram <Hewitt & Smith 1975>, or even prove that the proaram Is correct. ... -

In this case analysis discovers a bua. Our enalysis of N1 11 a voltaae divider was contingent on the assumption that no current would be drawn from the midpoint of the divider. Our enelysis of N2 wes contingent on it drawing · significent current. These essumptions ere contrldlcted by connecting the output of N1 to the input of N2. This contradiction is epp1rent from loc·l evidence in the structure of the proposed solution independent of the 1011 of the overall circuit. We heve ceught en unenticipated destructive interection between the subproblem solution modules. This pertlculer kind of bug, celled loading is common end should be considered whenever ports ere connected toaether.

The atetement of thla bua -- thet we heve 1 port voltege which we can't draw 1 current from, connected to 1 port which Wanta to draw 1 current et thet voltege -- cen eesily be turned into 1 atetement of 1 problem whose solution it en · epproprlete petch for thla bua. Wishful thlnklna tell· us thet If we hid 1 voltge-controlled voltge source inserted between N1 end N2 everythlna would be OK.

Thla metchla the aceler plen from the bq of tricks:

We now have a aooct place to absorb our conatant K, thus aolving the problem alven:

Suppose we were usina pure means-ends analysis rather than a debuaaing strateay. At point "* above we would then analyze our current circuit and compare It with the result we expected (the aoal). In this c111, analysis lelds to the following result:

But this Is not the result we were hoping for. We expected:

The difference between the answer we aot and the answer we wanted Is just that there Is an extra term (R 1 C 2 ) in the second coefficient of the denominator. Why is this term present? Allen Brown <Brown 1975> hn developed methods for localizlna buas usina cau11l and teleoloalcal renonlna about a circuit but it is certainly a more difficult prbblem to pursue this path than the one we have.

The Propaaation Theory of Enaineerina Analysis:

It Is Important that the bua localization process have access to the assumptions on which the bua manifestation is bned. This depends upon analysis beina able to explain its answers. In this section we will describe proaress that has been made on an analysis proaram that reasons qualitatively about circuits and can explain its results.

As part of the development of the PSBDARP circuit desianer, we have developed El, a new kind of electrical network analysis proaram <Sussman & Stallman 1975>. The literature is full of powerful and useful circuit analysis systems which implement the formal methods. What is novel about this proaram Is its rule-based approach to network analysis and its consequent ability to explain the basis of Its deductions.

EL is Implemented In ARS (Antecedent Reasonina ~stem), I problem-solvin& lln&UI&e Which implements rules IS demons with multiple patterns of invocation monitorlna an associative data base <Stallman & Sussman 1976>. It performs all deductiona in an antecedent manner, threadina the deduced facts with justifications which mention the antecedent facts used and the rule. of inference applied. These justifications may be examined by the user to aain lnsiaht into the operation of the system of rules es they epply to a problem. The same justifications are employed by the system to determine the currently active dele-base context for reasoning in hypotheticel situations. Justificetions ere also used in the analysis of blind alleys to extract Information which will limit future search.

EL is a set of ARS rules for electronic circuit analysis. This set of rules encodes familiar approximations to physical laws such as Kirchoff's laws and Ohm's law n well as models for more complex devices such as transistors. Facts, which may be aiven or deduced, represent data such as the circuit topology, device parameters, voltaaes and currents. The antecedent reasoning of ARS &ives analysis by EL 1 ·catch-n-catch-can· flavor suggestive of the behavior of a circuit expert. The justifications prepared by ARS allow an EL user to examine the basis of its conclusions. This Is useful in understanding the operation of the circuit as well as in debugging the EL rules. For example, a device parameter not mentioned in the derivation of a voltage value has no part in determining that value. If a user changes some part of the circuit specification (a device parameter or an Imposed voltaae or current), only those facts dependina on the changed fact need be ·forgotten· and re-deduced, so small changes in the circuit may need only a small amount of new analysis. Finally, the search-limiting combinatorial methods supplied by ARS lead to efficient analysis of circuits with piecewise-linear models.

The style of analysis performed by EL, which we call the method of propagation of constraints, requires the Introduction end menipuletion of some symbolic quentities. Though the system has routines for symbolic elgebra, they cen handle only linear relationships. Nonlinear devices such as transistors ere represented by piecewise-linear models that cannot be used symbolically! they can be applied only after one has guessed a particular operating region for each nonlinear device in the circuit. Trial and error can find the right regions, but this method of assumed states is potentially combinatorially explosive. ARS supplies dependency-directed backtracking, a scheme which limits the search as follows: The system notes a contradiction when it attempts to solve an impossible alaebraic relationship, or when discovers that a device's opereting point is not within the possible range for its assumed reaion. The antecedents of the contradictory facts are scanned to find which nonlinear device state auesses (more aenerally, which backtrackable choicepolnts) ere relevant1 ARS never tries that combination of guesses again. A short list of relevant choicepoints eliminates from consideration a larae number of combinations of answers to all the other (irrelevant) choices. The fact that the set of assumptions leadina to the contradiction is Inconsistent is summarized and recorded with antecedents beina that part of the support of the contradiction which are Independent of the assumptions. These summaries are examined whenever a choice has to be made, thus preventina rechoosina of an Inconsistent set of assumptions. Thus the justifications (or dependency records) are used to extract and retain more information from each contradiction than a chronological backtracking system. A chronological backtrackina system would often have to try many more combinations, each time wasting much labor rediscoverina the original contradiction.

Jon Doyle is now engaaed in further research on the uses of dependency information in tl\4t control of reasonina <Doyle 1976> · .L De Kleer, Jon Doyle, Guy Steele and this author have been developing an even more powerful rule-based languqe we call AMORD in which the EL rules can be expressed In a more hierarchical form.

History of this Project and Reletion to other work:

The PSBDARP theory of desian hn meny antecedents. The idea of successive refinement of plans appeara as a key doama of ·structured Proaramming· <Dijkstra 1970> <Wirth 1971> <Dahl et al1972>, elthough It elso appears in the Artificial Intelligence problem-solving literature. The idea of relaxation of a hierarchy of conatraints comes from <Freeman & Newell 1971>. There are also versions of GPS <Ernst & Newell 1969> which were purported to do reasoning in a hiererchy of ebstractlon speces. ABSTRIPS <Secerdotl 1973> showed how refinement of 1bstrect pl1ns could be used to guide 1 problem solver pest problems which would otherwise be combln·torlelly explosive. Recently the I'«>AH system <Secerdoti 1975> h1s developed this ide1 to are1t depth. The m1jor difference we heve with successive refinement Is our emphesis on engineering enelysls 1nd debug&ing. We ere sure th1t it Is impossible to build systems which cen deel with complex reel world problems without m1klng 1nd removing bugs. PSBOARP is 1 descendent of the HACKER <Sussm1n 1973> 1nd MYCROFT <Goldstein 1974> debugging systems. One miaht consider th1t GPS 1lreldy embodied the ide1 of debug&lna In that one mey t1ke · problem solver with 1 debug&lng str1tegy to be 1 speci1l cese of · problem solver which first ettempts to elimin1te the main difference between the alven end the 1011 1nd then reev·lu1tes the sltu·tlon 1fter 1 step. This Is true in principle, but GPS w11 never used for debuaaina. Polye <Polye 1945> h·d developed · theory of problem solvina which Included debugging but GPS only c1ptured the reduction end rephr1slng 1spects of Poly1's theory.

Recently Allen L Brown Jr. finished 1 PhD thesis et hAlt <Brown 1975> which explored the use of CIUS1I1nd teleoloaic·l re1sonlna In the troubleshootina of complex electrlcel systems. In this thesis Brown developed 1 set of linguistic conventions for the represent1tion of the pl1n of 1 complex, hler·rchically-structured system. Brown's methods depend on, end Inspired the construction of the EL 1n1lysis system <Sussmen I St1llmen 1975> which uses constraint propq1tion end cen expl1in how 1 result depends on 1ssumptions. Brown needed 1n1lysis by propq1tion of constr1ints to predict the consequences of 1 hypothesized feult In 1 component. These consequences are compered with the meesured v1lues 1s a test of the feult theory. The expl1netlons 1re critical In determining the f1ulty 11sumptlons. Joh1n de Kleer 1lso uses this technique In his debug&ing progr1m INTER <de Kleer 1976>. A related process of rel·x·tlon of symbolic constr·lnts h1s been 1pplied to the libelling of line dr1wlngs of visu1l scenes <Huffm1n 1970>. A beeutiful exposition of this technique cen be found In <W11tz 1972>. Some theoretic·! 1n1lysls of this technique 1ppears In <Freuder 1976>.

TOPLE <hAcDermott 1974> wes 1n e1rly 1ttempt to record the interectlons ·mona deductions for the purpose of deciding wh1t is currently believed to be true. hAcDermott used this information to help decide which of sever1l 1ssumptions must be thrown out In order to keep 1 consistent d1t1 b1se when 1 new f1ct conflicted with existing ones. MYCIN <Shortliffe 1974> <D1vls 1976> use dependency informetion to produce · expl1n1tions but do not use It for eny control purposes. The SRI Computer B1sed Consult1nt <Fikes 1975> mekes use of dependencies to determine the loalc·l support of facts in 1 m1nner slmil1r to ARS but does not use them to control search.

Two other recent rese1rch efforts 1t hAlT h1ve developed these idees further. Drew V. hAcDermott finished 1 PhD thesis <hAc Dermott 1976> concerning the design of such systems. Drew developed 1 rule-besed l1nguqe, c1lled NASL, In which It Is possible to express streteales, tactics, 1nd advice for design. He used this languqe to encode some general desian strategies 1nd some specific str1tegles for the design of electric·! systems. Howie Shrobe 1nd Ch1rles Rich <Rich I Shrobe 1976> designed 1nd mostly Implemented a system which ·underst·nds· 1 limited cl1ss of LISP progr1ms. They h1ve developed set of linguistic constructs for attaching 1 set of structured comments to 1 proar·m which relate It to its pl1n. These pl1ns look very much like the pl1ns of Brown. They h1ve also developed 1 system which re110ns 1bout the progr1m In terms of Its pl1n, 1nd which cen check th1t 1 proar·m In fact Implements Its go1ls. In effect their system employs the · teleologic1i inform1tion In the plen 1bout the p1rts of the proar·m being checked, 11 en outline for the verification of the progr1rn.

Fin1lly, there have been meny books ·bout the strateales of the desian process (for ex1mple <Aiex1nder 1964>,

<Aslmow 1962>, <Buhl 1962>, <Gieaa 1973>) but these 1re mostly simple 1dvice 1bout how to 1vold overlooking 1 good 1pproach when working out 1 h1rd problem. They offer little help In how to propose new solutions to new problems. Artlflcl·l Intelligence rese1rchers heve been Interested In the deslan process 1s 1 model of cre1tlvity. Computer Science in aener1l h1s been Interested In desian bec1use of the ·complexity b1rrlers· epp1rent In the deslan of lerae systems. Herbert Simon <Simon 1969> wrote 1 deliahtful 1nd Insightful book which rel1tes computer science to gener1l engineering design and to cognitive theory. At Cerneaie-~llon University, for ex1mple, Gr11on <Gnson 1970> wrote 1 PhD thesis on the rel1x1lion of erchitecturel constr1ints, 1nd Hanley <Hanley 1968> wrote 1 PhD thesis on computer-·lded deslan of computer Instruction sets.

One would expect the CAD liter1ture to dell extensively with systems to seve 1n engineer time 1nd effort. A survey of this liter1ture (see <Kuo & hAqnuson 1969> <Furm1n 1970> <Dertouzos 1972> <VIietstr1 I Wieling1 1973> <Rosenbrock 1974>) shows th1t the thrust of CAD development h8S been In the development of Interactive gr1phics p1ck1ges, librerles of speci1l purpose proar·ms, 1nd m·themeticelly sophlstlceted progr1ms 1imed 1t 1n1lysls or optimiz1tion of synthesis. Only 1 sm1ll ·mount of work h11 been done in the field of synthetic re1sonlng, 1nd then only ln. restricted domains where elaorlthms 1re ev1i11ble to solve 1 sm1ll cl1ss of problems. Such 1ppro1ches h1ve been p1rli1lly successful in the problem of printed-circuit layout (e.a. <Fletcher 1974>) 1nd filter deslan (e.a. <Choh1n I Fidler 1974>). Director <Director 1974> describes 1 circuit deslan progr1m which 11sumes 1 full-gr1ph imped1nce network 1nd then optimizes the network for the behavior desired. In the process, m1ny component v1lues become zero 1nd ere thus disc1rded! The CAD liter1ture is 1lmost completely ianor1nt of non-numeric1l techniques (except <Powers 1973>) end would benefit from 1n Infusion of these new idees. Besides our work, the TROPIC system <Letombe 1976> is one other 1pplicetion of 1rtlfici·l intelliaence idees to CAD. John S. Brown <Brown I Burton 1975> (It Bolt, Ber1nek 1nd Newm1n, Cembrldae, hAissachusetts) hes been applying both ertificiel lntelllaence Idees end CAD Idees to the problem of computer­ elded Instruction of circuit debuglng skills for technlcl1ns. We expect th1t the work of his aroup will contribute to the underst1ndlng of AI Issues In CAD.

Conclusions:

A m1jor problem confronting builders of IUIOmltic problem-solvina systems Is th1t of the combin1toriel explosion of se1rch-spaces. One w1y to 1tt1ck this problem is to build systems th1t effectively use the results of f1ilures to reduce the seerch space -- th1t le1rn from their exploretion of blind 1lleys. In simple ceses, as in en1lysls of circuits, v1rlous eutom1tic techniques such es the dependency-directed backtr1cking of ARS can ao 1 lona w1y tow1rd controlling the se1rch. In more complex sltu1tions, 11 In desian, it Is necessery to constr1in the se1rch es repldly IS possible -- even If th1t sometimes overconstr1ins the problem end causes 1 bug. At le1st we cen hope thet the debugalng problem Is eesler th·n the se1rch problem. In either c1se It is necesury to build problem solvers so th1t they c1n remember 1nd expl1in their reesoning. Both dependency-directed backtracklna 1nd problem solvina by debuggina elmost-riaht pl1ns depend on the 1bility to menipul1te the justific1tion of 1 conclusion 11 well 11 the 1bility to deduce it.

S·vina justific1tions for the intermedi1te results of 1 comput1tlon h1s other merits. It Is very difficult to debug . proar·ms cont1inlng l·rae ·mounts of knowled&e. The complexity of the Interactions between the ·chunks· of knowledae m1kes It difficult to 11certeln wh1t Is to bleme when 1 bug m1nlfests Itself. A progrem which c·n expl1in the reesons for Its beliefs Is more convincing when rlaht, end It Is e1sler to debug when wrona.

Acknowledgement:

• I would like to thank the meny people who have contributed to this project. Richerd (RMS) Stallman, Drew McDermott, Allen Brown, Guy (QUUX) Steele, Jon Doyle, Joh~n de Kleer, Marilyn hAetz end Gerald Roylence have worked with me on lt. Chuck Rich, Howie Shrobe, Scott Fehlmen, Mervin Minsky, Seymour Papert, Louis Br11da, P1ul Penfield, Kurt V1nlehn, Rlch1rd Fikes, John Allen, DIVId hAirr, P1t Winston, 1nd E1rl Secerdotl provided &ood ldvlce 1nd Important ldeiS.

Biblloarephy:

• Alex1nder, C. (1964) Notes on the Synthesis of Form, C1mbridge: Hlrvard University Press.
• Aslmow, M (1962) Introduction to Desian, Englewood Cliffs, NJ: Prentice-Hill, Inc.
• Brown, Allen (1975) Qullitltlve Knowledae, C1usel ReiSOnlna, 1nd the Loc·liz1tion of Fellures, Cembridse: unpublished hAlT Ph.D. thesis.
• Brown, John Seely end Rich1rd R. Burton (1975) '\Aultiple Represent1tlons of Knowled&e for Tutorl1l Reasoning· In D1niel Bobrow 1nd All1n Collins (Eds.), Represent1tion 1nd Underst1ndlna: Studies In Coanltlve Science, New York: Academic Press.
• Buhl, H.R. (1962) Cre1tlve Enalneerlna Deslan, Ames, lowe: The low· Stete University Press.
• Choh1n, V.C. 1nd J.K. Fidler (1974) "Computer Aided Desian of Filters for D1t1 Tr1nsmlsslon Using Frequency hAodul1tlon· Proceedlnas of the lntern1tion·l Conference on Computer Aided Desian, 1974.
• D1hl, O.J., E.W. Dljkstrl end C.A.R. Hoere (1972) Structured Proar1mmlna, London: Acldemlc Press.
• Devls, R1nd1ll (1976) Applicetions of Met· Level Knowledae to the Construction, hAIIntenance, 1nd Use of Larae Knowled&· Bases, Stenford, CA: Stenford University Artificiel lntelliaence Leboratory Memo 283.
• de Kleer, Johen (1976) Local Methods for Loclllzltlon of F1ults In Electronic Circuits, C1mbrld&e: hAlT Artlficl·l lntelliaence labor1tory Memo 394.
• DertouzoS, hAichHI (1972) "CIRCAL-2: Generei-Purpose On-Line Circuit Desian·, Proceedlnas of the IEEE. Vol. 60, pp. 3948, J·n. 1972.
• Dijkltra, Edsg1r (1970) -structured Proar·mmlng·ln Softw1re Enalneerina Techniques, J.N. Buxton 1nd B. Rendell (Eds.), NATO Scientific Aff1irs Division, Bruseels, Belaium, 1970.
• Director, S.W. (1974) -row1rds Autom1tic Design of lntqreted Circuits·, in Willl1m R. Spillers (Ed.) Besic Questions of Deslan Theory, New York: Amerlc1n Elsevier Publishing Comp1ny,lnc., p. 303.
• Doyle, Jon (1976) The Use of Dependency Reletionships In the Control of Re11onina, C.mbrid&e: hAlT Artifici1l · lntelliaence llbor1tory Working Peper 133.
• Ernst, Georae W. 1nd Allen Newell (1969) GPS: A C1se Study In Gener1lltv 1nd Problem-Solvlna, New York: Acldemlc Press.
• F1hlm1n, Scott (1973) A Plennlna System for Robot Construction T1sks, Cembrid&e: hAlT hAuler's Thesis.
• Fikes, Richard (1975) Deductive Retrieval hAechenisms for Stete Description Models, Menlo Perk, CA: Stenford Research Institute Artificial lntelllaence Center Technical Note 106.
• Fletcher, A.J. (1974) "EUREKA- A System for the Autometlc L1yout of Single-Sided Printed Circuit Boards,· Proceedings of the Zllnternetionel Conference on Computer Aided Desian, 1974.
• Freemen, P. end Allen Newell (1971) ·A hAodel for Functionel Reesonlna In Desisn: Proceedinss of lnternetlonal Joint Conference on Artlficlellntelliaence II, p. 621.
• Freuder, Eugene (1976) Syntheslzlna Constreint Expressions, Cembrldge: hAlT Artificlel lntelliaence L1b Memo 360.
• Furm1n, T.A. (1970) (Ed.) The Use of Computers in Ensineerlns Desian, London: English Universities Press.
• Gleaa, Gordon Lindsey (1973) The Science of Desian, Cembrld&e, Ena.: Cembrld&e University Press.
• Goldstein, Ire (1974) ·summery of hAYCROFT: A System for Understendlna Simple Picture Progrems,· Artificial Intelllsence, Vol. 6, No.3, Fell, 1975, pp. 249-288.
• Greson, Jeson (1970) Methods for the Computer-Implemented Solution of 1 Class of "Floor Plan· Desisn Problems, unpublished Ph.D. dlssertetion, Pittsburgh: Cerneaie­ Mtllon University.
• Henley, Frederick (1968) Usins 1 Computer to Design Computer Instruction Sets, Pittsburah: Cernegle-hAellon University Computer Science Depertment Ph.D. thesis.
• Hltwltt, C1rl 1nd Brien Smith (1975) Towerds 1 Prosremmlna Apprentice, C1mbrldae: hAlT Artificlel lntelliaence Leboretory Working Peper 90.
• Huffmen, DIVId (1970) -.mposslble Objects 11 Nonsense Sentences,· In hAIChine Intelllaence 6, Edinburgh, UK: Edinburgh University Press (1970).
• Kuo, F.F. 1nd W.G. hAqnuson (1969) (Eds.) Computer-oriented Circuit Desian, Englewood Cliffs, NJ: Prentice-Hall, Inc.
• L1tombe, Je·n-cleucle (1976) Artlflcl·l lntelllaence In Computer­ Aided Desian: The Tropic System, Menlo Park, CA: Stenford Rese1rch Institute Artlflcl·l lntelliaence Center Technic1l .Note 125. '
• McDermott, Drew (1974) Asslmlletlon of New lnformetlon by 1 N1turel Lenauge Underst1ndlna System, Cembricfae: hAlT Department of Electrlc·l Engineering 1nd Computer Science Mester's Thesis.
• McDermott, Drew (1976) Flexibility lnd Efficiency In 1 Computer Proarem for Deslanlna Circuits, C.mbrld&e: hAlT · Dep1rtment of Electrlcel Engineering 1nd Computer Science Ph.D. Thesis.
• Polya, Georae (1945) How to Solve It, Princeton, NJ: Princeton University Press,
• Polya, Georae (1962) hAithem·ticll Discovery: on Understendin~a le1rnina. 1nd Teechina Problem Solvina, Vols. I 1nd II, New York: John Wiley 1nd Sons, Inc.

• Powers, Gary (1973) "Non-Numerltal Problem Solvina Methods In Computer Aided Deslan,·ln Vlietstr1 1nd Wiellna1 (1973).
• Rich, Chsrles 1nd Howie Shrobe (1976) lniti1l Report on 1 LISP Proar1mmer's Apprentice, C.mbrldae: MIT Artlflclll lntelllaence L1bor1tory Technlc1l Report 354.
• Rosenbrock, H.H. (1974) Computer;.Aided Control System Desian, London: Acamlc Press.
• Secerdotl, E1rl (1973) "P11nnlna In 1 Her1rchy of Abstrsction Spsces; Proceedlnas of the Third lntern1tion1l Joint Conference on Artlfici1llntelllaence, Auaust, 1973, pp. 412-422.
• Secerdotl, Elrl (1975) A Structure for P11ns 1nd Beh1vior, Menlo P1rk, CA, Stenford Rese1rch Institute Artifici1l lntelliaenee Group Technlcel Note 109, 1lso New York: Amerlc1n Elsevier Publlshlna Comp1ny (1977)
• Shortllffe, E.H. (1974) MYCIN- A Rule-811ed Computer Proarem for Advisina Physlcl1ns Rea1rdina Antlmicrobi1l Therapy Selection St1nford, CA: Stanford lkllversity Artificial lntelllaence Leboretory Memo AIM-251 (October 1974), elso MYCIN: Computer-Bised Medlc1l Consultetions, New York: Amerlcen Elsevier (1976).
• Simon, Herbert (1969) The Sciences of the Artificial, Cembrldae: MIT Press.
• Stellman, Richerd 1nd Gerald .ley Sussm1n (1976) Forw1rd Reesonlna end Dependency-Directed Beckiritkiii In e System for Computer-Aided Circuit Analysis, Cembridae: MIT Artificial lntelllaence Leboratory Memo 380. (To appeer in the AI Journel)
• Sussmen, Ger1ld .ley (1974) ~Virtuous Neture of Buas·, Proceedinas of the Artificl1l lntelllaence Simul1tlon of Behavior Conference, Sussex, UK.
• Sussmen, Gerald .ley (1973) A Comput1tional Model of Skill Acquisition MIT Dept. of Math. PhD Thesis, MIT Artificial lntelllaence Labor1tory Technlc1l Report 297 (Auaust 1973), 1lso A Computer t.Aodel of Skill Acquisition, New York: Americen Elsevier Publlshina Compeny (1975).
• Sussmen, Ger1ld Jey 1nd Rich1rd St1llm1n (1975) "Heuristic Techniques In Computer-Aided Circuit Anelysls,· IEEE Tr1nssctlons on Circuits 1nd Systems, Vol. CAS-22, No. 11, Nov., 1975.
• Vllestr1, .L 1nd R.F. Wiellna1 (1973) (Eds.) Computer-Aided Desian, Amsterdem: North-Holl1nd Publlshlna Comp1ny, Inc.
• W1ltz, D1vld (1972) Gener1tlna Sem1ntlc Descriptions from Dr1wlnas of Scenes with Shldows, C1mbridge: MIT Artlflcllllntelllaence Llbor1tory Technicel Report 271.
• Wirth, N. (1971) ~01r11111 Development by Stepwise Refinement,· Communlcetlons of the ACM. Vol.l4, No.4, April 1971.

Postscript:

Due:

Problem Set In Electricity (epproprlete for AI 2!. MIT students) Next IJCAI

Problem 1:

WEEI-AM (590 kHz) needs 1 ·dummy load· for use in meinten1nce .of their 50 kw tr1nsmitter. A dummy lo1d Is a resistor connected to the output of the tr1nsmitter, in lieu of 1n entennl, to ellow edjustments lnd melsurements to be mlde on the trensmitfer under controlled conditions without redi1tin1 the test sianels (which mlaht Interfere with other stations). The only resistor the)'! heve, cepeble of dissipatina 50 kw, is e 1 ohm· 1r1phite bfOCjk in I drum Of Oil (used to Clrry Off the helt). The tr1nsmitter,ljlowever, needs a 50 ohm resistive load-- it . is to be 1djusted to dper1te in e 50 ohm 1ntenn1. Can you help the m1n from WEEI? Desian 1 device (mlde of one Inductor 1nd one cepecitor) to; m1tch his trensmitter to the 1 ohm resistor? How much current will flow in the resistor when the trsnsmitter is beina tested?

Problem 2:

· Desian 1 volt·ae 1mpllfler with 1 aeln of 20 dB. The Input lmped1nce musf be 1t IelSt 47 kohms, the output c1pable of drlvlna 1 e 4 ohm lo1d et 20 wetts rms. The emplifler must be epproprlete for medium qu11ity 1udlo 1pplic1tions. Power Is 1velleble et +48 1nd -48 volts DC.

This report describes reseerch done et the Artiflciel Intelligence Leboretory of the Massechusetts Institute of Technoloay. Support for the leboretory's reseerch Is provided in pert by the Advenced Rese1rch Projects Aaency of the Dep1rtment of .Defense under Office of Nevel Reseerch cintrect N00014-75-c0643