Combining Constraint Propagation and Backtracking for Distributed Engineering

This work was funded by Navy contract SHARE N00014-92-J-1833 under the US ARPA DSO (formerly SISTO) MADE program.

An Engineering Constraint Manager Agent

We are exploring one obvious approach: KQML-based agents. With this technology, one can ``wrap'' legacy tools (e.g., CAD systems) with software, usually called Application Program Interfaces (APIs), that allow them to communicate via a common agent protocol, in this case, KQML[Finin 1992] We are attempting to define reusable, generic KQML-agents useful for engineering design. We call the whole framework of reusable messages and agents Process-LinkF0.
F0:{ This is a development and abstraction of the Next-Link research project documented at http://cdr.stanford.edu/NextLink/NextLink.html on the WWW.

The core generic agent is Redux'[Petrie 1993]that assumes a particular model of the design process consistent with the fact that some design decisions are to divide an issue or a task into subissues or subtasks, and/or to make statements about the design. Thus we say a decision consists minimally of a goal (the issue or task), and results, consisting of at least one subgoal or at least one assignment (a statement about the design). Constraints may be violated by some set of assignments. Constraint violations are resolved by problem solvers rejecting/changing decisions that resulted in conflicting assignments.

This model is consistent with the generate-and-test model of design. A decision is made, assignments generated, and a test made to see if the assignment is consistent with the set of known active constraints. If not, the user may choose to leave the design inconsistent, or, at any time, may reject one or more of the decisions that led to the inconsistency. One important function of Redux' is to remember that the rationale for one decision might be the rejection of another, and, in turn, the reasons for the rejection. This detail has been documented elsewhere[Petrie 1995]and is outside the scope of this paper, but the basic functionality is dependency-directed backtracking (DDB)[Stallman and Sussman]

Generate-and-test with DDB allows for incremental rejection of design decisions, and thus the maintenance of rejection reasons useful for design. But generate-and-test is much less efficient than constraint propagation for many engineering problems. Thus, some constraint solver should be combined with Redux'. A major challenge is to be able to combine DDB with constraint propagation and generate rejection reasons as needed.

Moreover, there are many different kinds of constraints; e.g., algebraic with continuous domains, symbolic with discrete domains, etc. And there are many different extant constraint satisfaction systems. Our goal, therefore, was to construct a generic Constraint Manager (CM) that would allow different solvers to ``plug and play'', route constraint solving requests to appropriate solvers, and send not only consistency information, but also rejection reasons as needed to requesters. And the messages exchanged between the CM, Redux', solvers, and requesters should be domain-independent.

We also noted that the basic constraint formalism of variables is not sufficiently structured for engineers who want to reason about which type of object to use in an assembly based upon its features and problem requirements. Thus the CM had to not only translate among solvers but also to include a better engineering formalism.

While we have made substantial progress on these two issues with the CM, this paper reports on the fundamental issue control of problem solving and combining constraint propagation and DDB.

Control of Constraint Solving Issues

• Constraints and variable domains change during problem solving. A constraint or variable may be the result of a specific design decision, which may later be rejected in favor of another decision. This revision is unlimited. For example, as engineers decide to use a part, new variables corresponding to its features come into play. If the part is discarded (perhaps only temporarily) from the design, so are those variables and associated constraints.
• Especially in collective problem solving, incremental reasoning is important in engineering design. If the constraints or domains change, it is inefficient to start from scratch and resolve the whole problem each time. Perhaps more important to the user, the resulting answers may be very different from the current context of problem solving[Dhar 1990].
• Engineers want control over problem solving. They don't want a constraint satisfaction system to give them the answer; they want information about consistent alternatives[Park 1992]. They may even want to live with some inconsistencies for a period of problem solving.
• Since most constraint propagation algorithms do not ensure global consistency, backtracking is necessary. This is also true for overconstrained problems and for many situations where generate and test is an appropriate problem solving strategy. In these cases, engineers want to know the constraints, domains, and decisions that might be changed to remove the inconsistency[Park 1992].
• In distributed collective design, changes in constraints, variables, domains, and assigned values have various effects on design decisions by different engineers. These effects should be noted.

Task Decomposition

Separating problem solving from constraint propagation allows more control over problem solving. We extend this notion to say that there is a general service of consistency management that includes constraint propagation before decision making and consistency checking afterwards. (Also included is the matching of constraint types to constraint solvers and the translation of constraints and results among them.)

We extend further this decomposition in identifying a separate task of dependency-directed backtracking (DDB) bookkeeping that is especially important for incremental revision by multiple problem solvers with dynamic constraints and domains. In order to determine the incremental effects of changing conditions, more DDB support is required than is provided by strictly constraint-based approaches such as Dechter's dynamic constraints[Dechter and Dechter 1988] or even the backtracking included in [Mittal and Falkenhainer].

The problem solver can not only make choices of values to be assigned to variables, but can also reject these assignments at will. This may occur in response to a constraint violation. DDB support provides the problem solver, upon request, with the AND/OR tree of assignments responsible for the conflict. Given a set of assignments to reject, the reasons for the rejection should be noted in order to 1) avoid thrashing and 2) determine when the rejection is no longer necessary.

