|
|
- Consumers The consumers C of a role r in an inference structure I, denoted
- by C (r), are the inferences in I that have the role as an input.
- Initial roles The initial roles of an inference structure I are the input roles
- that are not produced by any inference step in I. We will use the notation [left arrow R]s to denote the set of input roles of the inference step s. When no indices are given,
refers to the set of input roles of the whole inference structure.
- Terminal roles The terminal roles of an inference structure I are the output
- roles that are not consumed by any inference step in I. We will use the notation [left arrow R]s to denote the set of output roles of the inference step s.
- Substitution to a knowledge role A substitution of a value a:type (where a is a
- ground term) to a knowledge role [nu]:type is denoted by [sigma] = {[nu]/a}.
- The instance of an inference step s obtained by carrying out substitution [sigma] is
- denoted by s[sigma]. For multiple substitution, [sigma] is of the form [sigma] = {([nu]1/a1), ..., ([nu]n/an)}. The instance of an inference structure I obtained by carrying out substitution [sigma] to all its knowledge roles is denoted by I[sigma]. We use the notation [sigma]:type([left arrow R]), to denote that [sigma] is a substitution for a set of variables of exactly the types of the initial roles. In this case I[sigma] denotes an instance of the inference structure I obtained by carrying out the substitution [sigma], i.e., substitutions of all its input roles. We use the notation s[sigma], where [sigma]:type([left arrow R]s), to denote an instance of the inference step s obtained by substitution of its input roles. The same can be applied for terminal, internal, and external roles. When the type is not given, [sigma] is a substitution for all knowledge roles in the inference step or inference structure.
- Sequence of substitutions The sequence of two substitutions
- [sigma] = {([nu]1/a1), ..., ([nu]n/an)} and [nu] = {w;(w1/b1), ..., (wm/bm)} is denoted by [sigma]|-[nu] = {([nu]1/a1), ..., ([nu]n/an), (w1/b1), ..., (wm/bm)}.
- The sequence operator has precedence over the application of the substitution to
- an inference step or structure. When two substitutions substitute different values to the same variable, the right-most substitution has precedence (i.e., overwrites the left-most substitution for that variable). Example: consider the following inference step s(x1,x2;y), and two substitutions, [sigma]:type([left arrow R]s) and [nu]:type([left arrow R]s), where [sigma] = {(x1/5), (x2/6)} and [nu] = {(y/5)}, [sigma]|-[nu] = {(x1/5), (x2/6), (y/5)}. s[sigma]|-[nu] denotes an instance of s obtained by carrying out the substitution [sigma]|-[nu].
- Satisfying an inference structure Let [sigma] be a substitution for all knowledge
- roles occurring in an inference structure I, and DEF the definitions of all inference steps occurring in I. [sigma] satisfies I if and only if DEF | = I[sigma]. To avoid writing DEF repetitively and to improve the readability, we will write sat(I[sigma]) to denote that the inference structure I is satisfied by a substitution [sigma], where [sigma] corresponds to a valid execution of I. A valid execution of s means that the particular instance of s solves the problem-solving step for which it was designed. In the previous example, s[sigma]|[nu] is a valid instance of s if, for example, the inference step performs the minimum operation on its input knowledge roles. The same can be applied to inference structures. We use the notation sat(s[sigma]) to denote the satisfaction of the inference step s.
2.2.1. Subsumption
In hybrid systems, inheritance triggers subsumption among the objects and will lead to other types of anomalies unique to hybrid systems. A taxonomy of anomalies that can occur in such systems has been proposed by Lee and O'Keefe (1993):
- Subsumed rules: Subsumed rules arise due to the subsumption relationship between literals used in the rules.
- Redundancy: Redundancy arises as a direct consequence of subsumed rules.
- Semantic conflict: Semantic conflict occurs when any pair of rules that have the same conditions lead to semantically different actions, among which there exists a partial or complete subsumption relationship.
- Structural conflict: Structural conflict is identified by subsumption relationships in the condition and action parts of the rules.
- Unnecessary conditions: In hybrid systems, unnecessary conditions can occur when an action in a rule is propagated to another rule as a condition and results in at least one subsumption relationship between a pair of literals in the condition clause.
- Unreachable goals: Unreachable goals may arise due to mutual exclusivity among the objects used in the condition of the same rule.
- Circular rules: The definition of circular rules has been extended for hybrid systems.
Instead of addressing directly the different types of anomalies due to subsumption mentioned above, we define different types of subsumption, and identify the type of anomaly that may be caused by that specific type of subsumption. This approach abstracts from implementational details, by addressing these issues on a conceptual level. For each type of subsumption, we provide a counterpart example, where an object hierarchy of two levels is assumed: S = a1 [union] a2 [union] ... [union] an being the first level and every ai1 = {ai1, ai2, ..., aij} being the second level, where the elements in the set are subclasses of ai.
A classification of the subsumption relation is given in Figure 2.
The explicit subsumption is the type of subsumption that has been considered in the traditional V&V activities in rule-bases. In rule base systems, subsumption occurs in the case that the more general rule can always be fired whenever the restrictive rule is fired. For example, whenever rule (1) succeeds, rule (2) will also succeed. Therefore, in what follows, rule (1) is subsumed by rule (2):
p(x) [wedge] q(x) > r(x) |
(1) |
p(x) > r(x) |
(2) |
FIGURE 2 A classification of the subsumption relation.
FIGURE 3 Partial (A) and complete (B) subsumption.
This kind of subsumption can be detected by comparing whether or not one rule has additional conditional statements to the other rule when the two rules have the same conclusion. However, such structural checking cannot cover the semantics of relationships in the rules of hybrid systems, which may include object hierarchies.
In order to cope with this problem, we introduce the notion of implicit subsumption. This type of subsumption1 takes into consideration the semantic relationships that exists between the objects on which the rules operate.
1We talk about subsumption between inference steps and subtyping between knowledge roles. In fact, subsumption between inference steps is caused by subtyping relationships between knowledge roles.
Implicit subsumption Let [sigma] = {([nu]1/a1), ..., ([nu]n/an)} and [sigma] = {([nu]1/a1), ..., ([nu]m/am)} where n [less than or equal to] m. [sigma] is subsumed by [sigma], written as [sigma] [inverted y] [sigma], iff

where ai , aj may be sets of values.
We distinguish two types of implicit subsumption, depending on the relationship between knowledge roles: partial and complete subsumption. An example of partial subsumption is given in Figure 3A, where the graphical notation is equivalent to s(x,y;z) [inverted wedge] s(x;z), using the notation provided in the previous section. An example of complete subsumption is given in Figure 3B, equivalent with s(x,y;z) [inverted wedge] s(x,y;z).
In Figure 3, s is subsumed by s as for any value of x, where x is a subtype of x,s computes the same value for z as s does, regardless of y. We will use to denote partial or complete subsumption, and [inverted y]c to denote complete subsumption.
In the following, we define the different types of subsumption. For each type, a brief analogy with the counterpart in rule bases is also given.
|