Production System (Past)

Key Member

Toru Ishida

Project Objective

This series of research initiatives on concurrent production systems [15] 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 compete or cooperate to solve a single problem or multiple problems.

Research Results

1.
Optimization of production rules [2,12]:

The problem addressed here is 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 algorithm can generate programs that are as efficient as those obtained by manual optimization, and thus can reduce the burden of manual optimization.

2.
Parallel production systems [1,6,7]

The fundamental problem in parallel production systems is how to guarantee the serializability of 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.


  
Figure18: Organizational Adaptation

3.
Distributed production systems [4,8,9]:

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. 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.

4.
Multiagent production systems [10]:

Multiagent production systems are different from parallel or distributed production systems, which aim at improving the performance of a single production system. 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 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.

5.
Meta-level control of production systems [3,5,11,14]:

Because various events occur asynchronously in a multiagent network, the agents must cooperatively control their rule execution processes. 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. 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. The architecture has been applied to a multiagent system called CoCo, which concurrently performs cooperative operations such as public switched telephone network control.

The above results have been compiled and published from Springer-Verlag [13].


  
Figure19: Production System Agent

References

1.
Toru Ishida and Salvatore J. Stolfo, ``Towards Parallel Execution of Rules in Production System Programs,'' International Conference on Parallel Processing (ICPP-85), pp. 568-575, 1985.

2.
Toru Ishida, ``Optimizing Rules in Production System Programs,'' National Conference on Artificial Intelligence (AAAI-88), pp. 699-704, 1988.

3.
Toru Ishida, ``CoCo: A Multi-Agent System for Concurrent and Cooperative Operation Tasks,'' International Workshop on Distributed Artificial Intelligence (DAIW-89), pp. 197-213, 1989.

4.
Toru Ishida, Makoto Yokoo and Les Gasser, ``An Organizational Approach to Adaptive Production Systems,'' AAAI-90, pp. 52-58, 1990.

5.
Toru Ishida, Yutaka Sasaki and Yoshimi Fukuhara, ``Use of Procedural Programming Languages for Controlling Production Systems,'' IEEE Conference on Artificial Intelligence for Applications (CAIA-91), pp. 71-75, 1991.

6.
Toru Ishida, ``Methods and Effectiveness of Parallel Rule Firing,'' CAIA-90, pp. 116-122, 1991.

7.
Toru Ishida, ``Parallel Firing of Production System Programs,'' IEEE Transactions on Knowledge and Data Engineering, Vol. 3, No.1, pp. 11-17, 1991.

8.
Les Gasser and Toru Ishida, ``A Dynamic Organizational Architecture for Adaptive Problem Solving,'' AAAI-91, pp. 185-190, 1991.

9.
Toru Ishida, Les Gasser and Makoto Yokoo, ``Organization Self-Design of Distributed Production Systems,'' IEEE TKDE, Vol. 4, No. 2, pp. 123-134, 1992.

10.
Toru Ishida, ``A Transaction Model for Multiagent Production Systems,'' CAIA-92, pp. 288-294, 1992.

11.
Yutaka Sasaki, Keiko Nakata, Toru Ishida and Yoshimi Fukuhara, ``Advantages of Meta-level Control Architectures in Maintaining Rule-Based Systems,'' IEEE Conference on Tools with Artificial Intelligence (TAI-93), pp. 495-496, 1993.

12.
Toru Ishida, ``An Optimization Algorithm for Production Systems,'' IEEE TKDE, Vol. 6, No. 4, pp. 549-558, 1994.

13.
Toru Ishida, Parallel, Distributed and Multiagent Production Systems, Lecture Notes in Artificial Intelligence 878, Springer-Verlag, 1994.

14.
Toru Ishida, Yutaka Sasaki, Keiko Nakata and Yoshimi Fukuhara, ``A Meta-Level Control Architecture for Production Systems,'' IEEE TKDE, Vol. 7, No.1, pp. 44-52, 1995.

15.
Toru Ishida, ``Parallel, Distributed and Multi-Agent Production Systems: A Research Foundation for Distributed Artificial Intelligence," International Conference on Multi-Agent Systems (ICMAS-95), Invited Talk, pp. 416-422, 1995.


Top
Page
Free
Software
Publications Related
Servers
Location Laboratory
Page