This bookkeeping is especially desirable if constraints and variable domains can change. Part of this task is to determine the effect of these changes on the current solution and inform the affected agents. For instance, the deletion of a constraint may mean that a known conflict is no longer the case and an earlier preferable solution may be possible[Petrie 1995]. Not only variable assignment values, constraints, and domains, but also choices about goal composition may be revised in response to constraint violations. The DDB bookkeeping must be done in all cases. In particular, we say that a goal, variable value assignment, constraint, variable domain definition, or rejection is valid or valid depending upon conditions determined by the problem solverF1.
F1:{ "Validity" in the Redux model is analogous to the classical logical sense of being a valid consequence, usually denoted by the entailment symbol.}

Consideration of the DDB bookkeeping task suggests more work for the consistency management task. Constraint propagation and DDB are dissimilar constraint satisfaction techniques. The former filters out some inconsistent values prior to a choice. The latter is used when further inconsistencies necessitate rejection of choices. But overconstrained problems are common. In these cases, DDB needs to consider constraints and choice of domains as well as assignments used to filter choices during constraint propagation. Then consistency management must perform some K-consistency algorithm[Freuder 1978] to generate rejection reasons that include these constraints and domains for use by the DDB bookkeeping function.

Agent Responsibilities and Interactions.

Figure 1: Constraint Solving Tasks and Agents

Agent technology provides a good structure for separating tasks and making generic functionality easily available. These task divisions of Section 3 suggest agent responsibilities and interactions. The problem solving is performed by domain-specific agents, DDB bookkeeping by Redux', and consistency management by the Constraint Manager, as illustrated in Figure 1, which also suggest some of the messages that must be passed between such agents.

