Combining Discrete and Continuous Process Models

COMBINING DISCRETE AND CONTINUOUS PROCESS MODELS

Daniel S. Weld

Artificial Intelligence Laboratory Massachusetts Institute of Technology Cambridge, Massachusetts 02139

which dP.!ine the action's cffec l on the state by an abrurt change. Qualitative Process Theory [7] , on the other hand , employs continuous process models, in which actions take time :tnd gradu:tlly change the value of quantities such as the level of fluid in a con tainer.

ABSTRACT

Two notions of process have been used in programs that reason about change: discrete models, which represent changes as instantaneous, and continuous models, which represent changes as processes that act gradually over time. We describe a technique calleLi aggregation which unilies the two types of models and allows both to be used when performing qualitative simulation.

Aggregation is a technique for recognizing cycles of processes and generating a continuous process that is equivalent to each cycle. A qualitative simul ator may start prediction with a simple discrete model and use aggregation to generate a continuous process model when discrete simulation bogs down in a cycle. Ag\Jregation thereby allows a simulator to switch back and forth between different types of models depending on which type is most expedient.

To test these ideas, we have written a program, PEPTIDE, wh ich performs qualitative simulation in the domain of molecular genetics. The fl exibi lity of PEPTIDE's aggregator allows the program to detect cycles wi thin cycles and predict the behavior of complex situations.

I INTRODUCTION

1\ number of AI programs perform some type of qualitative sirnul :ttion ·· they predict the future behavior of a sy!;tem in rluJ!itat ivc terms. Why is this an interesting problem? Any program which does planning or problem solving, needs to predict the effects of proposed actions; qualitative simulation provides a useful descrirtion since it removes often irrelevant numeric detail. Qualitat i·Je simulation is also useful when generating explanations, especi:1lly when describing the mechanism of a complex device [2, 12, 6, 1, 13, 15]. Finally, qualitative simulation is the only way to predict the behavior of the many systems which are incompletely speci fied.

To simulate a system, a program needs to represent the processes that cause change. Two fundamentally different quulitative models of change have been developed: discrete and continuous process models. STRIPS [5] illustrates a discrete model, in which actions are atomic; eaci1 action has add and delete lists In this paper we discuss the f:lctors that make a domain well suited to using ei ther a discrete or cont inuous process model, and we present a new technique, a,9greg:1 tion, that c:tn be used to unify the two models of change... The c:ssen tial motivation belrind aggregation is that processes often repeat .. consider the cycles of an internal combustion engine. When reasoning about repeatit tg cycles of processes. it is frequently useful to eliminate irrelevan t detail by considering tire whole cycle as a sin(lle. more abstract process. This is what an aggreg:ttor does: it recognizes cycles of discrete and continuous processes, and it gener:ttes a continuous process abstracti on of the cycle. A program called PEPTIDE l1as been written to test this idea in the domain of mol ecular genetics. Implemented in Zetalisp on a Symbol ics 3600, PEPTIDE has run a dozen e:<amples including the one in this paper and several t11 at am considerably more complex [14].

lhio mport describes research done at the Artificial lntcllia~nce Laboratory of the Mas~ilchusetts Institute of Technolo3y. Support for the laboratory's Arfi licial lnt~'toyenco:; re3e3rch is provided in part by the Advanced flcsearch Projects A~ency ct the Department of Defense under Olfrce of Naval Research contract N00011·75· C·OG43 and the Office of NavAl Research urouer contract number N0014·80-C·0505.

II REPRESENTATION

The operation of any simu lator is crucially dependent on the represen tations used to moclel quanti ties of interest and tile processes which cause change. We describe our assumptions about these representations below.

The system parameters that the simulator models are called quantities, We distinguish between two types of quanti ties: linear and nominal. Linear quantities have an <>Ssociatecl total order wh iie nominal quantities represent categories with no internal structure. For example, the charge of a ·battery and the strengt11 of tile curren t through a circui t could be model;:)[] with a linear quontity, but the state of a switch in the circuit might be better represented by a nominal quantity with two possible values: open and closed.

We assume that time is composed of both instants and intervals. Instants a!·e infinitesimal , whi le intervals are extended. Betwc:en any two non·overlapping intervals lie one or more instants. Tile distinction between instants and intervals allows us to classify types of change. If a change is be::;t considered as occuring in an instant, we model it with a discrete p rocess. If the change occurs over an interval, we use a continuous process.

It should be emphasiLt>d tlrat we clo not attempt to extend either nroclcl. Considerable work is already IJc:iroq clone on th~t front. [3, 4, 8, I 1. 16].

Discrete processes are appropri ate when modeling changes in nominal quantities (e.g. the fli p of a circuit's switch) and abrupt changes in linear quantities (e.g. the change in the current through a circui t following the switch's flip). It is often useful to as~ume that discrete processes are atomic·· they either happen full y or not at all. Atomicity is useful when modeling situations where mutually exclusive actions are possible [9]. Situation -action rules are an efficient means for representing discrete processes.

