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