Definition of the messages to be exchanged and the functional responsibilities of the agents is a major technical challenge. We describe here the overall principles. A full description of the KQML messages that the current implementations exchange is beyond the scope of this paper. The types of messages exchanged between a problem solver and Redux' are covered in [Petrie 1995]. The basic messages from the problem solver to the CM are requests for elimination of variable domain choices via constraint propagation. The CM will return the consistent vs inconsistent choices. The CM also performs automatic consistency checking as variable value assignments are made. The CM remembers consistency requests and replies and will later initiate a message if changes, such as a domain change or an assignment being made, would cause a different response, including an overconstrained condition in which no choices are any longer consistentF2.
F2:{See http://cdr.stanford.edu/NextLink/papers/protocol/performatives.html and http://cdr.stanford.edu/NextLink/ConstraintManager/constraint-manager.html for details.}

For interaction with the CM, we allow variable domain definitions to be a special case of assignments. Thus, a decision might result in the assignment Domain-Definition (section-modulus beam-1) [3-15], which may be changed later in problem solving.

Addition or relaxation of a constraint, a change in a domain definition, or the addition or invalidity of an assignment may mean that a reply by the CM to an earlier consistency question may need revision. Redux' will always inform the CM of constraint-related changes. The CM keeps a record of variable consistency requests and replies for the duration of a project. If the current change involves one of these variables, the CM will recompute consistency and inform the requesting agent if the new consistent domain is different from the old one. The domain-specific agent may in turn decide to revise its design decision, causing further incremental changes to the design state.

A special case worth noting involves the ``activation'' of constraints by the CM. If a variable domain definition is removed by the rejection of a decision, and not replaced by a new one, then the variable is not currently important for problem solving. For instance, if there is no valid assignment of a value to the variable
(section-modulus.beam-1) and no valid domain definition for this variable, then Redux' notifies the CM, which omits constraints with this variable from further consistency checking or propagation, even if the constraint is valid.

The problem solver may also request rejection reasons. Suppose that the CM tells an agent that no values in the domain of a variable are consistent. The agent would then like to know why. Doing so requires that the Redux' agent and the CM work together to generate rejection reasons sufficient for control of problem solvingF3.
F3:{ Redux' actually does more than is what is commonly referred to as ``dependency-directed backtracking'' in many systems, such as those analyzed in [Balkany 1993]. The latter only identify the ``nogoods'' and allow the search to be recontinued at any one of the choices responsible for the conflict, without affecting the others. Redux' additionally tracks the reasons for the conflict and ensures that the search will not thrash, as noted in [Petrie 1995]}.

In the case where all possible variable values are ruled out by constraint propagation, upon request, the CM will use a K-consistency algorithm[Freuder 1978] to generate the variable assignments and domains and constraints that directly caused the inconsistencyF4. The CM furnishes this information to the Redux' agent, which then determines which decisions by which agents were responsible for these assignments, domains, and constraintsF5.
F4:{ This idea was first suggested by Juergen Paulokat in 1995 in work on his dissertation.}
F5:{ An AND/OR tree of resolution possibilities is generated since more than one decision can result in the same variable assignment.}

The Secretaries' Nightmare

The problem can be summarized as follows:

Constraints: all-day meetings on weekdays in April; first meeting includes Axel, Brigitt, Dirk; second meeting includes Axel, Brigitt, Carl; if these two meetings are not held back-to-back, a third meeting, in between these two, must be held between Carl and Dirk; Carl is not to attend the first meeting.

Preferences: Back-to-back meetings and earlier dates.

Conditions: No central organizer, each person is free to change published availability dates as convenient or private schedule changes, Dirk and Carl can change the third meeting constraint, anyone can propose or reject dates.

Domains: Axel is available in April the week of the 4th, the 18th and 19th, and the 25th and 26th. Brigitt is available the 7th, 8th, 19th, and the week of the 25th. Carl is available on the 7th, 19th and 26th. Dirk is available on the 7th, 8th, 18th, and 25th.

Modeling: Our method does not take into account how agents come to agree upon variable names, goals, etc. We assume that the agents propose common variables, domains, and constraints. Let Axel's meetings be A-M1, A-M2, A-M3, with similar notation for the others. The constraints are sent to Redux' by any one of the participant agents in
Constraint-Def statements that include a constraint name, expression, and list of variables. We list the constraints here in the form : :

C-1: (> Date.M1 Date.M2),
C-2: (= Date.A-M1 Date.B-M1 Date.D-M1 Date.M1),
C-3: (= Date.A-M2 Date.B-M2 Date.C-M2 Date.M2),
C-4: (= Date.C-M3 Date.D-M3 Date.M3),
C-5: (AND (> Date.M2 Date.M3) (> Date.M3 Date.M1))
C-6: (= Date.M2 (+ 1 Date.M1))

Figure 2: Two Possible Initial Decisions

There are various ways the agents could model their Redux' decisions. One we will use will be to make the scheduling strategies explicit. So, we say there is a top-level (root) goal of, say, ``Assign Meeting Dates for M-1 and M-2'', called Schedule-Meetings. There are two possible decisions to be made, according to the preferences. One is to schedule back-to-back and the other is to schedule three meetings. Let us call the first decision Back-to-Back and the second Three-Meetings. Both decisions have goal Schedule-Meetings and, as results, subgoals Choose-M1: Choose Date for M1 and Choose-M2: Choose Date for M2. However, these decisions differ in that Three-Meetings posts a third subgoal of Choose-M3: Choose Date for M3. We also extend the Redux model by allowing a new constraint to depend for its validity on a decision. In this case, were the decision Back-to-Back to be made, Redux' would inform the CM of the constraint C6: (= Date.M2 (+ 1 Date.M1)). The
Three-Meetings decision results in the constraint C-5: (AND (> Date.M2 Date.M3) (> Date.M3 Date.M1)) . These two possible decisions for goal Schedule-Meetings are illustrated in Figure 2 with goals as ovals and decisions as triangles.

The problem solving scenario can be organized in steps. For each step, we explain how the Process-Link agents would interact. Each of the meeting participants is an agent.

Step 0: Each agent publishes a domain definition; e.g. Domain-Def Date.A-M1 {4,5,6,7,8,18,25,26} and Domain-Def Date.A-M2 {4,5,6,7,8,18,25,26}.
Issue: Like constraint definitions, domain definitions are first sent to Redux'. Redux' always forwards constraint and domain definitions to the CM because these definitions and may depend upon decisions. Agents make changes to constraints and domains either directly, or indirectly through decision revision, and Redux' informs the CM of such changes.

Step 1: Upon requests by each of Axel, Bridget, and Dirk, the CM indicates two consistent solutions for the two meetings: [7, 19] and [25, 26]. Axel proposes that the earlier preference overrides the back-to-back meeting preference, makes decision Three-Meetings, and goes on to make decisions for Choose-M1 and Choose-M2 resulting in the assignments Date.M1 := 7 and Date.M2 := 19, respectively. Redux' communicates these assignments to the CM. All the agents have registered an interest in such assignments, so they are notified as wellF7.
F7:{ This is a Redux' feature called RequestFeature.}.

Step 2: The requirement for a third meeting to be scheduled is only now introduced as the goal Choose-M3. Carl and Dirk send their domain definitions for the associated variables. Before anyone requests the CM for consistent values for Date.M3, the CM detects that the problem is now overconstrained as soon as Redux' passes along the domain definitions. The CM now determines that the reasons are constraint C-5, the assignments Date.M1 := 7 and Date.M2 := 19, and the domains for Date.C-M3 and Date.D-M3.
Issue: The issue here is the ``activation'' of constraint C-5. In order to simulate backtracking functionality as well as to illustrate control of constraint solving, this constraint should not to be considered initially. We choose to make the constraint directly upon that decision Back-to-Back, rather than add conditions to the constraint. This has the advantage that as the Three-Meetings decision is made and rejected, constraint C-5 comes and goes, and is considered by the CM only when appropriate. Constraint C-6 is modelled similarly.

A notice of the conflict is sent by Redux' to all of the participants, as all of their domain definitions are implicated. Axel asks Redux' for the reasons and Redux', based on information from the CM, includes the decision Three-Meetings as one of the causes. Axel responds by changing the decision to Back-to-Back, resulting in deactivation of C-5 and activation of C-6. Variables Date.C-M3 and Date.D-M3 are no longer considered. After making a consistency request to the CM, Axel assigns Date.M1 := 25 and Date.M2 := 26.

Step 3: However, now Dirk objects to the scheduled meeting as being too late and rejects Date.M1 := 25. The CM reports the problem is now overconstrained. All participants are notified as their domain definitions are implicated. Someone must expand their domain.
Issues: The problem solvers are free to reject solutions. If the problem becomes overconstrained, the CM and Redux' can state the reasons, including domain definitions. The key constraint in this case is C-6.

Step 4: Brigitt offers to cancel another meeting and be available on the 18th by sending a new domain definition. Redux' tells everyone that the (overconstrained) conflict is resolved and notifies the CM of the change. Remembering previous consistency requests, the CM notifies everyone that the two meetings can be held on the 18th and 19th. Dirk chooses to keep the Back-to-Back decision and remake the decisions about the choice of meeting dates for M1 and M2, resulting in the assignments Date.M1 := 18 and Date.M2 := 19.
Issues: The CM notification is based on a change to a previous response. Also, the context of scheduling back to back meetings is maintained.

Step 5: Then Carl's schedule changes so that he is available on the 8th. This change in his domain causes Redux' to send two messages: one to Axel suggesting that the Three-Meetings decision, together with [7,19], may be possible after all, and one to the CM, notifying it of the domain change. The CM sends Axel, Brigitt, and Dirk messages confirming that [7,19] is available because the third meeting can be scheduled on the 8th. Even better, the CM will note a back-to-back meeting on [7,8] is now possible. Brigitt, in order to make the 18th free again, changes the date decisions to result in the assignments Date.M1 := 7 and Date.M2 := 8.
Issues: Redux' volunteers information about a possible change to an earlier context. The CM volunteers complementary information about variable value possibilities, based upon previous interest.

Step 6: Axel objects saying that he has already planned another meeting in Los Angeles on the 19th to take advantage of his presence there. He takes up the Redux' suggestion of Three-Meetings, reverts to this decision and to the decision for
Date.M1 := 7. (The decision for Date.M2 := 19 is unchanged.) The goal to have a third meeting is reinstated and and satisfied with a decision that Date.M3 := 8.
Issues: Problem solvers are free to use the volunteered information at any time. If it were no longer the case that this option was available, Redux' would not let the decision be made. In this case, as soon as the context changed, constraint C5 was in force, C6 was not, and the goal of choosing a value for M3 was again valid.

Problem Summary:

This problem shows that it is simple and yet difficult to support formally. Further, the difficulty of following even this simple example illustrates the need for a bookkeeping and notification service. The problem is representative of engineering design in which domains and constraint change as components are added and deleted from the design and designers change their preferences. In particular, it illustrates control of problem solving strategy by the users interleaved with constraint propagation and dependency-directed backtracking and the nature of the interactions between the agents.

Conclusions

The backtracking bookkeeping also should prevent problem solving thrashing. Though not illustrated, the problem solvers are free to pick inconsistent solutions and delay their resolution indefinitely. However, problem solvers are not allowed to rechoose a rejected decision while the reasons for the rejection are still valid. Moreover, these rejection reasons are used to warn problem solvers if they may be entering in a cycle of making and rejecting old decisions.

Further, consistency calculations must be based on the current state of problem solving. This means the CM needs to be notified by the bookkeeping agent whenever the validity of a constraint, domain, or value assignment changes, as well as of the addition of new ones. In turn, the CM needs to remember previous consistency requests by problem solvers, and notify the requester later if the answer would be different given the change of state detected by the bookkeeping agent.

What does the problem illustrate? First, notice that the representation of C-5 can be very simple. It need not have any conditions about whether the other two meetings are back-to-back, as that is modeled in the decision itself. There is no need for a exists relation, which does not properly belong in constraints anyway. The constraint comes into play only when appropriate. While this condition could be modeled within the constraint itself, it imposes more work on both the constraint writer and the constraint solver, and such conditions may not be easy to express in more complicated engineering design problems.

Second, the need for backtracking is fundamental for hard (read practical) problems. The revision and notification illustrated could not be handled by any of the systems at the workshop from which this example was drawn and has caused problems in others. In this problem we show:

• The bookkeeping agent suggesting a previous solution,
• the CM suggesting a previous solution,
• the CM and bookkeeping agents generating the reasons for rejection of alternatives, and
• the problem solving agents free to choose and reject solutions based on arbitrary preferences.

The implementation status is that we have a prototype CM and message protocol implemented that can solve the secretaries' nightmare problem in conjunction with Redux' within the Process-Link agent framework. The CM works with the Next-Link electrical cable harness design application and we are developing other applications within the mechanical engineering domain while refining the agent message protocol, as well as the constraint notation and the ability to incorporate different types of constraint solvers.

Bibliography

[Balkany 1993] Balkany, A., Birmingham, W.P., Tommelein, I.D., ``An analysis of several configuration design systems,'' AI/EDAM7 1), 1-18, 1993.

[Bowen and Bahler 1992] Bowen J. and Bahler D., ``Task Coordination in Concurrent Engineering'', Enterprise Integration Modeling, C. Petrie, ed., MIT Press, October, 1992.

[Dhar 1990] [Dhar 1990] Dhar V. and Raganathan N., ``An Experiment in Integer Programming,'' Communications of the ACM, March 1990.

[Dechter and Pearl 1989] Dechter R. and Pearl J., ``Tree clustring for Constraint Networks,'' AI 38 353 - 366, 1989.

[Dechter and Dechter 1988] Dechter, R.J and Dechter, A., ``Belief Maintenance in Dynamic Constraint Networks, Proc. AAAI-88, St Paul MN, 37-42, 1988.

[Finin 1992] Finin, T., Fritzson, R., & McKay, D., ``A Language and Protocol to Support Intelligent Agent Interoperability,'' Proc. of the CE & CALS `92 Conf., Washington , June 1992. See also http://www.cs.umbc.edu/kqml/ on the WWW.

[Freuder 1978] Freuder, E.C., ``Synthesizing Constraint Expressions,'' Communications of the ACM, 1 11, 958 - 965, 1978.

[Gaertner and Miksch 1995] Gaertner, J. and Miksch, S., ``Shift Scheduling with the Projections First Strategy," Oesterreichisches Forschungsinstituts fuer Artificial Intelligence - OeFAI, Technical Report, Vienna, 1995.

[Mackworth 1988] Mackworth, A., ``Knowledge Structuring and Constraint Satisfaction:The Mapsee Approach,'' IEEE PAMI, Nov. 1988.

[Mittal and Falkenhainer] Mittal, S. and Falkenhainer, B., ``Dynamic Constraint Satisfaction,'' Proc. AAAI-90, 25-32, MIT Press, 1990. [Park 1992] Park, H., Lee, S., and Cutkosky, M., Section 5 of ``Computational Support for Concurrent Engineering of Cable Harnesses,'' Proc. Computers in Engineering Conference, San Francisco, 1992.

[Petrie 1993] Petrie, C., ``The Redux' Server,'' Proc. Internat. Conf. on Intelligent and Cooperative Information Systems (ICICIS), Rotterdam, May, 1993.

[Petrie 1995] Petrie, C., Webster, T., & Cutkosky, M., ``Using Pareto Optimality to Coordinate Distributed Agents,'' Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AIEDAM), 9, 269-281, 1995.

[Stallman and Sussman] Stallman, R. and Sussman, G., ``Forward Reasoning and Dependency-Directed Backtracking,'' Memo 380, Massachusetts Institute of Technology, AI Lab., Sept. 1976.