3.1. Facts and justifications

The (A)TMS treats each property in the current configuration state as an atomic proposition that we call a “fact.” Table 1 lists some facts that occur in Scope Selection. For example, the property that “Selling Products & Services” is selected is represented by the fact BP_SPS. A fact is only a valid part of the configuration if it is justified. To this end the (A)TMS maintains a set of “justifications.” Each justification encodes a logical implication: ?justificand → ?fact where ?justificand is a conjunction of other facts that allows inferring ?fact. If ?justificand is the empty conjunction then ?fact will hold unconditionally and the justification is termed an “independent justification.” Figure 3 depicts some justifications used in Scope Selection. For example, it contains an independent justification for BT_SPS.

Fig. 3.

Example justifications corresponding to the Business Adaptation Catalog (BAC) rules in Figure 1.

Justifications are annotated with additional information about their source (the so-called “owner” of the justification). For example, the justification BT_SPS → BP_PP is linked to the BAC rule that spawned it. This is a feature used in explanations but we do not elaborate on it further here. More important, justifications are categorized by an attribute, “strength.” The strength of a justification s is a positive number that is used to categorize the justification based on the two defined constants c_strong and c_user (where c_strong > c_user). There are three categories as follows:

1. 1. Strong justifications (s ≥ c_strong): These are due to constraints.

2. 2. User justifications (c_strong > s ≥ c_user): These are stated on behalf the user.

3. 3. Default justifications (c_user > s > 0): These encode defaults.

There is a unique special fact false that encodes inconsistency. A constraint violation (inconsistency or “conflict”) is recorded as a strong justification for false. BT_SP ∧ ¬BT_SP  →  false is an example of a conflict depicted in Figure 3.

In Scope Selection all facts and strong justifications are entered into the (A)TMS at the time of initialization of the configuration. In order to keep things simple we limit our exposition to this scenario in the sequel, although facts and justifications can be introduced to and removed from the (A)TMS at any time.

The (A)TMS determines which facts are parts of the current configuration state. These facts are assigned a logical status s_in. Facts with independent justifications have status s_in. In addition, a fact has status s_in if it has at least one justification with overall status s_in, that is, where all facts in the justificand have status s_in. All facts that are not assigned status s_in are considered to be “unfounded” (have status s_unfounded). We revise this slightly in the next section in connection with the concept of “dropping a choice.”

The configuration state is inconsistent if false has status s_in. Table 1 also gives the logical status of the facts that results from the given set of justifications depicted in Figure 3.

3.2. Choices

The user can directly express that they support a particular property (fact) by means of a user justification. They can later change their mind about previous decisions or choose to forego defaults and user selections in the process of juggling alternatives in search for an acceptable consistent overall configuration solution. The (A)TMS must both support the user in juggling alternatives and provide a means for a consistent “undo” functionality, that is, allow the user to revert back to previous steps without any visible side effects.

We call facts the user can directly influence (including the defaults) “choices.” More formally, we define the term “soft justification” to cover both user justifications and default justifications. A fact justified by at least one soft justification is termed a “choice.” A choice with an independent soft justification is an “independent choice.”

Note that a fact with an independent strong justification is a “premise.” A premise cannot be a choice because the user has no influence on its validity. In addition, a choice without a soft justification whose justificand has overall status s_in is considered to be inactive as a choice.

The (A)TMS supports the following operations:

• • The user or an agent on their behalf can communicate a new user justification. This may turn a fact into a choice, or it may add a soft (user) justification to an already existing choice. Such user justifications are usually (but must not be) independent justifications.

• • If a user justification from the (A)TMS has been asserted “in error” it may be retracted. This would happen in the context of an “undo” operation. It may remove a choice if the fact has no other soft justifications.

• • Normally, if the user is willing to forego a choice they will “drop” it as a whole. Formally, this results in disabling all soft justifications of the choice. (In particular, the user can drop a choice that is only due to default justifications, thus overruling the default.) The disabled justifications are not physically removed from the (A)TMS but they are ignored when determining the facts to be assigned status s_in. A dependent choice can only be dropped if it is active as a choice.

• • The user can “pick” a dropped choice. This is the inverse function to dropping a choice. It means reenabling all soft justifications. A dependent choice can only be picked if it is active as a choice. [The application may decide to ensure that a choice picked by the user has/gets a user justification, but this is a decision outside the (A)TMS.]