Continuous processes, on the other hand, are appropriate when modeling gradual, strictly-monotonic changes in linear quanti ties. It is importan t to note that con tinuous processes c::m't affect nominal quantities because there is no way to monotonically change a quantity with no inherent order. Cont inuous processes are ideal for describing the change that occurs when a battery is connected through a resistor to ground. We define continuous processes by a set of preconditions and a set of influences. The precondi tions are predicates on quantities that tell when the process is active, i.e. when the influences are en forced. The influences say how various quantities will be modified by the activity of the process. The e!ectric current process wou ld be active whenever the switch was closed and the battery's voltage was greater than zero. The process would have two influences: a decrease in the charge in the baitery and an increase in the temperature of the resistor.

The power of continuous models comes from a technique called limit analysis [8] . When a simulator performs limit analysis, it takes influences of a continuous process and predicts when these influences wi ll cJuse tt1e preconditions to be violated or the preconditions of ancther, inactive process to become satisfied. Tt1us, limit analysis predicts that the electric current process wifl be active until the b<~ttery's voltage drops to zero.

Ill AN EXAMPLE OF AGGREGATION

With two fundamentally different ways of thinking about how a system behaves, an important problem is how to choose which one to use at a given time. Since discrete processes are simpler, we rnnl<e them t11e default. We only use· continuous processes when the simulator needs the power of limit analysis, i.e. when there are repeating cycles.

The system starts by simulating the effects of discrete processes until it recognizes a cycle. Then the aggregator produces a continuous process with the same preconditions as the cycle's, and with influences equivalent to the net result of a :;ingle iterati on of the cycle. At this point the continuous simulat·Jr can use limit analysis to predict tile eventual result wi thout laboriously simulating each ih~rntion of the loop.

To make this clear, we present a simple example in the domain of molecular genetics.

A. ~xanll?le Definition

Consider a container with two individuals, E and DNA."' DNA i::, a long chain, and E has a large cleft (Figure 1).

For clarity of presentation, the example is described graphically. The appendix contains the actual PEPTIDE description.

DNA

Figure 1: Initial Situation

We define two discrete processes:

· BIND

If there is an E whose cleft is empty and there is a DNA with nothing bound to its right end, then the E will bind the right end of the DNA.

· SNARF

If there is an E bound to the right end of a DNA, then the E will digest the rightmost segment of the DNA. The result will have E floating free, and the length of DNA one shorter than before.

B. Di sc rete Simulation

Initially the process BIND is active, and SNARF is not. PEPTIDE creates an instance of BIND that is associated with E and DNA and simulates it. The resulting si tuation is shown in Figure 2.

--8

Then the process SNARF is active; an instance is created and simulated. Figure 3 shows the result.

Next the process BIND is again active, but before the discrete simulator can predict its effects, the aggregator recognizes a cycle.

C. rule Recognition

The notion of a repeating cycle of processes implies that the process instances in each iteration are "the same" in some sense. For the aggregator to recognize cycles, it must be able to detect when two processes are the same. But sameness is not equivalent to equality, as the example above shows. The two instances of the BIND process are not equal since they involve DNA chains of dilfering length, but the processes are clearly the same in an important sense.

We define two instances of a process to be the same if each of the individuals associated with the two instances are the same. Two individuals are the same if all their nominal quantities are equal; their linear quantities can be different. Thus the two instances of BIND are seen to be the same because the only difference is in the

E

length of DNA, and length is a linear quantity. Ignoring differences in linear quantities makes sense when looking for cycles, because we wish to consider cycles as continuous processes which cause changes in linear quantities but not in nominal quantities. For the domain of molecular genetics, there are two other linear quanties (besides the length of a chain) which are important: the number of identical molecules in a group, and the position of a binder on a chain.

Once two processes instances have been recognized to be the sarne, PEPTIDE searchs through a history record [10] of the past simulation to determine exactly which processes are in the cycle [14]. In the case of our example, this is quite easy; the cycle is simply (BIND SNARF).

D. Generation of a Continuous Process

A continuous process consists of a set of preconditions and a set of influences. First, the aggregator analyzes one iteration of the cycle to determine the influences. For the simple (BIND SNARF) cycle, it is easy to determine that there is only one influence: a decrease in the length of DNA. Complex cycles, however, can require more sophisticated analysis (e.g. resolution of contradictory influences (14]).

To generate the continuous process' preconditions, the aggregator simply combines from each of the discrete processes in the cycle the preconditions that refer to linear quantities; nominal preconditions cancel out. For our example, this results in only two preconditions:

• There must be at least one free DNA.
• There must be at least one free E.

E. Continuous Simulation

