Contexts: Dynamic Identification of Common Parameters in Distributed Analysis of Complex Devices

1 Introduction

Cooperation and communication between agents is an important issue in distributed problem solving ([Corkill and Lesser, 1983], [Georgeff, 1983], [Konolige, 1980], [Durfee et a/. , 1987], [Erman et a/. , 1980], etc.). An agent in a distributed problem solving system must de­ tennine the other agents with which it must commu­ nicate, the types of information that should be shared, and how this information can be communicated. Making these determinations depends on the fact that an agent must understand communications from other agents . Previous approaches to this can be divided into three categories (or combinations thereof): common language, shared memory, and static multiple language solutions.

Common language approaches (e.g. [Hewitt and Ko­ rnfeld, 1980]) assume that all agents work in the same language. In shared memory solutions, the semantics of a communication are derived from its location in the shared memory ([Erman et al. , 1980], [Konolige, 1980]).

Static multiple language solutions assume that it is pos­ sible to dynamically translate assertions in one language to assertions in another (e.g. [Smith ei al. , 1981]).

Unfortunately, these solutions are inadequate for sys­ tems that perform analysis in complex engineerin& do­ mains ([Penberthy, 1987],[Addanki and Davis, 1985J). A behavioral description of the ideal heat engine in figure 1 requires analysis within the domains of Thermodynam­ ics, Mechanics, and Geometry. In our approach, each domain is an active module that consists of a declara­ tive, logical database of the knowledge in the domain, backward and forward chainers to perform inference in the domain, and domain specific heuristics that control this inference. The Thermodynamics domain gives the behavior of the gases in the piston-cylinder assemblies, Mechanics gives the kinematic and dynamic behaviors of the pistons, links, cranks, etc., and Geometry provides the structural constraints and computations.

Analysis of the heat engine requires that these differ­ ent domain-specific analyses interact in order to find the final result. The interaction is a result of the different domains sharing common parameters. Each domain de­ fines its own constraints on the common parameters and the interaction resolves these constraints giving rise to the final solution. For example, the volume of the gas is a parameter common to Thermodynamics and Geome­ try, the position of the piston is a parameter common to Geometry and Mechanics, etc.

Since device behaviors change through time, parame­ ters are both problem- and time-specific. As behaviors change, old parameters disappear and new parameters are created. This dynamic nature of common parame­ ters makes it difficult to use either a common language, a shared memory semantics, or a language translator. Even though domains may use the same logical language, they use different extensional variable names since pa­ rameters are both problem- and time-specific. As a re­ sult, the domains would have to perform a multi-phase commit to agree with one another on all global name as­ signments, clearly a tedious approach. Shared memory approaches require all common locations (parameters, in our case) to be predefined, a difficult problem when parameters come and go dynamically. Lastly, matching common parameters requires translations to take place over the extensions of the different languages. The dy­ namic nature of the extensions, when combined with the problem of multiple extensional names, makes a priori specification of the translation tables difficult .

Fortunately, parameters in applied physics carry a lot of spatial, temporal, and structural knowledge with them. This knowledge can be expressed in a common sublanguage. Although this sublanguage is dynamic, it is possible to carry out translation over its extensions. In this paper we introduce the notion of contexts as the encapsulated description of a parameter in this common sublanguage. We show how contexts can be used ef­ ficiently to provide matching of parameters across do­ mains. We begin by defining the structure of contexts. We then show how contexts can be matched in order to determine common parameters across domains. By means of an example we demonstrate the utility of con­ texts. Finally, we discuss our work in relation to other communication paradigms in distributed problem solv­ mg.

2 What's in a Context?

A context is defined for each parameter and consists of four parts: (1) related spatial information, (2) the pa­ rameter's dimension (e.g. length, ma·;~length ), (3) tem­ poral information, and ( 4) units of me~~;e. This section describes each of these parts in detail.

Every physical quantity represented by a parameter 1 is associated with an underlying geometric or structural entity. It is impossible to define a quantity without refer­ ring to this structural entity. For example, a "force," by its very definition, requires the existence of an agent and a target [Martin, 1982]. The agent is either a physical object or a field and the target is another object. Hence, these objects (or fields) are the structural entities that must be mentioned when defining a force.

Properties in Thermodynamic systems, as another example, are either intensive or extensive [Moran and Shapiro, 1988]. Intensive properties are functionally de­ pendent upon position, a geometrical entity. Examples of these properties include pressures, temperatures and densities. Extensive properties are functionally depen­ dent upon the structural boundaries that define the sys­ tem; such boundaries comprise a structural entity. For example, the volume of a gas (an extensive property) is the volume of its container. The structural "entity" as­ sociated with the gas volume would be the surfaces that define the container's inner boundaries.

1 From now on we will use the terms quantity and param­ eter interchangeably.

In addition to structure, the dimension of parameters is important. A set of dimensions that suffices for ap­ plied physics includes {Mass, Time, Length, Tempera­ ture, Electrical Current} . All physical quantities in ap­ plied physics can be measured in terms of these dimen­ sions (i.e. {[M], [T], [L], [K], [!]}). Parameters in one domain can be compared with parameters in another domain if and only if they have the same dimensions . Obviously, temperatures (dimension [K]) must be compared with temperatures, forces (dimension [[J:}{l) with forces, etc.

Dimension and structure can obviously disambiguate between parameters that refer to different objects. Sometimes, however, we need to disambiguate between two or more parameters with the same dimension that refer to the same object. The length and height of a rect­ angular object, for example, share both the same object and the same dimension. In this case we depend upon an unambiguous structural description to discriminate be­ tween them; just identifying the "object" of both param­ eters is insufficient. In general, the structural descrip­ tion for a 3d-segment (volume) of an object is specified by the 2d-boundaries (surfaces) that surround it. Sim­ ilarly, a 2d-patch (surface) of an object is specified by its ld-boundaries (segments) . Finally, any lei-segment (edge, arbitrary line segment) of an object is specified by its Od-boundaries (endpoints). These points are de­ scribed in an object-specific coordinate system. 2 By us­ ing these descriptions we can differentiate parameters, such as length and height, that refer to different pieces of the same object.

We also are interested in analyzing devices whose be­ havior changes through time, devices whose parameter values may vary through time. One must therefore en­ sure that when domains compare the values for parame­ ters they compare the values at the same point (or inter­ val) in time. Thus, time must be included in the descrip­ tion of a physical quantity to disambiguate temporally separate measurements.

Lastly, the type (scalar or vector) and units of mea­ sure for each parameter are added to contexts. This in­ formation is used to perform mathematical conversions of the values passed between domains. Type informa­ tion ensures that values are handled in an appropriate way. For example, to compare two scalar values, one simply checks their value in the same system of mea­ surement. Comparing vectors, on the other hand, re­ quires three steps. First, the vectors must be trans­ lated to a common frame of reference. Second, the vectors must be converted to a common representation (e.g. polar vs. cartesian). Third, the vector coordinates must be converted to a common system of measurement . Units of measure are needed to support the different systerns of measurement adopted by each domain of applied physics (i.e. SI, CGS or EES)[Martin, 1982].

2 As seen later in this section, these coordinate systems may differ. We provide a mechanism for converting between these coordinate systems using standard analytic geometry formulae.

These four types of information (space, dimension, type, and units) unambiguously define parameters of physical systems. As a result, if two contexts match they describe the same parameter . The task of identi­ fying common parameters between domains is therefore reduced to the task of finding contexts from one domain that match contexts of another domain.

3 Using Contexts

Now that contexts have been described in general, this section will illustrate how contexts are used to effectively determine common parameters across domains. In par­ ticular, this section shows how the domains of Ther­ modynamics and Geometry use contexts to determine common volume parameters in the ideal heat-engine of figure 1. Each of these domains first generates its own set of contexts and then matches them against contexts from the other domain.

3.1 Generating Contexts

To begin, suppose that heat is applied to the first pis­ ton chamber from time t1 to time t2. Thermodynamics models the gas behavior as a polytropic process, deduc­ ing that its volume must increase during time interval [t1, t2]. The following propositions are used by Ther­ modynamics to represent these changes in volume (e.g. from O.lm 3 to 0.2m 3 ):

(gas-volume air-piece-1 v1 T1) vl=O.lm 3 ,Tl=h (gas-volume air-piece-1 v2 T2) v2=0.2m 3 , T2=t2

Contexts for these propositions must now be created. The structural context for a gas volume is the set of surfaces that define a region of space which exactly contains the gas. By ex­ amining the heat engine, Thermodynamics finds that the gas is contained by the surfaces of the inner chamber (i.e. the sur­ faces base1-ic1, basel, and latsf-ic1 ). This structural information is contained in the global structure specification for the piston-cylinder assembly (see figure 2).

The dimension and temporal information for each param­ eter must also be included. Thermodynamics knows that the dimension for volumes is [L 3 ]. The temporal extent for each volume parameter is contained in the correspond­ ing proposition [Penberthy, 1988]. The resulting contexts for the gas-volume propositions can be seen in figure 3.

The Geometry domain also computes volumes, but it uses a different language and a different set of rules. The Ge­ ometry domain determines three distinct volumes for each chamber in the heat-engine example (see figure 2). Volume VA is the one bounded by the inner piston surface and the inner surfaces of the cylinder housing. This volume depends on the position of the piston relative to the cylinder housing. Volume VB is the one for the material needed to build the cylinder. Volume Vc is the volume for the material needed to build the piston.

These three volumes are represented by the Geometry domain with the following propositions:

(volume-of inner-chamber-1 VA 11)

(volume-of cylinder-1 VB 11)

(volume-of piston-1 Vc 11)

VA= O.lm 3

VB= 0.09m 3

Vc = 0.03m 3

ll=[h, h]

The Geometry domain must convert these propositions into contexts before trying to communicate with other do­ mains. Since every volume is defined by a unique set of bounding surfaces, these surfaces make up the structural context for a volume. As before, this information is writ­ ten explicitly in the problem description (see figure 2) and is easily retrieved. The Geometry domain knows that all vol­ umes have dimension [L 3 ], and it knows the temporal extent of each parameter by examining the corresponding proposi­ tions. This information is collected for the three volumes and then formed into separate contexts as seen in figure 4.

At this point each domain has calculated values for its vol­ ume parameters and has generated the corresponding con­ texts. The domains must now compare their contexts, looking for contexts whose structure, dimension, and time values match.

3.2 Matching Contexts

The algorithm for matching contexts consists of three phases: "canonicalize," "hash," and "temporal match." In the canon­ icalize phase each domain ensures that the structure and dimension portions of each context are in canonical form. 3 Since the structural elements of a device are uniquely named and common to all domains, an alphabetized string is used for the canonical representation of a structural set. For exam­ ple, the set of structural elements from Geometry's context for VA, {base1-ic1, basel, latsf-icl}, is represented by the canonical form "basel basel-ict latsf-ict". The canon­ ical form for a given dimension is an expression in a tree form, identical to that used in [Martin and Fateman, 1971]. Since the current implementation uses Macsyma for calcula­ tions, each domain already uses this representation for di­ mension equations; no extra conversion work is needed.

Assuming that the Geometry domain transmits its canon­ icalized contexts to the Thermodynamics domain and vice versa, the hash phase of the matching algorithm begins in both domains. In this phase a hash-sort of contexts is used. The key for each context is an ordered pair, consisting of the context's dimension followed by its structure. Since all the elements of these lists are in canonical form, the buckets of the hash table contain contexts whose dimension and struc­ ture values match. In our example three buckets (represented by the following hash keys) contain contexts:

1. ([L 3 ], "basel basel-icl latsf-icl")
2. <(L 3 ], "basel base2latsf-pl")
3. ([L 3 ], "basel-icl basel-ocl base2-ocl latsf-icl latsf­ ocl")

The temporal match phase of the algorithm finds all con­ text pairs in the hash buckets whose time values overlap. Currently we use the standard O(N 2 ) search, where N is the number of contexts within a given bucket, to match the temporal components of local and remote contexts. The tem­ poral comparisons are done by referring to a global partial order of timepoints, as described in [Penberthy, 1988]. In our example, only bucket 1 (as defined above) contains matching contexts. Two pairs are found in this bucket, identifying Ge­ ometry's volume VA and Thermodynamic's volumes Vl and V2 as common parameters. Geometry and Thermodynamics can now exchange values for these volumes, possibly using the unit conversion techniques described earlier.

Other examples of context pairs exist in the heat engine example. 4 The domains of Kinematics and Geometry find the position of the piston and crank-arm assemblies as common parameters. The Kinematics domain discovers that the Solid Dynamics domain shares an interest in the acceleration of all mechanical linkages. Solid Dynamics and Thermodynamics exchange values for the forces exerted by the expanding gases. All of these common parameters are identified by matching their structural context, their dimensions, and their time val­ ues. In addition, the use of units and type information is especially useful when Kinematics uses polar coordinates to represent accelerations and Dynamics uses Cartesian coordi­ nates for the same parameters (e.g. acceleration of the crank arm) .

3 We canonicalize both the set of structural elements and the dimension formula to provide for efficient matchiflg.

4 Due to a lack of space, the actual matching processes for these contexts are not described in detail.

4 Implementation

The language used by each domain is built from a gen­ eral first-order temporal language as described in [Penberthy, 1988]. This general language also supports an interface to Macsyaa ([Martin and Fateman, 1971], [Symbolics, Inc., 1988]} for performing the symbolic mathematical calculations required by each domain.

Contexts are implemented as frame-like structures. Each domain translates its language descriptions into contexts by using pre-defined functions. As demonstrated in the example, these functions perform two tasks. First, they perform syn­ tactic extraction from the individual language descriptions for the time, dimension, and value sections of a context. Sec­ ond, they unify simple clauses in the domain knowledge bases to complete the structural section of a context. Since the structural specification is global to all domains, these unifi­ cations are reduced to the matching of conjunctions against a database of facts. No inference is required.

A framework for distributed problem solving has been im­ plemented to support the passing of contexts between do­ mains. This framework consists of several LISP machines, each with its own implementation of a particular domain of applied physics. As of this writing, four domains have been implemented and tested: Thermodynamics of Ideal Gases, Planar Solid Dynamics, Planar Kinematics, and Pla­ nar Geometry. These domains communicate with one an­ other using a network protocol specifically designed for ex­ changing contexts. This protocol supports multiple machines (e.g. domains) connected together on a LAN.

5 Discussion

Many researchers have recognized the importance of inter­ action between cooperating agents in a distributed problem solving system (e.g. [Corkill and Lesser, 1983], [Georgeff, 1983], (Konolige, 1980], [Durfee et al. , 1987], [Erman et al. , 1980]). However, many of the proposed styles of interac­ tions are typically static in nature. By static, we mean that the different problem solvers in the system know a priori the classes of data .that must be exchanged and to whom or where the data must be sent.

The Hearsay II architecture proposed in [Erman et al. , 1980] is typical of many distributed problem solving systems[Durfee et al. , 1987], and is an excellent example of static interaction. It consists of multiple knowledge sources, a blackboard divided into separate sections, and meta-level demons. Each section of the blackboard contains the data relative to a specific task performed by the architecture and is statically defined. Knowledge sources interact with one another by reading and writing data to these sections. How­ ever, since the blackboard sections are static, the types of interaction between knowledge sources are static.

Suppose that one wanted to build a system for analyz­ ing mechanical devices by using a similar architecture. In this approach each knowledge source would represent a given domain of applied physics. Since these knowledge sources would necessarily exchange values for common parameters, the blackboard should contain a unique location for each pa­ rameter. Unfortunately, the task of specifying blackboard lo­ cations for parameters is quite difficult. This difficulty arises from the fact that the set of parameters used to analyze a device often changes during the analysis.

Analysis requires multiple sets of parameters since a given set often depends upon the structural configuration of a de­ vice. Since a device may undergo changes in configuration, the corresponding parameter set might change. For example, the gas volumes within the heat engine of figure 1 depend on the respective pistons being inside their cylinder housings. If a piston were to leave its housing, the parameters describing the corresponding gas volume would be invalid. The pis­ ton might also collide with other parts of the heat engine, requiring new parameters to describe the new forces and ac­ celerations caused by collision. If a problem solving system were to analyze such a behavior, it would start with a set of parameters that included gas volumes, switch to one without gas volumes, then switch to a set describing the interaction of falling pistons and other phenomena. 5

This continual change in parameters would pose serious difficulties for a blackboard system that depends upon stati­ cally declared interaction. The blackboard would necessarily undergo a dynamic reconfiguration for each new parameter set. Further, this reconfiguration would have to be known to all knowledge sources. While this could be implemented, such overhead would be computationally expensive. Static declarations of interaction, therefore, are not feasible for dis­ tributed problem solving systems that analyze mechanical devices.

Dynamic interaction, where the individual problem solvers are free to change communication patterns, is needed. A few such reconfigurable systems (e.g. [Hewitt and Kornfeld, 1980], [Smith and Davis, 1981], [Findler and Gap, 1987]) have been proposed. Hewitt et.al. describe the concept of actors and message passing, and how this metaphor can be used in problem solving. Hewitt proposes a fine-grain parallel archi­ tecture of actors that can change dynamically. He also defines the semantics for messages passed between these actors. One might think of contexts as the semantics for messages passed between domains.

In [Smith and Davis, 1981] and [Smith and Davis, 1983] Smith et.al. recognize the utility of dynamic interaction be­ tween multiple nodes (problem solvers). In particular, they identify result sharing as a form of cooperation in which indi­ vidual nodes assist one other by sharing partial results, based on somewhat different perspectives of the overall problem. Result sharing permits the dynamic exchange of common re­ sults but, as the authors point out, implementing this re­ quires a solution to several communication problems. These problems demonstrate that a. node must (1) select particular results to be transmitted, (2) choose the nodes that will re­ ceive these results, and (3) upon receipt of a result, decide whether or not to accept it. The concept of a context, as introduced in this paper, is the key to solving these commu­ nication problems in the domain of applied physics.

Similarly, Riesbeck in [Riesbeck, 1979] identifies a solution (known as conceptual dependency (CD) structures) for com­ munication problems in a distributed system for story un­ derstanding. CD structures represent conceptual meanings and, like contexts, are exchanged between problem solvers. Whereas CD structures are designed for communications be­ tween entities in a natural-language understanding system, contexts are designed solely for communications in systems that analyze engineering systems.

6 Conclusions and Future Work

In this paper we described contexts, a representation that permits the dynamic identification of common parameters between distributed problem solvers in a system that ana­ lyzes mechanical devices. A context represents the structural elements, temporal extent, dimensions, and units associated with each physical parameter. The four concepts described in contexts are inherent in all domains of applied physics. Each domain therefore can use a language particular to its area of expertise, without being restricted by a global, common language for all concepts.

5 Although this is an unusual example, any mechanical de­ vice that involves changes in configuration (e.g. typewriters, cam shafts, locks) would require multiple sets of parameters.

Contexts provide the ability to determine, for each prob­ lem, the parameters that one domain must exchange with an­ other. However, this is only the first step in. distributed anal­ ysis of engineering systems. In the future we will explore the utility of contexts and related structures in situations aris­ ing from dynamic interaction. For example, one must deter­ mine what actions to take when conflicting parameter values are detected. This would require a mechanism to determine which domain is in error, i.e., a mechanism for comparing justifications across domains. This problem is further com­ plicated by the use of different languages in different problem solvers. In addition to the resolution of conflicts, one must also provide devices for the exchange of partial solutions, for queries between domains, etc. Contexts provide a framework for these and related tasks, but the details have not been formalized. Nevertheless, all of this work relies on contexts. Without contexts, domains could not identify common infor­ mation easily. Without the exchange of common information, complex devices could not be analyzed .