I
have worked on a series of research initiatives on concurrent production
systems, which can be classified into three categories:
1.
Synchronous parallel
production systems or parallel rule
firing systems, where rules are fired in parallel to reduce the total
number of sequential production cycles, while rule firings are globally
synchronized in each production cycle,
2.
Asynchronous parallel
production systems or distributed
production systems, where rules are distributed among multiple processes,
and fired in parallel without global synchronization, and
3.
Multiagent production
systems, where multiple production system
programs compete or cooperate to solve a single problem or multiple problems.
I
first investigated the performance of a single production system. It has been known
that as the scale of rule-based expert systems increases, the efficiency of
production systems significantly decreases. To avoid this problem, recently
developed production systems have been enabling users to specify an appropriate
ordering or clustering of join operations, performed in the production system
interpreters. Various efficiency heuristics have been introduced to optimize
production rules manually. However, since the heuristics often conflict with
each other, users have had to proceed by trial and error.
The
problem deals with how to estimate the efficiency of production system
programs, and how to automatically determine efficient join structures. For
this purpose, the cost model for production systems is introduced to estimate
the run-time cost of join operations. An optimization algorithm is then
provided based on the cost model. This algorithm does not directly apply
efficiency heuristics to programs, but rather enumerates possible join
structures under various constraints, and selects the best one. Evaluation
results demonstrate that the optimization algorithm can generate programs that
are as efficient as those obtained by manual optimization, and thus can reduce
the burden of manual optimization.
For
further speed-up of production system programs, parallel production systems are
proposed. The fundamental problem in synchronous parallel production systems is
how to guarantee the serializability of production rule firings. Interference
analysis is introduced to detect cases where a parallel firing result differs
from the result of sequential firings of the same rules in any order. Based on
a data dependency graph of production systems, general techniques applicable to
both compile- and run-time analyses are provided. Two algorithms are then
proposed to realize the parallel rule firings on actual multiple processor
systems:
An
efficient selection algorithm is provided to select multiple rules to be fired
in parallel by combining the compile- and run-time interference analysis
techniques.
The
decomposition algorithm partitions the given production system program and
applies the partitions to parallel processes.
A
parallel programming environment is provided, including language facilities to
allow programmers to make full use of the potential parallelism without
considering the internal parallel mechanism. A parallel firing simulator is
implemented to estimate how effective parallel firings of production system
programs are. The effectiveness of parallel rule firings has been evaluated in
several production system applications. Results show that the degree of
concurrency can be increased by a factor of 2 to 9 by introducing parallel
firing techniques. The sources of parallelism are investigated based on the
evaluation results.
I
then extended parallel production systems to distributed production systems.
For asynchronous execution of production systems, parallel rule firing, where
global control exists, is extended to distributed rule firing, where problems
are solved by a society of production system agents using distributed control.
To perform domain problem solving in a distributed fashion, the agents need
organizational knowledge, which represents both the necessary interactions among
agents and their organization.
Organization
self-design is then introduced into the distributed production systems to
provide adaptive work allocation. Two reorganization primitives, composition
and decomposition, are newly introduced. These primitives change the number of
production systems and the distribution of rules in an organization.
Organization self-design is useful when real-time constraints exist and
production systems have to adapt to changing environmental requirements. When
overloaded, individual agents decompose themselves to increase parallelism, and
when the load lightens the agents combine with each other to free extra
hardware resources. Simulation results demonstrate the effectiveness of
this approach in adapting to changing environmental demands.
I
finally investigated multiagent production systems, which are interacting
multiple independent production systems, and thus are different from parallel
or distributed production systems, which aim at improving the performance
of a single production system program. A transaction model is introduced to
enable multiple production systems to communicate through a shared working
memory. To achieve arbitrary interleaved rule firings of multiple production
system agents, each transaction is formed when a rule for firing is selected.
An efficient concurrency control protocol, called the lazy lock protocol, is
introduced to guarantee serializability of rule firings. As a result of
allowing interleaved rule firings, however, ensuring the serializability
becomes no longer enough to guarantee the consistency of the shared working
memory information. A logical dependency model and its maintenance mechanisms
are thus introduced to overcome this problem.
I
also discussed the control issues of multiagent production systems. Because
various events occur asynchronously in a multiagent network, the agents must
cooperatively control their rule execution processes. Meta-level control
architecture is required to prioritize the rule firings, to focus the attention
of multiple agents on the most urgent tasks. To implement this, the procedural
control of production rule firings is first introduced. The key idea of
implementing the flexible control is to view production systems as a collection
of independent rule processes, each of which monitors a working memory and
performs actions when its conditions are satisfied by the working memory. Procedural Control Macros (PCMs), which are
based on Hoare's CSP, are then introduced to establish communication links
between the meta-level control processes and the collection of rule processes.
Although the PCMs are simple and easy to implement, through embedding them into
procedural programming languages, users can efficiently specify the control
plans for production systems.
The
meta-level control architecture has been applied to construct a multiagent
system called
1.
Toru Ishida. Parallel
Firing of Production System Programs. IEEE Transactions on Knowledge and
Data Engineering, Vol. 3, No.1, pp. 11-17, 1991.
2.
Toru Ishida, Les
Gasser and Makoto Yokoo. Organization Self-Design of Distributed Production
Systems. IEEE Transactions on Knowledge and Data Engineering, Vol. 4,
No. 2, pp. 123-134, 1992.
3.
Toru Ishida. An
Optimization Algorithm for Production Systems. IEEE Transactions on Knowledge and Data Engineering, Vol. 6, No. 4,
pp. 549 - 558, 1994.
4.
Toru Ishida. Parallel, Distributed and Multiagent Production
Systems. Lecture Notes in Artificial Intelligence 878, Springer-Verlag,
1994.
5.
Toru Ishida, Yutaka
Sasaki, Keiko Nakata and Yoshimi Fukuhara. A Meta-Level Control Architecture
for Production Systems. IEEE Transactions
on Knowledge and Data Engineering, Vol. 7, No.1, pp. 44-52, 1995.