MASSACHUSETTS INSTITUTE OF TECHNOLOGY
`
`ARTIFICIAL INTELLIGENCE LABORATORY
`
`Memo No. 880
`
`Sept. I976
`
`Forward Reasoning and Dependency-Directed B‘acktrack.ing-
`In a System for Computer-Aided Circuit Analysis
`
`by Richard M. Stallman and Gerald jay Sussman
`
`Abstract:
`
`We present a rule-based system for computer-aided circuit analysis. The set of rules,
`called BL, is written in a rule language called ARS. Rules are implemented by ARS as pattern-
`directed invocation demons monitoring an associative data base. Deductions are performed in an
`_ antecedent manner, giving EL's analysis a catch-as-catch-can flavor suggestive of the behavior of
`expert circuit analyzers. We call this style of circuit analysis propagation. of constraints. The
`' system threads deduced facts with justifications which mention the antecedent facts and the rule
`used. These justifications may be examined by the user to gain insight into the operation of the
`set of rules as they apply to a problem. The same justifications are used by the system to
`determine the currently active data-base context for reasoning in hypothetical situations. They are.
`also used by the system in the analysis failures to reduce the search space. This leads to effective
`control of combinatorial search_ which we call dependency-directed backtracking.
`
`Work reported herein was conducted at the Artificial intelligence Laboratory, a Massachusetts
`Institute of Technology research program supported in part by the Advanced Research Projects
`Agency of the Department of Defense and monitored by the Office of Naval Research under
`contract number NOOOI4-75-C-0643.
`'
`
`Page 1 of 69
`
`FORD 1318
`
`

`
`Many people contributed to this work: Allen Brown, Drew
`' HcDermott. Johan de Kleer. Kurt Vanlehn. Louis Braida. Richard
`Fikes. and Earl Sacerdoti gave us some excellent
`ideas. Bug
`'
`Steele. Charles Rich and Ben Kuipers gave us some important
`editorial help. John Allen. David Harr. Pat Uinston and Paul
`Penfield also provided good advice.
`
`Contents:
`
`Introduction
`Analgsis by Propagation of Constraints
`Facts and Laws
`The Hethod of Assumed States
`Making Choices
`Dependencies and Contexts
`_ Contradictions
`Compound Devices and Identified Terminals
`The Queue-based Control Structure
`The Data Base of Facts and Demons
`Conclusions
`Appendix: An Annotated Example
`Notes
`_
`Bibliography
`
`'
`
`2
`5
`11
`14
`15
`18
`22
`24
`27
`30
`33
`36
`82
`85
`
`Page 2 of 69
`
`FORD 1318
`
`

`
`Stal lrnan & Suseman
`
`2
`
`Analysis
`
`Introduction
`
`A major problem confronting builders of automatic problem-solving systems is that of
`the combinatorial explosion of search-spaces. One way to attack this problem is to build systems
`that effectively use the results of failures to reduce the search space -- that learn from their
`exploration of blind alleys.B""" ’"°V‘ Another way is to represent the problems and their solutions in
`such a way that combinatorial searches are self limiting.“""'°"’
`A second major problem is the difficulty of debugging programs containing large
`amounts of knowledge. The complexity of the interactions between the "chunks" of knowledge
`makes it difficult to ascertain what is to blame when a bug manifests itself.c°"“""‘"V One approach
`to this problem is to build systems which remember and explain their reasoning.E""°‘""‘ Such
`programs are more convincing when right, and easier to debug when wrong.
`We have designed and implementedusp a problem-solving language called ARSAR5 in
`which problem-solving rules are represented as demons with multiple patterns of
`invocationP°"""""'°°"° ""'°‘°"°" monitoring an associative data base.°°'° "°’°° It performs all
`deductions in an antecedent manner, threading 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 gain insight into the operation of the system of rules as they apply to'a problem.
`The same justifications are employed by the system to determine the currently active data-base
`context for reasoning in hypothetical situations.c°"'°*' justifications are also used in the analysis of
`blind alleys to extract information which will limit future search.
`We have used ARS to implement a set of rules for electronic circuit analysis. This set of
`rules, a version of BL.“ encodes familiar approximations to physical laws such as Kirchoff's laws
`and Ohm's law as well as models for more complex devices such as transistors. Facts, which may.
`be given or deduced, represent data such as the circuit topology, device parameters, and voltages
`and currents. The antecedent reasoning of ARS gives analysis by EL a"'catch-as-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 voltage or current), only those
`facts depending 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 supp.lied by ARS lead to efficient analysis of circuits with piecewise-linear models.
`The application of -a rule in ARS implements a one-step deduction. A few examples of
`one-step deductions, resulting from the application of some EL rules_ in the domain of resistive
`network analysis, are:
`
`I: If the voltage on one terminal of a voltage source is given, one can assign the voltage on the
`other terminal.
`
`2: If the voltage on both terminals of a resistor are given, and the resistance is known, then the
`current through it can be assigned.
`3: If the current through a resistor, and the voltage on one of its terminals, is known, along
`
`Page 3 of 69
`
`FORD 1318
`
`

