Research on Production Systems

 

Overview

 

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.

 

Single production system

 

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.

 

Parallel production systems

 

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.

 

Distributed production systems

 

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.

 

Multiagent production systems

 

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.

 

Meta-level control architecture

 

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 CoCo, which concurrently performs cooperative operations such as public switched telephone network control. The every day operations of telecommunication network operation centers are investigated, and then implemented in CoCo. The configuration of the CoCo agents, the plan description language, and experiments of multiagent rule firings are described.

 

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.