Figure 1: Pareto Optimality
It is frequently difficult to find a global objective function even for problems that otherwise can be easily mapped into integer programming (IP), a general technique for satisfying multiple objectives with constraints. This is because it is difficult to assign a metric to different objectives. For example, how should the cost of the artifact
be weighted with respect to its time to market, weight, or various features? The difficulty of generating an ``objective'' function is increased by the fact that even small numeric changes in weights can generate very different solutions[3].
When problem solving is distributed over multiple agents with expertise in different domains, the difficulty is exacerbated. For example, an electronics engineer may want to use a position sensor that the mechanical engineer finds too heavy for the gimbal and motors of an artifact they are collaboratively designing. The resolution of such a conflict is often not subject to any objective algorithm. Such conflicts are likely to be resolved by intervention of a manager or simply the give and take of normal engineering discussion. An objective function is simply not an appropriate tool for support of such conflicts.
There are decision support tools for providing argumentation in such a situation[3,15] and for attempting to optimize multiple objective decisions[7]. It is sometimes feasible to at least perform local optimization over weighted objectives[2]. We do not here address all of the problems in these approaches beyond noting that there seems to be no general solution to multiple objective optimization. However, there is a simpler but useful formalism applicable to the satisfaction of multiple objectives among distributed agents: the tracking of Pareto optimality.
``Tracking'' means that the problem solver is automatically notified of Pareto optimality loss and of the particular opportunity to improve the design*. In this paper, we show that this functionality has three important properties for multiple objective problem solving: 1) opportunities to improve the local solution are noticed that otherwise would be lost, 2) resolution of conflicts may be delayed indefinitely, and 3) ``thrashing'' during problem solving backtracking is prevented. These properties are especially important when problem solving is distributed. We also show how this tracking function is implemented with novel artificial intelligence techniques.
Figure 1: Pareto Optimality
Pareto optimality[5] is an economics term for describing a solution for multiple objectives. No part of a Pareto optimal solution can be improved without making some other part worse. Figure 1 shows four geometric examples of Pareto optimality. In these figures, the circles represent objectives that are satisfied best when the area of the circle is maximized. The constraints are that the circles may not overlap and must fit within the triangle.
We might further impose a global objective function in this case that is equal to the sum of the circle areas. Only one of these figures is globally optimal whereas three of them are Pareto optimal. One figure is not Pareto optimal because the area of one circle may be enlarged without violating the constraints. This can occur in a distributed design project because one of the other circles has been moved or modified by one of the team members.
Pareto optimality is a predicate. While one may be able to assign a quantitative metric, such as the area of the circle, the answer as to whether the global solution is Pareto optimal is ``yes" or ``no". It does not matter initially how much a circle can be enlarged, only that it can be. How much is to be evaluated after the possibility is noted. A corollary is that Pareto optimality does not address local extrema with respect to any utility. Neither does Pareto optimality provide a method for choosing among preferences or alternatives.
Nevertheless, tracking Pareto optimality is an important function for distributed agents. Detection of a lack of Pareto optimality is an alert to an opportunity to improve the design that otherwise might be missed, especially when no one engineer understands all of the design dependencies. Once such a lack has been detected, then special purpose algorithms can provide various evaluation functions that are likely to be domain-specific. Tracking Pareto optimality does not preclude such methods and it does not require an objective function that must compare ``apples and oranges'' in complex domains: it is a domain-independent function.
We illustrate the utility of tracking Pareto optimality with a scenario from our current domain: electrical cable harness design. It is important to carefully consider such an example because providing Pareto optimality as a coordination function is novel and its importance may not be sufficiently understood. While our implementation is of technical interest, it is this idea that is the main principle of this paper, and one that can be freely reused independently of our implementation.
After a careful reading, it can be seen that the following example is actually very simple, and easily generalizable to any configuration design task. What the reader should note is how quickly even such a simple example becomes difficult to follow. It becomes even more difficult in practice when each engineer is trying many versions and may be unaware of the decisions of other engineers. Even such simple problems require the "bookkeeping" provided by Pareto optimality tracking.
The design of electrical cable harnesses for missiles, airplanes, and other complex artifacts consists of configuring the topologies of cable harnesses that satisfy electrical connectivity requirements; routing cables through a three dimensional space with bending and clamping constraints; selecting connectors, shielding, and other parts; and optimizing for weight and cost.
Figure 2: Cable Design Components
There are distinct tools for 1) specifying the physical environment, 2) generating the cable topology, 3) free space routing, and 4) parts selection as illustrated by Figure 2. Different engineers may use different copies of these tools for different cable harnesses that may conflict in their routing solutions. In addition, each tool may produce a solution that may conflict with another tool. E.g., it may not be possible to generate an acceptable routing with a given topology. Or, after parts selection, the resulting path refinement may show that the initial routing is not feasible. Or the overall design manager may object to the combination of cable weights.
Figure 3: Cable Harness Environment
The role of Pareto optimality in the cable harness design scenario can be illustrated with a simple example consisting of only two cable harnesses and a few versions of each. This scenario begins with an environment in which the cables are to be placed. The environment, illustrated in Figure 3, is a space with connection points, physical obstacles, hazardous zones (e.g., high temperature, EMF, vibration, or flak), restricted spaces, and clamping points.
Figure 4: Jane's Solution: P2V2
In this scenario, there are two engineers, say Jane and Joe, attempting to configure and route cable harnesses Cable-1 and Cable-2 respectively. Cable-1 is a simple cable with no topology that is to run from connector Con2 to Con7. Cable-2 is a cable harness, with various topologies possible, that connects Con1, Con3, Con4, Con6, and Con9.
In Figure 4, we show the second routing, P2V2, of Cable-2. (The first routing went through the high temperature zone and a third version could not be clamped. A more detailed version of the scenario is available.)
Figure 5: Joe's Versions 1-5 for Cable-1
Meanwhile, Joe has had more difficulty in finding a solution for Cable-1 as shown in Figure 5. The first four tries have run into problems: these four versions are marked with an ``X''. The reader should note that, in particular, version P1V3, was blocked by the restricted zone in the upper right part of the environment. Joe finally finds an acceptable solution with version P1V5.
Figure 6: Conflict: P1V5 & P2V2
Figure 7: Jane's Resolution: P2V4
When Jane and Joe publish their solutions, some global constraints can be evaluated. A Constraint Manager, and the reader, will note that both cables pass through the same narrow area making one or both inaccessible for maintenance as shown in Figure 6. Suppose that Jane moves her cable to the left to solve the problem as shown in Figure 7. This is now local version P2V4.
The current solution consists of the current two local versions: {P1V5, P2V4}. There are at least three major types of support that could be used in this scenario: negotiation, explanation*, and change. We will briefly discuss the first two but emphasize the last in this paper. To this end, we now suppose that the restricted zone in the upper right part of the environment has been removed. This is a realistic occurrence: space is reserved for possible use until late in the design process when it is clear that the space is not needed.
Figure 8: A Better Solution: P1V3 & P2V2
It may be obvious to the reader exactly what effect this change should have on the design. However, distributed engineers in a complex design may easily miss the dependence of their various versions on not only changeable specifications but also on the decisions of other engineers. Even in this very simple example, here condensed, involving only two (2) cables and only a few versions of each, the desirability of some bookkeeping about such dependencies may be evident.The necessity for such bookkeeping becomes even more clear when one realizes that each version actually consists of subsets of versions of configurations, paths, part selections, and refinement iterations*.
What should happen as a result of the restricted space becoming free is that Joe should be notified that previously rejected version P1V3 is now possible.* Suppose that Joe now instructs the system to make this earlier version the current one.
At least one ramification of Joe's revision is that Jane should now be notified that version P2V2 in Figure 4 is possible again. If Jane takes advantage of this opportunity to improve the design, the result, as shown in Figure 8, is a solution in which both cables have improved their routing over the solution consisting of {P1V5, P2V4}. This better solution, {P1V3, P2V2} is new: it had not been previously considered. Without proper bookkeeping, this possibility can easily be missed.
In principle, the notifications to Joe and Jane can be made by detecting that the total solution is no longer Pareto optimal and assuming that earlier designs are preferred unless otherwise indicated. In the example, P1V3 was blocked by the restricted space. When the latter was removed, the current routing for Cable-1 could be improved without decreasing the satisfaction of any other objective. But then this removed a source of conflict blocking the best solution for Cable-2: P2V4. Thus, this routing could also be improved. The solution became Pareto suboptimal in both cases and this was the basis for the notifications. In the next section, we show how such tracking can be accomplished, supporting change as well as negotiation and explanation.
In order to implement a principle such as Pareto optimality, one must have a formal notion of an objective, the satisfaction of an objective, and conflicts between objectives. The Redux model of design problem solving[12] provides such formality. Only a subset of this model is needed to perform the bookkeeping duties described above. We call this subset Redux' and have implemented it as a coordination service agent[13] that performs a number of useful functions for distributed design[14]. In this section, we describe this model and show how in particular it supports the tracking of Pareto optimality. To simplify matters, we do not distinguish further the complete problem-solving Redux model and the dependency tracking subset Redux' in this paper.
In the Redux ontology, a design decision consists, minimally, of a goal (or ``objective" or ``task") that it reduces (``satisfies" or ``accomplishes"), and a result. A result is either a set of assignments and/or subgoals.
In practice, a goal or an assignment can be any arbitrary statement about the design: the representation is semi-structured. The semantics of the types, only, are determined by the Redux model. Though they have additional properties, the most important semantics of a goal is that it is satisfied when either a decision has reduced it to solely assignments, or if all of its subgoals are satisfied. The important point to make about assignments is that these are what may violate constraints.
Constraints are defined by task agents. Violations are detected either by these agents or by a generic Constraint Manager. What is communicated to Redux is that a violation has occurred, along with the constraint and the assignments involved. The semantic commitment is simply that assignments are results of decisions and are the only things that may violate a constraint. And a constraint violation may be resolved by ``taking back'' an assignment: revising a design decision. Constraint violations may also be resolved by relaxing a constraint or by removing statements about the design environment that form conditions for the constraint. For example, the overall container size may be enlarged leaving more room to route the cables.
Figure 9: Two Decisions
The Redux model of design is illustrated in Figure 9 with two decisions, P2-V2 and P1-V5. As shown, it is a constraint between the two assignments that implicitly connects the two goals. In terms of the two-cable harness scenario, one goal is ``Route Cable-1". Each goal represents a task that may be worked on by an engineer/agent independently. One assignment is path P1V5, the result of decision P1-V5 by Joe. (The name of the decision is arbitrary - in this application, cable routing decisions are automatically named after the paths they create.)
Similarly, Jane has reduced the goal ``Route Cable-2" with the decision P2-V2 with the result of the assignment path P2V2. Figure 9 also shows that Jane's decision may lead to other subgoals: e.g., to select parts and refine the path with spline fits. Illustrated is a subgoal ``Choose Shielding for Cable-2'' to be worked on by engineer James.
The incompatibility between the two is expressed as a constraint: simply not (``path P2V2'' and ``path P1V5'')*. In this case, the constraint is generated by a user using a menu and clicking on two designs.
Figure 10: A Decision Revision
Figure 10 shows the Redux model of the situation in which Jane has gone from version P2V2 to P2V4. Decision P2-V2 has been rejected because of the conflict between assignments P2V2 and P1V5. The new decision to route Cable-2 is represented by decision P2-V4 with result ``path P2V4". This figure also introduces the notion of a decision rationale.
A rationale is an optional property of a decision in the Redux model. But some rationales are automatically constructed without explicit input from an engineer/agent. In this case, Redux is told that there is a conflict between assignments P1V5 and P2V2. Redux informs Joe and Jane each that this conflict can be resolved by rejecting either P1-V5 or P2-V2. When Jane chooses to resolve the conflict by rejecting P2-V2, Redux remembers that the rationale for the rejection is the combination of the constraint and assignment P1V5. Further, when P2-V4 is made, Redux provides a rationale consisting of the rejection of P2-V2 because it knows that this is the next attempt to satisfy goal ``Route Cable-2''. The result is a rationale* for P2-V4 that consists of the rejection of P2-V2 that in turn has a rationale including the constraint and assignment P1V5.
Figure 11: Change Propagation
Figure 11 illustrates how Redux has information sufficient to provide Pareto optimality tracking. There is now an information link between decision P2V4 and path P1-V5 via the rejection of decision P2V2. When Joe rejects path P1-V5 in favor of P1-V3, Redux uses this link to notify Jane that the earlier decision P2V2 to use route P2-V2 is no longer blocked by the path P1-V5 of Cable-1.
Similarly, since the constraint itself is involved in the rejection reason, then a similar propagation of change occurs when a constraint is relaxed. For example, it was the relaxation of the restricted space constraint that allowed Joe to change the routing of Cable-1 in the scenario from P1-V5 to P1-V3.*
Figure 12: Goal Block
While this is not the main topic of this paper, it is worth noting here that this model provides several other important coordination services. For example, when P1-V2 is rejected, James working on goal ``Choose Shielding for Cable-2'' is notified that his current work may be in vain, indicated by the darkening of the goal in Figure 10. A new route may render the current work on selecting parts and refining spline fits useless. Redux can make this and similar notifications because of the links in the model as detailed in [13].
A good example of this capability is a Goal Block, illustrated in Figure 12. Suppose that Jane cannot find another way to route her cable if the first way is blocked by Joe's cable. Obviously this should be Joe's problem as well. But also suppose, as may happen, that Jane's routing depends upon a particular cable topology defined by Jack. In Redux, this may be represented as a subgoal relationship and/or a simple input to Jane's task. In such a case, both Jack and Joe should be notified. With Redux, Jane need only declare the goal blocked: Redux will notify the appropriate contributors.
Pareto optimality is modeled by defining objectives as goals, the satisfaction of these objectives as assignments, and the connection between these satisfactions as constraints. By recording decisions and generating decision rationales, the Redux model specifies linkages between the objective satisfactions (decision results) sufficient to implement a form of Pareto optimality. Specifically, detection of Pareto optimality depends upon information generated in the course of design and revision. A general look-ahead mechanism is intractable. The Redux model at least insures that the design will be Pareto optimal with respect to options already considered.
That this is useful is illustrated by the cable scenario. While Redux does not look ahead and guarantee that P2V2 will be consistent with P1-V3 (not a domain-independent task), it does give the designers the opportunity to test this new possibility that might otherwise be be unnoticed. The more one designs with revision, especially with multiple designers and engineers, the more complex become the dependencies and the more likely that Pareto optimality will be lost without notice unless a tracking system is implemented. It is especially important to notice that something other than standard version control is needed. The final scenario configuration of {P1V3, P2V2} would not have been captured by a ``snapshot" of any previous state of the whole design since the two routes had never been considered together.
In addition to preventing the loss of opportunities to improve the design as discussed above, there are two other general benefits that accrue from this approach. First, conflicts do not need to be resolved when they occur. The problem solver may decide to defer resolution of some conflicts as part of the solution strategy. This is even more important when multiple agents participate in a conflict: each would like the freedom to schedule conflict resolution. This is not possible with approaches that depend upon numerical tracking, such as [2].
This approach also ensures that at the least agents will be notified if they attempt to revisit a problem solving state known to be bad, thus avoiding thrashing. And they are guaranteed that a proposed set of decision rejections will resolve the given constraint. Together, these properties ensure that the combined set of users will not generate the same conflict over and over, perhaps in a cycle that is not easily predicted. This guarantee is unique to Redux: it is not true of systems such as that of [2] or [16] or any other that supports this kind of revision capability.
Redux represents work from artificial intelligence in two major ways. One is the model ontology. It was developed out of many experiments and represents a hypothesis that a large class of design can be represented by these types of objects and their linkages. The design strategy represented is implicitly depth-first search with dependency-directed backtracking, though there is no commitment to top-down design. Goals may be introduced in any order and subgoal linkages do not necessarily represent goal decomposition. Multiple designs are also not precluded by the depth-first search paradigm though an additional context maintenance mechanism is necessary.
One of the most important ontological commitments in the Redux model is the distinction between a goal and a constraint. They both appear to be a type of specification or requirement. What is the difference between requiring that a cable connect two parts and that it not weigh more than two pounds? The difference is indeed an arbitrary choice of representation, but it can be a useful difference. One basis for a distinction is the requirement in the Redux ontology that initially, before any relevant decisions are made, a goal is not satisfied and a constraint is not violated. For example, before any design decision is made, the electrical connections are not made but no weight limit is exceeded. This distinction is common to other systems, such as integer programming in which constraints are to be respected while some global objective is to be maximized.
It is also the case that goals typically represent specifications that can be met as a matter of degree and constraints are ``hard," though they too may be relaxed. The Redux model makes no commitment to this, but it can be shown that a problem solver may miss solutions if constraints are relaxed before all ways of satisfying a goal are tried.
An important ontological commitment of the Redux model is to distinguish between decision validity and decision optimality. This distinction is not only useful in design, but is necessary for building any coherent revision system. Many decisions are made for reasons that may later become invalid. For example, one may choose an airline flight, or a cable component, because of cost. If that cost changes, this rationale may be invalid. In the Redux model, we say that the decision optimality has been lost and in fact the decision may be suboptimal. But the flight or the component may still be perfectly possible and continue to be part of the plan or design.
But if the flight is canceled, or the component becomes unavailable, then the choice is no longer viable. The same is true if the engineer simply revises the decision for whatever reason. Now the decision is no longer valid. Any assignments that resulted from it are no longer part of the design. And work should be suspended on any of the subgoals that resulted from it* Thus he distinction between optimality and validity is useful in helping people manage change while retaining control.
The notion of validity in the Redux ontology is general and bears further comment. The general idea is that of logical validity. A proposition is either a valid inference from the axioms or not. In the Redux model, the validity of a decision is defined by formal rules and is inferred or not depending upon the state of the system: that is, Redux is a nonmonotonic system. We also say that assignments and goals are valid or invalid, depending upon whether they have the support of a valid decision. Again, this notion of validity is whether it can be inferred given the state of the system. If a goal is invalid, there is no valid reason to work on it. If an assignment is invalid, it is no longer a design feature supported by a valid design decision.
Apart from these ontological concerns, Redux is based upon work in truth maintenance as detailed in [12]. Here we simply note that the implementation of the model is not conceptually important. It could have been implemented in Prolog: the implementation decisions are about whether to cache or not and how to detect change computationally. We have chosen to use work previously done on dependency-directed backtracking that maps directly on to the concept of Pareto optimality.
In particular, the sort of ``no-good'' justification for the rejection that is automatically generated by the truth maintenance system during dependency-directed backtracking will become invalid exactly when Pareto optimality is lost[12]. Dependency-directed backtracking means jumping back to any one of the contributing decisions, as opposed to, say, chronological backtracking. However, it implies a search mechanism that ensures that one does not jump back to a search state previously visited nor omit a new possible state[11].
To elaborate briefly on the rationale to be constructed for a rejected decision, given a constraint C that is violated by the conjunction of a set of assignments {A1 ... An}, there is a corresponding disjunct of conjuncts of decisions. Each conjunct set DCi = {D1 ... Dm} corresponds to an assignment Ai: these are the decisions currently supporting the assignment. In addition, there may be an additional set of ``facts" {F1 ... Fl} upon which the constraint or its violation is conditional.
To resolve a constraint violation by changing design decisions then means rejecting all of the decisions supporting one of the assignments. Suppose the culprit is selected to be Ai. Then each of the corresponding decisions in DCi should receive a rejection rationale. This rationale will contain a reference to the constraint C so that if it is relaxed, the rationale will become invalid. Similarly, it will refer to the facts {F1 ... Fl}. And it will refer to the other assignments {A1 ... A{i-1}, A{i+1} ... An}.
Goal blocks are similarly treated: some decision must be revised to resolve the goal block. Decisions creating the blocked goal as well as inputs to rejected decisions must also be included in the rationale.
Implementation details have been previously described[12]. Rather than repeat them, it is more important here to note that this rejection rationale can be used to prevent thrashing and incompleteness. Whenever one of the other conflicting assignments or contributing facts, or the constraint, is no longer the case, the decision rejection rationale is no longer valid. Thus it is valid whenever the constraint would be violated if the decision were to be remade. And it is not valid otherwise.
The behavior of this rejection rationale is what is needed with dependency-directed backtracking to eliminate search thrashing and incompleteness. And, in the Redux model interpretation, it is also the mechanism needed to track Pareto optimality. Though Pareto optimality has been previously connected to a kind of truth maintenance[4], this mapping between dependency-directed backtracking and Pareto optimality is novel.
How is such a model to be practically implemented for distributed engineering? As with other systems that provide some sort of design rationale service, it is important that the user not be overly burdened with communications with such a service. At the same time, one must deal with legacy systems for various design tasks. Our solution is to use Application Program Interfaces (APIs) that translate between the execution of the existing code and messages to and from the Redux server to reduce the number of messages that must be sent directly by the user.
Next-Link is a framework for the distributed application of generic engineering services to cable design and similar routine engineering and configuration tasks* The legacy system in this case is a set of design tools with user interfaces, already exchanging a simple set of messages. In [14], we detail how these existing messages are translated into messages about decisions in the Redux formalism. In the current Next-Link system, we use these messages and additional ones to coordinate the design.
Messages to Redux are sent by each software agent, either through normal execution of the agent during design, or by request of the user and additional functions added to the interface.
Messages from Redux are conveyed to the engineer as ``pop-up'' mail messages in the user interface of each agent. An indicator alerts the engineer to messages from Redux. By pressing a ``button" on the interface, the user sees the message. This was easy to add to the existing interface because a message mechanism already existed in the interface.
Here we only sketch some of the messages that are exchanged in the cable scenario above. One is simply declaration of a constraint violation. This might be sent by any of the agents, but specifies the constraint and the assignments involved in the conflict. The constraint violation does not have to be removed immediately. The engineers my proceed with an ``inconsistent" design as desired. We have found that this capability is essential when engineers participate in the cable harness design process. They frequently choose to temporarily override constraints knowing that these constraints are likely to be rendered inactive by subsequent developments in the design.
Any agent may request complete information on how to resolve any existing constraint violation at any time. The Redux server then identifies the decisions supporting the assignments. This is an important task for supporting the negotiated resolution of the conflict that involves AND/OR and subsumption relationships among the decisions.
The decisions form an AND/OR tree because multiple decisions may support a particular assignment. To take an example from the thermodynamics domain, the choice of a heat exchanger may be used by one agent simply to transfer heat and by another agent to support a pipe. If the heat exchanger were involved in a conflict, Redux would notify both agents and note that both decisions would have to be rejected in order to revise the heat exchanger. This is in addition to other decisions and agents that may be in conflict with the heat exchanger. Each agent affected will receive a notification and each may ask for the AND/OR tree of possible solutions.
Redux will also note any subsumption relations between the decisions. For example, through a set of dependencies tracked by Redux, it may be that the validity of one decision depends upon another and both are involved in a conflict. Redux will note that the dependent decision should be rejected before the one on which it depends since the reverse order would cause both decisions to be rejected.
Redux allows any agent designated as a ``Design Manager" to be privileged. A Design Manager receives all notifications of conflicts. Further, though normal task agents are not allowed by Redux to reject any decision made by another agent, a Design Manager may reject any agent's decision.
The cable scenario is implemented by representing the restricted space and the cable overlay problem as constraints. The removal of the restricted space with the Environmental Editor (EE) agent is translated by the Redux API into a message to Redux that the constraint has been relaxed. This results in a message from Redux to Joe, through his Free Space Manager (FSM) agent, that route P1V5 is no longer optimal and that P1V3 is now the preferred route. When Joe agrees, the FSM notifies Redux of the change in decisions. Redux then notifies Jane, through her FSM agent, that P2V4 is no longer optimal and P2V2 is preferred.
Either engineer may also send a variety of questions to Redux requesting further explanation information about the status of the design. For example, a given decision might have been rejected for a variety of reasons. Redux will in this case generate a structured English message to Jane (based upon the generic Redux model of design) that decision P2V2 may be be optimal because the previously preferred decision P2V3 is invalid and there is no longer an overlap conflict with path P1-V5:
The path for cable 2, P2-v2,
which was generated by decision P2V2, may now be optimal.
The reason is - Decision P2V2 is preferred to
decisions P2V3 P2V4 because the fact
"shortest cable" is believed.
It had been rejected
- to resolve a violation of constraint-2,
"cables overlap",
over assignments A-9 A-3
but assignment A-9, "path P1-v5", is no longer valid
- because P2V3 overrode P2V2
but P2V3 is no longer valid.
Figure 13: Next-Link Architecture
The architecture of the current Next-Link system is shown in Figure 13. Each agent in the architecture has a basic API for communication. In the current implementation, this is KAPI: the KQML API from the SHADE project[6]. This basic agent communications protocol allows each agent to be located anywhere on the Internet. On top of this KAPI is a Redux API that implements a service-level protocol for communicating with the Redux server.
We are also implementing a service-level protocol for a Constraint Manager. We do not here detail the Redux and Constraint Manager protocols beyond noting that they are intended to be domain-independent and the Constraint Manager protocol is intended to allow a variety of constraint systems to be used for design in conjunction with the Redux server.
The messages from Redux are now sent to the software agents because a user interface already existed for such messages. An alternative is simply for Redux to send email to the user rather than the agent. Similarly, the user may send KQML messages directly to Redux. We plan to build a generic World-Wide Web interface to Redux using the HTTP capability of KAPI and have already implemented a basic forms page.
The Redux server is implemented and Next-Link can perform the two cable scenario and others. We are currently working to expand these services, increase the granularity of the design decisions visible to Redux, represent multiple parallel designs and projects, and resolve conflicts by rejecting several decisions at once though only one revision would logically eliminate the conflict. An example of the last capability is weight reduction: changing the weight of one component might technically keep the total under the limit, but it might be better to reduce the weights of several components at one time.
However, the basic support for the tracking of Pareto optimality is implemented as described. This provides a method of combining local versions for distributed version control. Conflict resolution can be delayed as desired, and problem solving ``thrashing'' eliminated. Most important, opportunities to improve the design, generated by previous conflict revision, will not be lost. This is novel functionality necessary for distributed design with conflict and revision.
Hisup Park and Andrew Conru were designers of the original First-Link system and have contributed to the current Next-Link system. The cable scenario in this paper is due to Hisup Park. Andrew Conru carefully read a first draft of this paper and made many valuable comments. The authors are also indebted to the reviewers of this paper for their many useful suggestions.
[2] Descotte, Y. & Latombe, J. (1985). Making Compromises among Antagonist Constraints in a Planner. Artificial Intelligence 27, pp. 183-217.
[3] Dhar, V. & Raganathan, N. (1990). An Experiment in Integer Programming. Communications of the ACM, March .
[4] Doyle, J. (1985). Reasoned Assumptions and Pareto Optimality. Proc. of the 9th IJCAI, pp. 87-90.
[5] Feldman, Allan M. (1980). Welfare Economics and Social Choice Theory. Kluwer, Boston.
[6] James G. McGuire et al. (1993). SHADE: A Medium for SHaring Design Knowledge among Engineering Tools. Journal of Concurrent Engineering: Applications and Research (CERA), 1(2), September.
[7] Korhonen, P. & Wallenius, J. (1990). A Multiple Objective Linear Programming Decision Support System. Decision Support Systems, 6, pp 243-251.
[8] Jintae, Lee, & Lai, Kum-Yew (1991). A Comparative Analysis of Design Rationale Representations. MIT Sloan School TR CCS TR 121, May.
[9] Park, H. et al. (1994). An Agent-Based Approach to Concurrent Cable Harness Design. Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AIEDAM), Vol. 8, pp. 45-61, March.
[10] Park, H. (1995). Modeling of Collaborative Design Processes for Agent-Assisted Product Design. Dissertation, Center for Design Research, Stanford U., January.
[11] Petrie, C. (1991). Context Maintenance. Proc. 9th Nat. Conf. on AI, pp. 288-295, AAAI Press, July.
[12] Petrie, C. (1992). Constrained Decision Revision. Proc. 10th Nat. Conf. on AI, pp. 393-400, AAAI Press, July.
[13] Petrie, C. (1993). The Redux' Server. Proc. Internat. Conf. on Intelligent and Cooperative Information Systems (ICICIS), Rotterdam, May.
[14] Petrie, C.et al. (1994). Design Space Navigation as a Collaborative Aid. Proc. AI in Design: 3rd Internat. Conf., pp. 611-623. Lausanne.
[15] Ramesh, B. &Dhar, V. (1994). Representing and Maintaining Process Knowledge for Large-Scale Systems Development. IEEE Expert, 9,2, pp. 54-59.
[16] Wilkens, D. (1988). Practical Planning, Morgan Kaufmann, San Mateo.
Charles Petrie
is a Senior Research Associate at the Center for Design
Research at Stanford University. Prior to this, Dr. Petrie was a
founding member of the AI lab at the Microelectronics and Computer
Technology Corporation (MCC). He has a Ph.D. in computer science from
the University of Texas at Austin and has published extensively on
inferencing architectures, truth maintenance, and enterprise
integration. His current research interests are concurrent planning
and design, decision rationales, and change management. Dr. Petrie is
a member of AAAI, IEEE, and ACM.
Mark Cutkosky is the Charles M. Piggott Associate Professor and
Associate Chair for Design and Manufacturing in the Mechanical
Engineering Dept. at Stanford. He joined the Design Division of the
Stanford M. E. Department in 1985, after working for several years in
the Robotics Institute at Carnegie-Mellon University and as a design
engineer at ALCOA, in Pittsburgh, Pennsylvania. Dr. Cutkosky is a
Principal Investigator of the SHARE project, director of the Dextrous
Manipulation Lab and a co-director of SIMA , the Stanford Integrated
Manufacturing Association. His primary research interests are
computer-aided concurrent engineering and robotics.
Teresa Webster is a Research Assistant at Stanford University's Center for Design Research. She has a Ph.D. in biochemistry from Oklahoma State University and prior to Stanford, worked on applying computer technology to problems in molecular biology and chemistry. Her postdoctoral work was done in the Department of Biology at M.I.T. In 1985 she joined Harvard University's Molecular Biology Computer Research Resource, and held a Lecturer appointment in the department of Biostatistics. In 1989 she became Director of Computational Development at Arris Pharmaceutical Corporation, a company founded to apply artificial intelligence approaches to pharmaceutical design. In 1993 she entered Stanford Master's in Computer Science program to obtain formal CS training.
_______________________________________________________________
Charles Petrie