Production System (Past)

Key Member

石田 亨

Project Objective

プロダクションシステムは, ルールの集合によって手順を構成しようとする プログラミ ングパラダイムである. 各ルールは条件部と動作部からなり, 条件部が満足さ れると動作部が実行に移される. 条件部は, ワーキングメモリ と呼ばれるデーターベースとのパターン照合を通じて, その成否が判定され る. ワーキングメモリは, 動作の実行によって更新されるので, その結果, 別のルールの条件部が新たに満足され, 連鎖的にルールが発火する. この循環 は, 認識ー実行サイクル(recognize-and-act cycle)と呼ばれ, 人間をはじめとする知 的行動のモデルと考えられている.

プロダクションシステムは, 歴史的な背景からエキスパートシステム記述用 言語という側面が強調されがちである. しかし一方では, 単純な構成の中に, プログラムとデータベースという情報システムの2大要素を結合しようという, 極めて野心的な側面を有している. この研究では, プロダクションシステムをエキスパートシステム等の応用プログラムから 特徴づけるのではなく, 実行メカニズムや構造, 機能から捉え, その多様な 発展の可能性を探る.

Research Results

以下に主要な研究成果を示す.

  1. プロダクションシステムの 最適化

    プロダクションシステムのソースプログラムを入力と して, 高速に実行可能な新たなソースプログラムを出力する. 最適化技術は, 条件照合アルゴリズムやコンパイラとは独立に, プロダクションシステムの高速化に寄与する技術である [2,13]. プロダクションルールを最適化する問題は, データベースシステムにおけ る問合わせ最適化と類似している. ルールの条件 部はデータベースへの問合わせと見倣せるからである. しかし, 従来の問合わせ最適化技術を直接用いても, 良い結 果は得られない. データベースの場合とは異なり, プログラムの動作特性を考慮した最適化が必要とされるからである.

  2. プロダクションシステムの実行制御

    宣言的に書かれたルールの発火順序を手続き的に制御する. ルールが発火するか否かは実行時に決定されるので, サブルーチンのようにルールを呼び出すことはできない. そこで, 個々のルールを「データベースを監視し条件が満足さ れれば発火しようとするプロセス」だと考える. ルールをプロセスと見倣すと, 発火を制御するプランとルールの間に何らかの プロセス間通信機能が必要となる. 試みに, HoareのCSP (Commuicating Sequential Processes) に基づく同期型通信機能を参考に, ルールの発火を制御する マクロを導入する [5,12,15]. このアイデアは実装が極めて容易であるにもかかわらず, 驚くほど強力な 実行制御言語を実現できる.

  3. プロダクションシステムの並列発火

    プロダクションシステムの並列処理は, 条件照合を並列に処理する 並列条件照合と, 複数のルールを 並列に実行させる並列発火の2種に分類される. 我々は並列発火の可能性に着 目し, その実現手法を初めて提案している [1,6,7]. プロダクションシステムの並列発火では, データベースシステムにおけるトラ ンザクションの直列化(serializability)に 相当する問題が生じる. 直列化の条件はプロダ クションシステム固有であるものの, 直列化できないルールは並列に 実行してはならない. また, 競合解決による実行順序の制御を期待する場合 には, 並列実行の対象とはなり得ない. こうした制約を満足させた我々の手法は, 種々の並列プロダクショ ンシステム計算機に実装された.

  4. 実時間プロダクションシステム

    プロセス制御やネットワーク管理等のように, 時々刻々変化する環境の中で, 連続的にかつ制 限時間内に問題を解決する方法(実時間連続問題解決)を検討する. まず, 並列プロダクションシステムを 分散プロダクションシステムへと発展させる [10]. 分散プロダクションシステムは, 複数のルールをネットワーク上のプロセサ群 で非同期並行的に 実行させるものである. しかし, 一つ一つのルールに別個のプロセサを割り当てるのは資 源効率が良くない. そこで, 負荷に応じてルールをグループ化し(これを問題 解決組織と呼ぶ), 各グループを別個のプロセサに割り当てる. 負荷の度合は環境の変化に依存するので, 問題解決組織も刻々変化させる必要がある [4,8,9,11]. (図17参照)

      
    図 17: 問題解決組織による適応

  5. マルチエージェント・プロダクションシステム

    異なる役割を持つプロダクションシステムの集合体が協力して 問題解決を行なうモデルを提案した [3]. プロダクションシステムが独立に作成されたことを強調する ため, この形態のシステムをマルチエージェント・プロダクションシステムと 呼び, 分散プロダクションシステムと区別した. 題材として, ネットワーク管理を行なうプロダクションシステム群を とりあげ, 開環境での問題解決が遭遇する諸課題を明らかにした. (図18参照)

  
図 18: プロダクションシステム・エージェント

上記の一連の研究成果をとりまとめ, Springer-Verlagと朝倉書店から出版し た [14,17]. また ICMAS-96 で招待講演を行なった [16].

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,'' National Conference on Artificial Intelligence (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,'' IEEE Conference on Artificial Intelligence for Applications (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,'' National Conference on Artificial Intelligence (AAAI-91), pp. 185-190, 1991.

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

  10. Toru Ishida, ``A Transaction Model for Multiagent Production Systems,'' IEEE Conference on Artificial Intelligence for Applications (CAIA-92), pp. 288-294, 1992.

  11. 石田 亨, Les Gasser, 横尾真, ``エージェントの組織による実時間連続問題解決,'' 人工知能学会誌, Vol. 7, No. 2, pp. 300-308, 1992 (論文賞).

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

  13. Toru Ishida, ``An Optimization Algorithm for Production Systems,'' IEEE Transactions on Knowledge and Data Engineering, Vol. 6, No. 4, pp. 549-558, 1994.

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

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

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

  17. 石田 亨, プロダクションシステムの発展, 朝倉書店, 1996.


Top
Page
Free
Software
Publications Members Location Related
Servers