`
`Stal Iman 8- Sussman
`
`3
`
`Analysis
`
`with the resistance of the resistor. then the voltage on the other terminal can be assigned.
`
`4: If all but one of the currents into a node are given, the remaining current can be assigned.
`
`The style of analysis performed by EL, which we call the method of propagation of
`constraints,p'°”°'°"°" requires the introduction and manipulation of some symbolic quantities.
`Though the system has routines for symbolic algebra,sV"“’°"° '"°"“’”""°" they can handle only linear
`relationships. Nonlinear devices such as transistors are represented by piecewise-linear models that
`cannot be used symbolically;
`they can be applied only after one has guessedA""‘°° 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 algebraic relationship, or when discovers that
`a transistor’s operating point is not within the possible range for its assumed region. The
`antecedents of the contradictory facts are scanned to find which nonlinear device state guesses
`(more generally, the backtrackable choicepoints) are relevant; ARS never tries that combination of
`guesses again.’ A short list of relevant choicepoints eliminates from consideration a large number
`of combinations of answers to all the other (irrelevant) choices. This is how the justifications (or
`
`dependency records) are used" to extract and retain more information from each contradiction than
`a chronological backtracking system.B““'°°'“"" A chronological backtracking system would often
`have to try many more combinations, each time wasting much labor rediscovering the original
`contradiction.
`
`H How it works:
`'
`In EL all circuit-specific knowledge is represented as assertions in a relational database.
`Qeneral knowledge about circuits is represented by kiwi, which are demons subject to pattern-
`' directed’ invocation. Some laws represent knowledge as equalities. For example, there is one demon
`for Ohm's- law‘for resistors, one demon that knows that the current going into one terminal of a
`resistor must come out of the other, one demon that knows that the currents on the wires coming
`into a node must sum to zero, etc. Other laws, called Monitors handle knowledge in’ the form of
`inequalities: For example, I-l‘llJNi TOR—DIODE knows that a diode can have a forward current if
`and only if it is ON, and can never have a backward current.
`_
`When an assertion (for example, (= (VOLTAGE (C 01)) 3.14) . which says that the
`voltage on Ql’s collector has the value 8.1 volts) is added to the data base. several demons will in
`general match it and be triggered. (in this example, they will include DC-KVL. which makes sure
`that all other elements’ terminals connected to Ql’s collector are also known to have that voltage.
`and VCE—l‘lONlTOR-BJT. which checks that Q1 is correctly biased for its assumed oper-ating region.).
`The names of the triggered laws are put on a queue, together with arguments such as the place in
`the circuit that the law is to operate. Eventually they will be taken off the queue and processed,
`
`perhaps making new deductions and starting the cycle over again.
`When a law is finally processed, it can do two useful things: make a new assertion (or
`several), or detect a contradiction. A new assertion is entered in the data base and has its
`
`antecedents recorded;
`
`they are the asserting demon itself, and all the assertions which invoked it or_
`
`Page 4 of 69
`
`FORD 1318
`
`