In conjunction with choices we introduce the additional logical status s_out. A fact has status s_out if it does not have status s_in, but could be switched to status s_in merely by picking choices (i.e., without adding new justifications). A fact that has neither status s_in nor s_out has status s_unfounded.

When deciding which choice to automatically drop in case of a conflict it is important to take the strength of its soft justifications into account. We define the strength of a choice to be the highest strength of its founded soft justifications (enabled or not). (A founded justification is one whose justificand contains no unfounded facts). Note that dropping or picking a choice will not affect the strength of any choices.

3.3. Assumption-based TMS (ATMS)-like label calculation

In order to automatically decide which choices to drop in case of a conflict, to provide guidance to the user in resolving conflicts and removing unwanted facts, and to facilitate exploring alternatives in general, the (A)TMS can calculate the minimal logical support in terms of choices for selected facts. This calculation is performed on demand for selected facts only and then incrementally maintained for these facts. The idea of calculating minimal logical supports on demand is not new: an approach is presented by Petrie (Reference Petrie1992, Reference Petrie1993) in which the minimal set of “decisions” that support a constraint violation is produced upon request. Retraction of such decisions, similar at least in intent to our “choices,” removes the violations. This is done with a model above the TMS, which in this implementation is a JTMS. However, the dependency-directed backtracking of the underlying JTMS in Petrie (Reference Petrie1992) versus the (A)TMS labeling in this paper is a fundamental utility for determining this minimal set.

Our calculation of minimal supports derives from the ATMS labeling defined by De Kleer (Reference De Kleer1986a) for the ATMS, and we refer to the minimal support of a fact as its “label.” Because this is based on the concept of “choices” rather than “assumptions” we might call our component a choice-based TMS, but we chose to stick with established terms. We place the “A” in parentheses to indicate that there are some deviations from the original definitions of De Kleer (Reference De Kleer1986a).

We first introduce the terminology. An “environment” is a logical conjunction of choices (implemented as a set). An environment is “active” if all of its choices are active and picked. Otherwise it is “inactive.” A “label” is a disjunction of environments (implemented as a set). A fact that has status s_in will have at least one active environment in its label (when calculated). An environment in the label of a fact means that the fact can be derived from the set of choices in the environment but not from any proper subset of these choices. Table 1 also shows the labels for selected facts. An environment that allows deriving false is called a “nogood.”

Labels can be characterized as follows [Fig. 4 summarizes the two basic operations on labels: addition (⊕) and multiplication (⊗)]:

• • Labels are kept minimal: logically redundant environments (supersets) are removed. A nogood can be removed from any label other than that of false. Hence, the nogoods are always computed as a prerequisite to computing other labels if and only if the configuration state is inconsistent as determined by the JTMS functionality.

• • The singleton environment of a choice c is in the label of c regardless of whether c is an independent choice or not (this differs from de Kleer, Reference De Kleer1986a).

• • The label of a conjunction of facts is the product (⊗) of the labels of all of the facts in the conjunction. The label of the empty conjunction (left-hand side of an independent justification) is the empty environment, designating unconditional truth.

• • The labels of the justificands of all strong justifications for a fact are added (⊕) to its label.

• • If a choice is conditional (i.e., it is not independent), a conditional label is maintained separately. This is the sum (⊕) of the labels of the justificands of all its soft justifications. The conditional label plays a role in determining the activation status of a choice and can be used for more detailed explanations. In Table 1 the choices BT_SP and BT_CR are conditional choices with conditional labels BP_PP ∨ BP_SPS and BP_SPS (not shown in Table 1), respectively.

  Fig. 4.

  The addition and multiplication of labels.

  

We give an example of why it is opportune to have the singleton environment of a dependent choice in its label (as opposed to the ⊗ product of its conditional label with the singleton environment). In Figure 3 we see that BT_MAT is selected when BT_SP has status s_in because of a strong justification. In the setting of Table 1BT_SP is a dependent choice (a default that only holds if BP_PP holds as well). Now the label of BT_MAT gives its minimal support. The “immediate” support is the default justification. Of course, BT_MAT will also be switched to s_out if BT_PP is removed from the configuration by dropping both (user) choices in its label, but there is no need to consider this if the user simply wants to remove BT_MAT. Hence, the total information can be reconstructed using the conditional label if needed, but only the immediate support is expressed in the label (and propagated).

