ソフトウエア科学会研究会資料シリーズ

ISSN 1341-870X No.19

MACC2001
第 10 回マルチエージェントと協調計算ワークショップ
論文集

武田英明編

ソフトウエア科学会研究会資料シリーズ

MACC2001
第 10 回マルチエージェントと協調計算ワークショップ論文集
2002 年２月１日発行
編集武田英明〒101-8430 東京都千代田区一ツ橋 2-1-2
国立情報学研究所
http://www-kasm.nii.ac.jp/~takeda/
電話 03-4212-2543
FAX 03-3556-1916

発行

日本ソフトウエア科学会〒113‑0032 東京都文京区弥生 2‑4‑16 学会センタービル内
http://www.jssst.or.jp/jssst/
電話

FAX

03‑5802‑2060

03-5802-3007
ISSN 1341‑870X No.19

目次1
はじめに
武田 英明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
アドバイザリーコミッティとプログラム委員 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
パネルセッション

1. 社会的エージェントの可能性
石田 亨, 中西 英之, 長尾 確, 小野 哲雄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
エージェントモデル

2. 義務と権利に基づく社会行動の即応制御モデル
大澤 一郎 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. BDI Logic の sequent calculus による演繹体系
新出 尚之，高田 司郎 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

4. マルチエージェントによるチーム航行支援 (S)安藤 英幸，広野 康平，大和 裕幸 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5. Wizard of Oz 法を使ったマルチキャラクターエージェントインタフェースの評価 (S)辻本 秀樹，北村 泰彦，辰巳 昭治 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
エージェントプロトコル

6. エージェント基盤のための協調プロトコル：Agent Platform Protocol
高橋 健一，鍾 国強，雨宮 聡史，峯 恒憲，雨宮 真人 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
7. マルチエージェントシステムへの投機的計算導入手法
山本 京司，佐藤 健 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
8. モバイルエージェント系における分散制約充足
沼澤 政信，栗原 正仁，能登 正人 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
9. ユーザ選考に基づく分散コンテンツキャッシュポリシ (S)中塚 康介, 八槇 博史 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
コミュニティのためのエージェント

10. 口コミによる分散型情報収集システム
吉田 匡志，伊藤 雄介，沼尾 正行 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
11. 知識の階層構造を用いた協調的情報推薦 (S)濱崎 雅弘，武田 英明，河野 恭之，木戸出 正継 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

1 タイトルに (S) とあるものはショートペーパー、その他はロングペーパー

ロボット

12. RoboCupRescue における最少通話による協調の実現
森本 武資，河野 健二，竹内 郁雄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
13. 異種端末間の協調による高齢者・障害者の移動支援、Robotic Communication Terminals(S)矢入（江口）郁子、猪木 誠二 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
学習と知識獲得

14. 未来状態の予測を利用したマルチエージェント強化学習法
長行 康男，柴田 直樹，伊藤 実 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
15. 環境状況の変化に応じて自己の報酬を操作する学習エージェントの構築
森山 甲一, 沼尾 正行 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

16. 自律学習における CITTA による部分知識の結合 (S)山川 宏，宮本 裕二，馬場 孝之，岡田 浩之 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
17. ネット情報を使った意思決定のための知識獲得エージェント (S)藤本 和則，山本 裕 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
特別セッション [ゲーム理論／意思決定／経済学的アプローチに基づくマルチエージェント]

18. 情報財の開発インセンティブについて
藤山 英樹 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

19. 人工市場における複雑さの発展の分析
和泉 潔 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
20. X-Economy - マルチエージェント経済におけるシミュレーションプラットホーム
川村 秀憲，車谷 浩一，大内 東 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

21. P2P 電子マーケットにおけるエージェント間の提携に基づく売買交渉機構について
服部 宏充，伊藤 孝行，新谷 虎松 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
22. U-MART：経済学と工学をエージェントが結ぶ
喜多 一、出口 弘、寺野 隆雄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

23. エージェントシミュレーションによる「チープ・トーク」モデルの拡張
小山 友介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
24. エージェント系としてのレプリケータダイナミックスとその制御
國上 真章、寺野 隆雄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

25. エージェントシミュレーションによる Prospect 理論と GARCH モデルの関連性の分析
高橋 大志、寺野 隆雄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
26. 複数財オークションについて
松井 知己，渡辺 隆裕 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

27. セキュアマルチエージェント動的計画法の設計と組合せオークションへの適用
鈴木 幸太郎．横尾 真 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

1

はじめにプログラム委員長 武田 英明

本論文集は日本ソフトウエア科学会「マルチエージェントの発表が行われた．時間帯によっては通常セッションよりむと協調計算研究会」の第 10 回ワークショップ（第 10 回マルしろ特別セッションの方に人があつまり，立ち見がでる状況

チ・エージェントと協調計算ワークショップ，MACC2001）でであった．従来の MACC の発表者が人工知能を中心とす発表されたものを集めたものである． MACC2001 においてる情報工学の分野であったの対して，この特別セッションのは投稿された論文はプログラム委員による査読を受けて，著発表者はセキュリティの研究者や経済学の研究者など幅広者による加筆・修正ののち発表，本論文集に掲載というプロ

いものであり，この分野が広範な範囲の人々の興味をひき

セスを 経ている．本年度は，通常セッションにロングペーパつけており，今後の発展の可能性を示していた．

ー9 件，ショートペーパー7 件，特別セッション 10 件の発表が行われた．

このようにマルチエージェントの分野は単に人工知能ある
いは情報工学の特定の興味でなく，広範な興味・話題を含

MACC2001 は金沢のラポート兼六を中心に 2001 年 11

みようになっている．このような認識のもとで MACC は来年

月 16 日，17 日に開催された．参加人数は約 60 人で，基本度は電子情報通信学会人工知能と知識処理研究会と共同的に全員泊りがけで行った．

で，エージェント／マルチエージェントの話題を広く含むよう

初日は前日より金沢大学で開催していた電子情報通信
学会人工知能と知識処理研究会と共同企画でパネルを行な会議として開催されることになった．同じく 11 月中旬に函館での開催が予定されている．

った．その日は懇親会を兼ねた夕食の後，発表者以外の参本ワークショップ開催にあたってはプログラム委員のみな加者の 30 人弱のポジションペーパー発表が行われた．ポジさまの協力のもとで成功裏に開催することができた．ここに感ションペーパー発表とはいえ，興味深い発表もあり，活発な謝の意を表する．

質疑が行われた発表もあった．
翌日からは２トラックのパラレルセッションとして行った．今
回は，特別セッションに多数の論文が集まったため，基本的に１つのトラックを特別セッションとして行った．
通常セッションは，ロングペーパー，ショートペーパーを織り交ぜ，「コミュニティのためのエージェント」，「ロボット」，「エージェントモデル」，「エージェントプロトコル」，「学習と知識獲得」というセッションに分けて行った．
特別セッションは「ゲーム理論／意思決定／経済学的ア
プローチに基づくマルチエージェント」というテーマで 10 件
Preface
Hideaki Takeda, 国立情報学研究所, National Instituteof Informatics.

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

アドバイザリコミッティ
石田 亨（京都大学）
奥乃 博（京都大学）
所 真理雄（ソニー）
中島 秀之（産業技術総合研究所）
西田 豊明（東京大学）
本位田 真一（国立情報学研究所）

プログラム委員[委員長] 武田 英明（国立情報学研究所）
伊藤孝行（北陸先端科学技術大学院大学）
和泉 潔（産業技術総合研究所）
磯崎 秀樹（ＮＴＴ）
大澤 一郎（産業技術総合研究所）
大沢 英一（はこだて未来大学）
大澤 幸生（筑波大学）
小野 典彦（徳島大学）
北村 泰彦（大阪市立大学）
佐藤 理史（京都大学）
椹木 哲夫（京都大学）
島津 秀雄（ＮＥＣ）
菅沼 拓夫（東北大学）
菅原 俊治（ＮＴＴ）
角 康之（ＡＴＲ）
高間 康史（東京工業大学）
垂水 浩幸（香川大学）
津田 和彦（筑波大学）
中内 靖（防衛大学校）
長尾 確（名古屋大学）
西村 俊和（立命館大）
橋田 浩一（産業技術総合研究所）
平山勝敏（神戸商船大学）
藤本 和則（ＮＴＴ）
松原 繁夫（ＮＴＴ）
本村 陽一（産業技術総合研究所）
八槇 博史（京都大学）
横尾 真（ＮＴＴ）
吉田 哲也（大阪大学）

2

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

1

パネル： 社会的エージェントの可能性
石田 亨†

中西 英之†

長尾 確‡ 小野 哲雄††

エージェント研究の流れは，コンピュータインタフェースのるかどうか確かめる実験を行なった．この実験はバランス理一形態として人間のコンピュータ利用を支援する「個人的エ論にもとづいて行われた．バランス理論によると，2 人の人間ージェント」から，社会的役割を持ち，人と人のインタラクショがある対象に同じ心情(好意もしくは敵意)を持つ場合の方ンに介在する「社会的エージェント」へと向かっているようにが，片方は好意を持ち，もう片方は敵意を持つ場合よりも，2思われる．本パネルでは，ソフトウェアエージェントからロボ人の間の関係が良くなる．エージェントと人間 2 人の関係にットに至るまでの，我が国で最新の研究を紹介し，「社会的これを当てはめた．
実験ではまず，エージェントが同意の態度を示すことで人

エージェント」という新しい研究分野に定義を与え，その可間に好意を持たれ，逆に反意の態度を示すことで敵意を持

能性を議論する．

たれることを確かめた．次に，バランス理論が人間 2 人とエ

1

パネルプログラムージェントの関係に成り立つかどうかを観察した．バランス理• 司会 石田 亨

論が成立するとすれば，エージェントが両方の人間に同意• 社会心理学実験報告： エージェントは人間関係を操や反意の態度を取る場合の方が，片方にだけ同意して，もう片方に反意する場合より，人間同士の関係は良くなる．

作できるか 中西英之

実験の結果，人間同士の会話が無いときは，人間関係を• 社会的マシンとしての会話ロボット 長尾確

エージェントが操作できた．しかし，少しでも会話があると，• Robovie：コミュニケーションにおける身体性と関係性

エージェントは人間関係を操作できなかった．少しの会話が小野哲雄

エージェントの能力を失わせた原因を探るため会話分析を

2

各講演概要

行ったところ，会話を通して人間 2 人が互いに共感することが原因であると判明した．

2.1 社会心理学実験報告： エージェントは人間関

2.2 社会的マシンとしての会話ロボット係を操作できるか

長尾確 （日本ＩＢＭ東京基礎研究所）
中西英之（京都大学社会情報学専攻）

IBM 東京基礎研究所では、新たなヒューマンインタフェー

ソフトウェアエージェントが人間関係に及ぼす影響を明らスとして会話ロボットに関する研究を進めている。 IBM の取かにする第一歩として，エージェントが人間関係を操作できり組むロボットは、手足の動きなど外観の機能や動きを追求するのではない。「人間にとって役に立つ、便利な助手のよPanel: Potential of Social Agents† Toru ISHIDA, Hideyuki NAKANISHI 京都大学社会情報学専攻 Department of Social Informatics, Kyoto
University‡ Katashi NAGAO 日本アイ・ビー・エム株式会社 東京
基 礎 研 究 所 IBM Research, Tokyo ResearchLaboratory† † Tetsuo ONO 公 立 は こ だ て 未 来 大 学 , Future
University Hakodate

うな存在」として利用できるようにするための仕組み、つまり知能の部分にフォーカスを当てている。人間とのコミュニケーションの手段は非常に身近な「会話」である。しかしながら、人間が機械に対して話しかける行為に抵抗を感じるという問1

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

2

題をまずはクリアしなければ役には立たない。人間は無意識性」と「身体性」に注目し，社会的ロボットの実現可能性とそのレベルで、存在感があり、動作する対象が自分に注意をの研究方法について述べる．

向けていることを感じ取ると、それは「自分とコミュニケートす

エージェントやロボットなどの人工物が社会的存在となるる対象なのだ」と直感的に認識していると思われる。IBM はためには，人と自然で円滑なコミュニケーションを実現しなけ

直感的で臨場感のある「会話」によって、人間と機械がスムればならない．しかし，いまだに人は，エージェントやロボット

ーズなコミュニケーションを行なうために、「ロボット」という入とのインタラクションに違和感を持ってしまう．この理由は，これ物を利用している。ロボットは、話しかけられると、ユーザ

れまでのコミュニケーション研究が言語的側面だけを重視しーの意図を理解し、必要な情報を集めて自動的に処理し、てきたことによる．本発表では，自然なコミュニケーションを

適切な応答の生成を試みる。さらにはユーザーと行ってきた実現するには，その成立の基盤をなす「関係性」と「身体性」

会話の履歴を記憶する能力を持たせることにより、ユーザーに注目する必要があり，さらにそれらの機能をシステムに取の嗜好にあった行動をロボットが自発的に行なってくれるよ

り込む必要があることを主張する．

うになるだろう。また、ユーザーに特化し同調するような仕組

本発表では，2 つの研究事例を紹介する．まず，Ono [1]

みとして感情を理解できるシステムもあらかじめ組み込んでは，人とロボットの間に関係性を構築するためのインタフェー

おけば、ユーザーがうれしいとき、ロボットもうれしいし、楽しスとして，エージェントマイグレーションを用いた手法を提案

いとロボットも喜んでくれるだろう。ロボットが知性と感情を持した．具体的には，ユーザとインタラクトしていた携帯端末上

ちあわせるようになったとき、便利さだけでなく、人間を癒しのエージェントがロボットへ移動することにより，両者の間にてくれる存在となるだろう。人間との会話や知識を処理する関係を構築することを目指したものである．実験の結果，エインテリジェンスを持たせたとき、ロボットは人間にとって本当ージェントが移動したときユーザはロボットの発話を理解できに信頼のおけるパートナーになり得るだろう。また、ロボット

るが，移動しないときは理解できないことが明らかとなった．

は、コミュニティを媒介し、人同士のコミュニケーションを促進

次に，Ono [2]は，コミュニケーションにおける空間表象のするシステムとしても機能する。たとえば、会話ロボットは遠伝達と身体動作の関係に注目し，共創対話のモデルを提案

隔地にいるもの同士が非同期でコミュニケーションする場合した．本モデルは，身体の同調的動作による対話者間の関に、物理的な存在感を備えた、擬似的な対面性を実現する係の構築，および，この関係に基づく情報の伝達のメカニズことができる。また、長い経験を通じて個人情報を獲得した

ムを理解するためのモデルである．ヒューマノイド型ロボット

ロボットは、その人の外在化された記憶あるいはパーソナリを用いた実験の結果，人は身体の同調的な動作により円滑ティを持つシステムとして機能できるようになるだろう。これは、な情報伝達を行っていることが明らかとなった．

ロボット（あるいはエージェント）が文字通り人間の代理人に

これらの研究成果から，コミュニケーションにおける関係

なるということであるが、もしロボットの信用や責任という問題

性と身体性の重要性が確認できた．さらに，これらの結果は，がうまく技術的あるいは社会的に解決できれば、人間は自社会的ロボットの実現方法に示唆を与えるものである．

分のコピーあるいは分身を作って同時に複数の作業ができ[1] T. Ono, M. Imai (2000). Reading a Robot's Mind: A

るようになるだろう。そのようなロボットを社会的マシンと呼び、Model of Utterance Understanding based on the Theoryof Mind Mechanism, AAAI-2000, pp. 142--148.

その可能性と課題について議論する。

[2] T. Ono, M. Imai, H. Ishiguro (2001). A Model ofEmbodied Communications with Gestures between

2.3 Robovie：コミュニケーションにおける身体性とHumans and Robots, CogSci-2001, pp. 732--737.

関係性
小野哲雄（公立はこだて未来大学／ATR メディア情報科学研究所）
近年，エージェントやロボットの社会性に関する議論が行われている．本発表では，コミュニケーションにおける「関係2

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-171

義務と権利に基づく社会行動の即応制御モデル
大澤 一郎

A new computational model of socially interactive systems driven by obligations and rights is proposed. Obligations and rights are explicitly represented with the operators \O" and \R", and theinternal computation is interactively executed on are ective architecture based on recall and observation inside. We implement a prototype system toshow its performance on some social domains suchas business transactions, secure information handling, and driving on the road.

1

許可を双対なものとみなして体系化しようとして [4]、義務論理のパラドックスを生じさせていた。 Castel-

franchi [2]は権利を社会的コミットメントに基づいて派生するものと考えたが、 Norman [5]は権利を明示的に表現し、権利の概念を柔軟に扱おうとした。 Alonso[1]は、義務と権利の関係に着目し、権利の背後にある
周囲の義務を含めて権利を定義しようとしている。このような権利の明示的表現という論理的な研究の流れに対応して、 Sloman[3]らのグループは、データーベースにおけるセキュリティ管理を一般化して、役割 (ロール) に基づく義務と権利をオブジェクト指向モデルに導入している。また、 Wagner [8]はエージェント指向モ

はじめにコンピュータ・システムが社会のあらゆるところに

デルに義務と権利の枠組みを導入しようとしている。

入り込み、政治、経済、金融から、一般の人々の生活ま本研究では、このような研究動向を踏まえ、義務と権

でもが、世界中に張り巡らされたコンピュータ・ネット

利に基づいて社会的に自律動作するインタラクティブ

ワークによって密接に結び付けられつつある。このよ

システムの内部計算モデルを提案し、実際に実装したプ

うな状況下では、ネットワーク内で活躍するエージェン

ロトタイプによる社会的行動の内部シミュレーションを

ト・システムも社会的あるいは組織的に守られた特殊な示す。以下では、 2 節でシステム内部における情報の存在ではなく、社会人と呼ばれる成人のように社会で一表現形式を説明し、 3 節で基本となる計算モデルを集

人前に行動できなければならない。しかしながら、これ合的概念に基づいて提案する。そして、 4 節でマルチまでの大半のエージェント・システムは、 BDI モデル

エージェントによる実装と、 5 節でプロトタイプによで代表されるような、欲求ベースで行動する幼児のようるシミュレーションを紹介する。

な存在でしかなかった。

2

近年、社会的行為における義務と権利の重要性が明ら義務と権利の表現

かになるにつれ、この分野で多くの研究が行われつつ

2.1 BDI モデルの言語拡張ある。様相論理の一種である義務論理の多くは、義務と義務と権利に関する情報を明示的に扱うために、人工知能における BDI モデル [7]を言語拡張する。義務A re ective computational model of socially interactive systems
Ichiro Osawa, AIST 情報処理研究部門

を O (obligation) で表現し、権利を R(right) で表現する。

3

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

2.2

基本的な BDI モデルでは、システムの内部状態を信2

メッセージの解釈

念 B (belief) と 欲 求 D (desire) と 意 図 I (intention) に

オブジェクト指向システムでは、システムがメッセー

よって表現する。信念 B がシステムの信じている情報ジを受信すると、受信メッセージに対応するメソッドがで、欲求 D がシステムの望んでいる状態あるいは事自動的に起動され、メソッドのプログラムに従ってメッ

象、意図 I がシステムの決意した状態あるいは事象でセージの処理が実行される。メッセージの基本的な送受ある。例えば、システム s が x という命題を信じてい信機構に義務や権利の概念は含まれていないので、送て、 y という状態を望み、 z という事象を意図してい信者によって異なるメッセージ処理を行うようにするにる場合を以下のように表現する。

は、メソッドのプログラム内に送信者情報に基づいた分

Example 1

岐処理を内在させておかなければならない。

Bs:x

^

Ds:y

^

それに対してこのシステムでは、明示的に定義して

I s:z

欲求 D は実現すれば望ましい状態であり、将来におある規則に基づいて、受信したメッセージを義務 (あいて成り立つ可能性があると信じていれば、他の欲求とるいは情報) として解釈し、義務の履行という形式で相反していても良い。一方、意図 I は実現を確信してメッセージの処理を実行する。例えば、システム tom

身を委ねるような状態あるいは事象であり、将来においからの質問メッセージに対して必ず回答しなければなて必ず成立すると信じていなければならない。

らな いシス テムの 場合、以下 の規則 を定義 してお く(M s:内容@t は t から s へのメッセージを表す)。

義務 O は、あるシステム s がシステム t に対して状態あるいは事象の実現の責務を負っていることを表現

