NEXT-LINK Redux Prime

The NEXT-LINK Redux' Agent

Redux is a general model of design. Although a complete problem solver can be written explicitly with Redux, we hypothesize that the model is common to many design and engineering problem solvers. So we have extracted a partial implementation of this model called Redux' that captures the dependencies generated by any problem solver that can be interpreted as a Redux problem solver. This interpretation, for any given problem solver, becomes the Redux API in the Next-Link architecture.

In the Redux model of design, the design begins with goals that are to be satisfied (alternatively, tasks to be accomplished). In the scenario, the goals are to route the two cables. In order to satisfy a goal, or make progress in doing so, a design decision must be made. The results of a decision may be subgoals and/or assignments: statements about the design. In the scenario, assignments are routed paths.

In making decisions, constraints may be violated by the resulting assignments. In the scenario, the collision between the two paths is represented as a constraint violation. While goals and constraints are a matter of knowledge representation, there are differences between them in the model. Goals are initially unsatisfied. A goal is satisfied when a decision reduces it soley to assignments, or when its subgoals are all satisfied. A constraint is initially unviolated: it is only violated by assignments made by decisions.

Scenario Messages

What are the messages exchanged betwen agents, such as the Free Space Manager (FSM), and Redux'? They are too numerous to document here, but in the scenario, one is to declare a constraint with a specification of the two conflicting paths. This might be sent by the Design Manager (DM). In turn, Jane and Joe are each notified that they are involved in the conflict. Either can ask for possible solutions. Jane declares a resolution of the constraint by rejecting her path. Jane then picks a new path. Each of these actions results in a well-defined message to Redux', resulting in the decision rationales. One of several features not mentioned in the scenario is dealing with subgoals. Suppose that Jane's rejected routing also involved a subgoal that a third engineer, James, was supposed to work on: James should be told of the change as well. This is also part of the work of the Redux' agent.

In the scenario, the restricted space caused Joe to reject an earlier path that ultimately provided a rationale for the current path. When the restrion was eliminated, Redux' notified Joe of this possibility. How this is done is more easily seen in the case when Joe reverts to the earlier path and Jane is then notified. If Joe's path P1v5 is no longer valid, than the rejection of Jane's path P2v2 is no longer necessary to resolve the collision with P1v5. Since Redux' maintains a dependency between Jane's current path, P2v4, Redux' can recognize the situation and notify Jane.

The interested reader will recognize that Dependency-Directed Backtracking (DDB) rationales are being kept by Redux'. And the semantics of these rationales is that they maintain a type of Pareto optimality.

All of the messages to and from Redux' are accomplished either with email messages from Redux' directly to the user, or with "pop-up" menus on the users' tool, such as the Cable Editor (CE) or the FSM. For example, Jane may receive a message that the earlier path, P2V2, is now (Pareto) "optimal". Jane may receive the message either in email or on the tool being used as a pop-up message. The actual text of such a message is:

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.
The complexity of such messages is still problematic, but the meaning is that while P2v3 was initially preferred to P2v2, the former was rejected. This leaves P2v2 as the best choice, since the collision with P1v5 is no longer applicable.

Goal Blocks

If you have read this far, your patience may extend to considering the problem of goal blocks. What if, after the collision with Joe's path, every design Jane tried was too heavy or too expensive? This should be Joe's problem too, because it is his cable that is blocking her single solution. Redux' will remember this and will also help when the problem is not so obvious, in the case of subgoaling. Suppose that Jane's goal to route Cable-2 was a subgoal of a previous decision on how to route the cable made by Jack. In this case, Jane is constrained in her choices by both Joe and Jack and both should be notified in this instance, which is created by Jane simply declaring to Redux' that her goal is blocked. She need not mention the other decisions: Redux' will identify them and notify the appropriate users.

What the user should carry away from this page is the idea that even simple scenarios with well-understood domains quickly lead to coordination complexity. "Bookkeeping" agents such as Redux' are useful for managing this complexity. Design Rationales are a useful by-product of this bookkeeping. And there are many potential applications: all modern airplanes and civil engineering projects, for example, may benefit in cost and time from the application of such distributed engineering management.

Further Reading

Redux can be better understood with an example from another domain. The functionality is simple but is novel with respect to other approaches to coordinating distributed design. As a brief last note on the topic, Redux' implements a notion of authority. Only agents that made a decision may reject it, except for the Design Manager, which may reject anyone's decision.

To see how the proposed approach relates to similar research, including SHADE, please see the related research.

MAC users may retrieve compacted self-extracting binhexed copies of a PowerPoint 3.0 presentation of how Redux is used to achieve the scenario. (50K)

______________________________________________________

Charles Petrie