Because rapid dropping and repicking is to be supported, it is not opportune to remove inactive environments from labels. If a choice is dropped, all environments that contain the choice are simply deactivated. If the choice is repicked, the corresponding environments must be checked to see if they should be reactivated. In addition, any environments in a label that had not been propagated in the label calculation must be propagated on reactivation.

If a label cannot be calculated within allocated time or space resources then the union of all environments in the label is calculated as a fallback. This is a much easier calculation, but still useful. Assume we have an inconsistency and the union of all nogoods. Then it is clear that at least one of the choices in this union must be dropped. After a decision to drop one is made, the nogoods (or their union) must be recalculated and the process continues until the inconsistency is resolved. Thus far, this fallback calculation has not been invoked in conjunction with Scope Selection.

3.4. Retracting justifications

If strong justifications are retracted, many internal computations must be redone, particularly if the set of nogoods is potentially affected. Retracting a soft justification is easier. The effect retracting a soft justification can have is similar to that of dropping a choice. It differs in that it can affect the strength of a choice or remove a choice entirely. If only the strength is affected this may cause a revision of automatically dropped choices (see Section 3.5). If the choice is removed this will cause removal of environments as well.

Although a configuration session ideally consists of just adding justifications and dropping and picking choices, retraction of soft justifications is also needed to be able to provide an “undo” function without any side effects.

3.5. Declarative handling of defaults

To deactivate a nogood it suffices to drop one choice in the nogood. This can be done automatically in a declarative fashion if the decision to do so is unambiguous and independent of any processing order. This is done in the (A)TMS based on the strength of choices.

Given a set of founded justifications J and a set of (manually) dropped choices there is a unique set of choices that is dropped automatically by the (A)TMS. This set can be constructed iteratively as follows: let D be the overall set of dropped choices (initially only the manually dropped choices). Let N be the set of active nogoods that have a unique minimal (strength) choice given J and D. Order N by descending strength of minimal choices. Drop the minimal choice in the first nogood in N. Remove any now inactive nogoods from N (at least the first element). N is still ordered by descending strength of the least preferred choices. Repeat the above process until N is empty. Note, that when dropping a minimal choice for some nogood in N this choice cannot be stronger than any minimal choice of a previous element and will thus not make it necessary to revise dropping previously dropped choices.

Although the set of automatically dropped choices is defined as above, the (A)TMS provides an incremental mechanism to determine which choices must be automatically dropped or repicked when changes to either justifications J or the manually dropped choices occur.

As a matter of principle, choices because of user input should never be dropped automatically. This is the origin of the basic distinction between user and default justifications. Hence, in practice, we restrict N to nogoods with minimal default choices. If user choices are also dropped automatically, then more elaborate explanations or messages are required.

3.6. Declarative handling of incompleteness in the ATMS

The configuration must be not only consistent but also complete. In Scope Selection there are requirements that at least one of a set of BAC items is selected. The added difficulty in an interactive setting is that the case that some items in such a set have not yet been specified (incompleteness) must be distinguished from the case that they are all intentionally deselected (constraint violation).

The BAC items correspond to CSP variables with possible values selected or deselected. However, the (A)TMS as a propositional system has no notion of a problem variable. Consequently, in the IPC completeness is handled procedurally outside the CCE (mainly by checking if a required variable assignment is indeed present). There is, however, a special representation used there to represent an intentionally unspecified variable and to allow constraints to act on this. This is a fact stating that a variable is “nil” (unassigned). We call such a fact a “nil facet fact” and represent it as nil(v), where v denotes a problem variable [known outside the (A)TMS]. Thus, the justification nil(v ₁) ∧ · · · ∧ nil(v _n) →^strong false can be used to express that leaving all variables v ₁, … , v _n (intentionally) unspecified is inconsistent (a constraint violation).

If none of these nil facet facts can be disproved and some of them are unfounded this is an incompleteness that cannot be detected by the (A)TMS without some further mechanism. The seemingly easy way to handle this is to initialize the nil(v) fact of each variable v with a default justification (of suitably weak strength). In Scope Selection there was a requirement to have the fact v = deselected represent nil(v) as well for a problem variable v variable representing a BAC item.