`
`Stal lman & Sussman
`
`4
`
`_
`
`Analysis
`
`contradiction is to be handled. A contradiction indicates that somepreviously made arbitrary
`choice (e.g. an assumption of the linear operating region of some nonlinear component) was
`incorrect. ARS scans backward along the chains of deduction from the scene of the contradiction,
`to find those choices which contributed to the contradiction, and records them all in a NDGDUD
`assertion to make sure that the same combination is never tried again.
`(NOGUUD ( (NUDE O1)
`CUTUFFI
`l (MODE US) ON)) is a NOGODD assertion that says that it cannot be simultaneously true
`that transistor Ql is cut off and diode D5 is conducting. Such a NDGUOD might be deduced if Q]
`and D5 were connected in series. Next, one of the conspiring choices is arbitrarily called the
`"culprit" ("scape-goat" might be a better term) and re-chosen differently. This is not mere
`'undirected'trial and error search as occurs when chronological backtracking with a sequential
`
`control structure is used, since it is guaranteed not to waste time trying alternative answers to an
`irrelevant question. The NOGODD assertion is a further innovation that saves even more
`computation by reducing the size of the search space, since it contains not all the choices in effect,
`but only those that were specifically used in deducing the contradiction. Frequently some of the
`circuit’s transistors will not be mentioned at all. Then, the NOGOOD applies regardless of the states
`assumed for those irrelevant transistors.
`If there are ten transistors in the circuit not mentioned in
`
`the NDGUUD, then since every transistor has three states _(in the EL model) the single NOGUOD has
`ruled ‘out 3‘0-=59O19 different states of the whole circuit. .
`
`Page 5 of 69
`
`FORD 1318
`
`

`
`Stal Iman 8. Sussman
`
`S
`
`Analgsis
`
`Analysis by Propagation of Constraints
`
`Consider a simple voltage divider:
`
`
`
`Suppose that the voltage at the midpoint is known to be 3 volts. relative to the indicated ground.
`Since there is known to be no DC current through the capacitor, it is possible to determine the
`strength of the voltage source. Forward reasoning is doing it this way: First, use Ohm's law to
`compute the current through R2 from its resistance and the difference of the voltages on its
`terminals. Next, the current through R‘ can be seen, via KCL, to be the same as that through R2.
`Finally, that current, together with Rl's resistance and the voltage at the midpoint, can be fed to
`Ohm’s law to produce the voltage at the top. This is an example of what we call "forward
`reasoning" or (as applied to circuits) "propagation of constraints".
`However, not all circuit problems can be solved so simply. Consider a ladder network:
`
`Kl
`
`K3
`
`K3
`
`o_—o
`.1
`
`Such a network might be solved with three node equations or by series-parallel reduction. More in
`the spirit of forward reasoning is "Guillemin‘s Trick":
`We assume a node voltage, e, at the end of the ladder. This implies a current, e/5. going
`down R6 by Ohm's Law. KCL then tells us that this current must come out of R5. But we know
`the voltage on the right of R5 and the current through it, so we deduce that the voltage on its left
`is 2e. We use this voltage to deduce the current through R4 and then KCL to give us the current
`
`Page 6 of 69
`
`FORD 1318
`
`