Finally, the continuous simulator can predict the eventual result of the repeating cycle by performing limit analysis. Since PEPTIDE knows that if the length of a chain is ZERO the individual doesn't exist, it is easy for the continuous simulator to predict that eventually DNA will be gone and only E will remain. At this point the simulator summarizes the net effect of the continuous process and adds it to the history structure with the name CP1 . Then PEPTIDE switches back to discrete mode. Since DNA is gone, no processes are active; thus simulation is complete.

F. Cycles Within Cycles

If we had specified that initially there were many DNA individuals in the container, then there would still be DNAs present and BIND would be active. But before it could be simulated discretely, the aggregator detects that this BIND is the same as the first, since the only difference between the initial situation and the current one is a change in the linear quantity, the number of identical DNA molecules. A search of the history structure reveils the following cycle: (BIND SNARF CP1 ). The influence of this new cycle is a decrease in the number of DNAs. Continuous simulation of this cycle again results in the conclusion that eventually all the DNAs will be eaten.

The occurrence of nested cycles in this simple example demonstrates their ubiquity; it is essential that an aggregator be capable of handling them. The key point is that when aggregating, PEPTIDE considers each previous continuous processes (i.e. whole cycles of processes) as a single discrete process. Without this ability the aggregator could not use the information from previous aggregations when constructing the continuous process for the outside cycle.

IV LIMITATIONS AND FUTURE WORK

Although aggregation is a powerful technique, it can 't detect all cycles, and should be tested on more domains.

A. Failure to Recognize all Cycles

As explained above, the aggregator recognizes cycles by ignoring the value of linear quantities. Although this method works in many cases, it fails when new linear quantities are generated dynamically.

We have not discovered any cases where this happens naturally in the domain of molecular genetics, but we can create artificial pathological situations. This is unsurprising because PEPTIDE's representation language is powerful enough to specify an arbitrary type 0 (unrestricted) grammar. Since this implies that we could use the discrete model to build a Turing machine, it becomes quite clear why PEPTIDE can't always decide whether simulation should halt. ·

B. Qualitative Simulation of Ott1er Domains

For aggregation to be useful as a qualitative simulation technique, two conditions must hold for the domain in question:

• It must be possible to characterize interesting parts of the domain by continuous processes and linear quantities.
• Some processes must repeat their actions cyclically. These repetitious actions can be either discrete, continuous or both.

We suspect that aggregation could be useful in many other domains. Digital electronics is a natural domain in which aggregation could be applied. There are many devices at different levels of detail whose states are usefully considered as linear quantities: counters, LIFO queues, and processor pipelines. Furthermore, many processes repeat cyclicly. Detailed paper simulations suggest that aggregation could be usc: fully applied to this domain.

Another potentially fruitful domain is that of complex machinery. Internal combustion engines have many repetitious processes: the strokes of the pistons, the movements of valves, the rotation of gears and differentials. These cycles affect numerous interesting linear quantities. For example, the friction from each piston's stroke increases the engine temperature, and the spurt of fuel-injected gas lowers the level in the tank and increases it in the combustion chamber.

We feel that it is very important to test the utility of aggregation for prediction, instruction, and diagnosis in another domain.

V CONCLUSIONS

Both discrete and continuous process models have their strengths. Discrete process models are simple, and can model changes in nominal as well as linear quantities. Continuous process models facilitate limit analysis of gradual changes in linear quantities. We described a technique, called aagregation, which allows a qualitative simulator to use either model depending on which best fits the situation.

The aggregator recognizes cycles of processes by ignoring the values of linear quantities and generates a continuous process abstraction of the cycle by deducing the net influences of one iteration of the cycle. A test program, PEPTIDE, has used aggregation to solve a dozen problems in the domain of molecular genetics. The flexibility of PEPTIDE's aggregator allows the program to predict the behavior of complex systems by detecting cycles nested within other cycles.

ACKNOWLEDGMENTS

I owe many thanks to my advisor, Randy Davis; to Ken Forbus, Dave Chapman , and Brian Williams who contributed greatly; to Bruce Donald for insightful comments on a draft; and to the many other people who form the stimulating environment of the MIT AI Lab.

APPENDIX

The actual PEPTIDE code for the example (with only formatting changes) is displayed in Figure 4. Capitalized words are keywords defined by PEPTIDE.

(DEF-EXAMPLE exonuclease (DEF-INDIVIDUAL dna (CHAIN)) (DEF-INDIVIDUAL exonuclease (BINDER (cleft))) (DEF-PROCESS bind (IF (AT-END? ?x RIGHT dna) (BIND oxonuclease>cleft dna>?x))) (DEF-PROCESS snarf (IF (A~D (BOUND? exonuclease>cleft dna>?x) (AT-END? ?x RIGHT dna)) (REACT exonuclease>cloft dna>?x (*DECR-CHAIN right)))) (ASSERT (COMPLEMENTARY exonucloase>cleft dna>?a)) (ASSERT (EQ ONE (NUMBER-OF dna))) (ASSERT (EQ ONE (MUMBER-OF exonuclease))))

Figure 4: PEPTIDE Code for the Example