However, initially deselecting all BAC items as a default is not a good idea as it clutters up the labels (and explanations) in the (A)TMS and causes much irrelevant calculation. For this reason we provide a separate mechanism as follows: The (A)TMS can be told that a particular fact represents nil(v) for a problem variable v. If any other fact pertaining to the variable v implies ¬nil(v) this must be communicated to the (A)TMS as an opposing fact to nil(v). This will be any value assignment to v [except one that happens to coincides with the fact representing nil(v)]. In the case of a variable v representing a BAC item in Scope Selection v  =  selected is the only opposing fact. In case the variable v represents the observable color, nil(v) would not relate to any value assignment. All value assignments for color would be opposing facts. In case the variable v is numeric the fact v  =  0 might be considered as representing nil(v) or not (as the case may be for the particular product model).

The basic idea is that the (A)TMS treats an unfounded fact nil(v) in a special way. The status of such a fact is set to s_out if any opposing fact has status s_in. Otherwise, it is set to status s_nil (instead of s_unfounded). The status s_nil is thus a flavor of the status s_unfounded used for nil facet facts. A conjunction of facts has an overall status s_nil if it contains at least one fact with status s_nil and no fact with status s_out or s_unfounded (as distinct from status s_nil).

The (A)TMS uses the status s_nil solely to detect incompleteness. This means that a justification for false will signal incompleteness if its justificand has status s_nil. If the justificand has status s_in it will signal inconsistency. For all other purposes status s_nil is treated as s_unfounded. Any justification for false that contains nil facet facts is thus “a potential source of incompleteness.” Figure 3 contains one example,

where the last two facts in the justificand are nil facet facts.

Often the purpose of a default is to prevent incompleteness from occurring in the first place. A justification for such a default may be entered into the (A)TMS by normal means, but it will be present regardless of whether incompleteness is signaled or not. For this reason the (A)TMS provides an interface function tms_choose that allows defining a potential source of incompleteness and associating it with a default to handle it in such a way that the default is only activated in case this source signals incompleteness. tms_choose has the following four arguments and causes justifications (1) and (2) to be entered into the (A)TMS with some special handling for (2):

1. 1. ?condition: A set (conjunction) of nonnil facet facts that must hold as a precondition (BP_PP in the above example from Fig. 3)

2. 2. ?nil_facet_facts: A set (conjunction) of nil facet facts defining the incompleteness (¬BT_SP and ¬BT_SS in the above example from Fig. 3)

3. 3. ?default: An opposing fact to one of the given nil facet facts that is to be set as default (as discussed in Section 4.3 this will be the fact BT_SP)

4. 4. ?default_strength: A (fitting) strength for the ensuing default justification (the normal default strength is used here in Scope Selection)

(1)

(2)

Justification (2) is automatically disabled in circumstances when it would generate an additional unneeded conflict, for example, when (1) signals a conflict or when the nil facet fact that ?default opposes attains logical status s_in. It is reenabled when these circumstances no longer apply.

We consider this approach to be simpler and more practical to compute than logically more complete approaches such as the extended ATMS (de Kleer, Reference De Kleer1986b).

4.1. Architecture

An overview of the architecture of the Scope Selection application (our case study) is given in Figure 5. It makes use of the declarative configuration logic of the (A)TMS component of the CCE. The other components of the CCE, in particular its variable management, are not used. The application implements its own variable management in the scoping adaptor. The scoping adaptor also manages the access to the scoping model (the BAC) and the workspaces. One workspace contains all the configuration decisions of one customer.

Fig. 5.

The architecture of scope selection application (case study). [A color version of this figure can be viewed online at journals.cambridge.org/aie]

The services of the scoping adaptor are designed to meet specific requirements of the application. For example, the Scoping Adapter performs the following:

• • Manages a problem variable for each item of the BAC.

• • Translates the business rules in the BAC into (A)TMS justifications. We look at this in more detail in Section 4.3.

• • Splits the Scope Selection process into several substeps: high-level scope definition, detailed Scope Selection, and the definition of business options. The (A)TMS is initialized with the relevant variables and business rules for each individual step.

• • Includes a change history to enable the user to track changes made to the configuration.

Use was made of the new features of the (A)TMS: the declarative handling of defaults and incompleteness. Defaults occur with two different strengths: normal defaults formulated in the business rules and stronger “preselection” defaults formulated in conjunction with predefined scenarios the user can select.

4.2. Structure of scoping elements

For each problem variable v (item in the BAC) we create two facts in the (A)TMS:

• • One fact represents “v = selected.”

• • The second fact represents “v = deselected.”

If exactly one of the two facts is active (i.e., have status s_in), the assignment (selection status) of the variable is well defined and consistent. However, if both facts are active this is regarded as a conflict (inconsistency). To this end a strong justification is entered into the (A)TMS for each variable v as follows:

Furthermore, if neither fact is active, then this variable is “unspecified.” In the Scope Selection application, any variable that remains unspecified at the end of the Scope Selection process is considered as “out of scope” and the corresponding item is then treated as deselected.

All facts of the form v = deselected are declared as nil facet facts in the (A)TMS; v = selected is the opposing fact to v = deselected (see Section 3.6).

4.3. Transition to the declarative approach

The existing product model was reused without any adaptation of the preexisting rules. This was actually a precondition for the successful transition from the previous implementation and increased the acceptance of the new Scope Selection application by the responsible managers. The existing rules, however, had originally been defined in the context of a procedural approach. With the transition to the declarative approach, these rules are now interpreted as logical inferences (constraints).

The rules of the product model are defined in form of “self-centric” IF–THEN–ELSE rules of the following form:

(3)

where «condition» refers to an expression comprising one or more variable assignments connected with logical operators AND and OR and «status 1» defines a selection status of the BAC item that the rule is attached to. The rule specifies that this will be set if «condition» is fulfilled. Here, «status 2» is the opposite of «status 1». It will be set if «condition» is not fulfilled and ELSE is specified.

In the following we describe how these IF–THEN–ELSE rules are translated into logical inferences.

First, «condition» is transformed into disjunctive normal form (DNF), and references to the variable assignments are replaced by corresponding references to facts. An element of this DNF will be a conjunction of facts (e.g., f ₁ ∧ · · · ∧ f _n). The system derives an implication (4) for each such element of the DNF:

(4)

where f ₀ is the fact that assigns «status 1» to the variable that the rule is assigned to. In the event of an optional ELSE statement, «status 2» is handled similarly based on the DNF of NOT «condition». We do not elaborate on this explicitly in the sequel.

Each implication (4) can be treated as a logical clause (5) (recall that p ⇒ q is equivalent to ¬p ∨ q).

(5)

where ¬f _i represents the opposing assignment to f _i, that is, that ¬(v  =  deselected) is v  =  selected and vice versa.

For logical completeness it would seem advisable to generate a complete set of n + 1 justifications, one for each f _i (e.g., ¬f ₀ ∧ f ₂ · · · ∧ f _n  →^strong ¬f ₁ for f ₁). However, logical completeness is not necessarily considered a boon by all. In Scope Selection the business experts that formulated an implication p ⇒ q through a rule did not believe that ¬q ⇒ ¬p made sense in an explanation (e.g., because it violates perceived causality) and considered the latter inference to be “unwanted.” (Managers required that even if ¬q is chosen, p is not to be excluded in the UI.)

Therefore, the system creates only two justifications based on clause (5). One justification directly implements the implication (4) [which is closely linked to the business intent of the rule (3)]:

A second justification is needed to check the consistency and completeness of the configuration in the absence of a complete set of justifications:

An inconsistency is detected if all involved facts in the justificand are founded. In the case that at least one such fact is a nil facet fact (representing ¬v for some problem variable v) which is in s_nil status (logically unfounded), incompleteness is detected (refer to Section 3.6).

Some rules that are formulated to act on the deselection of an item require special attention. The simplest form of such a rule is

where A and B are items in the BAC. Let ¬a be the fact A = deselected and b be the fact B = selected. If the rule were simply translated into the justifications

this will not infer b if ¬a is unfounded (or nil). As discussed in Section 3.6, stating an initializing default justification for the deselection of each variable does not work well. A different translation is instead applied to these rules based on the actual business intent of the rule that states a (directed) fulfillment of a completeness requirement in a procedural form (b is needed in the absence of a). Here we use the tms_choose function to generate the following two justifications (see Section 3.6):