`
`Stal lman 8. Sussman
`
`8
`
`Analysis
`
`.9
`.9’
`
`5
`
`—_P.5'
`
`*3
`*3
`
`‘I
`
`K3
`
`5'
`
`£5
`
`/0
`
`Ki
`
`But now we know 8e - IO, therefore, e - 5/4 volt. We have solved the network with 1 equation in I
`unknown.
`
`Alas, Guillemin’s trick fails in the following circuit:
`
`
`
`At first glance, this is a 3 node equation network with no possible series-parallel reductions. We
`want to generalize CuilIemin’s trick to solve this network (with fewer than 3 equations).
`We first assume a node potential, el, at ‘the top of R6. Thus. we deduce that the current
`through R6 is ellé. At this point we can make no further one-step deductions. Rather than give
`up, let's poke it again. We assume a node potential, e2, at the top of R}. We can now conclude
`that the current through R4 is e2ll and the current through R5 (measured to the right) is (e2-ex)/2.
`We can now use KCL to deduce that the current through R7 (to the right) is (3e|-2e2)I-i and that
`the current through R3 is (3e2-e])l2:
`
`Page 7 of 69
`
`FORD 1318
`
`

`
`Stal lman 8 Sussman
`
`7
`
`Analysis
`
` 1-
`
`-
`
`At this point we can deduce that the voltage on the leftmost terminal of R7 is el+(3/4)(3el-
`2e2) or (l3e1-6e2)/4. We can also deduce that the voltage on the leftmost terminal of R3-is
`e2+8((3e2-el)/2)=l3e2-4e‘. Since these terminals are connected together we have two expressions for
`the same node voltage. Setting them equal and simplifying. we get e1=2e2. The result of this
`‘simplification is:
`
`' C
`
`ontinuing, we deduce that the current through R2 must be 5e2/l0=e2l2. By KCL, the
`current through R1 must be ‘2e2. Ohm's law now gives as the voltage at the left of R! as l5e2. But
`this voltage is set by the voltage source, so l5e2=30. We conclude that e2=2:
`
`Page 8 of 69
`
`FORD 1318
`
`

`
`Stal lman & Sussman
`
`8
`
`Analysis
`
`
`
`We have solved the network with only two unknowns. As we approach a full graph
`
`network, this method degrades smoothly to be the node method, but usually it uses far fewer
`unknowns.
`
`What have we been doing?
`
`A fundamental concept here is that of a one-step deduction.
`
`In the case of a resistive
`
`network with voltage and current sources there are only a few kinds of one-step deductions
`
`possible:
`
`1: If the voltage on one terminal of a voltage source is given, one can assign the voltage
`on the other terminal.
`
`2: If the voltage on both terminals of a resistor are given, then the current through it
`
`can be assigned.
`3: If the current through a resistor is given, and the voltage on one terminal is given,
`then the voltage on the other terminal can be assigned.
`4: If all but one of the currents into a node are given, the remaining current can be
`
`assigned.
`
`Another basic concept here is that of a coincidence. A coincidence occurs when a one-
`
`step deduction is made which assigns a value to a network variable which already has a value.
`We have seen several coincidences.
`In the ladder network example a one-step deduction of type 3
`assigns the node voltage 8e to a node which is already at 10 volts.
`In the second example, the node
`at the top of R2 was assigned two different node voltages by two one-step deductions of type 3,
`and the voltage l5e2 even though it already was known to be 30 volts.
`In each of these cases the
`coincidence resulted in the formulation of an equation between the competing assignments. At the
`.time of a coincidence, the resulting equation should be solved, if possible, for one of its unknowns
`in terms of the others. The circuit is then redrawn with that unknown eliminated.
`
`Page 9 of 69
`
`FORD 1318
`
`

`
`Stal lman & Sussman
`
`8
`
`Analgsis
`
`Thus, the basic propagation analysis algorithm is rather simple:
`
`Algorithm: Propagation of Constraints
`Choose a datum node and assign it a potential of 0.
`IF there is a one-step deduction available
`Choose a deduction and make it.
`
`loop:
`
`ADVICE:
`
`[1] IF the last action was the assignment of
`a node potential, look for a type I, 2, or 3
`deduction involving that node.
`[2] IF the last action assigned a current,
`look for a type 3 or 4 deduction involving
`that branch.
`
`IF the deduction caused a coincidence TH EN
`
`IF the equation implied by the coincidence is a
`
`tautology
`
`Ignore the coincidence (and be
`
`reassured by the fact that it checks!).
`contradiction
`
`ERROR: You did something wrong.
`
`otherwise
`
`Solve for one unknown in terms
`
`of the others (or for a number, if
`
`there are no others!). Eliminate
`
`that unknown throughout the circuit.
`
`00 to loop.
`IF there is a node without a node potiential
`Choose such a node and assign it a new node potential variable.
`Go to loop.
`RETURN
`
`‘All of the unknowns introduced by the algorithm are sure to have had their values determined by
`the time the algorithm returns.
`
`Now, what about choosing where to place unknowns? We want to get as much action as
`we can out of each one. One measure of the simultaneity of the situation is given by a count of
`the number of unknown nodes connected to a given one.B'°‘d° For example, consider our ladder
`again. All nodes except the ground and the top of the voltage source are unknown.
`In the
`following circuit each unknown node has been annotated with the number of unknowns it is
`connected to.
`.
`
`Page 10 of 69
`
`FORD 1318
`
`

`
`Stal lrn_an & Sussman
`
`10
`
`Analgsis
`
`If
`We can see that the middle node has two unknown neighbors while the others have only one.
`we place a node potential on the middle node, we can only deduce one current while if we place it
`at either one of the l neighbor nodes we will get the whole answer. The rule is to place the node
`potential at a node of minimum unknown neighbors. This also has bearing on where to place the
`In general, we want a node which is maximally connected to unknowns, so as to constrain
`them quickly.
`
`Page 11 of 69
`
`FORD 1318
`
`

`
`Stal lman 8. Sussman
`
`11
`
`Analgsis
`
`Facts and Laws
`
`Analysis by propagation of constraints is a form of antecedent reasoning in which a
`given, closed set of questions (in this case, the voltages and currents at all points in the network) is
`to be answered. ARS provides a general framework for the implementation of antecedent
`reasoning systems; we developed it to support the particular set of rules for electrical analysis
`which we call EL. Like any programming language, ARS is best explained by showing how it can
`be used to implement an example. We will now display sample parts of EL, and how they
`implement parts of the analysis method already described.
`To EL a circuit is made up of devices and nodes. A device is any of the components one
`would normally think of as present in the circuit, such as resistors, capacitors, transistors, and
`voltage sources. Each device has two or more terminals by which it is connected to the rest of the
`circuit. But two device terminals are never connected directly. Instead, they are both connected to a
`common node (that is the sole purpose of nodes).
`ARS requires that all knowlege to be manipulated be represented as assertions. and their
`manipulators to be expressed as demons. EL therefore deals with facts that name the devices and
`nodes in the circuit, and state which terminals connect to which nodes. A node or device is named
`
`by an lS—A assertion, such as (lS—A R1 RESISTOR) or (IS-A N54 NUDE). The lS—A assertions
`serve several purposes. They control the matches of restricted variables and they enable EL to
`find all the nodes in the circuit, which is necessary for deciding where to put a symbolic unknown
`when one is needed.
`
`Most devices -have parameters; for example, a resistor has a resistance and a transistor
`has a polarity. These parameter's values are recorded, if known, by facts like
`(a (RESISTANCE R1) 1888.8) , which says that Rl’s resistance is I000 Ohms. They do not have
`to be specified, and EL can be "back-driven" to deduce them if enough voltages and currents are
`known. An example of this use of EL to aid the choice of device parameters is given in the
`appendix.
`
`‘The connections of the circuit are described by assertions like (CONNECT N54 (#1 R1) ) .
`
`each naming a single node and a single device terminal. These assertions need never be entered
`by an EL user, however, because we supply a'special input format for conveniently defining
`devices and wiring them up into circuits (see Appendix).
`Each type of device has conventional names for its terminals. For example, a resistor's
`terminals are known as #1 and #2: a transistor's are called ‘E, B and C. The conventional
`
`terminal names have to be used because they are the ones that the laws for the device know about.
`It would be easy to wire a resistor up by its #3 and #4 terminals, but the EL law embodying Ohm’s
`Law would not know about them.
`
`The knowledge EL accumulates during the analysis of a circuit involves mostly the
`
`values of the voltage at or the current through particular device terminals. They are represented
`
`by assertions such as (= (VOLTAGE (#1 R1)) 18.8). The values of symbolic unknowns, when
`learned, are stored in the form (VALUE X15 15.4) .
`
`Perhaps the simplest circuit rules are those, such as Ohm’s law, which can be represented
`by algebraic equations.
`In ARS such a law can be written very simply:
`
`Page 12 of 69
`
`FORD 1318
`
`

`
`Stal (man 8- Sussman
`
`12
`
`Analgsis
`
`(LAN DC-OHM ASAP ((R RESISTOR) V1 V2 I RES)
`(l
`
`((= (VOLTAGE (#1 !?Rl)
`
`!>V1l
`
`(-
`
`(VOLTAGE (#2 !?Rl)
`
`!>V2l-
`
`(= (CURRENT (#1 !?Rl)
`
`!>ll
`
`(u (RES-ISTANCE !?Rl
`
`!>RESl)
`
`(EQUATION ' (&- V1 V2)
`
`’(&* RES ll RH
`
`This is the EL law that implements Ohm's law. Like all EL laws, it has an arbitrary
`name, a set of slots or antecedent patterns to control its invocation. and a body which in this case
`consists of an algebraic equation. The name, chosen by us for mnemonic significance, is DC—OHl1.
`ASAP indicates its invocation priority, which is normal. as it is for all laws that are simply equations
`between circuit parameters. DC—OHl1 declares the local variables V1. V2.
`1 and RES to hold the
`two terminal voltages, the current. and the resistance value of the resistor.
`In addition, the type-
`restricted local variable R is used for the resistor about which the deduction will be made. The
`long list beginning with (= (VOLTAGE
`contains the demon's trigger slots. Their purpose is
`to provide patterns to direct the invocation or triggering of the demon, and to gather the
`information needed in applying Ohm's law once the demon is invoked.
`The ARS antecedent reasoning mechanism will signal OC—OHl1 whenever a fact is asserted
`that matches any of OC—OHl1's trigger slots. OC-OHH itself then automatically checks all of its trigger
`slots to see which ones are instantiated and which ones are not. That information is passed to the
`function EOUATION, whose job is to deduce whatever it can from the equation it is given.
`If one
`of the terms in the equation (I , V1, V2. and RES,
`in this case) is unknown. EQUATION can
`deduce it from the others.
`If all the terms are known, EOUATION checks that they actually satisfy
`the equation, and if any of them is an algebraic expression involving symbolic variables, EOUATION
`can solve for one of them. Whenever EOUATION asserts a conclusion. it automatically records the
`instantiations of the trigger slots as the antecedents of the conclusion.
`Notice the (l before the list of trigger slots in OC-OHM. That is the list of mandatory
`§l_gt_s, of which in this case there are none. Mandatory slots are just like trigger slots except that
`the law is not processed unless all of them are instantiated. OC-OHl1's slots are not mandatory. since
`if any single one is missing OC—OHl1 can accomplish something by deducing a value for it.
`Mandatory slots are useful when a law is contingent on some fact. For example, different laws
`apply to conducting transistors and cut-off transistors. EL represents the knowlege that a transistor
`is cut off with an assertion such as
`
`(OETERN-INEO (MODE O1) CUTOFF)
`
`When a transistor is cut off, no current flows into any of its terminals. One law, OC—BJT—CUTOFF—
`TC. enforces the absence of collector current:
`
`(LAN OC—BJT-CUTOFF-(C ASAP ((0 BJT)
`
`IC)
`
`((DETERl1INEO (l‘1OOE l?O) CUTOFFH
`
`((= (CURRENT (C !?Ol)
`
`!>ICll
`
`(EOUATION ‘TC 8.0 0))
`
`Page 13 of 69
`
`FORD 1318
`
`

`
`Stal lman 8. Sussman
`
`13
`
`Anatgsis
`
`If that is
`This law has a mandatory slot requiring that the transistor in question be cut off.
`known, the law will be applied and will deduce that the collector current is zero.
`If that is not
`known, the law will never be applied. Note that the slot that detects a known value of the collector
`current is not a mandatory slot. and its only function is to make sure that such a known value will
`be noticed by the law and checked for consistency.
`
`Page 14 of 69
`
`FORD 1318
`
`

`
`Stal Iman 8. Sussman
`
`14
`
`Analysis
`
`The Method of Assumed States
`
`The propagation method can be extended to any devices with laws that are invertible:
`
`if
`
`one terminal voltage or current is in fact fixed when others are given, then an algebraic expression
`
`for it in terms of those others may be needed in the course of propagation. Moreover, the
`expression must be "tractable". in the sense that the (human or mechanical) algebraic manipulation
`
`system may need to substitute in it, simplify it, or even solve it for unknowns appearing in it. in
`order to carry out the solution. For example, handling a diode is too complicated, since it would
`create the need to solve exponential equations. But even an "ideal diode" - a piecewise-linear
`
`approximation to a real diode - is too complicated to be handled symbolically as fluently as is
`necessary.
`It would introduce conditionals and "max" and "min" functions into the expressions. and
`they are not invertible.
`'
`But if the algebraic manipulation technology can't handle the device's laws as a whole.
`
`stronger methods of reasoning can break them down. Electrical engineering has a method known
`as the "method of assumed states". which is applicable to piecewise-linear devices such as ideal
`It involves making an assumption about which linear region the device is operating in (for
`a diode, whether it is "on" or "off"). This makes the conditionals simplify away, leaving tractable
`
`algebraic expressions to which propagation of constraints applies. Afterwards, it is necessary to
`
`check that the assumed states are consistent with the voltages and currents that have been
`determined.
`
`For an example of such reasoning, consider the diode and resistor in series: Assuming
`
`the diode to be nonconducting, we would deduce that there is zero current flowing. and that the
`
`voltage at the midpoint equals e. Since e is positive. that contradicts the conditions necessary for
`
`the diode to be off, as we assumed. On the other hand, if we assume that the diode is conducting.
`
`we deduce that the voltage at the midpoint is zero, and can then determine the amount of current.
`
`The current is flowing downward through the resistor and diode. which is consistent with the
`
`assumption that the diode is conducting.
`
`When this method is mechanized, it is necessary to cycle through all of the possible states
`(linear regions) of the device, testing each one for consistency with thevoltages and currents that
`follow from it. When there are several complicated devices, it is necessary to consider all
`combinations of all different states for each device. This causes an exponential explosion of the
`
`number of states of the system that must be investigated.
`
`Page 15 of 69
`
`FORD 1318
`
`

`
`Stal Iman & Sussman
`
`15
`
`Analgsis
`
`For example, this circuit
`
`‘
`
`+ Vac»
`
`has three transistors.
`
`If the transistor model admits three states, active, cutoff and saturated, then
`
`there are, at first glance, 3-.:=3=:=3 or 27 different triples of states that must be considered, of which
`only one (all three transistors active) is self-consistent. But actually, the states of the transistors are
`
`the stages ar_e coupled only for AC signals and have-no effect on each
`completely independent;
`other's bias conditions. Knowing this, we can find the correct state for each transistor separately.
`giving only 3+3+3 or 9 assumptions to be tested. Such situations are very frequent, and their
`‘
`detection is an effective way of reducing the work entailed by the combinatorial search for the
`COITECI states.
`
`Page 16 of 69
`
`FORD 1318
`
`

`
`Stal lman G Sussman
`
`18
`
`.
`
`Analgsis
`
`Making Choices
`
`Using the method of assumed states requires the ability to make choices, and to handle
`contradictions by making new choices. These abilities are built into ARS, but the conditions for
`the detection of a contradiction are a matter of expert electrical knowlege, contained in EL laws.
`An equation law detects a contradiction if it sees that the equation is not satisfied by the known
`values of the quantities in it.
`However, the method of assumed states carries another sort of knowlege, of the
`boundaries of the different operating regions of piecewise-linear devices.
`I-IL has special laws
`known as monitor laws which check that a device is in fact in an environment consistent with the
`state assumed for it. The conditions tested by monitor laws are often inequalities, which are not as
`conducive to symbolic manipulation as equations. ARS's symbolic’ algebra routines are helpless
`with them, so monitor laws can't do their job unless numerical values are known for all the
`parameters entering into the inequality.
`_
`When the operating region of a nonlinear device is known, that knowledge is represented
`by a DETERMINED assertion, such as (DETERMINED (MODE O1) CUTOFF) . The general form is
`DETERMINED, followed by the "question", followed by the "answer". Such knowledge might have
`been deduced (such as when we first learn that a transistor’: emitter current is zero, and then
`deduce that it must be cut off), or it might be the result of an arbitrary choice.
`In the latter case.
`the choice itself is represented by a similar CHOICE assertion:
`(CHOICE (MODE O1) CUTOFF) ,
`from which we pretend that the DETERMINED assertion was "deduced". The reason for having the
`two different assertions is that all the transistor laws that depend on the transistor's state can look
`for the DETERMINED, and thus work no matter how the known state was arrived at, while the
`backtracking mechanism can look for the CHOICE, and avoid trying to choose other answers for a
`question whose answer is not in doubt.
`In fact, for the sake of efficiency, we have lumped together the state conditions not by
`state but by the circuit variable they test. Here is the monitor that checks transistors’ collector
`currents for consistency with whatever state is assumed.
`
`(BE-DROP NUMBERII
`(IC NUMBER)
`(MONITOR—LAU IC—MONITOR—BJT HIPRI—ASAP ((0 BJTI
`((= (CURRENT (C l?O)l
`l>IC)
`(= (BE-DROP !?O)
`!>BE—DROPll
`(I
`
`(COND ((APPROX IC 8.8)
`(OBSERVE “(DETERMINED (MODE ,0) CUTOFF) ANTECEDENTSII
`((< (&x IC BE-DROP) 8.0)
`(CONTRADICTION DEMON ANTECEDENTS OI)
`(T (ASSERT—NOOOOO "(MODE ,0)
`‘CUTOFF ANTECEOENTS NILIIII
`
`It is called a MONITOR—LAlJ instead of just a LAN so that it will insist on having numerical values
`for the local variables declared to need them, IC (the collector current) and BE-DROP (whose sign
`indicates the polarity of the transistor). A zero collector current is consistent with only one state,
`CUTOFF. The function OBSERVE reports a contradiction to ARS if the transistor is in any other
`In addition, as a timesaving measure, if the transistor's state has not at the moment been
`chosen, OBSERVE chooses CUTOFF since it is the only consistent choice.
`If IC and BE-DROP have
`
`Page 17 of 69
`
`FORD 1318
`
`

`
`Stal lman & Sussrnan
`
`17
`
`Analgsis
`
`' opposite signs, the collector current is flowing backwards through the transistor, which is
`impossible in any state;
`in that case, a contradiction is reported to ARS for processing. Otherwise.
`there is a physically possible, nonzero collector current, which is consistent with any state except
`CUTUFF. The function ASSERT—NOGDOD reports that to ARS. causing a contradiction if an
`assumpti