Example 4する。この義務の表現を用いれば、商店主が客から代金

Oi; s: ans; s; p[を受け取った場合に商品を渡さなければならないという規則を次のように記述することができる。但し、 [行為]3

は done(行為者; 行為) の略記である。

3.1

Example 2[

自己反映型即応計算モデル
計算モデル

信念 B 、欲求 D、意図 I 、および義務 O と権利 R にOs; t: give; t; x]

] ^ Bs:price(x; p) ^ Bs:[take; t; p]
なお、基本的な BDI モデルでは、意図 I は行為の実←] ← M i:[ans; s; p]@s ^ s = tom[

Ds: sell; t; x

基づいてシステムをインタラクティブに動作させるために、その計算機構として自己反映型 [6]の即応システム
RRS を用いる。この節では、この計算機構のベースに行を意図する場合と、状態の達成を意図する場合の両なっている計算モデルを集合論的な概念に基づいて定義方に用いられるが、本モデルでは意図 I を行為の実行する。
自己反映型即応システム RRS は、時々刻々と変化

意図のみに用い、状態達成の意図は自己に対する義務する状態 RSt と想起規則 RR とから構成され、時刻

Oi; i:x で表現している。

権利 R は、システム s に事象の実行権があることをt における状態 RSSR

De nition 1 (自己反映型即応システム RRS )RRS = (RSt ; RR)[t = 0; 1; 2; ; ; ]RSt = (SOt ; SMt ; SRt )ば、その客から代金を受け取る権利があるという規則を以下のように記述できる。

Example 3[]
Os; t:[sell; t; x] ^ Bs:price(x; p)^Bs::[take; t; p]

時刻 t におけるシステムの観測としては、外部世界

Rs: take; t; p←

t は、観測 S Ot と記憶 S Mt と想起

t の 3 状態から構成される。

表現する。例えば、商店主は客に商品を売る義務があれからのメッセージ M あるいはイベント情報 E 、若し
くはシステム自身がその時点で想起している信念 B と
欲求 D と意図 I と義務 O と権利 R に関する想起情報

t01 の中から、まだ未観測のものを一つだけ取捨選

SR択することができる。すなわち、システムの観測対象で4

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
ある世界 Wt は、メッセージ M とイベント情報 E か: I ×S Mt →E
RR4 : O ×S Mt →D + R
RR = RR1 + RR2 + RR3 + RR4
RR : (M + D + I + O )×S Mt →E + B DI + OR
RR3

ら成る外部世界 OWt と、想起 SRt01 に基づく内部世界から構成されており、時刻 t における観測 S Ot は次のように表現できる。但し、 : は

 とほぼ同義で、右以 上 の こと か ら 時刻 t に お ける 想 起 S Rt は、 記 憶側の集合に含まれる要素の種類 (タイプ) を拡張 BDI モ

t と想起規則 RR から以下のように定義できる。
De nition 5 (想起 SRt )S Rt = ∪x∈SMt ∩(M ∪D∪I ∪O) RR(x; SMt )S Rt : E + B DI + OR

デルのオントロジーに基づいて補足的に表現している。

:

SM+ E は、集合 S の要素が M あるいは E の情報であることを表している (尚、省略形として M + E の代わりに M E 、 B + D + I の代わりにBDI 、 O + R の代わりに OR を用いている)。
例えば S

3

M

ここで強調しておきたいことが一つある。このモデル

De nition 2 (観測 SOt )Wt = OWt ∪S Rt01 : M E + B DI + OR
S Ot  Wt −S Mt01 : M E + B DI + OR
jS O t j  1
記憶 S Mt は、直前の記憶 S Mt01 をベースに計算する。 S Mt は、 S Mt01 の情報をほぼ全て継承するが、の本質的な点であるが、システムが想起していても観測していない情報は、システムに認識されておらず、シス
テムの動作に全く影響を与えていないということである。 RR3 による行為の実行だけは、実行それ自体をシステムが観測していなくても外界に何かしらの影響があるので間接的な情報の観測によってシステムは影響されメッセージ M の場合は、そのメッセージから想起規則

るかも知れない。しかしながら、それ以外の信念 B 、

RR で想起され未観測のものがあるときだけ継承され

欲求 D、意図 I 、義務 O、権利 R の想起に関しては、る。解釈の終了したメッセージを記憶から抹消するため

直にその想起を観測しない限りはシステムに影響を与えである。そして観測 S Ot を加えることで時刻 t におけることがない。

る記憶 S Mt が計算できる。

De nition 3 (記憶 SMt )SMt = S Ot ∪(SMt01 −M )∪fmjm∈S Mt01 ∩M^jRR(m; S Mt01)−S Mt01 j > 0g
SMt : M E + B DI + OR
想起規則 RR は、記憶 SMt 内の情報に基づいて想3.2

記憶の自動調整シ ステ ムの 信念 B は時々 刻々変 化し てい る。あ る
時、活動用のエネルギーが不足してきたという信念に基
づいてエネルギーの補充欲求が生じたとしても、その後の信念の変化によって、活動用のエネルギーが不足しているという信念が消えてしまうことがある。このような起す る情報 を求め る規則 である。規 則は大 きく分 類

場合には、エネルギーの補充欲求も消滅してほしい。こして 4 つのタイプがある。 (1) メッセージ M から信念の思考の自動調整機能は以下のように簡単に実現でき

B あるいは義務 O を想起する規則 RR1 、(2) 欲求 Dる。

De nition 6 (欲求・意図・権利の活性状態)
xはactive , x∈SRt ∩S Mt ∩(D ∪I ∪R)から別の欲求 D 、あるいは意図 I 、義務 O 、権利 R を想起する RR2 、 (3) 意図 I から実行プロセスを想起す
る RR3 、そして (4) 義務 O から欲求 D あるいは権利システムの欲求 D 、意図 I 、権利 R は、想起規則に

R を想起する RR4 である。 RR1 でメッセージを解釈

基づ いて想 起され、 それが観 測され ること で活性 化

し、 RR2 はいわゆるトップダウンのプランニング、し、システムの動作に影響を与える。しかしながら、

t 内の信念等の変化によって、活性化していた欲求

RR3 が意図に対応する行為の実行、 RR4 が義務 O かSMら欲求 D や権利 R を想起する。

D 、意図 I 、権利 R の想起がなくなってしまうことがDe nition 4 (想起規則 RR)
RR1 : M ×S Mt →B + O
RR2 : D ×S Mt →D + I + O + Rある。この場合、観測によって S Mt 内に加えられている欲求 D、意図 I 、権利 R に関して、以下の定義にしたがって活性状態でなくなったものを継承しないように5

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-174する。

項の 1 つ目は表示されていなければならない情報で、

De nition 7 (修正 SMt )S Mt = S Ot
∪S Mt01 ∩(E ∪B ∪O)∪fxjx∈S Mt01 ∩(D ∪I ∪R) ^ xはactiveg∪fxjx∈S Mt01 ∩M^jRR(x; S M + t 0 1)−S Mt01 j > 0g

2 つ目は非表示でなければならない情報である (他エー
ジェントの表示情報は「情報 @ エージェント」という表現形式によって自己の表示情報と区別している)。出

4

力項には、入力項の条件が満たされた時に自己の表示

D に付け加えるべき情報を定義しておく。以下に示し

Aた例は、食べたいという情報があり、食べる権利のあるものに関する情報がエージェント m から観測できない

マルチエージェントアーキテクチャ

4.1

場合に、食べる権利のあるものを欲求するという情報を自己の表示 AD に付け加えるという規則である。

基本エージェント

Example 6

前節で述べた自己反映型即応システムを効率よく実装

fするために、表示と観測に基づいて各エージェントが自[]g×fRx:z 3 [eat; z ]@mg → Dx:y 3 [eat; y ]Dx: eat

律動作するマルチエージェントアーキテクチャ [9]を用4.2いる。各エージェントは、自己および他エージェントのエージェントの拡張

表示している情報を常時観測し、エージェント毎に定義

規則 AR を拡張し、自己の表示情報を更新するだけされている規則に基づいて表示情報の更新計算を行う。

でなく、他エージェントに直接作用して他エージェント

システム内で変化する情報は全体の僅かな割合なので、の表示情報を更新できるようにしてある。すなわち、出この計算は非常に素早く実行できる。全てのエージェン

力項の情報定義を「情報 @ エージェント」という形式

トの表示情報が固定した時点で、自己反映型即応システ

で記述しておくことで、入力項の条件が満たされた時にムの一時刻における計算が終了する。

出力項の情報が別のエージェントの表示情報として用い

De nition 8 (エージェント)
エージェントA = (観測AO ; 規則AR ; 表示AD )られる。これはエージェントのモジュール性を損なうよ
うにも思えるが、オブジェクト指向のメッセージに代わ各エージェントはローカルに情報を保持し、保持してるものとして利用することができる。

いる情報が全てそのまま表示される。自己の表示していそして、人間の長期記憶あるいはデーターベースのよる情報は全て観測できるが、他エージェントの表示情報

うに持続性をもって蓄えられる情報を処理するために、に関しては予め観測したいものを宣言しておく。すなわ

特殊なエージェント m を用意した。この m エージェン

ち、観測したい情報の種類と情報源を予め観測 AO とトに対して、「+情報@m」という形式で直に表示情報して定義しておく。例えば、 memory エージェント内を送ると、内部に情報が書き込まれ持続的に表示されの意図情報を観測したい場合には以下のように定義してる。その後に情報を抹消したい場合は「 情報@m」とおく。

いう形式で m エージェントに抹消希望の情報を送る。

0

Example 5[observing; I x:y @memory ]4.3※xとy は変数

自己反映型即応システムのアーキテクチャ

この定義により、 memory エージェントの表示 AD

自己反映型即応システム RRS は、 m エージェントに I a:[eat] 等の情報が表示されていれば、その情報をを含む 12 の主要エージェントから構成される (図 1)。

観測することができる。

sensor エージェ ント は、外 部 から のメッ セージ あるDe nition 9 (規則 AR )規則AR : 表示情報×非表示情報 → 表示情報
規則 AR は、観測した自己および他エージェントの表示情報から自己の表示 AD を更新計算する。各規則

ントは sensor エージェントが観測したメッセージをは 2 つの入力項と 1 つの出力項から構成される。入力

解 釈 終了 ま で 一時 的 に 保持 す る。 メッ セージ 解 釈 はいは イベン ト情報、 若しくは システ ムが想 起して い
る BDI+OR 情報の中からまだ未観測のものを観測して m エージェントに書き込んでいく。 stm エージェ

6

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

8.4857

5

3

5.1

893
-.817.

149.49154

71/09

5

義務と権利に基づく社会行動システム
プロトタイプ・システム

これまでに、本システムにおける情報表現 (2 節)、計

5+21/*9*9154

算モデル (3 節)、実装方法 (4 節) に関して説明してき149.767.9*9154

た。この節では、 SUN の SICStus

3.357;

Prolog (v.3.8.5)

上に実装したプロトタイプシステムでの実験に基づき、
62*4

7.,*22

義務と権利をベースにした社会行動の即応制御がどのよ*,9:*957

うに実現できるかを概説する。
例 題 と して、 こ の プロ ト タ イ プシ ス テ ムに 対 し、interpretation エージェントが想起規則 RR1 に基づ

Tom という人物から Jo という人物の血液型を尋ねられたという簡単な状況を考える。システムは Tom に対する問いに対しては回答する義務があり、 Jo はシ

いて行い、結果を recall エージェント内に表示する。

ステムが管理している病院の患者なので、システムは

図1

アーキテクチャ

desire エージェントと intention エージェントと rightdoctor 権限があればデーターベース DB に問い合わせエージェントは欲求 D と意図 I と権利 R を管理し、て調べることができる。

活性状態のものを memory エージェント内に表示し、活性状態でなくなったものを m エージェント内から抹5.2

消する。 obligation エージェントは義務 O を管理し、この例題で必要となる主要な想起規則は、以下の想起

未達成 の義務を memory エージェ ント内に表 示し、規則と次節 (5.3.) で述べる役割に基づく想起規則の二達成した義務を m エージェントから抹消する。 plan

種類になる。

エージェントは memory エージェント内の BDI+OR

Example 7

情報 を観測し、 想起規 則 (RR2 と RR3 と RR4 ) に 基

想起規則 (RR1 )づ き想 起 され た情 報 を recall エー ジェ ント あ るい は

(1) Oi; tom:[ans; tom; q ] ← M i:[ans; tom; q ]@tom

想起規則

想起規則 (RR2 )actuator エージェントに表示する。

込まれていないものを各単位時間毎に最大で一つ取捨選(2) Dx:(y : p) ← Dx:[ans; z; y : p] ^:Bx:(y : p > a)(3) Dx:role(doctor ) ← Dx:(y : p) ^ B x:patient(y ) ^:Rx:role(doctor)(4) I x:[ask; DB; q] ← Dx:[ask; DB; q ](1) の想起規則は、 Tom からの問い合わせに対する回答義務を表現している。 (2) は、対象 y の属性 p 値

択し、 m エージェントに書き込んでいく。この観測制を対象 z に報告したい欲求があるが、その値を知らな

限は、システム内に雑多なシンボル情報が一度に流れ込い場合に、その値を知りたいという欲求の想起で、 (3)んで解釈処理等が混乱するのを避けるためで、どの情報は、対象 y の属性 p 値を知りたいという欲求があり、を選択するかはこのエージェントに託されている。以下

y は患者であ るが、 doctor 権限がない場合に doctorは現在の取捨選択の優先順序である (同優先度内ではラ権限が欲しくなるという欲求の想起である。最後の (4)ンダム)。

は、データーベース DB に問い合わせたいという欲求

4.4

sensor エージェント

sensor エージェントは、外部からのメッセージとイ

ベント情報、およびシステムが想起している BDI+OR
情報を観測し、その中からまだ m エージェントに書き

1. 外部の注目情報源 (話相手等) からの情報
2. 内部で想起された BDI+OR 情報
3. 外部からの情報があれば、問い合わそうという意図の想起規則である。
その他に、本論文中では範囲外としてあまり言及してこなかったが、義務達成時に義務情報を抹消するための7

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
規則が必要になる。

6

Example 8(5) :Ox; y:[ans; y; q ]← Ox; y:[ans; y; q ] ^ [ans; y; q > a]@x6

結論と今後の方向

義務と権利に基づいて社会的に自律動作するインタラ
クティブシステムの内部モデルを提案した。表現形式として BDI モデルを拡張し、計算モデルとして自己反映

5.3

役割に基づく情報管理 (役割エージェント)型即応計算モデルを提案した。

義務と権利に関する多くの規則は、部長や医者等の役

マルチエージェントベースのプロトタイプ実装によ割 (権限) という枠組みで管理するのが望ましい [3]。こり、例題として取り上げた doctor 権限による質疑応答のシステムでは、役割に応じて専門の役割エージェント

以外に、商取引での基本的な売買における義務と権利のを用意し、役割に応じた義務と権利の定義が可能になっ問題や、自動車の運転における左方優先義務を順守したている。さらに、役割によって得た情報を役割エージェ

直進等の例題シミュレーションでシステムがうまく動作

ント内で管理することで、異なる役割での越権的な情報することをこれまでに確認している。

処理を防いでいる。以下の想起規則は doctor という役

Example 10

割エージェント内で定義されている。

店主の想起規則 (RR4 )Example 9[]

Rx=shop: take; y; m^

← Ox; y:[sell; y; a]

想起規則 (RR2 )(6) Rx=doctor:[ask; DB; y : p]
← Dx:(y : p) ^ B x:patient(y)(7) I x=doctor:[ans; z; q > a]
← Dx:[ans; z; q ] ^ Bx=doctor:(q > a)
想起規則 (6) は、対象 y の属性 p 値を知りたい欲求(

Bx:price a; m)^:[take; y; m]@x

運転手の想起規則 (RR2 )[] ← Dx:[go] ^ :Bi:exist(c; L)

Rx=driver: move

今後は、システムに複数の役割がある場合の役割同士間の相互関係モデル、および義務の達成条件の一般的なモデル、そして達成不可能な場合の責任 (義務) のモデがあり、 y が患者であれば、データーベース DB に問ルを構築し、システムに実装していきたいと考えていい合わす権利の想起である。 (7) は、対象 z に質問 qる。また、 Sloman 流の役割ベースの義務と権利の管の回答を行いたい欲求があり、 doctor 権限においてそ理方式と Wagner のダイアグラムを融合させ、義務との回答を知っていれば、 doctor という役割条件で回答権利のダイアグラムから想起規則を自動生成することを行う意図が想起されるという規則である。

で、既存の義務と権利に関する外部モデルとこの論文で提案した内部モデルをリンクさせていきたい。

5.4

シミュレーション (情報管理)

図 2に実行履歴を示す。観測情報の右側は情報源で、

参考文献[1] Eduardo Alonso. Right and coordination in multiagent systems. In UKMAS'98, 1998.
[2] Cristiano Castelfranchi. Commitments: From individual intentions to groups and organizations. In
In Proc. ICMAS-95, pp. 41{48, 1995.
[3] Emil C. Lupu and Morris Sloman. Towards a role
based framework for distributed systems management. Journal of Network and Systems Manaement,
Vol. 5, No. 1, pp. 5{30, 1997.
[4] J. J. Ch. Meyer and R. J. Wieringa, editors. Deontic logic in computer science. Wiley&Sons, 1993.
[5] Timothy J. Norman, Carles Sierra, and Nick R.
Jennings. Right and commitment in multi-agent
agreements. In In Proc. ICMAS-98, pp. 222{229,1998.

想起の○が未観測の情報、●が観測済みの情報を表している。最初 (時刻 320) に Jo が患者であるという情報を観測している。時刻 331 で Tom からの問い合わせメッセージ (Jo の血液型) を受けた。時刻 332 で Tomからのメッセージを回答義務として解釈し、時刻 333以降で doctor 権限欲求を想起している。時刻 416 でdoctor 権限を得たので DB への問い合わせを実行し、

時刻 423 に情報 (A 型) を得ている。その結果、 Tomへの回答意図が想起され、時刻 424 でその意図を認識し、 doctor 権限で Tom への回答を行っている。

8

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
時刻 t

観測 (S Ot )00320

Bi.patient(jo) @ i

00331[ans,tom,jo:bt] @ tom○ Oi,tom.[ans,tom,jo:bt]

00332

Oi,tom.[ans,tom,jo:bt] @ i○ Di.(jo:bt)

00333

Di.(jo:bt) @ i○ Di.role(doctor)

7

想起 (SRt )● Di.(jo:bt)

00416

Ri.role(doctor) @ i○ Ri/doctor.[ask,db,jo:bt]● Di.(jo:bt)

00417

Ri/doctor.[ask,db,jo:bt] @ i○ Di/doctor.[ask,db,jo:bt]● Ri/doctor.[ask,db,jo:bt]● Di.(jo:bt)

00418

Di/doctor.[ask,db,jo:bt] @ i○ Ii/doctor.[ask,db,jo:bt]● Di/doctor.[ask,db,jo:bt]● Ri/doctor.[ask,db,jo:bt]● Di.(jo:bt)

00419

Ii/doctor.[ask,db,jo:bt] @ i○ [ask,db,jo:bt] @ i/doctor● Ii/doctor.[ask,db,jo:bt]● Di/doctor.[ask,db,jo:bt]● Ri/doctor.[ask,db,jo:bt]● Di.(jo:bt)

00423

Bi/doctor.(jo:bt>a) @ db

○ Ii/doctor.[ans,tom,jo:bt>a]● Ri/doctor.[ask,db,jo:bt]● Di.(jo:bt)

00424

Ii/doctor.[ans,tom,jo:bt>a] @ i○ [ans,tom,jo:bt>a] @ i/doctor● Ii/doctor.[ans,tom,jo:bt>a]● Ri/doctor.[ask,db,jo:bt]● Di.(jo:bt)

00425[ans,tom,jo:bt>a] @ i/doctor
図2

シミュレーション[6] Ichiro Osawa. A computational model of an intelligent agent for natural language dialogue systems.
In Proc. of PRICAI'90, pp. 209{214, 1990.
[7] Anand S. Rao and Michael P. George . Modelingrational agents within a bdi-architecture. Technical
Report 14, AAII, 1991.

[8] Gerd Wagner. Towards agent-oriented information systems. Technical report, Freie University
Berlin, 1999.
[9] 大澤一郎. 人間と対話する知能エージェントのモデル. コ
ンピュータ・ソフトウェア, Vol. 13, No. 2, pp. 35{44,
1996.

9

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

1

BDI Logic の sequent calculus による演繹
体系
新出尚之 高田司郎

In this paper, we give a sound and complete

我々はそれを解決する方法として, BDI アーキテク

deduction system for BDI logic whose base is re-

チャの Logic based な実現を検討している. そのためstricted to propositional CTL, using Gentzen’s se-には , BDI Logic の公理化や, 一階述語論理の導出原

quent calculus. In this system we can construct

理に相当するものの構築が必要となる. しかし , 現状

a proof of a formula using Wang’s algorithm with

では BDI Logic の公理化は十分とはいえず , ベース

some extension. In this way, we can check the prov-

を命題論理の CTL に制限した BDI Logic の subset

ability of a formula straightforwardly, and in addi-に対する健全で完全な演繹体系が Rao らによって与tion, can give an easily understandable proof of the

えられている [3] 程度であるが , これは Hilbert styleformula.

のもので , 論理式の証明を見通しよく行うには向いておらず , BDI logic で書かれた仕様の論理的検証など

1 はじめににも向いていない.

BDI Logic [2] は , branching time temporal logic

本論文では , Rao らと同じく命題論理の CTL をベーの 一種で あ る CTL* [1] に , BEL(信念), DESIRE(願スとする BDI Logic の subset について, Gentzen の望), INTEND(意図) といった心的状態を表す様相を導sequent calculus [7] による健全で完全な演繹体系を入して拡張した時相述語論理であり, マルチエージェ

示す. これは , 彼らが 与えた tableau 法による BDI

ント環境を含む合理的エージェントの仕様記述 [2] [5]logic の論理式の充足可能性の判定アルゴ リズム [3]などに用いられている.

に , ほぼそのまま対応するものとなっている. また,

BDI Logic を基礎概念においた合理的エージェン

この体系では , 命題論理の証明手続きとして知られる

トの実現手法として, BDI アーキテクチャ [4] [6] が提Wang のアルゴ リズムを拡張したものを用いて, 論理

案されている. しかし , 現状の BDI アーキテクチャ式の証明可能性のチェックを見通しよく行え, 証明もは , 動作の基本となるループや心的状態の更新が手続人間にとって直感的に理解しやすいものが得られる.

き的に行われているなど , 論理体系との整合性が不十分な箇所が多いため, 仕様の自動検証が行いにくい,

2 論理式の定義

論理的記述力への制約が多いなどの問題点がある.

命題記号の集合 P をあらかじめ決めておく. 命題
論理の CTL をベースとする BDI Logic の論理式は ,Deduction Systems for BDI Logics Using SequentCalculus.
NIDE Naoyuki, 奈良女子大学理学部情報科学科. Nara
Women’s University.
Shiro Takata, ATR メディア情報科学研究所. ATR Media Information Science Lab.

以下のように定義される.

• p ∈ P ならば p は論理式 (これを原子命題という)• φ と ψ が論理式ならば φ ∨ ψ, ¬φ, AX φ, A(φ Uψ), E(φ U ψ), BEL(φ), DESIRE(φ), INTEND(φ)

10第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

20

満たす w ∈ W が存在するもそれぞれ論理式• (I-D) 任意の w ∈ W に対し , (w, t, w0 ) ∈ I を

必要に応じて括弧で曖昧さを除去. true は q ∨ ¬q の満たす w0 ∈ W が存在する

略記 (但し q は 適当に 選んで 固定し た P の 要素),を全て満たせば (BKD45 DKD IKD )CTL -structure と呼ぶ.

false, φ ∧ ψ, φ ⊃ ψ, φ ⇔ ψ は それぞ れ ¬true,¬((¬φ) ∨ (¬ψ)), (¬φ) ∨ ψ, (φ ⊃ ψ) ∧ (ψ ⊃ φ) の直感的には , state が一般の時相論理での「点時刻」,

略記, また EX φ, AF φ, EF φ, AG φ, EG φ はそれぞあるいは一般の様相論理の可能世界意味論での「可能れ ¬ AX ¬φ, A(true U φ), E(true U φ), ¬ EF ¬φ,世界」にあたり, Rw が時間の前後関係, B, D, I が様

¬ AF ¬φ の略記. 優先順位は , 単項論理記号 (¬, AX な相としての信念 · 願望 · 意図を表す可視関係である.

ど ), ∧, ∨, ⊃ の順とし , 冗長な括弧は適宜省く.

3.2 論理式の解釈と恒真性

3 意味論
3.1

w ∈ W に 対し , St w に 属 す る state の 無 限 列

BDIK
CTL -structure(t0 , t1 , · · ·) で , 条件 t0 Rw t1 , t1 Rw t2 , · · · を満たす

以下のものを定めておく.

ものを, t0 で始まる w 上の path という.

BDIK
CTL -structure M = hW, {St w | w ∈ W }, {Rw• 可能世界の集合 W (6= ∅)• W の各要素 w に対して, state の集合 St w (6= ∅)| w ∈ W }, L, B, D, Ii と世界 w ∈ W , state t ∈ St wとその上の関係 Rw ⊂ St w × St w (但し , Rw はに対し , 論理式 φ が真である ((M, w, t) |= φ と書く)

total であること. すなわち, 全ての t ∈ St w に対ための条件を, 以下のように定義する.

00

し , ある t ∈ St w が存在して t Rw t を満たさね• φ が primitive proposition である (φ ∈ P ) 場合,ばならない)(M, w, t) |= φ iff φ ∈ L(w, t)• W の各要素 w と St w の要素 t の組に対し , 命題

• (M, w, t) |= ¬φ iff (M, w, t) 6|= φ

記号への真偽値割り当て L(w, t) ⊆ P

• W,

S

S

w∈W

w∈W

• (M, w, t) |= φ ∨ ψ iff (M, w, t) |= φ or

St w , W 上の 3 項関係 B, D, I ⊂ W ×(M, w, t) |= ψ• (M, w, t) |= AX φ iff for all t0 s.t. t Rw t0 ,St w × W . 但し , 条件

◦ (w, t, w0 ) ∈ B かつ t ∈ St w ならば t ∈ St w0(M, w, t0 ) |= φ

◦ (w, t, w0 ) ∈ D かつ t ∈ St w ならば t ∈ St w0• (M, w, t0 ) |= A(φ U ψ) iff◦ (w, t, w0 ) ∈ I かつ t ∈ St w ならば t ∈ St w0が満たされねばならない†1

t0 で始まる w 上の任意の path (t0 , t1 , · · ·) に対し ,その中のある state ti があって (M, w, ti ) |= ψ

このとき, tuple M = hW, {St w | w ∈ W }, {Rw |かつ for all j s.t. 0 ≤ j < i, (M, w, tj ) |= φw ∈ W }, L, B, D, Ii を BDIKCTL -structure と呼ぶ. ま• (M, w, t0 ) |= E(φ U ψ) iff

た, それがさらに条件

t0 で始まる w 上のある path (t0 , t1 , · · ·) とその0• (B-D) 任意の w ∈ W に対し , (w, t, w ) ∈ B を中のある state ti があって, (M, w, ti ) |= ψ かつ

満たす w0 ∈ W が存在する
0

for all j s.t. 0 ≤ j < i, (M, w, tj ) |= φ000

• (M, w, t) |= BEL(φ) iff for all w0 s.t. (w, t,• (B-4) 任意の w, w , w ∈ W に対し , (w, t, w )∈ B かつ (w0 , t, w00 ) ∈ B ならば (w, t, w00 ) ∈ Bw0 ) ∈ B, (M, w0 , t) |= φ

• (B-5) 任意の w, w0 , w00 ∈ W に対し , (w0 , t, w)• (M, w, t) |= DESIRE(φ) iff for all w0 s.t. (w, t,∈ B かつ (w0 , t, w00 ) ∈ B ならば (w, t, w00 ) ∈ Bw0 ) ∈ D, (M, w0 , t) |= φ0

• (M, w, t) |= INTEND(φ) iff for all w0 s.t. (w, t,• (D-D) 任意の w ∈ W に対し , (w, t, w ) ∈ D をw0 ) ∈ I, (M, w0 , t) |= φ
†1 Rao らの論文 [2] [3] ではこの条件を明示的に要請してはいないが , BEL などの様相記号の意味の定義が整合的であるためには明らかに必要であろう.

論理式 φ が , 全ての BDIKCTL -structure M の全ての世界 w, state t に対し (M, w, t) |= φ を満たすと11

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
Kき, φ は BDIKCTL -valid であるといい, BDICTL |= φ と書く. また, 全ての (B

KD45

KD KD

D

I

3

定義 4.1 S を sequent とする. 各ノード が 1 つのsequent をラベルとして持ち, 根のラベルが S であり,)CTL -structure M

について同様の条件を満たすとき, φ は (B

KD45

KD

)CTL |= φ

N の子ノード が N1 , · · · , Ni であり, N およびと書く (いずれも, 誤解のおそれのない場合単に |= φ

N1 , · · · , Ni のラベルが S 0 , S1 , · · · , Si であるならと書き, 単に valid であるということがある).

ば,

I)CTL -valid であるといい, (B

KD45

KD KD

D

I

D

KD

かつ葉以外の任意のノード N が条件

S1

···
S0

Si

という推論規則が存在するを満たす木を, S の推論木という.

4 演繹体系

以下では , ρ = A(φ U ψ) の場合は AX ρ を , また

本 章 で は 演 繹 体 系 (BBDIKCTL を導入する.

KD45

KD KD

D

I

ρ = E(φ U ψ) の場合は EX ρ を , ÆX ρ と表記する.

)CTL お よ び

なお本稿では , sequent の →定義 4.2 S の推論木 T の葉でないノード N0 から ,の両側は論理式の multi set とする (従って exchange

その子孫の葉ノード L までの経路 N0 , N1 , · · · , Nnの推論規則は必要ない). また本稿では , 文中で se-(= L) が , 以下の条件を全て満たすとき, この経路をquent の範囲を明示するために , sequent 全体を [ ] で導出のループという.

1. N0 と L は等しいラベルを持つ

くくることがある.

2. N1 , · · · , Nn−1 の中には L と等しいラベルを持以下, ギリシア大文字は論理式の multi set, ギリシ
ア小文字は単一の論理式を表す. また, 論理式の multi

つものはないset Γ と単項論理演算子 K に対し , K(Γ) で Γ の各論

定義 4.3 ある論理式 ρ = A(φ U ψ) あるいは ρ =理式に K を付加して得られる multi set を表す.

E(φ U ψ) が存在して, 導出のループ N0 , N1 , · · · , Nnとその各ノード のラベル S0 , S1 , · · · , Sn (= S0 ) が以下の条件を全て満たすとき, これを終局性論理式 ρ を

4.1 推論規則
KD45

(B

D

KD KD

I

持つ導出のループという.

)CTL の演繹体系は , 表 1 の推論規則のうち BEL–K, DESIRE–K, INTEND–K 以外の全て

1. Si = [ρ, Γ → ∆] かつ Si+1 = [φ, ÆX ρ, Γ → ∆](これらを含めてもよいが冗長), また BDIKCTL の演繹体を満たす整数 i (0 ≤ i < n) と Γ, ∆ が存在する.

系は同表のうち BEL–KD45, DESIRE–KD, INTEND–

また, Si = [ρ, Γ → ∆] かつ Si+1 = [ψ, Γ → ∆]KD 以外の全てを推論規則として持つ.

を満たす整数 i (0 ≤ i < n) と Γ, ∆ は存在しない.

これらの規則は , 実は Rao らの BDI logic の決定(大まかには , S0 から Sn までの過程のどこかで ,アルゴ リズム [3] の pseudo tableau の構築の各 step

ρ に対する AU 左か EU 左が適用されており, かに対応し ている. 例えば 規則 BEL–KD45 は , [3] のつ, 導出のループはその前提のうち右へ行く経路)

6.2 節, pseudo-(B

KD45

D

KD KD

I

2. Si = [Γ, Γ0 → ∆, ∆0 ] および Si+1 = [Γ → ∆])CTL -tableau の構築にを満たす全ての整数 i (0 ≤ i < n) と Γ, Γ0 , ∆, ∆0

おける (d) に相当する.

に対し , Γ0 に含まれる全ての論理式はこの体系では , 前提が結論より大きくなる規則が存在するので , Wang のアルゴ リズムをそのまま適用は• 原子命題できない. しかし , 6 章で述べるように , Weak の形を• トップレベルのオペレータが BEL, DESIRE,
INTEND のいずれかである論理式

制限することによって, 証明図が必ず有限で止まるか• Γ に含まれる論理式

ループし , 無限に伸びないようにすることができる.

のいずれかである. また, ∆0 に含まれる全ての論

従って証明可能性の判定は有限の手間で行える.

理式は4.2 証明可能性の定義• 原子命題KD45 KD KD
ここでは , BDIK
D I )CTL の演
CTL および (B• トップレベルのオペレータが BEL, DESIRE,
INTEND のいずれかである論理式

繹体系での, sequent の証明可能性の定義を与える.

12

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
表1
Γ → φ, ∆(¬左)¬φ, Γ → ∆(BKD45 DKD IKD )CTL , BDIKCTL の推論規則

φ, Γ → ∆ ψ, Γ → ∆(∨左)φ ∨ ψ, Γ → ∆φ, Γ → ∆(¬右)Γ → ¬φ, ∆Γ → φ, ψ, ∆(∨右)
Γ → φ ∨ ψ, ∆Γ→∆
(Weak)
Γ, Γ0 → ∆, ∆0

ψ, Γ → ∆ φ, AX A(φ U ψ), Γ → ∆(AU 左)A(φ U ψ), Γ → ∆Γ → ψ, φ, ∆ Γ → ψ, AX A(φ U ψ), ∆(AU 右)
Γ → A(φ U ψ), ∆ψ, Γ → ∆ φ, EX E(φ U ψ), Γ → ∆(EU 左)E(φ U ψ), Γ → ∆Γ → ψ, φ, ∆ Γ → ψ, EX E(φ U ψ), ∆(EU 右)
Γ → E(φ U ψ), ∆Γ→Θ
(AX–KD)
AX(Γ) → AX(Θ)

4

Γ→φ(BEL–K)
BEL(Γ) → BEL(φ)Γ, BEL(Γ) → BEL(∆), Θ, BEL(Θ)(BEL–KD45)
BEL(Γ) → BEL(∆), BEL(Θ)Γ→φ(DESIRE–K)
DESIRE(Γ) → DESIRE(φ)Γ→Θ(DESIRE–KD)
DESIRE(Γ) → DESIRE(Θ)Γ→φ(INTEND–K)
INTEND(Γ) → INTEND(φ)Γ→Θ(INTEND–KD)
INTEND(Γ) → INTEND(Θ)(但し , Θ は高々1 つの論理式とする)• ∆ に含まれる論理式の葉までが , 終局性論理式 A(p U BEL(q)) を持つ導出のいずれかである.

のループになっていることに注意.

(大まかには , S0 から Sn までの過程で Weak を

こ の 証 明 の 下 か ら 3 段 目 以 上 は, 直 感 的 に は適用して, AX, AU, EU をトップレベルに持つ論「 BEL(q) ならば A(p U BEL(BEL(q))) 」と , 「『 A(p U

理式が消されることはない)

BEL(q)) ならば A(p U BEL(BEL(q))) 』がある時刻で定義 4.4 sequent S が証明可能であるとは , 以下の成り立つならばその直前の時刻でも成り立つ」を示す

条件を全て満たす S の推論木 T が存在することをいことによって, 数学的帰納法に近い感覚で「全ての時う. ここで initial sequent とは , [Γ, φ → ∆, φ] という刻で『 A(p U BEL(q)) ならば A(p U BEL(BEL(q))) 』

形の sequent である.

が成り立つ」を示していることになる. このように ,1. T の全ての葉は , initial sequent をラベルとし得られる証明は , Hilbert style の演繹体系に比べ, 直て持つか , あるいは導出のループの終点である

感的な理解しやすさで優るものになる.

2. T の全ての導出のループを合わせたグラフ (導また, 全く同様にして, 例えば A(INTEND(AF φ) U

BEL(φ))

出のループに含まれるノード と枝全てからなる⊃A(INTEND(AF φ)

U

BEL(φ) ∨0グラフ) の各連結成分 T (これは T の部分木にな¬ BEL(EF φ)) の証明もできる. これは , コミット メる) に対し , ある論理式 ρ があって, T 0 に含まれント 戦略 [2] の blind commitment が single-minded

る T の導出のループは全て, 終局性論理式 ρ を

commitment より強いことの証明になっている.

持つ

5 健全性

KD45 KD KD
BDIK
D I )CTL の演繹体系に
CTL および (B

本 章 で は (BKD45 DKD IKD )CTL の 健 全 性 を 示 す.

おいて, [→ φ] という sequent が証明可能であるとき,

BDIKCTL の健全性もほぼ同様に示せる.

論理式 φ が証明可能であるという.

sequent S = [φ1 , φ2 , · · · , φn → ψ1 , ψ2 , · · · , ψm ] (n4.3 例

≥ 0 ≤ m) に対し , 論理式 ¬φ1 ∨· · ·∨¬φn ∨ψ1 ∨· · ·∨ψm
KD45

KD KD

)CTL における論理式 A(p U(但し n = m = 0 のときは false) を , S に対応する論

BEL(q)) ⊃ A(p U BEL(BEL(q))) の証明である (ス理式と呼ぶ. S に対応する論理式が (M, w, t) で真の図 1 は , (BDI

ペースの都合で図の一部を持ち上げ ている). このとき, (M, w, t) で S が真であるといい, (M, w, t) |= S

論理式は ¬ A(p U BEL(q)) ∨ A(p U BEL(BEL(q)))と書く. 特に , sequent S が valid であるとは , S に対の略記であるため, 証明の一番下はそれに → を前応する論理式が valid であることと定義する.

置し た ものに なって い る. な お, 下から 3 段目の補題 5.1 導出のループ の中には , 空 sequent [→] はA(p U BEL(q)) → A(p U BEL(BEL(q))) から一番右

現れない.

13

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

図1

5(BKD45 DKD IKD )CTL での証明の例

p, AX A(p U BEL(q)) → BEL(BEL(q)), pA(p U BEL(q)) → A(p U BEL(BEL(q)))(AX–KD)
AX A(p U BEL(q)) → AX A(p U BEL(BEL(q)))(Weak)p, AX A(p U BEL(q)) → BEL(BEL(q)), AX A(p U BEL(BEL(q)))(AU 右)p, AX A(p U BEL(q)) → A(p U BEL(BEL(q)))

q, BEL(q) → BEL(q), BEL(BEL(q))
q, BEL(q) → BEL(q), BEL(BEL(q))(BEL–KD45)(BEL–KD45)
BEL(q) → BEL(BEL(q))
BEL(q) → BEL(BEL(q))(Weak)(Weak)
BEL(q) → BEL(BEL(q)), p
BEL(q) → BEL(BEL(q)), AX A(p U BEL(BEL(q)))(AU 右)
BEL(q) → A(p U BEL(BEL(q)))
A(p U BEL(q)) → A(p U BEL(BEL(q)))(¬右)→ ¬ A(p U BEL(q)), A(p U BEL(BEL(q)))(∨右)→ ¬ A(p U BEL(q)) ∨ A(p U BEL(BEL(q)))

証明 定義から , 導出のループは長さ 2 以上でなけれ6(AU 左)

事実は変わらない.

ばならないが , 結論を空, 前提を非空にできる推論規

しかし , AX–KD を適用するには , Weak で BEL(Ξ)

則は存在しない.

を消さねばならず , この時, sequent に現れる各論理

補題 5.2 導出のループの中では , 推論規則 AX–KD

式が持つ BEL の個数の最大は減る. そして, それを増か BEL–KD45 のいずれかが 少なくとも 1 回適用さやせる規則は存在しない. 従って, BEL–KD45 が使われており, かつ, その両方は使われていない. また,れているならば AX–KD は使われていない.

DESIRE–KD, INTEND–KD は使われていない.

また, DESIRE–KD が 使われているとすると, se-

証明 導出のループの中では , 前提が結論より小さく

quent に現れる各論理式が持つ DESIRE の個数の最ない推論規則が使われていなければならない. 従って,

大がそこで減るが , これを増やす規則はない. 従って,AU/EU 左 · 右のいずれかか , または BEL–KD45 が使

DESIRE–KD は使われていない. INTEND–KD も同われている.

様である.

もし AU/EU 左 · 右が使われているならば , そこで

補題 5.3 終局性論理式 ρ を持つ導出のループの中でAX より内側にない AU(または EU) を 1 つ減らしては , 推論規則 AX–KD が少なくとも 1 回適用されておいる (ここで「 減る」とは , Si に対して Si+1 で , すり, かつ BEL–KD45, DESIRE–KD, INTEND–KD は

なわち結論に対して前提で減っていることを意味す使われていない. また, AX–KD のある適用から次のる. 以下も同様). よって, ループであるためにはそ適用までの間には , ρ に対する AU/EU 左が少なくとれをどこかで増やさなければならないが , それができも 1 回適用されている.

る規則は AX–KD か BEL–KD45 だけである. 従って
AX–KD†2 あるいは BEL–KD45 が使われている.

証明 終局性論理式 ρ を持つ導出のループの中には ,仮に , その両方が使われているとする. BEL–KD45がある. Weak の形の制限 (定義 4.3 の 2) から , ρ やの結論は補題 5.1 より空ではないので , それに現れるÆX ρ は Weak では消せないので , sequent に現れる論理式のうち, BEL を最も多く持つもの全ての集合を

論理式のトップレベルを BEL ばかりにすることはでBEL(Ξ) とする. すると, この先 Weak が適用される

きず , BEL–KD45 は使えない. 従って補題 5.2 から ,までは , 「 sequent に現れる論理式のうち BEL を最も

AX–KD が使われており, DESIRE–KD, INTEND–KD

多く持つもの全ての集合は BEL(Ξ) である」というは使われていない.

AU/EU 左が適用されて ρ が ÆX ρ になっている箇所

また, 同じ理由から , ρ は , AU/EU 左の適用で ÆX ρ

†2 但しこの証明では , ループを 1 周して戻ってきた時の ρ は , AU/EU 左の適用で得られた ÆX ρ の ÆX を
AX–KD で除去して得たものであるとは必ずし も保証していないことに注意. 他の論理式の部分論理式であった ρ が分解されて出てきた可能性を排除していな
いからである.

に変化しては , AX–KD の適用で ρ に戻ることを繰り返す. 従って AX–KD の適用から適用までの間には ,ρ に対する AU/EU 左が必ず適用されている.
補 題 5.4 AX–KD,

14

BEL–KD45,

INTEND–KD,

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

60

DESIRE–KD 以外のある推論規則の前提が S1 , · · · ,ない. なぜなら , R の子孫のうち T に属さないノー

Sn , 結論が S で あ り, か つ (M, w, t) 6|= S とな る

ド のラベルは , 帰納法の仮定から valid だからである.

(M, w, t) が存在するならば , (M, w, t) 6|= Si となる

するといつかは , あるノード N 0 とその子ノード N0i (1 ≤ i ≤ n) が存在する.

の間で , ρ に対する AU 左か EU 左が適用されている

また, AX–KD の前提が S1 , 結論が S であり, か箇所に着く.

つ (M, w, t) 6|= S となる (M, w, t) が存在するならば ,N 0 , N0 のラベルをそれぞれ S 0 , S0 とすると , S 0

t Rw t0 かつ (M, w, t0 ) 6|= S1 となる t0 が存在する.

が valid でないことから , ある (M, w, t0 ) が存在して証明 論理式の解釈の定義より直ちに従う.

(M, w, t0 ) 6|= S 0 である. また, ここで適用される AU

補 題 5.5 ρ が A(φ U ψ) か E(φ U ψ) の い ず れ

左か EU 左の前提のうち左は , 定義 4.3 の 1 から T 0

か で あ る と す る.

(M, w, t) 6|= [ρ, Γ → ∆] か つの外であり, 従って valid である. よって補題 5.5 か(M, w, t) |= [ψ, Γ → ∆] ならば , (M, w, t) |= ρ から (M, w, t0 ) |= ρ かつ (M, w, t0 ) 6|= ψ である. また,つ (M, w, t) 6|= ψ である.

(M, w, t0 ) 6|= S0 も成り立つ.

証明 論理式の解釈の定義より直ちに従う.

補題 5.3 より, N0 からその子ノード への過程で

補題 5.6 終局性論理式 ρ = E(φ U ψ) を持つ導出使われている推論規則は BEL–KD45, DESIRE–KD,

0のループの中で , ノード N と N の間で AX–KD が

INTEND–KD 以外のいずれかである. 補題 5.4 より,適用され て おり (すなわ ち, N のラベル S が AX–

ここで使われている推論規則が AX–KD 以外であれ

KD の結論で , N 0 のラベル S 0 がその前提), しかもば , (M, w, t0 ) 6|= S1 を満たすラベル S1 を持つ N0 の

0(M, w, t) 6|= S とする. すると, t Rw t なる任意の t000

子ノード N1 があり, また, AX–KD であれば , N0 の0に対し , (M, w, t ) 6|= S iff (M, w, t ) |= ρ となる.

唯一の子ノード N1 のラベル S1 に対し , t0 Rw t1 か

証明 あ る Γ が 存在し て S = [AX(Γ) → AX ¬ρ],

つ (M, w, t1 ) 6|= S1 となる t1 が存在する. いずれのS 0 = [Γ → ¬ρ] と書けることから , 論理式の解釈の定場合も N1 は T 0 の中にある.

義より直ちに従う.
定理 5.7 体系 (BKD45

以下, N0 から N1 への過程と同様にして, N1 から

D

KD KD

I

)CTL は健全である.

そのある子ノード N2 へ, さらに 子ノード N3 へ…

証明 sequent S の推論木 T の全ての導出のループをとたど ることを 繰り 返し , T の 葉 (T 0 の 葉で もあ合わせたグラフ G の連結成分の個数 j に関する帰納法

る) にたど り着いたら , それと同じ ラベルを持つ T 0で示す. j = 0 の場合は trivial なので , j < k (k > 0)の (葉でない) ノード に 戻ってさらに 続けていくこの場合を仮定して j = k の場合を示す.

とにより, ノード の無限列 N0 , N1 , N2 , · · · とそのラS が valid でないとする. 全ての推論規則は , 前提

ベル S0 , S1 , S2 , · · ·, および w 上の path t0 , t1 , · · · を ,が全て valid ならば 結論も valid であるので , 結論が(M, w, tapplAX (i) ) 6|= Si となるようにとることができ

valid でないなら前提のどれかが valid でない. 従っる. ここで applAX (i) とは , S0 から Si までの間にて T の根から子へ, ラベルが valid でないノード を選

AX–KD が適用された回数である.

んでたど っていくことができる. するといつかは , G

補題 5.3 より, S0 の → の左にある ÆX ρ は , AX–0のある連結成分 T の根 R に着く. なぜなら , そうでKD を適用されて ρ に変わっては , AU 左か EU 左のないと導出のループの終点でない葉に着いてしまい,

適用によって ÆX ρ に戻ることを繰り返す. N 0 から矛盾するからである.

N0 への過程における議論と同様にして, 任意の自然

0

T に 含まれ る T の 導 出のル ープ が 共 通に 持つ

数 ` に対し , (M, w, t` ) |= ρ かつ (M, w, t` ) 6|= ψ とな

終局性論理式を ρ とする. ρ = A(φ U ψ) またはる. すなわち, path t0 , t1 , · · · において, ずっと ρ が真

ρ = E(φ U ψ) である.

かつ ψ が偽である. ρ = A(φ U ψ) であれば , これはR からさらに子へ, ラベルが valid でないノード を

論理式の解釈の定義に反する.

0

選んでたど っていく. このとき T の外に出ることは一方, ρ = E(φ U ψ) であれば , path t0 , t1 , · · · が15

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

7

上記のよ うにし て取った path であることと, path

ベルとして sequent S, 第 2 ラベルとして sequent S 0

t0 , t1 , · · · が任意の自然数 ` に対し (M, w, t` ) |= ρ をを貼る.

満たすこととは同値であることが , 補題 5.6 を繰り次いで , w = w0 , t = t0 と置いて, S 0 とペア (w, t)

返し 適用することにより示せる. しかも, 上記のよに対し , 以下の ‘手順B’ (図 2) を (再帰的に ) 実行する.

うにし て取った path では , 任意の自然数 ` に 対し

手順B begin(M, w, t` ) 6|= ψ となるので , t0 から始まる path のうS 0 の → の左右が原子命題ばかりであるなら , 何もち, ρ が偽にならないうちに ψ が真となるものは存在しない. また, T の根 (w0 , t0 ) からノード (w, t) までしない. 従ってやはり論理式の解釈の定義に反する.

の経路のど こか (但し (w, t) は含まない) に , 第 2 ラ
ベル S 0 を持つノードがあるならば , ノード (w, t) に以上から , S は valid である.

「ループ 」というマークを付け , 後は何もしない.

6 完全性

いずれでもなければ , S 0 に様相論理版の Wang の本 章 で は (BKD45 DKD IKD )CTL の 完 全 性 を 示 す.

アルゴ リズムを準用する. すなわち, S 0 に対し以下の

BDIK
CTL の完全性も同様に示せる.

いずれかを行って得られる sequent 全ての有限集合
を {S100 , · · · , Sk00 } とする.

まず 6.1 節で , 証明可能でない sequent S を与えた
とき, ある (BKD45 DKD IKD )CTL -structure を構築する

1. Weak で , → の左ではトップレベルが AX の論

アルゴ リズムを与える. 続いて 6.2 節で , この (BKD45

理式以外を全て消す. → の右では , トップレベル

D

KD KD

I

)CTL -structure のある世界において S が偽とが AX の論理式があれば , そのうち 1 つを残してなることを示す.

他を消し , そうでなければ全て消す.
次いで AX–KD を適用する.

KD45

6.1 (B

D

KD KD

I

)CTL -structure の構築アルゴ

2. Weak で , → の左右それぞれについて, トップ
レベルが BEL の論理式全てを残し , 他を消す.

リズム

S を , 証明可能でない sequent とする. 以下の作業

続いて BEL–KD45 を適用する. その際, → の右を順に行う.

が空なら ∆, Θ を空とおき, そうでなければ →6.1.1 有限木の構築の右のうち 1 つを Θ, それ以外を ∆ と置く.

まず S = S0 とおき, S0 に次の ‘手順A’ を適用する.

3. DESIRE, INTEND に 対し , 1. と 同様のことを

手順A begin

行う.

S0 に Wang のアルゴリズムを準用し , ¬/∨/AU/EU

このとき, S100 , · · · , Sk00 は いずれ も 証明可能でない.

左 · 右を可能な限り適用する. その後, もし各 sequent

そこで , 各 Si00 (1 ≤ i ≤ k) に 対し , S0 = Si00 と 置の → の左同士か右同士に同じ論理式が複数回現れて000000
いて ‘手順A’ を適用し , sequent Si1, Si2, · · · を得る.

いれば , Weak でそれを 1 つに減らす.

000
000
Si1
, Si2
, · · · はそれぞれ , → の左右に原子命題とトッ

手順A end

プレベルが AX, BEL, DESIRE, INTEND の論理式だ

この結果得られる sequent のうち, 証明可能でない

けを持ち, → の左同士や右同士に同じ論理式が複数現もの全て (1 つ以上有限個) の集合を {S10 , S20 , · · ·} と0れない, 証明可能でない sequent である.

0

おき, そのうち任意の 1 つを S と置く. S は , → の000
ここで , 各 Sij
に対し , 以下を行う.

左右に原子命題とトップレベルが AX, BEL, DESIRE,

000
1. S 000 = Sijと置く.

INTEND の論理式だけを持ち, しかも → の左同士や

2. S 0 から Si00 を 得る際に AX–KD, BEL–KD45,

右同士に同じ論理式が複数回現れない.

DESIRE–KD, INTEND–KD のどれを使ったかに

ただ 1 つの要素 w0 を持つ集合 W と , ただ 1 つのよって, 次のいずれかを行う.

要素 t0 を持つ集合 St を作る. また, ペア (w0 , t0 ) を(a) AX–KD を使った場合
St に新たな要素 t0 を加え , T のノード

唯一のノードとする木 T を作り, このノードに第 1 ラ

16

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

8

INTEND のいずれかのタグが付いている. また, 一部
図2

有限木の構築の葉には「ループ 」というマークがつく.

S’’,
1 S’’’
12
21... S’’,2 S’’’...
( w 0 , t’’ )(w0 , t’’’)S’’,
1 S’’’
11(w 0 , t’)

AX AX ...

...

AX

S’’,
3 S’’’
31...
( w’, t 0 )6.1.2 枝刈り
T に対し , 以下の作業を可能な限り繰り返す.

... BEL

1. 「ループ 」や「行き止まり」のマークが付いていないノード で , しかも次のいずれかの条件

S, S’(w0 , t 0 )(a) 葉である(b) 子のノードに全て「行き止まり」マー0(w, t) に新たな子 (w, t ) を作って, それ

クが付いているに第 1 ラベルとし て sequent Si00 , 第 2を満たすものがあれば , それに「行き止まり」マー

ラベルとして sequent S 000 を貼り, 新た

クを付ける

2. 「 行き止まり」マークの付くノード N があり,な枝に AX というタグを付ける
0(直観的には , t から t に AX による可視N と同じ 親および同じ 第 1 ラベルを持つノード

関係の枝を張る)N 0 (6= N ) があれば , N 0 を削除 (N 0 への枝, および N 0 以下の部分木も含む)(b) BEL–KD45 を使った場合
0

木の有限性から , この操作は必ず停止し , その結果, 同

W に新たな要素 w を加え , T のノード
0(w, t) に新たな子 (w , t) を作って, それじ第 1 ラベルを持つ兄弟ノードは「行き止まり」マーに第 1 ラベルとし て sequent Si00 , 第 2

クの付くもののみ 1 個か , 付かないもののみ 0 個以上ラベルとして sequent S

000のいずれかになる. また, この操作の後も T は木でを貼り, 新たある.

な枝に BEL というタグを付ける(直観的には , w から BEL による可視関6.1.3 ループ枝の融合係で見える新たな可能世界を作る)

以下の全ての条件• (w, t1a ), (w, t2a ) は同じ親 (w, t) および同じ第 1(c) DESIRE–KD, INTEND–KD を使った場合ラベルを持つノード で , t1a 6= t2a

DESIRE, INTEND に対し , 2(b) と同様• (w, t1b ), (w, t2b ) は「ループ」マークのある葉ノーのことを行うド で , (w, t1b ) は (w, t1a ) の, (w, t2b ) は (w, t2a )3. 次いで , 今新設したノード を改めて (w, t) と置
き, S

000

0

を改めて S と置いて, ‘手順B’ を再帰的の子孫

• (w, t1c ) は (w, t1b ) と , (w, t2c ) は (w, t2b ) と同じに呼び出す.

第 2 ラベルを持つノード で , (w, t1c ) は (w, t2c )手順B end0の, (w, t2c ) は (w, t) の先祖

ど の段階においても, S は , S に含まれる論理式の 部分論理式 (その 中に A(φ U ψ) が あ る 場合はを 満た す ノード (w, t), (w, t1a ), (w, t2a ), (w, t1b ),AX A(φ U ψ) を含み, また E(φ U ψ) がある場合は(w, t2b ), (w, t1c ), (w, t2c ) が存在する限り, 以下の ‘手

EX E(φ U ψ), AX ¬ E(φ U ψ), ¬ E(φ U ψ) を含む) の順C’ (図 3) を繰り返す.

みからなり, しかも → の左同士や右同士に同じ 論理

手順C begin0

まず , (w, t2c ) から (w, t) までの 経路のコピ ーを

式はない. 従って S の可能性は有限通りしかない.
また, 1 つの S

0に対する Si00 の可能性も有限個しかな作る. すなわ ち, (w, t2c ) から (w, t) までの経路のノード が (w, t01 ), · · · , (w, t0i ) で あ ると する (ここでい. 従って ‘手順B’ は有限の手間で止まる.
このとき, T は W の要素と St の要素のペアをノー

t01 = t2c , t0i = t) と , St に新たな要素 t001 , · · · , t00i を増ド とする有限木で , 各ノード には sequent のラベル

やし , (w, t01 ), · · · , (w, t0i ) とそれぞれ同じ第 1・2 ラベが 2 つ貼られており, 各枝には AX, BEL, DESIRE,

00
00
ルを持つノード (w, t00
1 ), · · · , (w, ti ) を作って (w, t1 )17

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

9

コピーを行う. この再帰のネストは , 高々‘手順C’ を
図3

ループ枝の融合(w, t1b )(w, t2b ) (w, t1b )(w, t1a )(w, t2a ) (w, t1a )行った回数なので , この操作は有限で停止する.

deleted6.1.4 (BKD45 DKD IKD )CTL -structure の構築(w, t2a )(w, t)(w, t)(w, t’’
i )(w, t2c )(w, t2c )(w, t’’
1 )(w, t1c )(w, t1c )以下のよ うな tuple M = hW, {St w | w ∈ W },{Rw | w ∈ W }, L, B, D, Ii を作る.
• 各 w ∈ W に対し , St w = {t ∈ St | T がノード
(w, t) を持つ }• 各 w ∈ W に対し , Rw = {(t, t0 ) | T は (w, t) から (w, t0 ) へのタグ AX の枝を持つ }00
00
から (w, t00
2 ) へ , · · ·, (w, ti−1 ) から (w, ti ) へタグ AX
00を持つ枝を張る. また, ノード (w, t00
1 ), · · · , (w, ti ) に• 各 w ∈ W , t ∈ St w に 対し , L(w, t) は ノード(w, t) の第 2 ラベルである sequent の → の左に「コピー」のマークを付ける.
次いで , (w, t00
1 ) の第 1 ラベルのみ, (w, t2b ) のそれと同じに変更する.

現れる原子命題全ての集合• 各 w, w0 ∈ W , t ∈ St w に対し , B = {(w, t, w0 ) |但し (w, t00
1 ) に「ループ 」のマー

T は (w, t) から (w0 , t) へのタグ BEL の枝を持つ }クは付けない.
00
最後に , (w, t2b ) の親から (w, t00
1 ) へ , および (w, ti )• D, I に対しては同様

から (w, t1a ) へタグ AX を持つ枝を張り, (w, t2b ) の次に , T の根からそれぞれの葉 L への経路のうち,親から (w, t2b ) へ, および (w, t) から (w, t1a ) への枝

途中 (葉を除く) に葉と同じ第 2 ラベルを持つノードと , ノード (w, t2b ) を削除する.

N があるもの全てについて, L の直前のノード N 0 か

手順C end

ら L への枝のタグが何であるかに応じて以下のいずれかを行う.

直観的にはこの操作は , タグ AX の枝からなるルー• タグが AX ならば , 補題 5.2 よりある w, t, t0 , t00 がプ全てを含むグラフの各連結成分を, それと同等な枝存在して N 0 = (w, t0 ), L = (w, t), N = (w, t00 )を全て持つ単一のループに置き換える.

と書けるので , Rw から (t0 , t) を削除し (t0 , t00 ) を‘手順C’ 1 回あたり, 条件を満たす箇所が 1 つ減る

加え , St w から state t を削除

ので , 繰り返しは必ず停止する. この操作の後も T は木であり, また, 1 つのノードから出る, タグ AX を持• BEL ならば , 補題 5.2 よりある w, t, t0 , t00 が存在

つ枝で , その先のノード の第 1 ラベルが同じ ものはして N 0 = (w0 , t), L = (w, t), N = (w00 , t) と書

高々1 つになる. 特に , 「コピー」のマークを持つノーけるので , B から (w0 , t, w) を削除し (w0 , t, w00 )ド の子はただ 1 つである.

を加え , W から可能世界 w を削除• DESIRE, INTEND であることは , 補題 5.2 から

その後, 「コピー」のマークのある各ノード N に対し , その祖先で N と同じ第 2 ラベルを持ち「コピー」

ない
ここで , t Rw t0 を満たす t0 の存在しないような全0

マークのないノード N (必ず存在する) を選び , N の
0ての w と t に対し , (t, t) を Rw に加える. この場合,「コピー」のマークを外し , N 以下の部分木 (但し , N
0の子と同じ第 1 ラベルを持つ N の子と, それへの枝,

T のノード (w, t) の第 1・2 ラベルの → の左右にはおよびそれ以下の部分木を除く) を , 必要なら W や

AX をトップレベルに持つ論理式はないことに注意.

St の要素を増やしつつ, N 以下へコピーする. このとまた, (w, t, w 0 ) ∈ B を満たす w0 が存在しないようなき, コピーした部分木においても, ノード (w1 , t1 ) か

全ての w と t に対し , (w, t, w) を B に加える. このらその子ノード (w2 , t2 ) への枝のタグが AX であれ場合も BEL について同様の注意が成り立つ. D, I にば w1 = w2 , そうでなければ t1 = t2 となるようにすついても同様の操作を行う.

る. また, コピー元の部分木の中にさらに「コピー」

最後に , 3.1 節の条件 (B-4) や (B-5) を満たさないのマークを持つノードがあれば , 先に再帰的に同様の

w, w0 , w00 がある間, (w, t, w00 ) を B に加える (世界や18

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

state は有限個なので有限の手間で済む). そのような

10の前提の左だとすると, 帰納法の仮定から φ も ψ

00(w, t, w ) を 1 つ B に加える前に , 性質

も (M, w, t) で偽なので A(φ U ψ) も偽. 一方, 右0(w, t, w ) ∈ B ならば , T のノード (w, t) の第 2だとすると, 同じ 理由で ψ は (M, w, t) で偽. まラベルの → の左に 現れ る全ての BEL(φ) に 対

た, t Rw t0 を満たすある (w, t0 ) があって, それに

し , ノード (w0 , t) の第 1 ラベルの → の左には対応するノードの生成中に , sequent の → の右にBEL(φ) と φ が現れる

A(φ U ψ) が現れている. これに同様の議論を適が満たされているならば , 1 つ加えた後にもこの性質用して, (M, w, t0 ) で φ も ψ も偽か , あるいは ψが満たされるので , この操作が全て済んだ後も, このが偽でかつ t0 Rw t00 を満たすある (w, t00 ) があっ

性質は満たされている.

て, 同じ議論が繰り返せる. すなわち, t で始まる

これにより M は (B

KD45

D

KD KD

I

)CTL -structure に

w 上のある path があって, ずっと ψ が偽か , あなる.

るいはあるところで φ が偽でかつそこまでずっと ψ が偽である. 従って (M, w, t) で A(φ U ψ)

6.2 完全性の証明
定理 6.1 体系 (B

KD45

は偽.

D

KD KD

I

)CTL は完全である.

• → の右の E(φ U ψ) · · · 同様.

証明 sequent S が証明可能でないとする. 6.1 節のア

従って, 特に (M, w0 , t0 ) 6|= S である. よって, S は

ルゴ リズムで作られた (BKD45 DKD IKD )CTL -structure

恒真でない.

M は以下の性質を持つ.
Sw 3 t とする. ‘手順B’ で T のノード (w, t) を

7 判定アルゴリズム

000
生成した段階での Si00 から Sijに至る過程 (但し6 章で示したアルゴ リズムを, 証明可能な sequent0

w = w0 , t = t0 の場合は S から S に至る過程)に対しても適用すれば , sequent の証明可能性の判定

のど の sequent に対しても, その → の左に現れ

アルゴ リズムが得られる.
与えられた sequent S に Wang のアルゴ リズムをる論理式は (M, w, t) で真であり, 右に現れる論

準用し , ¬/∨/AU/EU 左 · 右を可能な限り適用する.

理式は (M, w, t) で真でない.
これを示すには , 論理式の構造に関する帰納法を, M

その後, もし 各 sequent の → の左同士か右同士に同の全ての state に対して同時並行で適用すればよい.

じ論理式が複数回現れていれば , Weak でそれを 1 つ

特に , A(φ U ψ), E(φ U ψ) に関しては次のように示に減らす.
この結果得られ る sequent のうち, 様相オペレ ー

せる.

• → の左の A(φ U ψ) · · · もし これが 偽なら , T

タを持たないか , S からの過程で既に現れている se-の作り方から , (M, w, t) で始まるある path で ,quent と同じものについては何もせず, それ以外の各

ずっと φ が真, ψ が偽となる. このとき, T のあ

sequent S 0 に対し , 6.1.1 節の ‘手順B’ と同様に , 様相るノード N とその子孫の葉ノード N 0 で , N か

論理版の Wang のアルゴ リズムを準用する. 得られら N 0 までの経路のノード の第 1 ラベルの → のた各 sequent Si00 に対し , S と同様に Wang のアルゴ

左に常に A(φ U ψ) があり, しかもその経路の枝

リズムを準用することを繰り返す.

が全てタグ AX を持つものがある. すると, N の

こうして, 定義 4.4 の条件を満たす推論木が作れれ

第 1 ラベルには , 終局性論理式 A(φ U ψ) を持つ

ば S は証明可能である. また, できなければ , 有限の導出のループを含む証明が存在することになり,手間でこの操作は行き詰まり, 証明可能でないとわ

矛盾する.

かる.
現在, このアルゴリズムの Prolog によるインプリメ• → の左の E(φ U ψ) · · · 同様.

ントが動作している (ftp://ftp.ics.nara-wu.ac.

• → の右の A(φ U ψ) · · · これに対しどこかで AU

jp/pub/nide/research/bdi-1.00.tgz).

右が適用されている. その次の sequent が AU 右19

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

11

参考文献

8 今後の課題[1] Emerson, E. A. and Srinivasan, J.: Branching Time Temporal Logic, Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency(de Bakker, J., de Roever, W.,
and Rozenberg, G.(eds.)), Springer-Verlag, 1989,
pp. 123–172.
[2] Rao, A. S. and Georgeff, M. P.: Modeling Rational Agents within a BDI-Architecture, Proc. of International Conference on Principles of KnowlegdeRepresentation and Reasoning, 1991, pp. 473–484.
[3] Rao, A. S. and Georgeff, M. P.: Decision Procedures for BDI Logics, Journal of Logic and Computation, Vol. 8,No. 3(1998), pp. 292–343.
[4] Singh, M. P., Rao, A. S., and Georgeff, M. P.:
Formal Methods in DAI: Logic-Based Representation and Reasoning, Multiagent Systems, The MIT
Press, 1999, pp. 331–376.
[5] Wooldridge, M.:
Reasoning about Rational
Agents, The MIT Press, 2000.
[6] 高田司郎, 五十嵐新女, 新出尚之, 榎本美香, 間瀬健
二, 中津良平: マルチエージェント環境において意図的に言語行為を遂行する合理的エージェントの基本設計, 電気情報通信学会論文誌, Vol. J84-D-I,No. 8(2001),
pp. 1191–1201.
[7] 萩谷昌己: ソフト ウェア科学のための論理学, 岩波講
座 ソフトウェア科学 11, 岩波書店, 1994.

複数のエージェントに関する BDI [5] をもつ logicへの拡張も, エージェントの quantifier を入れなければ直ちに行えるだろう. また, mutual belief [5] のように , BDI オペレータの無限ネストに相当するオペレー
タを持つ体系に関しても, 本稿の AU/EU に対する取り扱いと同様の手法によって, 演繹体系を作れると考えられる. これらを導入できれば , マルチエージェン
トシステムの BDI logic を用いた仕様記述や検証に有効であろう. さらに , DESIRE(φ) ⊃ BEL(DESIRE(φ))など , 合理的エージェントに要求される心的状態の整
合性公理 [2] [3] の導入も検討を要する. それらは今後の課題である.
エージェントの quantifier に関する取り扱いや, また, 現時点ではまだ , ベースが命題論理の CTL に限定されているので , これを CTL* や述語論理に拡張できるかど うかも今後の検討課題である.

20

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

1

マルチエージェントによるチーム航行支援安藤 英幸 広野 康平 大和 裕幸

リッジの業務は、周囲の船舶や自船の位置といった状

1 はじめに況に応じて、実行する業務を適応させる必要がある。

ビジネスや製造のプロセスモデルを整理し、情報やこのために必要となるプロセス表現の整理とワーク

業務の引継ぎの自動化を目指したワークフロー管理

フローエンジンの実装を行う。

システムが注目されている。

2 背景

ワークフロー管理システムの中心となるのは、プロセスモデルとそれを実行するワークフローエンジン

船上業務の種類は、例えば見張り、船位確認とである。一般にプロセスモデルは、コミュニケーショ

いったレベルの業務をユニットとして約 600〜700 ユン、作業の対象、ユーザーのアクティビティといったニット程度であると言われる [1]。それぞれの業務は、視点から有向ネットワークにより表現される。また

Hutchins も述べているように構造の良くわかった問

ワークフローエンジンは、プロセスのテンプレートか

題で、あらかじめ作業手順を定型化する事ができるらのインスタンスの作成、タスクの割り当て、実行と[2]。しかし、それら定型的な業務も、自船位置と航モニタリング、例外処理を行う。

路の関係、他船の位置と速度、ワッチレベル (watch

これらの枠組みは、定型的にプロセスモデルを記述

level) と呼ばれる危険度の指標、他の作業、作業の記できる場合には十分である。しかし、とりまく環境の録といった多様なコンテクストに応じて、行うべき業変化に対応してプロセスの更新が必要であったり、プ

務、優先順位、処理に要する時間、繰り返し業務に関

ロセスを外部環境との関連で表現するのが適していする時間間隔等が変更する。

る場合には、プロセスモデルの表現の工夫と、持続的

これらの船上業務についての詳細は SMS(Safetyにプラニング、スケジューリング、実行のモニタリン

Management System) マニュアルという印刷物の形グを行うワークフローエンジンが必要となってくる。

で各運航会社毎にまとめられ、船上で利用されてい本研究では、船舶のブリッジ業務に動的なワークフる。しかし、作業の状況への依存性が高い事からマロー管理システムを実装する事を目的としている。ブ

ニュアルが複雑化したり、マニュアルの見直しに必要な実作業の履歴の入手が現状では困難であることかTeam Navigation Support with Multi-Agents System
Hideyuki Ando, 東京大学 新領域創成科学研究科, Graduate School of Frontier Sciences, University of Tokyo
Kouhei Hirono, (株) 日本海洋科学, Japan Marine Science Inc.
Hiroyuki Yamato, 東 京 大 学 新 領 域 創 成 科 学 研 究 科,
Graduate School of Frontier Sciences, University ofTokyoら、ワークフロー管理システムに SMS マニュアルの情報を移植し、作業の見逃し、対応の遅れの防止、さらには、作業履歴の分析による基のプロセスモデルの改善が期待される。

21

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

2

論部分へのエキスパートシステム JESS(Java Expert

3 エージェントとアーキテクチャ

System Shell) [5] の利用、各レイヤーのコンポーネン

3.1 エージェントの構成

トの構成の変更といった改良を加えた。

ブリッジ業務の動的なワークフロー管理システム
は、プロセス、外的状況、作業者に関する情報をネッ

Agent

トワーク上で交換し、それらに基づいて適切な業務

Agent Knowledge Base(AKB)Agent Control Unit(ACU)

Social Model

SR

PS

A

Cooperative Planning
Layer(CPL)

Mental Model

SR

PS

A

Local Planning
Layer(LPL)

World ModelSR

PSのプラニング、スケジューリング、実行モニタリング
を持続的に行う必要がある。これらの実装にマルチエージェントを採用することとし、その実装のベー

Behavior BasedA
Layer(BBL)
Active PoBs

Sensors
ActorsCommunication
World Interface(WIF)スに、Jin らがワークフローによる協調設計支援のために開発した ActiveProcess 環境を利用する [3]。

Environment
User Interface

ActiveProcess の各エージェントは、ネームサーバー

inputを介して KQML メッセージを交換する。コンテンツ

フォーマットを利用している。本研究では、航海士の図2支援を行うユーザーエージェント、船長につきチーム

suggestion/
recommendation

SR
PS
A

User

言語としては、順序なしリストを表現できる独自のOther agents and systems
Information flow
Control flow
Situation recognition
Planning & scheduling
ActionAgent architecture

全体の業務プロセスを管理するマネージャーエージェ
ント、船舶運航に関する情報をもつセンサーデータ

エージェントの内部構成を図 2 に表す。全体は World

サーバーのラッパーとして働くリソースエージェント

Interface(WIF)、Agent Knowledge Base(AKB)、を配置した (図 1)。

Agent Control Unit(ACU) に よって 構 成 さ れ る 。
WIF はエージェントと外部環境とのインターフェー
スで、ユーザーインターフェース、他のエージェント

Resource agent
User agent

User agentとの通信、センサーデータの取得に利用する。エー
ジェントの持つ周囲の環境に関する知識、作業者のName server
Sensor data server

行うワークフロー、他エージェントに関する知識はManager agent
Requests and results messages in K Q M LWorld model, Mental model, Social model の 3 層

Register messages in K Q M L
Sensor data on UDP/IPに分けて AKB に置かれる。また、AKB はそれらの知識の登録、取り出しのためのインターフェースを

図1

Multi agents configuration

持つ。ACU では AKB の知識を基に即応 (BBL)、熟考 (LPL)、協調 (CPL) のそれぞれの層が独立して状況の認識、プラニング、アクションを行う。ACU 内

3.2 多層型アーキテクチャのレイヤー間の通信には KQML を使用する。即応ActiveProcess では、自律的な振る舞い、推論、エー層では、Pattern of Behavior(PoB) と呼ばれるエー

ジェント間の協調といった知的な機構に関しては、ドジェントの振る舞いのパターンを記述したモジュール

メインに合わせて開発を行う必要がある。本システの Active/Inactive の切り替えを行う。PoB には反射

ムでは、エージェントに求められるタスクの多様性的な対応を行うための reactive PoB と他の層からのから、即応、熟考、協調の 3 つの機能を独立したレ委託により Active な状態になる procedure PoB がイヤーとして実現し、協調ロボットの実装を良く整ある。

理した InterRAP アーキテクチャの概念を基本的にエージェントは全体として、AKB の知識をベース採用することとした [4]。ただし、熟考、協調層の推に即応、熟考、協調の各層がプラニング、スケジュー22

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
リングを行い、PoB の実行リスト (Active PoBs) のWorkflow3

チーム全体の作業プロ切り替えを判断している事になる。

セス

Activity

1 人の作業者に割り当

3.3 実装てる作業の最小単位

システムは WindowsNT/2K 上で開発を行った。
エージェントの開発には Java 言語を利用したが、他Work Element

Operation の集合

Operationのアプリケーションとの連携を容易にするため Visual

作業の最小単位表1

Role of each layer

J++ を用いて COM(Component Object Model) のDLL(Dynamic Link Library) として実装した。また、
ユーザーインターフェースの実装は Visual Basic を

4.2 プラニング、スケジューリング

用いた。

ユーザーの作業のプラニング、スケジューリング
は、図 4 の手順で行われる。外部環境の変化にマッ

4 プロセスマネージメント

チするルールが発火し、実行するべきサブツリーが選

4.1 プロセスモデル

択される。選択されたサブツリーは、順序の制約を満Wilkins らは、現実問題へのプラニング技術の適応

たすように展開され、一連のオペレーションにより構を考える場合、ドメイン知識の利用が不可欠である事成されるプランとなる。これに、それぞれの作業時間を指摘している [6]。ドメイン知識を利用したプラニを適応してスケジュールが構成される。この作業は継ングの代表として HTN(Hierarchical Task Network)

続的に繰り返される。また、現時点で、サブツリーのがある。HTN ではツリー構造によってプロセスを記

選択のために用意したルールの例を以下に示す。

述し、ゴールに合わせて上位概念を選択し、下位のツ• 周囲に船が接近してきた場合に起動

リーを展開し、最終的にプリミティブな操作で構成• ワッチレベルに応じた起動されるプランを得る。本研究でも、記述が可能であ• デフォルトで起動ることから、階層構造というドメイン知識を用いたプロセス記述を採用し、特に Jin らが ActiveProcess
で利用している Workflow, Activity, Work Element,

Operation の 4 階層によるプロセスモデルに従う事とした。プロセスモデルのツリーの各階層の役割を、
表 1 に示す。
また、動的な環境の変化に対応して適切なプラニングを行うために、全体のツリーのうちどのサブツリーを駆動するかという知識をエキスパートシステ

図4

Planning and scheduling

ム JESS のルールという形で記述する。（図 3)。
Workflow

rule 1

4.3 実行とモニタリング

rule 2

Activity
WorkElement
Operation

rule 3...

熟考層でスケジューリングが行われた作業は、ユー

rule n

ザーインターフェースを通して、ユーザーに対して提Hierarchical process model Process activation rules

図3

示され、その終了までをモニタリングされる。各作業のモニタリングは、図 5 に示す状態遷移規則に基づいProcess modelて行われる。エージェントとユーザーインターフェー

23

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17スの間で、図 5 の矢印の上に示されたフラグを交換
し、状態を遷移する。作業のモニタリングは、即応層

4

自船データ

1 秒間隔で生成

他船データ

3 秒間隔で生成（一般的なレーのレベルの作業モニタリング用 PoB が担当する。開ダーの周期が３秒であるため）。

始時には熟考層から Active にするメッセージが即応層に送られ、ユーザーインターフェースを介してユーザーに提示される。作業終了時には、ユーザーからの自船の運動

舵角とエンジンテレグラフ値の計算

入力より、応答遅れを考慮して終了の通知を受けて、熟考層が業務の終了を認識し、先のモニタリング用 PoB を Inactive にするように即応層にメッセージを送る。

船体運動計算する。
他船の運動

予め設定されたコースをトレー

計算

スさせて運動を再現。変針動作
は一定の角速度で回頭させていREADYNO REPLY

TO_ACTIVATE

る。

WAIT_FOR_ACTIONRES_COMMENCERES_ABORT RES_POSTPONENO REPLY

NO_REPLYEXECUTION_DENIEDRES_ABORTRES_POSTPONERES_DONEASK_CONFIRMATION

電子海図上に自船位置と他船位

TO_CONFIRM

RES_ABORT

置、それぞれの速度ベクトルを

RES_NOTICERECEIVE_NOTICEEXECUTION_COMPLETED

表示

WAIT_FOR_NOTICEEXECUTION_POSTPONED

重ねて表示。ECDIS と同等

invalid

表2

no reply

Specification of the simulator

EXECUTION_FAILED

5.1 プロセスツリーの展開
図5

State transition for operation monitoring

航海士エージェントは、「見張り」Activity 以下の階層構造を展開し、目視による監視、レーダーによる監視といった Operation を順次促し、次に「船位測定」

5 検証

Activity 以下の階層構造を展開し、下位の Operation

開発したエージェントの動作を確認するため、船舶の実行を提示し、当直航海士の作業遂行支援を行う事のデスクトップ型の操船シミュレータ（仕様を表 2 にを確認した。

示す）に接続した。自船、他船に関する情報は、レーダー装置を代替するセンサーデータサーバからネット

5.2 作業のモニタリング

ワーク上のリソースエージェントに対して送られる。

航海士エージェントは、状態遷移規則に基づき、モシミュレーションの海域は、伊豆大島東方で、自船はニタリング用の PoB を通して、ユーザーインター

洲崎沖変針点向け航行中とした。シミュレーション

フェースとの間でメッセージの送受信を行い、選択

は、ワッチレベル１ (当直航海士 1 名体制) として開された Operation が最終的に、正常終了、異常終了、始した。当直航海士は船長から「見張り」、「船位測延期、応答なしのいずれかの状態になるまでモニタリ定」、「避航操船」の 3 つの Activity を与えられていングを行った。また、応答が許容時間内にない場合にる。船長は船橋にいない状態であるが、「ワッチレベ

は、入力の催促を行った。

ルの切り替え」の Activity が常時割り当てられている。この状態で、以下の点についてシステムの動作を

5.3 動的な環境でのサブツリーの選択確認した。

「ワッチレベル切り替え」Activity が起動される

1. プロセスツリーの展開

条件を、この検証では TCPA （最接近までの時間）

2. 作業のモニタリング

がプラスで、DCPA（最接近時の距離）が 1 マイル

3. 動的な環境でのサブツリーの選択

以下となる船舶が、同時に、10 マイル以内に 2 隻以上現れたとき とした。船長エージェントは、リソー
スエージェントから TCPA, DCPA 情報を定期的に

24

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

5

取得し、この条件を満たす状態に変化した直後に、船ワークフローエンジンの機能としては、作業スケ長に対してワッチレベルの切り替え Operation を提ジューリングの作成に関して、iterative repair の導示し、船長はワッチレベルを変更した。 航海士エー入等による、より無理のないスケジュールの更新手法

ジェントはワッチレベルが変更された事を受け、「避の検討、作業者間の負荷分散、ユーザーによるスケ

航操船」Activity の担当を外し、代わって船長エー

ジュール変更を許すためのインターフェースが必要とジェントが「避航操船」Activity を担当するツリーに考えている。

加えた。

7 謝辞
6 まとめ

本研究の遂行にあたり、（株）日本海洋科学の東京

船上のブリッジ作業支援というドメインにおける動大学名誉教授小山健夫先生から多数のご助言を頂き的ワークフロー管理システムの設計を行うにあたり、ました。また、東京大学助教授の白山晋先生、増田

プロセスモデルとして、階層構造で表現されるプロセ

宏先生、海上安全技術研究所の伊藤博子氏には研究スモデルと、駆動するべきサブツリーを選択する規の遂行にご協力いただきました。システム開発にあ則を記述したエキスパートシステムのルールを併用

たり、南カリフォルニア大学の Prof. Yan Jin からはした。また、それらを実行するためのワークフローエ

ActiveProcess のソースコードの提供と多数のご助言

ンジンのアーキテクチャとして、マルチエージェントを頂きました。ここに感謝いたします。なお、本研究を採用し、特に、多様なタスクを並行してこなすためは平成 12 年度文部省科学研究費補助金による基礎基に、InterRAP の多層アーキテクチャを基に、エキス盤 (A)(2)-1230817 の補助を受けました。

パートシステムを推論エンジンとして使用するなど
参考文献の拡張を行った。
これらにより実装した動的ワークフロー管理シス[1] 日本造船協会第 238 研究部会. 新しいフリートサポー
トシステムの研究、平成 10 年度報告書. 社団法人 日本造船研究協会, 1999.
[2] E. Hutchins. The technology of team navigation,
1990.
[3] Yan Jin, Li Zhao, and Arun Raghunath. Activeprocess: A process-driven and agent-based approach to supporting collaborative engineering. In
Proc. of ASME Design Engineering Technical Conference, Las Vegas, Nevada, 1999.
[4] Jörg P. Müller. The design of intelligent agents:a layered approach, Vol. 1177. Springer-Verlag Inc.,New York, NY, USA, 1996.
[5] Jess. http://herzberg.ca.sandia.gov/jess/.
[6] D. Wilkins and M. desJardins.
A call forknowledge-based planning. AI Magazine, Vol. 22,
pp. 99–115, 2001.

テムが、環境を認識し、条件に適応するサブツリーを選択し、それを展開し、作業者のスケジュールを作成し、その実行をモニタリングする事を、船舶の操船シミュレーターを利用した実験において確認した。
実用に向けては、まだ非常に多くの課題がある。現時点では、プロセスモデルの準備とルールの数が十分ではなく、この整備が必須となる。また、エージェ
ントの認識できる情報は大きく制限され、例えば気象や海象といった情報を扱うことができない。これらを含めて、どのように人間とエージェントが協調的に作業を行うかを考えていく必要がある。

25

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

1

Wizard of Oz 法を使ったマルチキャラクタ
エージェントインターフェースの評価
辻本秀樹

北村泰彦 辰巳昭治

Character-agent interface is a user-friendly interface on the Internet. Most of the systems use asingle agent alone, but we here consider the eﬀectof multiple character-agents. We have developed an information retrieval system called Venus &Mars based on multiple character-agents interface.
In this paper, we observed and compared interactions between users and agents in two versions of

図1

マルチキャラクタエージェントインターフェース

Venus & Mars; one version employs a single character only and another employs multiple characters,

観を図 1 に示す。

by using Wizard of Oz method.

このようなマルチキャラクタエージェントインター
フェースを実装し、それぞれのエージェントが持ってい1 はじめにる情報を組み合わせて検索を行うことができる、Venus

今日ではパソコンやインターネットが社会に浸透し、& Mars[1] という情報検索システムがある。本研究では今までコンピュータに触れることの少なかった初心者

マルチキャラクタエージェントインターフェースが分散

ユーザが利用する機会も増えている。そのような初心者

した情報を統合するシステムに有効であるかを調べるた

ユーザを含め、ユーザに優しいインターフェースとしてめ、Venus & Mars のインターフェースをシングルエー

キャラクタエージェントインターフェースがある。また

ジェントとマルチエージェントで動作させ、それぞれのユーザ層が広がることで情報源も広がり、分散した情報

ユーザとエージェントのインタラクションを Wizard ofの統合が有効となる。ここで、キャラクタエージェント

Oz 法 [3][4][5] を用いて観測し、マルチキャラクタエー

インターフェースのほとんどがシングルエージェントに

ジェントインターフェースを評価した。これはシステムよるものであることから、それらのシステムを組み合わのインターフェース設計に生かせると考えられる。

せてマルチキャラクタエージェントインターフェースの2 Venus & Mars：協調型マルチエージェン

システムとして動作させるということが考えられる。こト検索システムのマルチキャラクタエージェントインターフェースの概
Hideki Tsujimoto, Yasuhiko Kitamura, Shoji Tatsumi, 大阪市立大学大学院 工学研究科 情報工学専攻, Department of Information and Communication Engineering, Graduate School of Engineering, Osaka
City University.

Venus & Mars は情報検索に不慣れなユーザでも、自然言語でより的確なレシピの検索を可能とすることを目標としたもので、Microsoft Agent を利用したマルチキャラクタエージェントインターフェースが実装されて26

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

2

致するキーワードが有ればそのキーワードについて発話する。

• 個人エージェント「ペッコ」：ユーザの入力を監視するエージェントで、絞り込み検索でユーザが入力した食材や味付けに関するキーワードをユーザの好みとして記憶しておく。献立検索エージェントが絞
り込み検索を行うためのキーワードを尋ねたときにそのキーワードを発話する。
これらのエージェントは検索時に 2 つの点で協調する。

1 つはコンが絞り込み検索を行うときにペッコがユーザの好みを発話することで、自動的にユーザの好みによる
図2

Venus & Mars の動作画面

絞り込み検索を行えるように支援する点、もう 1 つは健康に関するキーワードが入力されときにチョーがそれにいる。エージェントには、レシピまたは健康に関する知

対して食材を発話することで、健康に関する知識の無い識を持ちその領域での情報検索や助言を行う専門エー

コンがレシピ検索を行えるようになる点である。

ジェント（献立検索エージェント、健康物知りエージェント）と、利用者のプロファイルを情報検索に反映させ

3 評価

る個人エージェントが存在する。その動作画面を図 2 に

本研究ではマルチキャラクタエージェントインター示す。

フェースの評価のため、Venus & Mars において、そのユーザは話しかけたいエージェントをクリックし、自インターフェースがシングルエージェントとマルチエー

然言語のテキストで発話することができる。ユーザや他ジェントの場合でのユーザとエージェントのインタラクのエージェントの発話を取得したエージェントはそれぞ

ションを観測し比較した。

れ独立に処理を行い、音声による発話と身ぶりを交えて応答する。このときユーザやエージェントの発話は全て3.1 Wizard of Ozのエージェントに伝わっている。

当初行った Venus & Mars をそのまま用いた実験でVenus & Mars で登場するエージェントの役割とその行動は以下のようになっている。

は、それぞれのエージェントの持つ知識が少なく、入力に対する応答や協調が上手くできない場合が多かった• 献立検索エージェント「コン」：レシピを検索する

ため、インタラクションのほとんどがレシピ検索のキー

エージェントで、食材、料理名、味付けに関するキー

ワード入力という結果となった。このような状態を避け

ワードを知識として持っている。ユーザまたは他のるためには、エージェントはより多くの知識を持ち、自エージェントの発話に自分の知識と一致するキー

然言語での入力を正しく解釈して応答する必要がある。

ワードが有れば、そのキーワードと検索隠し味 [2]しかし、現在の技術ではそのような機能を実装するのはと呼ばれる追加キーワードを用いて検索する。また、難しいため、Wizard of Oz 法を用いて評価を行うこと

検索結果が多い場合には絞り込み検索を行うためのにした。

Wizard of Oz 法では wizard と呼ばれる人間のオペ

キーワードを尋ねる。

• 健康物知りエージェント「チョー」：健康に関するレータがシステムの一部分または全体をシミュレーショ

情報を提供するエージェントで、食材、病気や症状

ンし、見かけ上はコンピュータによるシステムとして動に関するキーワードと、食材が持つ効能、病気や症

作させ、被験者の行動を観測する。ここではオペレータ状に対して効果のある食材を知識として持つ。ユーがエージェントを操作するように Venus & Mars を改

ザまたは他のエージェントの発話に自分の知識と一造した。オペレータには被験者とオペレータの発話内容

27

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

3が見えており、それが返事できる内容のものであれば応調査し、その傾向や性別が偏らないように振り分けた。

答し、そうでなければ理解できなかったことを被験者にマルチエージェントの被験者の 1 人を除き、全員 20 回分からせるように発話する。オペレータが返事できる内以上の発話を行った。各被験者のはじめの 20 回の発話

容は、レシピ、健康、エージェントの個人的なこと、被を整理した結果を表 1〜3 に示す。

験者の好み、挨拶などの一般的な事柄とした。

表1

被験者の発話の種類

マルチ

シングル

質問

34( 36.2%)49( 49.0%)

検索依頼

43( 45.7%)29( 29.0%)

その他

17( 18.1%)

22( 22.0%)

合計

94(100.0%)100(100.0%)

3.2 評価方法
評価は次の 2 種類の実験により得られた結果を比較することで行った。

• マルチエージェント
前述のエージェント 3 体が登場する。最初に各エー
ジェントは自分の役割を明らかにするためにそれぞれ自己紹介を行う。特にコンとチョーは、「献立探し表2の名人」、「食は健康の基。いつでも健康でいられる
ように、体にいいものを教えてしんぜようぞ。」と被験者の発話内容

マルチ

シングル

いう台詞で役割を示している。ここでは 3 人のオペ

エージェント24( 25.5%)32( 32.0%)

レータがそれぞれの担当するエージェントを 2 章でレシピ

40( 42.6%)33( 33.0%)

述べたエージェントの役割と行動に従って操作する。

健康

13( 13.8%)3( 3.0%)好み

3( 3.2%)3( 3.0%)その他

14( 14.9%)29( 29.0%)

合計

94(100.0%)100(100.0%)• シングルエージェント
前述のエージェントの能力を全て持っているエー
ジェント 1 体（見た目はコンのものである）が登場する。献立検索と健康についての知識があることを示すため、このエージェントの自己紹介では上記の台詞を両方とも用いている。また、この場合もマル

表 1 は被験者の発話を種類によって「質問」、「検索依チエージェントの場合と同様に 3 人のオペレータが頼」、「その他」に分類し、表 2 は内容によって「エーエージェントを操作するが、レシピについての話題

ジェントについての個人的な話題」、「レシピについてのはコンのオペレータ、健康についての話題はチョー

話題」、「健康についての話題」、「被験者の好みについてのオペレータ、それ以外の話題はペッコのオペレーの話題」、「その他」に分類したものである。表の数値はタが操作するようにした。

それぞれの分類について、被験者の発話回数とその割合

被験者には自然言語で会話のできるキャラクタを利用を示している。表 3 はマルチエージェントの実験においしたレシピ検索システムであると説明し、どちらか片方て、被験者が表 2 で分類した内容をどのエージェントをのタイプを割り当てて実際に使ってもらう。被験者から対象として発話したかを示している。表の数値は発話内

エージェントへの発話回数が 20 回を越えるのを目安と容とその対象となるエージェントについて、被験者の発して 1 回の実験とした。また、オペレータがエージェン

話回数とその割合を示している。
表 1 からマルチエージェントとシングルエージェント

トを操作していることは実験終了後に伝えている。

のどちらにおいても検索依頼以外の発話が多く発生し

3.3 実験結果と考察ており、そのほとんどがエージェントについての質問で

3.2 節で記した方法で、大阪市立大学の学生 10 人にあったことから、エージェントは被験者の気をひく存在実験を行った。実験では被験者のパソコン歴、インターであったと考えられる。また表 2 から、マルチエージェ

ネット歴、レシピへの関心、健康への関心をアンケート

ントではレシピについてや健康についての検索に関係す28

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
表3

4

マルチエージェントでの被験者の発話内容とその対象

エージェント

レシピ

健康

好み

その他

ペッコ

8(33.3%)9(22.5%)3(23.1%)0( 0.0%)11(78.6%)

コン

7(29.2%)29(72.5%)2(15.4%)3(100.0%)3(21.4%)

チョー

9(37.5%)2( 5.0%)8(61.5%)0( 0.0%)0( 0.0%)

合計

24(100.0%)40(100.0%)13(100.0%)3(100.0%)14(100.0%)

る発話が多いのに対し、シングルエージェントではエー

い分けていることが分かった。これらの結果は、Venus

ジェントについてやその他の検索に関係しない発話が多& Mars のような分散した情報を統合して提供するシい。このことよりシングルエージェントでは被験者を飽ステムにとってマルチキャラクタエージェントインター

きさせやすかったと考えられ、マルチエージェントの方フェースが有効であることを表している。しかし、エーが検索に関係した発話を発生させやすいと言える。

ジェントの役割が意図したものと違って認識される可能また表 3 から、マルチエージェントにおいて被験者性があることも示していた。このことから、エージェン

は、レシピについては献立検索エージェントに、健康にトを設計する際にはその役割をはっきりさせる必要があ

ついては健康物知りエージェントに、その他の話題は個ると言える。

人エージェントに発話することが多く、エージェントを

現在は実験によって得られたシングルエージェントと使い分けていたと考えられる。これらのことから、マルマルチエージェントの場合での被験者のインタラクショ

チエージェントにおいて被験者は各エージェントの役割

ンの違いがどのような理由から起きたのか、また被験者を認識し、それによってマルチエージェントの方が検索

がエージェントの役割を認識するまでにどのようなインに関係した話題を発話が多く発生したと考えられる。まタラクションを行っているかという視点から結果の解析

た、どちらの場合においても被験者の好みについてのを続けているところである。

話題は少なかったが、マルチエージェントでは個人エー
ジェントにその他の話題を発話することが多かった。こ

参考文献

れは個人エージェントは司会者のような役割として認識[ 1 ] Yasuhiko Kitamura, et al.: Interactice Integration of Information Agents of the Web, Matthias
Klusch, Franco Zambonelli (Eds.), Cooperative Information Agents V, Lecture Notes in Artificial Intelligence 2182, Berlin et al.: Springer-Verlag, pp.113,(2001).
[ 2 ] Satoshi Oyama, et al: Keyword Spices: A New
Method for Building Domain-Specific Web SearchEngines, Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01),
pp.1457-1463,(2001).
[ 3 ] Yeonsoo Yang, Masayuki Okamoto, and Toru
Ishida: Applying Wizard of Oz Method to Learning
Interface Agent, Proceeding of Workshop on Software Agent and its Applications(SAA2000), pp.223230,(2000).
[ 4 ] Maulsby, D., Greenberg, S. and Mander, R.,
Prototyping an Intelligent Agent through Wizardof Oz, Proc. of the conference on Human factors incomputing systems, pp.277-284,(1993)[ 5 ] Dahlback, N., Jonsson, A. and Ahrenberg, L.,
Wizard of Oz studies - Why and How, Proc. of
the international workshop on Intelligent user interfaces, pp.193-200,(1993)

され、ユーザの好みを覚えておくという役割についてはあまり重要視されなかったか、上手く認識されなかったと考えられる。この点は、個人エージェントが被験者の好みを覚えていることをよりアピールすれば変化が見られるかもしれない。

4 まとめ
本研究では、情報検索システムにマルチキャラクタエー
ジェントインターフェースを実装した Venus & Mars
において、シングルエージェントとマルチエージェントの場合のユーザとエージェントのインタラクションをWizard of Oz 法を用いて観測し比較した。その結果、マルチエージェントの方が検索に関係する内容の発話が発生しやすく、ユーザを飽きさせない効果があると考えられた。さらに、マルチエージェントにおいて被験者は各エージェントの役割を認識しており、エージェントを使29

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

1

エージェント基盤のための通信プロトコル：
Agent Platform Protocol
高橋 健一

鍾 国強

雨宮 聡史

峯 恒憲 雨宮 真人

近年，ネットワークで接続された複数の機器が協調

エージェントシステムでは，エージェントの活動や交渉を行い仕事を達成するシステムを作る枠組みとを促進するための環境（Agent Platform，以降 AP

して様々なエージェントが提案されている．これらのと記す）（例えば，KODAMA の ACZ [1] [2] や FRM

エージェントシステムでは，エージェントの活動を促の Field [3]，Hive の cell [4] など）が準備されている．

進する環境（AP）が個々に準備されているが，それエージェントは，AP 上で，仕事の達成に必要な情報

ら異なる AP 上のエージェントシステムを相互運用すを得るためのコミュニケーションや仕事の達成に必る手段については提供されていなかった．そこで，本要な資源を得るための AP 間の移動を行う．これら

稿では，AP 間のプロトコルとして Agent Platformの AP は，元々各エージェントシステム固有のもの

Protocol(APP) を提案する．APP を用いることで，として開発されているため，そのような異なる AP

１）サーバを介さない P2P な AP 間通信と２）物理を持つエージェントシステムを相互運用することは的環境を意識する必要しないエージェントコミュニ

難しい．エージェントの標準化促進団体 FIPA [5] でケーションを実現できる．

は，Agent Communication Language（以降，FIPA

ACL）や，Agent Platform などの仕様が定められて

1 はじめにいるが，その FIPA ACL では，メッセージの送信側

インターネットの普及とともに，ネットワークで接と受信側エージェントの物理的なアドレスを指定す続された複数の機器によって実現された多くの情報シる，受信側エージェントの物理的位置を明確に意識しステムやサービスが提供されてきた．これらのシステた仕様となっている．しかし，これは，次のような弊

ムでは，分散された機器が互いの情報を交換するこ

害を引き起こす．

• モバイルエージェントとのコミュニケーションとで協調や交渉を行い問題を解決する必要が出てきており，このようなシステムを作る枠組みとして様々が困難．

なエージェントが提案されている．

エージェントが移動すれば，エージェントが存在するアドレスも変わる．すなわち，受信側エー

Communication Protocol for Agent Platform : Agent
Platform Protocol.
Kenichi TAKAHASHI, Zhong GUOQIANG, Satoshi
AMAMIYA, 九州大学 大学院 システム情報科学府,
Graduate School of Information Science and Electrical Kyushu University.
Tsunenori MINE, Makoto AMAMIYA, 九州大学 大学
院 システム情報科学研究院, Graduate School of Information Science and Electrical Engineering, Kyushu
University.

ジェントの物理アドレスを特定することは難しい．

• エージェントに，予め決定された連携を行わせることが難しい．
例えば，２種類のエージェント，Ping と Pong が存在し，Ping は，適当なタイミングで Pong にメッセージを送り，Pong の存在を確認する仕事を持つとする．このとき，２種類のエージェント30

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
が別々にインストールされ，予めそれぞれのアド

2

いに利用できるようになる．

レスを特定できない場合，Ping は，Pong の物

以下，２節では APP について述べ，３節で APP

理的なアドレスを知ることができないため，送を適用した AP の例として ACZ を紹介する．そして，信先としては，”Pong”とだけしか指定できない．

４節で APP を適用した ACZ を用いて，APP の機能

しかし，これでは，Pong が存在するアドレスがについての検証実験を行った結果について報告する．

指定されていないため，Ping から Pong にメッ
セージを伝達するには，Pong の物理的位置を検2 Agent Platform Protocol（APP）

索する機構が必要となる．

APP は，エージェントの活動をサポートする AP

これらの問題を解決するためには，まず AP 間に間の通信プロトコルであり，図 1 のように位置づけ

共通のインタフェースを提供するためのプロトコルをられる．APP は，低レベルの通信プロトコルとして定義しなければならない．そして，そのプロトコルで

TCP [8] を持つ．TCP では，信頼性のあるコネクショ

は，次のことを想定しなければならない．

ン指向型の通信を提供しており，データの欠損や重• AP にエージェントの物理的アドレスを管理さ

複，届けられる順序の違いなどを発生しない．

せ，エージェントに物理的な情報を意識させないようにする．

• 複数の種類の AP が存在しても，各 AP が一意にエージェントを識別できなければならない．

• AP によって，エージェントの管理方式が異なる．
• 要求した機能が，要求先 AP では実現されていない可能性がある．

• 一般に公開されていなければならない．
そこで我々は，AP 間でエージェントのコミュニ

図1

ケーションをサポートするためのプロトコルとして

APP の位置づけ

Agent Platform Protocol（以下，APP）を提案する．
APP では，１３の method と header が定義されたリAPP の主な特徴として次の点が上げられる．

クエスト／リスポンス指向のプロトコルであり，AP• サーバを介さない P2P な AP 間ネットワークのはそれらに従ったメッセージを用いて他の AP と協構築．

調を行う．APP は，次の機能を提供する．

• サーバを介さない Peer to Peer（以降，P2P）なAP 間ネットワーク．

P2P なネットワークでは，各ネットワークの構成要素が置き換え可能なため，耐故障性が高く，一つのAP の故障が AP のネットワーク（以降，AP で構成• エージェントメッセージの送受信機能．

されるネットワークを AP ネットワークと呼ぶ）に与• エージェントメッセージの伝達先の検索機能．

える影響は少ない．また，サーバ／クライアントモデ• エージェントの移動．

ルで構成された AP ネットワークのように，サーバのAP は，APP に従ってメッセージの送信先エージェ役割を担う AP に負荷が集中するという問題はなく，ントを検索し，メッセージの伝達を行うため，エー

更に，サーバの役割を担うような特定の AP への接

ジェントは，互いの物理的なアドレスを意識せず，コ

続は不要で，AP ネットワークの任意な一つの AP へ

ミュニケーションを行うことができる．エージェントの接続で AP ネットワークに加わることができる．

開発者は，AP に APP を実装することで，他で開発• エージェントメッセージの送受信機能の提供．

された異種の AP との通信が行えるようになり，様々

エージェントはコミュニケーション手段として，メッな場所で開発された様々な種類のエージェントを，互セージ（以降，APP によって用いられるメッセージ31

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
表1

APP で準備された method 一覧

分類

method説明

Connect

LINK

AP 間の認証及び通信経路の作成

DeLINKAP 間の通信経路切断

Deliver

MobileReply

GET LINK

要求先の AP が持つ通信経路情報の要求

ALIVE

要求先が活動状態であるか否かの確認

DELIVER3

エージェントメッセージの伝達

LOCATE AGENT

エージェントの検索依頼

GET AGENT LIST

要求先の AP が持つエージェント情報の要求

PUT AGENT LIST

保持しているエージェントの情報を他の AP に通知GET AGENT

エージェントを要求先の AP からローカルな AP に移動させる

PUT AGENT

ローカル AP 上のエージェントを要求先の AP に移動させる

ACCEPT

返答．要求を受理したときに用いる

SUCCESS

返答．要求が成功したときに用いる

FAILURE

返答．要求が失敗したときに用いると区別するために，エージェントメッセージと呼ぶ）

2.1.1 method

を用いた情報交換を行う．

AP は，エージェントのコミュニケーションや移動• エージェントメッセージの伝達先の検索機能の提供．

をサポートする環境を提供する．このため，APP では，１３の method を準備している（表 1）．

AP は，エージェントメッセージの送信先エージェ

Connect，Deliver，Mobile に分類される method

ントのアドレスが分からない場合，エージェントメッ

は，AP に対して要求を出し，その応答として，APセージの伝達先を探さなければならない．エージェン

は Reply に分類される method を用いる．

Connect サーバを介さないで P2P な AP ネッ

トメッセージの伝達先検索のため，APP では，（１）
他の AP に検索を任せる方法と（２）他の AP から情トワークを構成するための method 群．LINK

報を集め自分自身で検索を進める方法とを提供する．

によって，AP 間での認証を行い，お互いの存• モバイルエージェントの移動をサポート．

在を知り，相互に信頼性のある通信を可能とす

エージェントに，仕事の達成に必要な資源を求める．GET LINK は，要求先の AP が接続している AP の情報を要求する．AP は起動時に，まずAP 間を移動する手段を提供する．

LINK method を使って任意の AP に接続し，AP
2.1 AP メッセージ

ネットワークに加わる．次に GET LINK で AP

APP で用いられるメッセージを AP メッセージとネットワークの情報を求める．新たに得た AP

呼ぶ．AP メッセージは，method，header，body かネットワークの情報を利用して，複数の LINKら構成され，この順に記述される．ここで，method

を行うことで，特定の AP への依存度を下げる

は，AP メッセージが表す要求，または，応答を表す．

ことができる．DeLINK は，要求元の AP が通header は，method を解釈，処理するのに必要な情信を保証できなくなることを伝える．DeLINK報である．body は，各 method が対象とする任意のを受け取った AP は，接続可能な他の AP とのデータである．

接続が分断されないように GET LINK や LINK

method を使って，ネットワークが分断されない

AP メッセージ = {method, header, body}ように対処した後，DeLINK への応答を行わな

32

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-174

ければならない．ALIVE は，AP が実際に APは，保持しているエージェントの情報を他の AP

メッセージを受け付けることが可能であるかの確に通知する場合に利用する．

Mobile エージェントの移動を行うための method

認を行う．

Deliver エージェントメッセージを送受信する

群．POST AGENT は，要求先の AP にエージェ

ための method 群．DELIVER は，エージェン

ントを移動させ，GET AGENT は，要求先の AP

トメッセージを伝達する method では，bodyからエージェントを移動させる．

部にエージェントメッセージを指定し，aimAt

Reply Connect，Deliver，Mobile の各 method

header(表 2 参照) でエージェントメッセージのの 応 答 と し て 用 い ら れ る ．ACCEPT は ，各

受信側エージェントを指定する．DELIVER を受

method を受理したことを表し，FAILURE は，

信した AP は，aimAt header が示すエージェン

要求が失敗したことを，SUCCESS は，要求がトに body 部のエージェントメッセージを伝達す

成功したことを表す．

る．受信側エージェントが存在する AP が分から

2.1.2 header

ない場合の検索手段として，LOCATE AGENTAPP に お け る header は ，そ の 役 割 に よっと GET AGENT LIST を準備している．LO-て，general-header，body-header，authentication-

CATE AGENT は，他の AP に検索を任せる方

header に分けられる（表 2）．general-header は，す法であり（図 2(a)），LOCATE AGENT を受信

べての AP メッセージで必須であり，body-header

した AP は，aimAt で指定されたエージェントがは，body 部を持つ AP メッセージに必要とされる．

存在する AP を探し出し，見つかれば，body 部

authentication-header は，AP 間の認証が必要なとをそのアドレス（IP アドレス/Port 番号）としきに用いられる．header は，た SUCCESS を返す．GET AGENT LIST は，

header = header-name ”:” value

要求先の AP に，それが持つエージェントの情の形で表される．

報を要求する．これは，様々な AP からエージェ

2.1.3 body

ントの情報を集め，その情報を用いて目的のエー

body は，method で必要とされる任意のデータでジェントが存在する AP を自分で見つける場合にある．例えば，DELIVER の場合，body は，エージェ

利用する（図 2(b)）．また，PUT AGENT LIST

ントメッセージとなる．

3 APP の適用例
我々の研究室で研究・開発しているマルチエージェン
トシステム KODAMA（Kyushu university Open &Distributed Autonomous Multi-Agent）では，APとして ACZ （Agent Communication Zone）を利用する．本節では，まず，ACZ について述べ，次にACZ への APP 適用例を示す．
3.1 ACZACZ は，論理的なエージェント空間を物理的な構造にマッピングする機構であり，エージェント間のコ
ミュニケーションを実現するために必要となる物理的
図2

エージェントの検索方法

通信機能を提供する．通常，一つの計算機上に一つの33

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
表2

general-header

5

header 一覧

header-namevaluemessage-id

stringfrom

AP-Address

説明
メッセージつけられた固有の ID
メッセージを送信した AP のアドレス(IP-Address/port)
via*AP-Address

メッセージの経路

refer*message-id

メッセージの動機となった message-id

AP-TypestringAP のタイプ

authentication

authentication-typestring

認証方法-headerauthentication-value

string認証キー

authentication-expire

numberauthentication-value の有効期限

body-header

absolute

0 or 1

リンクの重要性

body-size

numberbody 部のサイズ

body-typestringbody 部のデータ形式

aimAt

stringbody 部のデータの対象* は，0 回以上の繰り返しを表す．

ACZ が存在し，分散環境上では複数の ACZ が存在

リモート層は，他の ACZ 上で活動するエージェン

する．これらの ACZ は，ネットワークを構成し，分

トのアドレスを記したテーブル RAT（Remote Agent

散した計算機の間での通信を制御する．この管理のた

address Table）と，他の ACZ の認可情報を記した

めに ACZ は，ローカル層とリモート層より構成されテーブル LT （Link Table）を持ち，他の ACZ 上でる（図 3）．

活動するエージェントへエージェントメッセージを伝達する際に利用される．

3.2 ACZ への APP の適用
ACZ のライフサイクルは，図 4 のように示される．

図3

ACZ の構造
図4

ACZ のライフサイクル

ローカル層は，ローカル ACZ 上のエージェントを管理するテーブル LAT（Local Agent address Table）

ACZ は生成されると直ぐに起動・初期化され，非活を持ち，ローカル ACZ 上のエージェントへのエー

動状態から活動状態になる．活動状態中は，エージェ

ジェントメッセージの伝達を行う．ローカル ACZ 上

ントの生成や消滅，エージェントメッセージの伝達がのエージェントの生成または消滅時には，その名前が行われる．そして，最後に停止され，活動状態から

LAT に追加／削除される．

非活動状態に変化する．このように，ACZ の動作は，

34

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

6

起動・初期化，エージェントの生成・消滅，エージェ

ら DeLINK を受け取った ACZ2 は（図 6 °1 ），ACZ

ントメッセージの伝達，停止の４つに分けられる．こネットワークの分断をさけるため，GET LINK で停のうち，エージェントの生成・消滅はローカル層での止する ACZ1 から ACZ ネットワークの情報を受け取動作であり，APP は関係しない．そこで，エージェり（図 6 °
2 ，°
3 ），ACZ3 との間にリンクを構成するントの生成・消滅以外の３つの ACZ の動作について（図 6 °5 ）．

APP がどのように適用されているかを示す．
3.2.1 ACZ の起動・初期化
KODAMA は，Java で開発されており，ACZ は次のコマンドで起動・初期化される．

java acz.ACZ (使用 port) (接続 IP:port)
図 5 のような状態において，

java acz.ACZ 2000 192.168.0.1:2020

図6

ACZ の停止動作

3.2.3 メッセージの伝達
エージェントメッセージの受信側エージェントがLAT のエージェントであれば，ローカル層でエージェ
ントメッセージの伝達を行う．RAT に登録されてい図5

ACZ の初期動作

るエージェントであれば，RAT からアドレスを求め，

DELIVER を用い，エージェントメッセージを伝達
で ACZ1 を起動すれば，ACZ1 は，まず，LINK をする．LAT，RAT 双方に登録されていないエージェ

使って，ACZ2 ( 192.168.0.1 /2020) との間で，相互ントであれば，そのエージェントの検索が行われる．

通信のためのリンクを作る．これは，ACZ1 と ACZ2

ACZ でのエージェントの検索は，KODAMA エー

が各自の LT に相互登録する（図 5 °
1 ，°2 ）ことにジェントの論理的構造を参照し，LOCATE AGENT

よって実現する．次に，ACZ2 の持つ ACZ ネットワー

を用いて行う．
（図 7）．KODAMA では，エージェン

クの情報を集め（図 5 °
3 ，°4 ），集めた ACZ 中の任トは階層的に配置され，エージェントの名前が階層意の ACZ との間で相互の通信経路を作成する（図 5の場所を示す．例えば，”root・A”の名前を持つエー°
5 ，°6 ）．図 5 では，ACZ3 とだけ通信経路を作成しているが，ACZ の設定†1 によって，任意の数の通信

ジェントは，”root”の名前を持つエージェントを上経路を作成することができる．このことで，ACZ1 はジェントを下位階層に持つ．ACZ は，検索依頼を表

特定の ACZ への依存度を減らすことができる．

す LOCATE AGENT を用いて，次の方針でエージェ

3.2.2 ACZ の停止

位階層に持ち，”root・A・child”の名前を持つエーントの検索を行う．

図 6 のような状態において，ACZ1 が停止すれば，(a) 検索は RAT，LAT から refer header に含ま

ACZ2 と ACZ3 の間での通信経路が無くなり，ネッ

れない ACZ で活動するエージェントで階層的にトワークが２つに分断される．このため，ACZ1 か最も近いエージェントを見つけ，見つけたエー†1 ユーザによって，ACZ 初期化時に作成される通信経路の枠組みが指定される．

ジェントが目的のエージェントであれば，始めに LOCATE AGENT を出した ACZ に SUC-35

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

図7

7ACZ でのエージェント検索方法

CESS で応答し（図 7 °2 ），目的のエージェン

ダムに選び，停止時には LAT，RAT，LT のテーブル

トでなければ，見つけたエージェントが活動すを初期化した．また，各 ACZ には，１０のエージェ

る ACZ に LOCATE AGENT で検索を依頼す

ントを準備し，それぞれに適当なエージェントとコる（図 7 °
1 ）．LAT，RAT が共に要素を持たミュニケーションを行わせることとした．この条件でない場合は，最初に LT に登録された ACZ に

1 時間経過したあとにすべての ACZ を停止させた．

LOCATE AGENT で検索依頼を出す．

このときの実験結果を表 3 に示す．

(b) LOCATE AGENT を受け取った AP は，via

表3

header を 見 て ，す で に 受 け 取って い る LO-

実験結果

総 AP メッセージ数

CATE AGENT 要 求 で あ れ ば ，始 め に LO-

2831

CATE AGENT を 出 し た ACZ に FAILURE

総起動・停止回数44で応答する．まだ，受け取っていない LOCATE

エージェントのコミュニケーション数

906

AGENT 要求であれば，(a) を行う．
(c) LOCATE AGENT の応答として SUCCESSを受け取った ACZ は（図 7 °3 ），検索結果を

4.1 ネットワークに関する評価

RAT に登録する．応答として FAILURE を受け実験では， ACZ の起動・停止が共に 44 回行われ結果として，ACZ は，目的のエージェントを見つた．IP=192.168.35.76，port=2200 の ACZ 停止時に発生した AP メッセージを例 1 に示す．†2 ．

けた場合，DELIVER で（図 7 °4 ），エージェント

例 1 では，192.168.35.76 の停止によって AP ネッ

取れば，検索失敗である．

メッセージを伝達する．

トワークが分断されることを防ぐため，GET LINK
で AP ネットワークの情報を求め，192.168.35.64 と4 実験の間に新しくリンクを作成した．192.168.35.73 とのAPP の有効性を検証するために，APP を実装し間には，すでにリンクを持っていたため，新しくリンた ACZ で実験を行った．実験では，各計算機に一つクは構成しなかった．
結果，44 回の ACZ の起動・停止にも係わらず，APの ACZ を準備し，合計８台の計算機を利用した．各

ACZ は，ランダムに停止・起動を繰り返すこととし，†2 すべての ACZ で 2200 番ポートを使用しているため，
ポート番号は省略した．

起動時には接続する ACZ を活動中の ACZ からラン

36

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-178

ことができる．
この検証のため，我々の研究室で開発している ACZに，APP を実装した結果，APP を実装した ACZ は，動的な経路変更機能を持つ P2P な ACZ ネットワー
クを構成することができた．
今後の課題は，ACZ 以外の AP に APP を実装し，

ACZ と相互運用が可能であるかを検証することと，
例 1: ACZ 停止時の AP メッセージ

APP で提供されるエージェント検索方法の効率を検証することである．

ネットワークから孤立した ACZ は，発生しなかった．
すなわち，本稿で提案する APP を使用することで，参考文献

サーバを介さない P2P な AP 間ネットワークを構成[1] G. Zhong, K. Takahashi, T. Helmy, K. Takaki, T.
Mine, S. Kusakabe and M. Amamiya, “KODAMA:
As a Distributed Multi-agent System”, Proceedingsof the 7th International Conference on Parallel andDistributed Systems: Workshops, IEEE Computer
Society Press, pp.435–440, Iwate, Japan, July.2000.
[2] 高橋 健一, 高木 幸一郎, 鍾 国強, 雨宮 聡史, 峯 恒憲, 雨宮 真人,“分散マルチエージェントシステム KODAMA”, 「ソフトウェアエージェントとその応用」特集ワークショップ,SAA2000, 157–164, 2000
[3] T. Iwao, M. Takada, M. Amamiya, “Flexible
Multi-Agent Collaboration using Pattern Directed
Message Collaboration of Field Reactor Model”,
Approaches to Intelligent Agents - Second Pacific Rim International Workshop on Multi-Agents,
LNAI, vol.1733, Springer, pp.1–15, 1999.
[4] N. Minar, M. Gray, O. Roup, R. Krikorian and
P. Maes, “Hive: Distributed Agents for Networking
Things”, IEEE Concurrency, vol.8, no.2, 2000.
[5] FIPA : http://www.fipa.org[6] T. Finin, Y. Labrou, and J. Mayfield, “KQML
as an agent communication language”, In Software
Agents, MIT Press, Cambridge, pp.291–316, 1997.
[7] E.D. Pietro, A.L. Corte, O. Tomarchio, A. Puliafito, “Extending the MASIF Location Service int
the MAP Agent System”, IEEE Symposium on
Computers and Communications, 2000.
[8] D. Comer, D. Stevens（村井 純, 楠本 博之（訳））,“TCP/IP によるネットワーク構築”, 共立出版, 2001.

でき，AP ネットワーク接続の頑健性が確認できた．

4.2 エージェントのコミュニケーションに関する評価
実験では，906 回のエージェントのコミュニケー
ションが試みられた．このうち，903 回のコミュニ
ケーションが正常に行われた．残り 3 回については，
相手のエージェントが存在しないため，コミュニケー
ションを行わないものであった．この実験で，エー
ジェントは，相手の物理的位置を意識することなく，
コミュニケーションが正常に行えた．このように APPを使用することで，ACZ はエージェントの位置透過性を与えることができた．

5 おわりに本稿では，エージェントの活動を促進する環境 APを相互運用するためのプロトコルとして APP を提案した．APP は，サーバを介さない P2P な AP 間ネッ
トワークで，エージェントが物理的環境を意識することなくコミュニケーションを行うための環境を与える

37

38

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 2
c から回答が来なければ, 処理を進めることはできな
4. 処理中断集合が空集合となっているものを選択
い. しかし, ここでエージェント a が \多くの契約者
して, 計算を続ける.
4 では, 処理中断集合が空集合の計算プロセスを選択
はオプションを付けない" ということを知っていれば,b からの回答を待たずに先行的に準備を進めることがしている. これは, 処理中断集合が空集合であるもの
できる.
は, デフォルトの仮回答または実際の回答と矛盾して同様にエージェント b が \契約者 c は, 多くの場合おらず, 処理を進めても成功する可能性が高いと思わオプションを付ける" ということを知っていれば, 事れるからである.
本論文では, 他エージェントからの回答を待ってい前にエージェント a に対してそのこと報告をすることができ, a はその報告を受けて準備の修正を行なう.
るリテラルを集合として保存している. これにより,
もしその後, c から \オプションをつけない" という回
他のエージェントからの回答が変化する場合に投機的答を b が受け取れば, b は a に対して先程の報告を訂計算の導入を行うことができる.
正し, さらに a は再度修正を行なう.
2 投機的計算導入の実現
この場合, エージェント a と b がそれぞれ投機的計
以下では, 他エージェントからの回答が変化する場
算を行なっている. もし回答が変化する場合に対応できなければ, エージェント b が先行的に出した回答を合に投機的計算を導入するための準備を行う．
エージェント a に送ることは危険性が高い. なぜなら
枠組
ば, エージェント b が出した回答は, 投機的計算の性
質上, 保証されていないからである.
ここでは, 投機的計算の枠組の定義を述べる.
第

2.1

定義 1

回答が変化する場合に対応するための手法の概略,.
1. 各エージェントは事前に質問に対するデフォル
トの仮回答を用意する.
2. 各エージェントは, 用意した仮回答をもとに以降の処理を進める.

,,Q を負リテ, は「失敗による否定」を表す.Q
をリテラルとしたときに, Q = Q と定義する.
Q を原子式としたとき Q を正リテラル

は 以下のようになる.

ラルとする ここで

定義 2
n 個のエージェントからなるマルチエージェントにお,hI ; Si である. ここ, I は, エージェントの識別子の列 ha1; :::; an i であり, S は, エージェントでの個別投機的計算の枠組の列 hSa1 ; :::; San i を表し以下のように定義される.
各エージェントでの個別投機的計算の枠組 S は, h6, E , 1, Pi の４つ組であり, それぞれは以下の通りとする.
 6 : 定数の有限集合.6 の要素をエージェント識別子と呼ぶ.
 E : 外部述語と呼ばれる述語の集合.Q が外部述語を持つリテラルで,S がエージェント識別子のとき,Q@S を質問リテラルと呼ぶ. (Q@S ) を(Q)@S と定義する.
 1 : 以下の条件を満たす質問リテラルの基礎式
全ての外部述語 p を用いた基礎原子式 p(t1 ; :::; tn )と 全 て の エ ー ジェン ト S に 対 し て,1 に は

 もしデフォルトの仮回答を使って計算を進,められるならば そのまま続ける

ける投機的計算の枠組は ２つ組.

で

 またはデフォルトの仮回答とは矛盾する回答を使わなければ計算を進められなければ,,その矛盾する回答の集合を覚えておき 計算,.

は中断し 他の計算プロセスの処理を始める(ここで, この集合を処理中断集合と呼ぶ.)
3. 計算中に回答が返されたならば,(a) 現在計算中および中断されている全ての計算プロセスをチェックし, その中に回答と矛盾する仮定を使用しているものがあれば,その仮定を処理中断集合に移す.
(b) 処理が中断されている全ての計算プロセスの処理中断集合をチェックし, その中に回答と一致するものが含まれていれば, それを回答待ち集合から削除する.

39

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 3
準備
p(t1 ; :::; tn )@S または (p(t1 ; :::; tn )@S ) のいず
れかが含まれているものとする. 1 をデフォルト
投機的計算の実行は, 以下の二つの過程からなる.
一つはプロセス簡約過程であり, もう一つは回答到着
回答集合と呼ぶ.
 P : 一般論理プログラム過程である.
プロセスは,(a) その計算を開始, または継続するかを判定する為の集合,(b) 計算の現在の状態,(c) そのプ
質問リテラル Q@S は, 以下の二つの意味を持っている.
ロセスで既につかわれたデフォルト ,(d) 最初に与えら
1. P のルール中の質問リテラル Q@S は,6 中の れた質問の変数に対する解代入,(e) 回答を返す相手,の 5 つの状態からなる.
エージェント S に対して行なう質問を表す.
2. 1 におけ る質問 リテラルは, 外部エージェン
一つの質問に対する証明を行うために, 一つのプロ
ト S への質問に対するデ フォルト の仮回答をセスリストが作成される. プロセスは, 場合分けのよ表す. もし,p(t1 ; :::; tn )@S 2 1S ならば, 質問
うな選択肢がある場合に分岐し, 各プロセスは, おのp(t1 ; :::; tn ) に対する S のデフォルトの仮回答はおの別な分岐計算を表す. プロセス簡約過程では, 計
yes であり,(p(t1; ::; tn))@S 2 1S ならば, 質 算を開始, または継続すると判定されたプロセスを新
問 p(t1 ; :::; tn ) に対する S のデフォルトの仮回
たなプロセスに変換する. プロセス簡約過程とは, 各
答は yes である.
エージェントにおける通常のプログラムの処理に相当
先程の保険契約の例題をこの枠組を使用して表すと,するものである.
以下のようになる.
一方, 回答到着過程は, 他エージェントからの回答
枠組: h h a; b i, h Sa ; Sb i iが来たときの割り込み処理に相当するものである. 本
Sa
論文と [1] [2] との差異は, 回答到着過程の手法の違い
 6a = fbg
である.[1] [2] では, エージェントからの返答を待って
 E a = fop cg
いる中断リテラルが 1 個だけであるのに対して, 本論 1a = fop c@bg
文では, 中断リテラルを集合としてプロセス中に保存
 P a:
するという形にしている. そして, 中断リテラルの集
prepare(P )plan(P ):合が空集合ならば, そのプロセスは, 他エージェント
から送られた実際の回答, もしくはまだ回答が返されplan(1)
op c@b:ていないならば, 事前に準備した仮回答と矛盾していplan(2)
op c@b:ないということになる. よって, そのプロセスを実行
可能プロセスとし, また, そうでないときはプロセス
Sbを実行中断プロセスとしている.
 6b = fcg
定義 E b = fopg
プロセスは 5 つ組 hSGS; GS; AD; AN S; IDi とする.
 1b = fop@cg
ここで,
 Pb:
 SGS :他エージェント からの回答を待っている
op@c:
op c
GS 内の質問リテラルの集合. 処理中断集合と呼ぶ.
1a は,\契約者はオプションをつけない" という仮定
 GS :拡張リテラルの集合. ゴール列と呼ぶ.
 AD:質問リテラルの集合. 仮定デフォルトと呼ぶ.
に, 1b は \契約者 c はオプションをつける" という仮
 AN S :初期ゴールにおける変数に対する解代入,定に相当する.
または他エージェントから送られた質問リテラル.
第

2.2

0

0

3

40

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 4
リストの処理とは独立に行なわれる.
 ID:送信エージェント識別子.
SGS とは, 真偽値の値がデフォルトまたは実際に他既質問集合 AAQ 及び既回答集合 RF は, 各エー
エージェントから来た回答の値と異なる質問リテラル
ジェント に対して各々ひとつずつ作成される. あるエージェントにおいて, 複数のプロセスリストが作成を格納する集合となる. この集合が空集合ならば, そのプロセスは現時点では仮定したデフォルト , またはされた場合でも, 各々のプロセスリストから同じ AAQ
を参照することにより, 質問の重複を避けることが可実際に来た回答とも矛盾していない. そのため, そのプロセスは成功する可能性が高く, 効果があると考え能となる.
られるのでそのプロセスの計算を開始, または継続す
ゴール G の証明について, 以下のように定義する.
る. 空集合でなければ, そのプロセスは計算を行なっ
定義ても失敗する可能性が高いので, 中断して他のプロセスに実行を移す.
AN S は, 初期ゴールに変数が含まれている場合は
 ゴール G を証明する為のプロセスリスト中で,あるプロセスが SGS = ; かつ GS = ; となった
その変数に対する代入が格納され, 他エージェントから質問を受け, その質問の証明を行う場合は, 質問リ
場合, ゴール G の証明に成功したとみなす.
 ゴール G を証明するためのプロセスリスト中のテラルが格納される.
ID は, 質問 を送ったエー ジェント の識 別子であ全てのプロセスが中断された場合, すなわち全プ
る. エージェント S からエージェント S への質問はロセスで SGS 6= ; となった場合, このゴール G
Q@S f rom S という形で送られ, この場合,ID = Sの証明に失敗したとみなし,G とする.となる. また, エージェントに対する質問がユーザー証明の失敗の定義は, ゴール G を証明するための証明から与えられた場合は,ID = u とする.
木において, 全ての枝に, 事前に用意した仮定デフォ
定義
ルトと異なるリテラルが現れるため, 失敗する可能性
プロセスにおいて, SGS = ; となるプロセスを実行が高くなる. それ故, ゴール G の証明も失敗する可能
可能プロセス, SGS 6= ; となるプロセスを実行中断
性が高くなる. このため, ゴール G の証明を失敗したプロセスとする.
とみなし,G としている.
第

6

0

0

4

,

計算状態を 以下のリスト及び集合で定義する.

2.3

プロセス簡約過程,,

以下の簡約過程では エージェント S において 各

定義 5

 プロセスリスト P S とは, 実行可能プロセス, 実
行中断プロセスの集合である

.

.

,

,

.

.

初期ゴールに対して独立に行なう.

,

初期ステップ : あるエージェント S で 初期ゴール列
GS に対して実行可能プロセス,,

初期ゴールが与えられた場合は 以下の処理を各々の,h;; GS; ;; ;; IDi を証= RFS = ; とし, 以下のス
テップ , ステップ , ステップ を繰り返す.

プロセスリスト P S は 初期ゴールが与えられる度に.

,は 変化しないことを表す エージェント S に複数の

 既回答集合 RF とは, 実際に他エージェントか,,とにする もし 書き換えが書かれてていない場合に.

ら返答された質問リテラルの集合である,

それぞれ N ewP SS N ewAAQS N ewRFS と書くこ

 既質問集合 AAQ とは, 他エージェントに送られた質問リテラルの集合である,

ステップで新しく書き換わった P SS AAQS RFS を明手続きに与え AAQS,

新たに作成される また 一つのエージェント内で あ1る初期ゴール GS から作成されたプロセスリストの,ステップ 1:

処理は 他の初期ゴール GS 0 から作成されたプロセス

41

2

3

h;; ;; AD; AN S; IDi というプロセスが

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 5プロセスリスト P SS 中に出現した場合,ID = S な
fh;; ff ail(BS )g [ GS ; AD; AN S; IDig
らば AN S をエージェント S に返し, ID = u なら L が基礎質問リテラル Q@S のとき
ばユーザーに対し AN S を出力する. また, プロセス
0 L 62 AAQ かつ  L 62 AAQ ならば,リスト中の全てのプロセスが実行中断プロセスとなっエージェント S に質問 Q@S f rom S を送り,た場合は,AN S の否定を S に返す, または u に出力
N ewAAQS = AAQS [ fLg とする.
する.
0 L 2 RFS ならば,
ステップさもなければ, プロセスリスト から実N ewP S =P S [ fh;; GS ; AD [ fLg; AN S; IDig とする.
行可能プ ロセス h;; GS; AD; AN S; IDi を選び, さ
0  L 2 RFS ならば,らに, GS から拡張 リテラルを選び, P S = P S 0fh;; GS; AD; AN S; IDig および GS = GS 0 fLg
N ewP S =P S [fhfLg; GS ; AD [fLg; AN S; IDig とする.とする.
0 さもなければ L 2 1 ならば,ステップ上で選ばれたリテラル L に対して以下
N ewP S =を行なう.
P S [ fh;; GS ; AD [ fLg; AN S; IDig
 L が正リテラルならば,とする.
N ewP S = P S [0 さもなれければ  L 2 1 ならば,
fh;; (fbody(R)g [ GS ); AD; AN S; IDij
N ewP S = P S [ fhfLg; GS ; AD; AN S; IDig
R 2 P and 9most general uni er(mgu) とする.
s.t. head(R) = Lg L が基礎負リテラルならば,
回答到着過程N ewP S = P S [ fh;; N ewGS; AD; AN S; IDig
こ こ で は, 回 答 が 到 着 し た 場 合 に つ い て の 処
ここで N ewGS =理 手 法 を 説 明 す る. あ る エ ー ジェン ト S か ら
ff ail(body (R))jR 2 P and 9mgu 
エー ジェント S に対し て回答 Q が返 されたとき,
s.t. head(R) = Lg [ GS
S は 以 下 の 処 理 を 行 う. 以 下 の 処 理 過 程 で は,新し く書き換わった SGSS ,ADS ,RFS をそ れぞれ L が f ail(BS ) という式ならば,
N ewSGSS ,N ewADS ,N ewRFS とする. もし, 書き
0 もし, BS = ; ならば N ewP S = P S :換えが書かれていなければ, 変化しないことを表す.
0 もし, BS 6= ; ならば BS から B を選び,
 プロセスの処理
BS = BS 0 fB g とし,
P S 中の全てのプロセスに対して以下を行う．
＊ B が正リテラルならば,
Q@S 2 SGSS ならば,
N ewP S = P S [N ewSGSS = SGSS 0 fQ@S g かつ
fh;; N ewGS [ GS ; AD; AN S; IDig
N ewADS = ADS [ fQ@S g
ここで N ewGS =ff ail((fbody(R)g [ BS ))j
Q@S 2 ADS ならば,R 2 P and 9mgu  s.t. head(R) =N ewSGSS = SGSS [ fQ@S g かつBg
N ewADS = ADS 0 fQ@S g＊ B が基礎負リテラルまたは,
基礎質問リテラルならば,
上記の処理後, SGSS = ; となっているプロセス
N ewP S = P S [(実行可能プロセス) を選択し計算を進める. そう
fh;; f B g [ GS ; AD; AN S; IDig[
第

0

0

0

0

0

0

0

0

2:

0

0

0

0

0

0

3:

0

0

0

0

0

0

2.4

0

0

0

0

0

0

{

0

0

0

0

0

{

0

0

0

0

0

42

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 6
行なう. この時, ag が \true" となっていれば, 他エー
でないプロセス (実行中断プロセス) は計算を中断する．
ジェントからの メッセージが来ているので, Answer
File を読み込み, 投機的計算に他エージェントのメッ RFS の処理
Q@S 62 RFS かつ Q@S 62 RFS ならば,セージを反映させる. その後,Flag File を \false" とN ewRFS = RFS [ fQ@S g
書き換える.
Q@S 2 RFS ならば,保険契約の例題における全体の構成は, 図 2 の通り
N ewRFS = RFSとなる. なお,c は投機的計算を行なうエージェントで
Q@S 2 RFS ならば,
はなく,c からエージェント b への回答はユーザーがN ewRFS = RFS [ fQ@S g 0 fQ@S g
行なう.
この処理は, 各エージェントからの最新の回答だ
Java
けを蓄えておくということを表す.
C
Message Server
第

{

0

0

0

{

0

0

{

0

3 計算機上への実装

0.

提案した手法の計算機上への実装を行なった シス

prologJava
Message Server

Agent B

prologJava
Message Server

Agent A

1 のようになる.
投機的計算部分に prolog を, 通信部分に Java を用いテムの構成は図図2

Java
Send Message
prolog

全体図

Java
Message Server

4 実行例

Answer File
Flag File.
以下で, エージェント a に prepare(P ) を与えた場
合の実行履歴を示す.
最初に, エージェント a の履歴を示す.
1. P Sa = fh;; fprepare(P )g; ;; ;; ;ig,
AAQ = ;, RF = ;2. P Sa = fh;; fplan(1)g; ;; fP = 1g; ;i;h;; fplan(2)g; ;; fP = 2g; ;ig
3. P Sa = fh;; fop c@bg; ;; fP = 1g; ;i;h;; fplan(2)g; ;; fP = 2g; ;ig
4. P Sa = fh;; ;; fop c@bg; fP = 1g; ;i;h;; fplan(2)g; ;; fP = 2g; ;ig
AAQa = fop c@bg

歴を示す

Agent

図1

,

実行例として 先に述べた保険契約の問題の実行履

システム構成.
,Flag File に \false"と書き込み, Answer File には何も書き込まないでおく.
prolog では, 投機的計算を進める過程において, 質
問リテラルが出現した場合, またはゴールの証明に成功もしくは失敗した場合, 質問リテラルまたは回答を対象となるエージェントの Message Server に送信する.
一方,Java で作成した Message Server では, 他エー
ジェントからのメッセージを受け取った場合,Flag Fileを \true" と書き換え, 実際の メッセージを Answer
File に書き込む.
prolog では,1 ステップ毎に Flag File のチェックをて実装を行なった 初期状態ではエージェント a からエージェント b にop c@b f rom a という質問を送る

43

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 7たことによって, それまで計算を行っていたプロセ
こ こ で, a は b か ら 回 答 が 来 る 前 に, デ フォルト
ス h;; ;; fop c@bg; fP = 1g; ;i 中の op c@b
op c@b を使用して P = 1 という解を得た.
が処理中断集合に移される. このプロセスは処理
第,つぎに エージェント a から中断集合が空集合でなくなるので, 実行中断プロ

op c@b f rom a とセスとなり, 別のプロセスの計算が行なわれる.

.

いう質問を受け取ったエージェント b の履歴を示す

1. P Sb = f= 2 となる.

a が出力する解は P

h;; fop cg; ;; fop c@bg; aig,
AAQb = ;,RFb = ;2. P Sb = fh;; ff ail(op@cg; ;; fop c@bg; aig
3. P Sb = fh;; fop@cg; ;; fop c@bg; aig
4. P Sb = f
hfop@cg; ;; ;; fop c@bg; aig
AAQb = fop@cg
エージェント b から c に対して,op@c f rom b

ここで,c からエージェント b に対して,

op@c という回答がきたとする. この時 エージェント b では以下.
1. P Sb = fのようになるh;; ;; fop@cg; fop c@bg; aig
RFb = fop@cg
先程まで SGS に入っていた op@c が AD に移された. これにより SGS = ; かつ GS = ; となるプロセスが出現し, op c@b の証明が成功した,とみなされ エージェント a に回答される,.

エージェント a は 先程とは翻った回答をエーという質問を送る.

ジェント b から受けることになる この時のエー, op@c は b のデフォルトと一致しない,
中断される. また,op c を証明するための計算プロセスが全て中断されたため, このゴールの証明に失敗したものとみなし, (op c), すなわち
op c@b がエージェント a に対して回答される.
続いて, このエージェント b からの回答を受け取ったエージェント a の履歴を示す.
(a) P Sa = fhfop c@bg; ;; ;; fP = 1g; ;i;h;; fplan(2)g; ;; fP = 2g; ;ig
RFa = fop c@bg(b) P Sa = fh;; fplan(2)g; ;; fP = 2g; ;ig;
hfop c@bg; ;; ;; fP = 1g; ;ig(c) P Sa = fh;; fop c@bg; ;; fP = 2g; ;ig;
hfop c@bg; ;; ;; fP = 1g; ;ig(d) P Sa = fh;; ;; fop c@bg; fP = 2g; ;ig;
hfop c@bg; ;; ;; fP = 1g; ;ig
履歴 (a) において, b から回答 op c@b を受け取っ

ジェント a は以下のようになる

ここで,(a) P Sa = f

ため 処理中断集合に入り この計算プロセスは.

h;; ;; fop c@bg; fP = 1g; ;ig;
hfop c@bg; ;; ;; fP = 2g; ;ig
RFa = fop c@bg,

エージェント a から 再び解 P,= 1 が得られる.

この実行履歴で示した通り エージェント a は翻った,

回答をエージェント b から受け取ることになるが 最.

,新の回答に基づいた解が得られる また この履歴で,は示していないが エージェント b が c から翻った回,

答を受け取った場合でも エージェント a の場合と同様にして最新の回答に基づいた解が得られる

5 おわりに.

,

本論文における成果は 投機的計算の手法を拡張し,他のエージェントからの回答が変化するという場合に,対処することが出来る手法の提案を行なった事 また,

その手法を計算機上に実装し 動作の確認を行なった.

,ことである 今後の課題としては 応用問題による効果の検証が挙げられる

44

.

第

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

謝辞,

本研究を進めるにあたり 北海道大学の原口 誠先生

,

,

参考文献

,

[1] Satoh,K., Inoue,K., Iwanuma,K., Sakama,C.,\Speculative Computation by Abduction under Incomplete Communication Environments", Proceed-

大久保 好章先生 神戸大学の井上 克己先生 和歌山,

大学の坂間 千秋先生 山梨大学の岩沼 宏治先生に貴,ings of the Fourth International Conference on.

MultiAgent Systems,to appear(2000)[2] 佐藤, 井上, 岩沼, 坂間, 不完全通信環境下におけるア
ブダクションによる投機的計算, 人工知能学会知識ベース研究会資料, SIG-KBS-9904, pp.43 - 48 (2000)[3] 山本, 佐藤, マルチエージェントシステムへの投機的計算導入手法, 第 15 回人工知能学会全国大会 (2001)

重なご助言 ご指摘をいただきました ここに謝意を

.

8

示します

45