• • ¬a ∧ ¬b →^strongfalse [as above, this corresponds to (1)]

• • empty justificand (true) →^{default_strength}b [this corresponds to (2) and is only active in case of an incompleteness]

The justification ¬a →^strongb is generated in addition against the event that ¬a attains status s_in (is deselected on purpose).

We close with an example using two rules from the BAC. We abbreviate by using fact substitutions directly in the formulation of the rules (the example refers to facts and variables given in Table 1):

(6)

(7)

Rule (6) states, the function “Sell Product & Services” requires “Product Portfolio.” The second rule (7) will ensure that “Product Portfolio” cannot be used without the functions “Sell Services” and “Sell Products.” In fact, this rule is formulated in a procedural manner to select the item “Sell Products” in the case that “Product Portfolio” is selected but “Sell Services” is not selected. The business intent is to associate a completeness requirement with a default to handle it.

Rule (6) is transformed into the clause ¬BP_SPS ∨ BP_PP and leads to the following justifications:

Rule (7) includes the pattern to infer the selection of BT_SP based on the deselection of BT_SS given the fact that BP_PP is selected. It corresponds to the clause ¬BP_PP ∨ BT_SS ∨ BT_SP. That this formulates a completeness requirement can be seen directly in that the clause contains a disjunction of selections (i.e., is not a Horn clause). The original rule gives information that this incompleteness is to be handled by selecting BT_SP as a default if required. Consequently, tms_choose is used with the following arguments: ?condition ={BP_PP}, ?nil_facet_facts = {¬BT_SS, ¬BT_SP}, ?default = BT_SP, and ?default_strength = default.

Altogether the following justifications are generated:

4.4. Benefits and practical compromises

The new Scope Selection application based on the (A)TMS in the CCE proved to be successful in fulfilling the functional requirements and also met the required SAP product standards for runtime performance. In one scoping step the system deals with up to 4000 problem variables that are connected via 14.000 logical inferences (justifications).

The existing product model could be reused without adaptation, but the rules are now interpreted in a declarative manner (as logical clauses), which provides some concrete benefits:

• • There is no need for any rule execution logic on top of the (A)TMS. This simplified the implementation of the new Scope Selection application significantly.

• • The development process of new constraint rules will become easier, because the developer does not have to worry about the rules defined by other developers and the order in which rules are applied.

• • Unwanted behavior caused by the procedural execution of business rules was eliminated. (An example of such unwanted behavior is that sometimes default selections were triggered that were meant to be set in a different situation. In addition, sometimes properties set by rules were not completely retracted when the user retracted the choices that triggered these rules. Previously, retracting a user choice did not always consistently remove all dependent items selected by rules along with it. The user was alerted to the need to verify the scope after removing an item and perhaps manually removing further items as well even if the user never directly selected these.)

• • More consistent explanations can be constructed based on the (A)TMS labels. Table 1 lists the labels for some facts used in our examples. In particular, Figure 2 shows the explanation of one fact as it is presented in the UI. Previously the production rules generated explanations by constructing chains of applied rules. There were, however, cases when this led to explanations more complex than needed that were confusing for the user.

• • The ability to retract user choices consistently was the basis for multistep undo/redo functionality in Scope Selection.

These benefits proved to be instrumental in convincing the managers to gradually accept a more purely declarative processing. However, the new Scope Selection application has also kept some of the previous procedural control flow. This has been done as a practical compromise to preserve the look and feel of the existing UI as much as possible and to avoid a major change in the user interaction of the Scope Selection process. There are two main points here:

1. 1. The UI provides strict guidance concerning the order in which some selections may be made. Mainly, the user has to follow the hierarchy of the BAC and first select a business package before they are able to select one of its business topics. To ensure this it is also unwanted that a business topic is inferred from a without inferring the parent business package by the same rule. For this reason the generic logical inference to deduce the selection of an item given the selection of a child item is not present in the current implementation (although it is logically correct).

2. 2. Although the (A)TMS provides support for declarative resolution of conflicts (declarative default handling), the managers requested that the system in addition resolve conflicts because of some heuristics, even when this is not justified declaratively. These heuristics are implemented by procedural means in the adapter layer (not in the CCE). In some cases, the system even retracts user decisions. However, the user is informed if this happens and can use the undo feature to revert to a previous state.