Commutative Production Systems
These types of production systems are used when the order of operations is not important and the changes are reversible
A production system is said to be Commutative if it satisfies the following properties with respect to any database \(D\):
-
Each member of the set of rules applicable to \(D\) is also applicable to any database produced by applying an applicable rule to \(D\).
-
If the goal condition is satisfied by \(D\), then it is also satisfied by any database produced by applying an applicable rule to \(D\).
-
The database that results from applying to \(D\) any sequence composed of rules that are applicable to \(D\) is invariant under permutations of the sequence.
|
Note
|
an irrevocable control regime can always be used in a commutative system because the application of a rule never needs to be taken back or undone. |
Consider for example, a system whose intitial database is \((C, B, Z)\), whose production rules are based on the following rewrite rules ("rewrite rules" are rules that replace one symbol with another):
-
\(R_1: C \rightarrow (D, L)\)
-
\(R_2: C \rightarrow (B, M)\)
-
\(R_3: B \rightarrow (M, M)\)
-
\(R_4: Z \rightarrow (B, B, M)\)
Further, consider that the termination condition is that the database only contains \(M\)'s.
The following diagram shows a graph search control regime:
@TODO: Insert commutative production system diagram
Production systems that are able to decompose their global databases and termination conditions are called decomposable
Efficient AI systems require knowledge of the problem domain:
-
The knowledge about a problem that is represented in the global database is sometimes called declarative knowledge.
-
The knowledge about a problem that is represented in the rules is often known as procedural knowledge.
-
The knowledge about a problem that is represented in the control strategy is often called control knowledge.
Procedure SPLIT
-
DATA\(=\)initial database -
\( \{ D_i \} \) \(=\) decomposition of
DATA, the individual \(D_i\) are now regarded as separate databases -
until all \(D_i\) satisfy the termination condition, do:
-
begin
-
select \(D^*\) that does not satisfy the termination condition
-
remove \(D^*\) from \( \{ D_i \} \)
-
select some rule \(R\) from the set of rules applicable to \(D^*\)
-
\(\{ d_i \}\) \(=\) decomposition of \(D^*\)
-
append \( \{ d_i \} \) to \( \{ D_i \} \)
-
end
Computational Costs of AI Systems
The overall computational efficiency of an AI system depends upon where along the informed/uninformed spectrum the control strategy falls
Computational costs of a production system can be divided into two types: rule application costs and control costs.
A completely uninformed control strategy incurs a small control strategy cost as arbitrary rule selection need not depend on costly computation. But, it incurs a high rule application cost as it needs to try a large number of rules to find a solution.
An informed control strategy, on the other hand, incurs minimal rule application costs as it can select the best rule to apply. However, it incurs a high control cost in terms of storage and computation.
@TODO: Insert cost comparison graph
The behaviour of the control system as it makes rule selections can be regarded as a search process.