Introducing Actions into Qualitative Simulation
Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. Knowledge Representation. Pages 1273-1277.
© 1989 International Joint Conferences on Artificial Intelligence
Abstract
Many potential uses of qualitative physics, such as robot planning and intelligent computeraided en~ineering, require integrating physics with actiOns taken by agents. Here we show how to extend qualitative simulation to include the effects of actions, resultin~ in action-augmented envi&ionmenb. The actiOnaugmented envisionment incorporates both the effects of an agent's actions and what may happen in the physical world whether or not an agent does something. Consequently, it provides a richer basis for planning and for reasoning about procedures than any previous representation. This paper defines actionaugmented envisionments and presents an algorithm for directly computing them. The properties of the algorithm are analyzed along with its suitability for robot planning and reasoning about engineering procedures. We describe results $enerated by a working imJ?lementation and diScuss potential extensions, mcluding incremental algorithms.
- Abbott, K. "Robust operative diagnosis as problem- solving in a hypothesis space", Proceedings of AAAI- 88, August, 1988.
- de Kleer, J. "An assumption-based truth mainte- nance system" Artificial Intelligence, 28, 1986.
- Decoste, D. "Dynamic across-time measurement in- terpretation" in preparation, 1989
- Falkenhainer, B. and Forbus, K. "Setting up large- scale qualitative models", Proceedings of AAAI-88, August, 1988.
- Forbus, K. "Qualitative process theory", Artificial Intelligence, 24, 1984.
- Forbus, K. "The problem of existence", Proceedings of the Cognitive Science Society, 1985.
- Forbus, K. "The Qualitative Process Engine", Tech- nical Report No. UIUCDCS-R-86-1288, December, 1986.
- Forbus, K. "The logic of occurrence", Proceedings of IJCAI-87, August, 1987. 1278 Knowledge Representation
- Forbus, K. "Introducing actions into qualitative sim- ulation", Technical Report No. UIUCDCS-R-88-1452, August, 1988.
- Hogge, J. "Compiling plan operators from domains expressed in Qualitative Process theory", Proceedings of AAAI-87, July, 1987. .
- Hogge, J. "The compilation of planning operators from Qualitative Process theory models", Technical Report No. UIUCDCS-R-87-1368, September, 1987.
- Hollan, J ., Hutchins, E., and Weitzman, L., "STEAMER: An interactive inspectable simulation- based training system", AI Magazine, Summer, 1984.
- Kuipers, B. and Berleant, D. "Using incomplete quantitative knowledge in qualitative reasoning" Pro- ceedings of AAAI-88, August, 1988. •
- Malin, J. and Lance, N. "An expert system for fault management and automatic shutdown avoidance in a regenerative life support system" Proc. First Annual Workshop on Robotics and Expert Systems, Instru- ment Society of America, June, 1985.
- Malin, J. and Harris, R. "CONFIG: Qualitative simulation tool for analyzing behavior of engineered devices", First annual workshop on Space Operations Automation and Robotics, Houston, Texas, August, 1987. [161
- Schmolze, J. "Physics for robots", Proceedings of AAAI-86, August, 1986.
- Winslett, M. "Reasoning about action using a pos- sible models approach", Proceedings of AAAI-88, Au- gust, 1988.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Plans involving the physical world must take into ac count the indirect consequences of actions. A robot mak ing tea, for instance, must exploit physical processes s~ch as liquid flow and boiling to carry out its plan. An In telligent CAD tool analyzing the safety of a power plant must be able to ascertain how the processes m the plant are affected by the act~ons of the pl~nt'~ operat<?rs. ~et little has been done to mtegrate qualitative physics with actions. For example, [16] illustrates how some simple qualitative physics notions might be used in robot plans, but provides neither a domain-indepenent theory nor al gorithms.
Moving qualitative physics into a planner is one ap proach. Hogge developed a domain compiler [10] that takes domain models expressed in Qualitative Process (QP) theory [5] and produces rules and operators for a temforal planner. Given a goal like "Increase .the water leve in this container", the planner can use Its knowl edge of actions, col!lbined with physics knowl~dge de rived from the domam model}. to figure out that It should place the container under a taucet and turn on the tap, thus allowing liquid to flow.
So far, tractable compilation has required undesirable simplifications 1 . Additional run-time inference could in principle overcome this (and other) problems, but ef ficiency plummets[ll]. For example, Hogge's planner could figure out how to get water into an empty pot and how to make water in a full pot boil, but without run time transitivity rules it could not compose th~se plans to boil water starting with an empty_p'?t. ~ddmg_ those rules caused it to exceed resource lim1tat10ns without finding a solution. Wh~e still promising, the _di~cult~ of reconstructing the entue framework of qualitative sim ulation into rules suitable for efficient planning makes exploring alternatives worthwhile. . .
Here we explore the dual approach: Movmg actiOns into the physics. The next sectiOn defines a new repre sentation the action-augmented envi&ionment (or AE), which in~ludes the effects of actions in the qualitative simulation. Section 3 shows how to compute AE~, and Section 4 examines the correctness and compleXIty of the algorithm, including its potential suitab~ty _for tw.o tasks: robot planning and proce~ure gen.eration m e~gi neered systems. Section 5 describes an ImplementatiOn and some examples. Finally, we describe our plans for future work.
2 Action-Augmented Envisionments
Informally, a qualitative '.tate describes a cl~ss of partic ular behaviors for a physical system. ~ons~der a pot ?f water sitting on a stove. If the stove IS switched on, m one state the water might be heating up, and in another state it might be boilin~. Qualitative states are li~ked by transition& which describe how these gross behaviOrs can change. The two states above, for instance, are .link~d by a transition correspond~ng .to t~e wat~r reachi_ng Its boiling temperature. Qualitative. s.Imulation consists of computing these states and transitiOns.
Every qualitative simulation leaves some "background information" unchanged. We do not, for example, con sider what the world would look like if the stove suddenly vanished. In fact, qualitative simulations focus on just those changes predictable by the physics used.
The complete set of states and transitions for some fixed set of background assumptions is the envi&ionment for that scenario. (We use the conventions of [8] as needed to describe envisionments and their aspects.) To capture the effects of actions, we must allow at least Figure 1: Actions can interact with processes Heat flow requires a path capable of transmitting heat. These axioms for BE1T-1LIGHED indicate how changes in location indirectly affect whether or not heat flow occurs.
1 For instance the compiler asswnes that if you influence a quantity in a 'particular direction it will actually change that way. Thus the planner could propose that one bail out a sinking ocean liner with a teaspoon.
Proceaa Beat-Flov(?arc,?dat,?path) Individuals: ?arc, Quantity(heat(?arc)) ?dat, Quantity(heat(?dat)) ?path, Beat-Path(?path,?arc,?dat) Preconditions: Beat-1ligned(?path) Quantity Conditions: 1[T(?arc)] > 1[T(?dat)] Relations: Quantity(flov-rate) flow-rate = T(?arc) - T(?dat) Influences: I+(heat(?dat),1[flov-rate]) I-(heat(?arc),1[flov-rate]) V ?c,?a Contained-Stuff(?c) A Location(Container(?c))=On(?a) => Simple-Beat-Path(BPath(?a,?c),?a,?c) V ?c Contained-Stuff(?c) => Beat-1ligned(?c) Knob(Stove)=OH => Beat-1ligned(Stove) V ?x,?y,?path Simple-Beat-Path(?path,?x,?y) A Beat-1ligned(?x) A Beat-1ligned(?y) => Beat-1ligned(?path)
some of the background assumptions to vary. For exam ple, switching the stove on will initiate a heat flow, and taking the pot off the stove will break thermal contact and thus end the heat flow. This extension requires the qualitative physics to be sensitive to changes in back ground assumptions. We use Qualitative Process theory because it provides two mechanisms for explicitly rep resenting such dependencies. First, views and processes are quantified, in that they explicitly define the kinds of objects they apply to. In Figure 1, for example, heat flow can occur between two objects with thermal prop erties connected by a heat path. Second, explicit pre conditions and consequences not involving dynamics are allowed (e.g., the stove's burner can be modeled as a heat path which operates only when Knob(Stove)=OH).
Let 'P be the set of background assumptions for a sce nario, with 'P 1 ~ 'P the fized auumptions of 'P. In pre vious qualitative physics systems 'P = 'Pt. Introducing actions means there will be a subset 'Pm, the manipulable auumptions of 'P 1 corresponding to those aspects which can be changed duectly or indirectly by an action. Now we can begin to characterize the action-augmented envi sionment A£ for a scenario. Let 'P~ be the set of consis tent combinations of 'Pm. If we denote the envisionment under a set of background assumptions 'P1 as £('P1), then States(A£) = UpE'P~ States(£(p U 'Pt )). The dynam
ical state transitions from each state S1 E States(A£) are simply the union of all transitions from the compo nent envisionments. To complete the definition of A£ we must extend the set of transitions to include all oc
currences of actions.
We define transitions due to actions by analogy with dynamical state transitions. In QP theory state tran sitions are represented as instances of limit hypotheses concerning changes in ordinal information. For instance, the hypothesis that the temperature of the water in the pot might reach its boiling temperature would be appli cable to any situation where the water is being heated, regardless of the heat source involved. Similarlr, we call an action hypothesis the conjecture that a particular action occurs. For example, the conjecture that the action Move-to(Potl,On(Stove)) is executed is an action hy pothesis. This hypothesis is applicable to a variety of states, namely whenever Potl is not On(Stove). The rest of this section defines the constraints which deter mine valid action hypotheses and the transitions they cause.
We make two restrictions for simplicity. First, at most one action can be taken at a time (single action auump tion). Since the vocabulary of operators could include compound operations, this assumption loses no general ity. Second, actions do not coincide with dynamical state transitions (separation auumption). This assumption forbids actions occuring in instantaneous states, which are both unlikely and hard to manage. In essense, it re quires that actions occur quickly relative to dynamical changes. This may restrict the expressibility of .A£s. Of ten this assumption is reasonable; for instance, a kettle's water doesn't cool apJ>!eciably while moving from a stove to a nearby tea_pot. When actions do take appreciable time, such as slowly opening a valve in a heating sys tem, the action could be modeled as a sequence of short actions or reified as a continuous change in the physics triggered by an initial brief action.
Consider an action hypothesis A?t as a partial function whose domain and range are 'P~. Let 'Pm, = A?t('Pm,)· Suppose S1 , S2 are qualitative states such that 'Pm, holds for S1 · The following restrictions must be satisfied for S2 to be a possible outcome of A?t occuring at S1: (1) Consistency: 'Pm, holds in S2 · (2) Continuity: When possible, no violations of continuity occur between S1 and S2 · (3) Closeneu: No state also considered to be a possible result of A?t occuring at S1 has more in common with sl than s2 does.
The consistency restriction is obvious. The continu ity and closeness restrictions express the desiderata that only the direct and indirect consequences of an action are causally connected to it: nothing else should change as a result. Continuity expresses the constraint that, when possible, continuous parameters change smoothly. Un fortunately, continuity cannot always be satisfied. Sup pose the pressure in a boiler is rising dangerously, and a safety valve is opened to bleed off excess steam. Intu itively, the discontinous action of popping the valve can result in the pressure instantly falling, a discontinuous change 2 · The definition of closeness depends on the de tails of the physics. The next section defines a measure of closeness for QP theory.
3 An algorithm for constructing AEs
The formulation of At's is based on sets of assumptions, so it is useful to describe the algorithm using the termi nology of assumption-based truth maintenance [2]. The Qualitative Process Engine (QPE) [7] uses an ATMS to efficiently generate envisionments for QP theory, and we base our algorithm on it. States are defined by particu lar sets ofassumptions SA= Q,U'P., where Q, is drawn from the set of possible ordinal assumptions and 'P, is drawn from 'P. The set of possible ordmal assumptions and 'P are computed automatically during the instanti ation of the QP model for the structural description of a scenario. Q, initially consists of choices for the relationship for each pair of numbers mentioned in quan tity conditions of view and process instances and other primitives of the QP language (e.g., correspondences and explicit-functions). As ambiguities and newly discovered limit points are uncovered during simulation, Q, is augmented to include choices for them as well. 'P, consists of choices for the preconditions of view and pro cess instances, as well as any choice sets explicitly defined by the domain model (e.g., declaring that any movable object has a Location which can range over the set of places in the scenario).
2 A more detailed model could capture the time it takes for the flow rate out to rise and thus preserve continuity, but always requiring such detail is inappropriate.
| Figure 2: Operators for the kitchen domain defOperator Move-To(?from,?thing,?to) | |
| Individuals: | ?from, Place(?from) ?thing, Mobile(?thing) ?to, Place(?thing) 1\ ?from i= ?to |
| Delete-List: | Location(?thing) = ?from ..., Clear(?from) Clear(?to) |
| ldd-List: | Location(?thing) = ?to ..., Clear(?to) Clear(?from) |
| defOperator Flip(?switch,?from,?to) | |
| Individuals: | ?switch, Switch(?from) ?from, Bas-Setting(?switch,?from) ?to, Bas-Setting(?switch,?to) 1\ ?from i= ?to |
| Delete-List: ldd-List: | ?switch= ?from ?switch = ?to |
The temforal scoping of facts is implicit in their ATMS labe, i.e., Location(Pot1) = On(Stove1) holds in a state exactly when it is implied by the assump tions defining that state. This compact representation of states greatly simplifies algorithms. Actions are repre sented by STRIPS operators (e.g., Figure 2), since they easily satisfy the single action and separation assump tions. We require that all facts mentioned in the add and delete lists of operator instances be assumptions in 'Pm·
Given a domain model, which specifies the particular physical theory to be used, and a scenario, specified by 'P 1, QPE expands the scenario by applying the abstrac tions of the domain model. This creates instances of views, processes, and derived objects (such as "water in the pot"). It is easy to extend this process to include operator instantiation, and to automatically accumulate 'Pm. Since QPE can search variations in 'P, as well as Q, States(A£) is computed via the standard envision ing procedure. Furthermore, since we have the operator instances we can create the set of A?t 's. All that remains is (1) to ascertain when these A?t's might occur and (2) to determilie their effect in each case.
Call the assumptions corresponding to the delete list and add list of an operator instance 4 and A?t, re spectively. To determine if an operator instance o, can apply to a situation St,
- Unless Individuals(O,) are implied by St, fail.
- Let 'P!= ( 'Pm 1 - 4) + A?t· If 'P! is inconsistent, fail.
To determine the effects of an action hypothesis we
must determine if 'P! can be extended into a consis tent situation S2 E States(A£) 3 · Since we already have States(A£), finding the results ofO, on St can be viewed as a filtering problem. The set of predicted outcomes C can be computed by the following algorithm:
- Let Ct = {Si E States(A£) I 'P! ~ Sj}
- Let C2 be the subset of Ct whose members do not violate continuity, when viewed with respect to St. If C2 is empty, C2+- Ct .
- Let c = {Sj E c2 I ·3Sr. E c2 s.t.(l Sr. n s, I > 1 sins, I)}
The first step provides initial candidates by enforc ing consistency, and the second uses the same continuity pruning used by limit analysis in QPE (see [7] for de tails). The final step provides a precise definition for closeness - literally, the number of assumptions shared with the previous situation. For each Sj E C, the set Transitions(A£) is extended to include a transition from S, to Sj, justified by O,.
Typically an action results in a unique next state, but not always. One reason is the ambiguity of qual itative representations. Consider again the boiler with relief valve. Once the relief valve is blown there will be ambiguous influences on the pressure - the flow out through the relief valve will act to decrease it, while the generation of more steam will act to increase it. Con sequently, the pressure could continue to increase, de creaseJ or remam constant. Unless extra knowledge can disambiguate them, each is a legitimate potential conse quence of that action. Other conseq.uences of an action can be underspecified as well. Constder throwing a pair of dice onto a table. We know that each die will stop with a J>articular face up, but we cannot predict in advance which face it will be.
4 Analysis
Our analysis addresses four questions: (1) Is the algo rithm reasonable? (2) What is the complexity of ex plicitly generating A£? (3) Under what circumstances would explicit generation make sense? ( 4) Could A£ be generated incrementally?
4.1 Is the algorithm reasonable?
Proving correctness assumes the existence of a formal standard, and there isn't one for this task. Instead, we show that the algorithm is consistent with two intuitions about causality and action: (1) no extraneous changes occur, and (2) only the minimal necessary changes are predicted.
An extraneous change involves change in some part of the situation that cannot be affected by the action. For instance, if I start my car, then in the absence of any mechanism to the contrary, the stove in my kitchen remains off. In QP theory this lack of connection is expre!i,'ied through p-componentl: Two individuals in distinct p-components cannot affect each other 4 · Sup pose an action affects only individuals in p-components 4lt, ... , 4ln and not 4J,. Now consider the subset of 'P!
3 1ndirect consequences of actions generally cause S1 - 'Pml i= sl -'Pml·
P-components and how they relate to the frame problem are detailed in [5].
relevant to <Pi· Any combination from that subset is consistent with the change. Because the p-components are distinct, combinations relevant to (Pi cannot mteract with the subsets relevant to <Pt. ... ,</> .... However, any re sult state where </Ji changes will have fewer assumptions in common with the previous state than a result state where </Ji does not change, and hence will be filtered out by the closeness criterion.
Defining the minimal consequences of change is dif ficult, as the literature on counterfactuals indicates. There are two natural definitions for this representation: maximal shared auumption6 and maximal shared con6e quence6. Since the set of conseq_uences is generally larger than the set of assumptions, It might be tempting to use it as the basis of closeness instead. However, doing so would violate our intuitions of causality. Consider a large pan of water that rests on two burners, one on and one off. Now turn off the operating burner. Maximiz ing shared assumptions leads to the conclusion that no heat is flowing from the stove, and the water will be gin to cool. Maximizing shared consequences can lead to the conclusion that the other burner becomes on, ex changing one heat flow for another but keeping all the properties of the water intact. Yet this interpretation vi olates our notion of agency, where the cooling water does not. Any particular choice of actions encodes what we think are important, primary facts about the world. In causal terms, facts derived from those changed directl,Y by an action have a secondary status. To satisfy thiS intuition we must maximize shared assumptions and let the consequences fall where they may.
4.2 Complexity
Here we summarize the complexity analysis in [9] . Since the standard envisioning process can compute State6(AE), we ask (1) how costly is the additional step of generating A?ts and their associated transitions and (2) how costly is it to generate State6(AE) relative to a standard envisionment £ (i.e., where 'Pm is empty)? H I State6(AE) I = n, then determining the effects of ac tions is O(n 2 ) · Unfortunately, n can be exponentially larger than State6(c('PJ )); for example, if'Pm consists of pairs of independent propositions p and ·p, the number of states could increase by 2l 'Pm 1- 1 . In other words, the temporal inheritance algorithm itself is cheap, but generating the states in the first place is expensive.
4.3 When would explicit generation make sense?
Explicitly generating a problem space is generally fool hardy and typically impossible, but that is just what envisioning does. The degree of interaction between the operator vocabulary and the rest of the domain model determines how dose worst-case performance is approached. If the operators are irrelevant to the domain model, then I State6(AE) I= I 'P~ I x I States(£) I· But generally interactions exist and thus only a small subset of the cross product may be consistent. A domain with complex dynamical behavior and only a few actions, all tightly coupled, would be the best case.
Reasoning about procedures for engineered systems appears to be just such a task. Consider a power plant (either stationary or on board a ship). Its dynamical state can be complex, and a badly-timed action can re sult in disaster. But the kinds of actions an operator can take are often limited to flipping switches and opening or dosing valves. Since an AE compactly represents the result of executing all possible plans, it could be useful in generating operating procedures and safety analyses. To deal with realistic systems will require the same de composition strategies as traditional engineering. For instance, operating procedures are often generated by combining procedures for subsystems (i.e.; a step in turn ing on a circulation system is aligning one leg of it, which itself is a procedure involving several steps). This sug gests computing AEs for subsystems independently and combining them, using the techniques of [4] to represent system boundaries.
4.4 Incremental generation
Typical "robot planning" domains are the worst kind of task for explicit AE generation, since 'P~ includes each possible location for every moving object, and thus could be huge. Incremental algorithms would be better, and appear both possible and feasible. The AE is just a prob lem space, whose operators are the actions which can be taken plus the set of limit hypotheses. Incremental temporal inheritance algorithms for QP theory exist [6], and could easily be extended to A?ts. The entire panoply of AI search strategies could then potentially be used to generate plans. However, the fact that some transitions will occur whether or not the agent desires them changes the nature of the problem somewhat. One way to view planning in the AE problem space is as playing a game with Nature. The agent controls actions, and Nature controls dynamics. This view is not exact, of course, since Nature is not generally held to have goals 5 and the "players" in this game don't take strict turns. Neverthe less, the metaphor is suggestive. For example, there is a "horizon effect" in this problem space which consists of dynamical changes undoing a state achieved by the agent. To assure that the intended effect of the action is maintained, qualitative simulation can be used to see if either (a) no relevant dynamical transitions occur or (b) they take sufficiently long that the next action can be performed before they occur.
5 An implementation
We have implemented the algorithm described in Section 3, and have successfully tested it on over a half dozen ex amples at this writing. They include several engineering fluid systems, a kitchen scenario 6 , and throwing dice. This section highlights some results from these exam ples.
The kitchen scenario indicates that the worst-case analysis need not be relevant to problems of interest. The system generated 244 situations, with 1054 transi tions between them (78 due to dynamics, the rest due to actions). For this problem, I States(c('PJ )) I = 25, and 'Pm includes 12 binary choice sets and one three-way choice (i.e., the location ofthe pot). Thus the worst case analysis predicts I States( A£) I = 25 x 2 12 x 3 = 307, 200, which is far more than 244. Since robot planning sce narios such as this are potentially the worst cases, these numbers seem reassuring.
5 Although Murphy's Law is tantamount to assuming that Nature is playing to win, i.e., to thwart the agent's goals if possible.
e The figures here provide a sample of the domain model, see [9] for details.
Figure 3: A sample plan from the .A£ Here is a sample plan for boiling water generated by graph search on the kitchen At.
- MOVE-TO(OH(COUNTER1),POT,UNDER(F1UCET1)).
- FLIP(KHOB(F1UCET1),0FF,OH).
- Vait until 1[1HOUNT-OF-IH(V1TER,LIQUID,POT)] = ZERO ----+ >.
- FLIP(KHOB(F1UCET1),0H,OFF).
- MOVE-TO(UNDER(F1UCET1),POT,OH(STOVE1)).
- FLIP(KHOB(STOVE1),0FF,OH).
- Vait until 1[TBOIL(V1TER,POT)] > 1[TEMPER1TURE(C-S(V1TER,LIQUID,POT))] ----+ =·
- Vait until 1[1HOUNT-OF-IH(V1TER,G1S,POT)]
- = ZERO ----+ > . 9. FLIP(KHOB(STOVE1),0H,OFF).
- MOVE-TO(OH(STOVE1),POT,OH(COUNTER1)).
A simple graph-search planner was built to find plans given a start state, goal, and .A£. The kitchen .A£, for ex ample, does indeed contain many correct plans for boil ing water starting with an empty pot (see figure 3), thus solving a problem Hogge's planner could not. Many of the plans are suboptimal (e.g., turning the stove and faucet off and on without moving the pot), and addi tional knowledge about efficiency and safety is needed to prune them.
To ensure that extraneous actions did not occur, two independent two-tank fluid systems were considered in the same scenario. As expected, the predicted effect of every action preserved assumptions concerning p components not affected by that action. The dice exam ple was developed to explore partially specified actions. The model allows a die to be on a table or in a hand with PICKUP moving the die from the table to the hand and TOSS putting it back. The FACE-UP of a die is either 1, ... ,6 (when on the table) or ROLLING, when in the hand. As expected, the algorithm generates six possible outcomes for each toss, each corresponding to a different value of FACE-UP. This example illustrates that the con straint satisfaction techniques used in QPE can be used for some reasoning about actions even in the absense of continuous parameters.
To explore reasoning about engineering procedures, a simple verifier was built which uses .A£s to determine if a procedure can be successfully executed with the de sired effects. It was tested with the simplified shipboard fuel oil service pump system (drawn from STEAMER [12]) depicted in Figure 4. The verifier confirmed that the starting and stoppin~ procedures depicted can, if exe cuted, lead \o the desued results.
6 Discussion
This paper describes a method for integrating quali tative physics with models of action. It defines the action-augmented envi6ionment, which compactly repre sents all predicted changes due to a physics and possible actions within a scenario. The representation is domain independent, in that it can be used for any problem that can be modeled using Qualitative Process theory. An algorithm for explicitly generating .A£s was presented and analyzed, and results from an implementation were summarized.
We believe this idea is an important step towards us ing qualitative physics in plannmg. Such understanding Figure 4: Verifying engineering procedures with .A£s This shipboard system (drawn from STEiMER) pumps fuel oil from a storage sump to the burner in the boiler's furnace. It has been slightly simplified by ignoring gauges and a safety bypass valve.

Starting the pump:
- FLIP(KNOB(SUCTIOH-LIHE),CLOSED,OPEN).
- FLIP(KNOB(DISCB1RGE-LINE),CLOSED,OPEN).
- FLIP(SELECTOR(FOSPUMP),STOP,ST1RT).
- FLIP(HIGH-LOV(FOSPUMP),LOV,HIGH).
- Vait until i[M1I-SPEED(FOSPUMP)]
- FLIP(HIGH-LOV(FOSPUMP),HIGH,LOV).
- > i[SPEED(FOSPUMP)] ----+ =.
Stopping the pump:
- FLIP(SELECTOR(FOSPUMP),ST1RT,STOP).
- Vait until i[SPEED(FOSPUMP)] > ZERO ----+ -.
- FLIP(KNOB(SUCTIOH-LINE),OPEH,CLOSED).
- FLIP(KNOB(DISCB1RGE-LIHE),OPEH,CLOSED).
could lead to important new applications, such as in creased automation of procedure generation and safety analyses. For example, an important problem in training operators of complex systems is teachin~ them what the operating procedures are, and motivatmg these proce dures in terms of the underlying principles of the plant. The ability to check a student's proposed procedure, for instance, could extend the ability of intelli~ent tutoring systems for this problem. Another problem 1s developing monitoring systems that can track system behavior and generate a running explanation of what is happening, to aid in fault management and operative diagnosis [14, 15, 1]. This algorithm is already being used to gener ate experimental knowledge-bases for measurement interpretation [3], so the explanations of system behavior can include the actions of operators. We suspect that for some engineering applications, the cost of explicit gener ation of .A£s may be offset by the increased confidence in the quality of the answer, particularly as we discover how to build multi-grain domain models [4]. However, incremental al~orithms are clearlr possible and may be the most practical for many applications.
Even if .A£s turn out to be infeasible to compute ex plicitly for all but the simplest systems, we expect the :AE representation to be a useful theoretical foundation for understanding plans and procedures involving the physical world. Consider the notion of safety. Suppose a domain model characterizes particular conditions or processes as undesirable or dangerous (e.g., the pressure in a boiler reaching its maximum rating or the level of water in it reaching the bottom). We can call a state
"unsafe" if one of these conditions holds in that state. An .A.EJenerated with this model will contain all the potenti perils inherent in the scenario. Any operating (or maintenance) procedure forces the system through some subset of the envisionment, deJ.>ending on the ini tial conditions and interleaving of actions and dynamics. Let the dynamic clo&ure of a state be those states which can be reached from it via a sequence of limit hypothe ses. A procedure which forces the system into an unsafe state is clearly unsafe. If the states traversed are all safe, and none of their dynamic closures contain unsafe states, then the procedure could be called safe, in the sense that arbitrary delays between executing the ac tions in their correct sequence cannot lead to harm. If the dynamic closure contains unsafe states, then the J.>ro cedure could be considered risky, and extra constramts imposed to ensure that transitions to undesirable states are avoided. The consequences of operator error can be examined by perturbing the procedure to see if it leads to unsafe states.
Currently we are exploring several extensions. (1) We are formalizing plan evaluation constraints, including ef ficiency and safety, for guiding the graph search through A£ and formulating incremental generation. (2) We are investigatin~ more detailed duration representations to reduce ambiguity. One J?Ossibility is to use partial quan titative information, as m Kuipers and Berleant's recent work [13]. (3) Winslett [17] has independently developed a pouible model& approach for general reasoning about actions which can be viewed as a generalization of the A£ technique. The algorithms described here, especially incremental versions, might thus be adaptable to more general problems involving reasoning about actions.
7 Acknowledgements
This paper benefited from discussions with Johan de Kleer, Marianne Winslett, Brian Falkenhainer, and Den nis Decoste. This research was supported by the Of fice of Naval Research, Contract No. NOOOH-85-K-0225, an NSF Presidential Young Investigator award, and an equipment grant from IBM.
@inproceedings{ijcai1989p204,
title = {Introducing Actions into Qualitative Simulation},
author = {Forbus, Kenneth D.},
booktitle = {Proceedings of the Eleventh International Joint Conference on
Artificial Intelligence, {IJCAI-89}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {N. S. Sridharan},
pages = {1273--1277},
year = {1989},
month = {8},
note = {Knowledge Representation},
url = {https://ijcai.org/proceedings/1989/204},
}
TY - CPAPER TI - Introducing Actions into Qualitative Simulation AU - Forbus, Kenneth D. T2 - Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89 PB - International Joint Conferences on Artificial Intelligence PY - 1989 SP - 1273 EP - 1277 UR - https://ijcai.org/proceedings/1989/204 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: