Compositional Model-Based Design
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Qualitative Reasoning and Naive Physics. Pages 1445-1449.
© 1993 International Joint Conferences on Artificial Intelligence
Abstract
Generative model-based design of physical devices is difficult because the space of candidate design solutions is typically very large, and the cost of testing each candidate design to verify that it .satisfies the desired behavior is substantial. In this paper, we present compositional model-based design (CMD), which addresses these problems by adopting a divideand-conquer strategy and by interleaving design generation and testing. The CMD method divides the specified behavior into separate fragments and constructs locally correct design fragment~ for each. The design fragments are then incrementally composed until a design for the entire specified behavior is obtained. We show how the CMD may be used for the conceptual design of a steam-boiler control system.
- [Babcock and Wilcox, 1975] Babcock and Wilcox. Steam/It• Generation and Use. Babcock and Wilcox Company, 1975.
- [Bose and Rajamoney, 1993] P. Bose and S. Rajamoney. De- signing for transitions in multi-region devices. In Proceed- ings of the 7th International Workshop on Qualitative Rea- soning, 1993.
- [Chapman, 1988] David Chapman. Planning for conjunctive goals. Artificial Intelligence, 1988.
- [Falkenhainer and Forbus, 1991] Brian Falkenhainer and K. Forbus. Compositional modelling: Finding the right model for the job. Artificial Intelligence, 1991.
- [Joskowicz, 1989] L. Joskowicz. Simplification and abstrac- tion of kinematic behaviors. In Proceedings of the IJCAI, 1989. IJCAI
- [Neville and Weld, 1992] Dorothy Neville and Daniel S. Weld. Innovative design as systematic search. In Proceed- ings of the AAAI Fall Symposium on Design from Physical Principles 1992.
- [Williams, 1989] Brain C. Williams. Invention from Firlt Principles via Topologies of Interaction. PhD thesis, MIT AI Lab, Cambridge, MA, 1989.
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
We present compositional model-based design (CMD), a divide-and-conquer strategy that facilitates the genera tive design of physical devices. The CMD method di vides the specified behavior into separate fragments and constructs design fragments for each. The design frag ments are then incrementally composed until a design for the entire specified behavior is obtained. The com position of independently designed fragments may result in a design which, due to adverse interactions between the fragments, violates the behavior established by one or more of them. The CMD method detects such inter actions and revises the composite design to re-establish the desired behavior.
Consider the design of a boiler control system for a steam plant that is required to supply steam at a steady, fixed pressure despite variations in the demand of steam at the load. Figure la shows a candidate design from [Babcock and Wilcox, 1975] which establishes this regu latory behavior as follows:
Fluctuations in the load are sensed by a governor control mechanism which adjusts the outflow valve to maintain the steam flow rate. to the load steady. To maintain the pressure at the drum steady, the change in the outflow rate is sensed and used to adjust the flow rate of the fuel/air mixture to the furnace. Consequently, the steam generation rate and the rate of steam flow from the boiler to the drum change to compensate for the outflow rate change, thereby, maintaining the steam pressures at the boiler and the drum steady.
To design such a device, compositional model-based design, given the basic input specifications 1 shown in qualitatively proportional to the steam mass which is steady since the partial influences on it (based on direct influences from the outflow and inflow) cancel.
1 We specify device behavior in terms of a region diagram


Assumptions A(DF) : A set of auxiliary assumptions under which the designed device works. There are four types of assumptions: (a) Codesignation assumptions. In extending a partial design, additional objects may be re quired. Often, instead of considering new objects, some of the existing objects may fulfill the role (a form of function-sharing). Codesignation [Chapman, 1988] ex plicitly considers the possibility that two objects may be identical. The causal-relations network in Figure 2 is based on the assumption, As , that the source codes ignates with the boiler. (b) Influence closure assump tions. The computed qualitative change is valid only under the closed-world assumption that all the partial influences on the quantity are known [Falkenhainer and Forbus, 1991]. This assumption is explicitly represented by listing all the known partial influences on the quan tity. For example, in the causal-relations network shown in Figure 2, assumption A2 is an influence closure as sumption specifying that the only known partial influ ences on the steam mass in the drum are a positive one from the steam inflow (from the boiler) and a negative one from the steam outflow (to the load) . (c) Influ ence dominance/cancellation assumptions. When there are opposing partial influences on a quantity, the quali tative change to it may be ambiguous. Influence domi nance/cancellation assumptions specify whether one set of partial influences dominates or cancels the other, thereby, permitting unambiguous computation of qual itative changes. 4 In Figure 2, the steam mass in the drum is steady based on an influence cancellation as sumption A3 which states that the inflow rate of steam from the boiler equals the outflow rate of steam to the load. (d) Quantity inequality assumptions. Quantity in equalities that are not justified by the model fragment instances must be assumed as initial conditions or re gion boundary conditions. For example, the inequality assumption A1 specifies an initial condition: the steam pressure difference between source, s1 , and drum, d, must be greater than zero (to enable the steam inflow from the source).
A design fragment is locally correct if, based upon its design and auxiliary assumptions, its causal-relations network can be constructed (using the domain model axioms and qualitative inference rules) and if its causal relations network entails all the behavior fragments spec ified in its behavior.
3 Behavioral Axioms
Two fundamental problems in composing design frag ments are: 1) If the composite design is incorrect, that is, due to adverse interactions, previously established be havior is violated, how is blame assigned to individual elements of the causal-relations network? 2) How is the incorrect design fragment revised to re-establish the de sired behavior or, more generally, what is the set of re vision operators?
4 This assumption may be refined to determine how the cancellation or dominance is achieved when the preliminary qualitative design is analyzed with quantitative information or exact equz.tions.
To address both these problems, we declaratively spec ify the axioms describing the necessary and sufficient conditions for the different types of behavior fragments to hold. By examining these axioms, we derive all the failure conditions-violations of the necessary and suf ficient conditions that may prevent the behavior frag ment from being established. For each failure condition, we devise all the revision operators that will re-establish the behavior fragment by revising the failed condition(s) to satisfy the behavioral axioms. Compositional model based design, therefore, solves the blame assignment problem by systematically searching the causal-relations network for the failure condition(s) associated with the behavior fragment. It solves the revision problem by ap plying one of the revision operators associated with the failure condition(s) to the incorrect design fragment.
Table 1 shows the behavioral axioms for qualitative changes and maintaining quantity inequalities. 5 Ax iom 1.1 states. that, in order for a quantity q to be in creasing in a region R, it must necessarily be positively influenced by a quantity, p, in R. In addition, in R, ei ther all quantities q" that are negatively influenced do not codesignate with q or, if some do, then the set of positive influences on q must dominate the set of neg ative influences (Axiom 1.2), resulting in a net positive influence on q (under an influence closure assumption, supported by a. set of codesignation assumptions) . Ax iom 2 specifies the conditions under which a quantity p partially influences a quantity q, positively or negatively, in a region R, and Axioms 3.1 and 3.2 specify the condi tions under which a causal relation between p and q ( di rect influence or qualitative proportionality) holds in a region R. Axioms for the activity and existence of model fragment instances are obtained from their definitions in the domain model. The next set of axioms specify the necessary and sufficient conditions for a quantity q to remain greater than a constant value c in a region R.
Failure conditions are determined by systematically enumerating the reasons why a desired behavior frag ment may not hold. For example, in a design fragment, if a quantity q is to be increasing in a region R and the causal-relations network does not establish it, then, from the behavioral axioms, it must be due to one of two failure conditions:
- The influence closure assumption for q does not con tain a positive partial influence on q (from Axiom 1.1). This failure may be revised in two ways (resulting in two distinct revision operators): a) forcing a quantity q' which is positively influenced to codesignate with q, or b) introducing a new positive influence p on q.
- The influence closure assumption for q includes nega tive influences and the set of positive influences on q does not dominate the set of negative influences on q (from Axiom 1.2). This failure may be revised in three ways (resulting in three distinct revision operators): a) pre venting the negatively influenced quantities from codes ignating with q, b) forcing the set of positive influences to dominate the set of negative influences, or c) intro-
5 Space restrictions prevent us from discussing the remain ing. Also, for simplicity, we show only the axioms for the specific qualitative changes q = inc and inequalities q > c.
clueing new positive influences on q such that the new set of positive influences on q dominates over the set of negative influences.
4 Operations on a Design Fragment
The three complex operations on a design fragment are: 1) constructing design fragments for basic behavior frag ments, 2) composing design fragments to establish their combined behavior, and 3) extending design fragments by posting auxiliary behavior fragments that enable or disable region transitions. Each operation consists of two phases: (a) a generative phase in which, working back wards from the behavior fragments to be established, all the necessary elements of the causal-relations net work down to the design components and their structural relations are generated, and (b) a verification phase in which the complete causal-relations network based upon the design components and structural relations identified in the generative phase is constructed (as in qualitative simulation) and checked to see whether the desired be havior is established or violated (due to unwanted inter actions). In each of these two phases, the basic revision operators described in the previous section are used to handle failure conditions.
Constructing Basic Design Fragments
Qualitative changes to quantities are the basic behavior fragments. In the generative phase, the behavior of a new design fragment is initialized to the desired quali tative change and failure conditions are repeatedly de tected and revised. When a revision operator introduces new objects (e.g. the source of a flow instance), all pos sible codesignations to the objects already in the design are considered and codesignation assumptions are for mulated. In the verification phase, the complete causal relations network is constructed based upon a set of codesignation assumptions. If the network does not es tablish the desired behavior, the failure conditions are identified and revised.
In the boiler control example, to establish the steam flow rate from the drum to the load to be increasing in region R1, a new design fragment is created with its behavior initialized to this increase. This design frag ment in incorrect because the necessary condition that the steam flow rate be positively influenced does not hold (Axiom 1.1; Table 1). One of the revision operators for this failure condition is applied, for example, the revi sion operator introducing a new positive influence on the steam flow rate. The operation involves searching the model fragments in the domain for a suitable causal relation that may introduce this partial influence. In this case, the operation finds, from the liquid flow model fragment, that the flow rate is inversely proportional to the resistance of the path. Accordingly, it attempts to recursively establish a decrease in the resistance of the path (Axioms 2, 3; Table 1) . This recursive process con tinues until design components and structural relations are reached.
In the verification phase, the complete causal-relations network is constructed. For example, since a steam flow instance from the drum to the load is active, the mass
Table 1: Behavioral axioms for a qualitative change, q=inc, and a quantity inequality, q < c.


of the steam in the drum is negatively influenced by the flow rate. This leads to other behavior fragments be ing established by the design including a decrease in the mass and pressure of the steam at the drum. In this case, the established behavior fragment, increasing of the out flow rate (by decreasing the path resistance, etc.), is not violated. Figure 4a shows relevant portions of the causal relations networks that establish two qualitative changes of region R1 of the boiler control example.
Composing Design Fragments
This operation composes two design fragments such that the composite design fragment establishes the combined behavior. In the generative phase, all possible codesig nation assumptions across the design fragments are for mulated. In the verification phase, the complete causal relations network is generated under a set of codesigna tion assumptions and checked to see whether it contin ues to establish all the behavior fragments. New inter actions may be due to two reasons: 1) A co designation assumption may force two previously separate quantities to be the same, thereby, requiring an influence closure assumption that is the union of the two previously sepa rate influence closure assumptions. 2) Composing design fragments may lead to new interactions between objects across the design fragments.
Figure 4b shows how the design fragments for two qualitative changes of region R1 are composed. Since all the objects are ground instances (e.g. drum, boiler), no codesignation assumptions are required. In the ver ification phase, upon constructing the complete causal relations network, one of the previously established be havior fragments, p sd = std, is violated. It was origi nally established under the assumption that the steam mass in the drum is uninfluenced. However, upon com position, the steam outflow from the drum (from the de sign fragment for increasing the outflow rate) negatively influences the steam mass. This interaction invalidates the earlier influence closure assumption, resulting in a decreasing steam pressure at the drum.
The failure condition for this violation is that the neg ative influence on the steam mass from the outflow is not canceled to keep the steam mass steady. The revi sion operator introduces a new positive influence on the steam mass in the drum. Upon searching the domain model, the fluid flow model fragment is found to have a suitable causal relation: a direct positive influence on the destination fluid mass by the flow rate. Accordingly, the operation attempts to recursively establish an ac tive fluid flow instance (with steam as substance and the drum as the destination) whose flow rate is positive (Axioms 2, 3; Table 1). In this case, since the source and path are not specified, they may codesignate with existing objects or new objects may be introduced.
Extending Design Fragments
A design fragment may be extended by posting addi tional behavior fragments to be established in order to make a region transition when the transition condition is reached or to prevent an unwanted region transition when conditions other than the transition condition are reached. Potential transition conditions for a region are generated by determining which qualitative changes in the region will result in a limit point being reached. If the transition is not wanted, behavior fragments that pre vent the transition point from being reached are added to the behavior of the design fragment to be later estab lished using the construct and compose operations. If the transition is desirable, then nothing is done. 6
In the composite design fragment of Figure 4b, if the source of the inflow to the drum codesignates with the boiler then, since the steam mass in the boiler is decreas ing due to the flow, it may eventually become zero. In this case, the .flow stops and the region makes an un wanted transition. Therefore, steam mass in the boiler must be maintained greater than zero, and this behavior fragment is posted as a necessary auxiliary behavior to be established by the design fragment. Figure 4c shows how this behavior fragment may be established by gen erating steam in the boiler at a rate equal to the rate of steam outflow from the boiler.
5 The CMD Method
Table 2 presents the algorithm for compositional model-based design. The algorithm accepts as input a device behavior expressed as a region diagram and a do main model , and produces as output a set of designs that generate the specified behavior. It uses a working set of design fragments and a set of design fragments for basic behavior fragments (qualitative changes to quanti ties). In Step 0, the working set is initialized such that each design fragment in the set corresponds to a region from the region diagram. The behavior of each design fragment is initialized to the set of qualitative changes in the corresponding region; the causal-relations network to empty; the design to the objects mentioned in the quali tative changes or quantity inequalities of the region; and, the assumptions to the quantity inequalities defining the boundary of the region.
The algorithm cycles, incrementally establishing the design fragments in the working set and the basic set. The body of the cycle consists of Steps 2 and 3. Step 2 constructs design fragments for each basic behavior frag ment in the region, and incrementally composes them until the combined behavior for the region is established. Once every design fragment in the working set ( corre sponding to every region in the region diagram) has been established, Step 3 extends each one by posting auxil iary behavior to enable region transitions or disable un wanted transitions. These new behavior fragments are established by cycling back through the algorithm from Step 1. Step 2 will construct (or retrieve from the basic set, if one is available) a design fragment that establishes the newly added behavior and will compose it with the design fragment.
6 This assumes that the device automatically shifts upon reaching the transition condition a.s in the boiler control sys tem. [Bose and Rajamoney, 1993] discusses the design of devices in which the transition must be actively effected by a. control mechanism.

The cycle continues until one of the end tests is met: either the user-set maximum time limit has been reached or all the behavior fragments and transitions in the re gion diagram have been established. The design solution is the union of the designs of the design fragments in the working set, and the assumptions underlying the design solution are the union of the assumptions of the design fragments in the working set.
5.1 An Example Trace
We illustrate how the CMD method designs a portion of the boiler control system shown in Figure 1. In the trace, we show only the the choices made by the method that will lead to the design shown in Figure 1; if it were to make alternative choices, a different design would re sult. Figure 5.1a shows the construction of the design fragments for the basic behavior fragments ofregion R1. The water level in the drum and the steam pressures in the drum and boiler are maintained steady by assuming they are uninfluenced. The outflow rate from the drum to the load is increased by decreasing the path resistance through a valve and lever mechanism attached to the governor sensing the steam demand changes at the load

(not shown in the figure). The composition of the design fragments for increasing the outflow rate and maintain ing the pressure at the drum steady (Figure 5.1b ), results in a violation of the latter behavior fragment since the outflow decreases the steam mass and pressure in the drum. To re-establish the steady pressure, an inflow of steam is introduced to cancel the outflow (Figure 5.1c).
Composition of the design fragment for maintaining the steam pressure in the boiler steady with the compos ite design fragment obtained above, under the assump tion that the source of the steam inflow to the drum codesignates with the boiler, results in the steam pres sure in the boiler decreasing due to the flow. Hence, the behavior fragment-maintaining the steam pressure in the boiler steady-is violated. To re-establish the steady pressure, a generation of steam is introduced to cancel the outflow (Figure 5.1d) .
The composition of the design fragment for maintain ing the water level in the drum steady to the composite design fragment obtained above, does not violate any of the previously established behavioral fragments. Step 3 of the method now extends the composite design frag ment to prevent unwanted transitions. Since the water in the boiler is decreasing due to steam generation, it will eventually become zero, leading to an unwanted transi tion from region Rt. To prevent that, an auxiliary be havior fragment specifying that the mass of water in the boiler must be steady is posted. In the next iteration through the method, a design fragment for maintaining the water level in the boiler steady is constructed by in troducing an inflow of water into the boiler to cancel the loss due to steam generation, and composed with the above design fragment (Figure 5.1e).
If the source of the inflow codesignates with the drum, then a previously established behavior fragment, main taining the water level in the drum steady, is violated. To re-establish the steady water level, an inflow of water into the drum from a tank is introduced to compensate for the loss due to the outflow of water (Figure 5.1f).
6 Discussion
In model-based design, our work is closely related to Williams' work [Williams, 1989] on Interaction-based In vention. His IBIS system precompiles the domain theory into an abstract space describing the interactions between quantities. It establishes a desired functional relationship between two quantities by finding a can didate path of potential interactions in this abstract space and verifying with the detailed domain model that the path establishes the desired relationship. More recently, Neville and Weld [Neville and Weld, 1992] have investigated potential problems due to the scal ing up of William's approach. In contrast to IBIS's at tempt to find a candidate design and then test it, the CMD method interleaves design generation and verifi cation by constructing design fragments and verifying that they establish fragments of the specified behavior. Also, if a design fails, CM D can determine why it failed and revise it using its failure conditions and associated revision operators. Ongoing work on model abstractions and the design of devices that require explicit mecha nisms to effect region transitions addresses some of the limitations of CM D .
@inproceedings{ijcai1993p200,
title = {Compositional Model-Based Design},
author = {Bose, Prasanta K. and Rajamoney, Shankar A.},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {1445--1449},
year = {1993},
note = {Qualitative Reasoning and Naive Physics},
url = {https://ijcai.org/proceedings/1993/200},
}
TY - CPAPER TI - Compositional Model-Based Design AU - Bose, Prasanta K. AU - Rajamoney, Shankar A. T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 1445 EP - 1449 UR - https://ijcai.org/proceedings/1993/200 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: