マルチエージェン
ジェントシステム
ステムにおける故ける故障の分散的自己診断

Decentralized Self-Diagnosis in Multi-Agent Systems
香田 徹*
Tohru K O H D A *吉田清明*
K iyoaki Y O SH ID A *朱雀保正+
Yasum asa SU JA K U +吉田紀彦*
N orihiko Y O SH ID A *Abstract— It is desired to construct a mechanical system that works for a long time without any human support. But
it is usually considered to be difficult to make the decentralized self-organizing autonomous system fault tolerant. In
this paper, we propose to apply the theories of self-diagnosable systems for computer networks to this problem. As
an example, we apply the highly structured one-step t-permanent fault diagnosable system, proposed by one of theauthors (T. Kohda), to a decentralized self-organizing autonomous robotic system that makes up a circle. The resultof simulation shows the usefulness of the proposed method.
Keywords— self-diagnosis, self-organization, fault tolerance, permanent fault, intermittent fault
1 は じめに
自律分散の観点から，人間の支援を受けることなく長期間に渡って動作可能なマルチエージェントシステムの構築が切望されている．しかしながら従来の自律分散系では，故障の発生そのものが想定されていないため，ひとたび故障が生じるとシステム全体の秩序が崩壊し，人為的な支援なしにその修復を行うことは不可能であった．これに対し我々は，コンピュータネットワークシステムにおける自己診断可能システムの一つである
highly structured システムを応用することを提案する．また，自律分散的に円周を形成するユニット群を題材にその有効性を確認する．
以下，２章では準備としてコンピュータネットワークシステムの自己診断可能システムの解説を，３章では本研究で応用した highly structured シス
テムの概説を行う．４章では highly structured シ
ステムのマルチエージェントシステムへの応用について ， 一般的見地から検討を加える ．５章
では，例題として取りあげた自律分散的に円周を形成するアルゴリズムや，作成したシミュレータの概説及びそのシミュレーション結果について述べる．最後に６章でまとめを行う．
2 自己診断可能シ可能システム
2.1 理 論 的 背景
コンピュータネットワークの故障診断の理論モデルとしては Preparata, Metze and Chien の提案による PMC モデルが最もよく知られている[1]． PMC* 九州大学大学院システム情報科学研究科, 〒812-81 福岡
市東区箱崎6丁目10番1号.
Dept. of Computer Science and Communication Eng.,KyushuUniversity, 6-10-1, Higashi, Fukuoka, 812-81 Japan.
E-mail:kohda@csce.kyushu-u.ac.jp,
seimei@cc.kurume-it.ac.jp, yoshida@is.kyushu-u.ac.jp+ 久留米工業大学電子情報工学科, 〒830 久留米市上津町
2228. Dept. of Information Science and Electronics Eng., Kurume Institute of Technology, 2228 Kamitsu-machi, Kurume,
Fukuoka, 830 Japan. E-mail:sujaku@cc.kurume-it.ac.jp

モデルにおける自己診断可能システムは，通常，ユニットの集合 V と検査の集合 E とで構成される
有向グラフ G = [V, E]で表現される．システムを構成しているユニットは他のユニットの状態を検査し，その状態（正常，故障）に応じた検査結果を出力する．ただし，各ユニットは自分自身の検査は行わず，故障ユニットによる検査結果は信頼できない．このような PMC モデルを用いて自己診断可能システムの必要十分条件，構成方法，検査結果の集合（症候群と呼ぶ）から故障ユニットを検出する解析問題などの研究が盛んに行われてきたが，それらの研究では，故障ユニットは時間的に状態の変化がない 永久故障（permanent fault）として扱われてきた．しかしながら，現実のディジタルシステムでは，故障状態が時間的に変化すること及び検査が不完全な場合などを考慮した 間欠故障(intermittent fault) の概念の必要性が最近説かれている．
間欠故障ユニットが正常ユニットから検査されている場合，その検査結果は検査のたびに変化し得る．さらに間欠故障ユニットが複数の正常ユニットから検査されている場合，それらの検査結果は必ずしも一致しない．仮にシステム内の幾つかの故障ユニットが正常と判定されたとすると，その診断は 不完全 (incomplete) であるとみなされる．また正常ユニットが一つでも故障と判定されたとすると，その診断は 不正確(incorrect) であるとみなされる．間欠故障の存在は診断を不完全なものにする可能性を意味している．
不完全であっても不正確では決してない診断特性を確保するために，間欠故障を含む故障診断(hybrid fault diagnosis)に対する幾つかの種類の診断可能性 (diagnosability)が定義されている．それらの中でも最も一般的なのは t/r/ t -diagnosability[4]と呼ばれる．ここで t はシステム内における永久故障ユニットと間欠故障ユニットとの和の最大値，rは間欠故障ユニット数の最大値 (t ³ r) を表している． t は症候群の空間 (syndorome space) の大きさを表現し，故障ユニットの診断の際に有効である．

PMC モデ ル
Preparata らはユニットを節点に，検査を孤に対応 さ せ ， 節 点 v の 集 合 V = {v} と 孤 (v, u ) の 集 合

L1 = X，L0= X(1)になる故障パターンが存在する．これを自明な故障パターンと呼ぶ．

2.2

E = (v, u ) とで定められる有向グラフ G = [V , E ] を用いて自己診断可能システムを表現した．孤 (v, u ) の始点 v ，終点 u に対応するユニットは各々，検査ユニット，被検査ユニットと呼ばれる(図１)．さらに そ の 検 査 結 果 a(v, u ) を 孤 の 重 み に 対 応 さ せ ，a(v, u ) を表１のように定義した（＊印は０または１を意味する）．すなわち，検査ユニットが故障していれば，その検査結果は信頼できないとするものである．ただし，各ユニットは自分自身を検査することはできない．またこれらの検査結果の集合は症候群(syndrome)と呼ばれる．
図1

PMC モデルにおけるシステムの基本構成

検 査ユニ ットv

表1

弧 (v,u)被 検 査ユニ ット

0 or 1
検 査結 果a(v,u)

u

PMC モデルにおける検査結果 a(v, u )検査ユニ ット 被検査ユニ ットuv
正常 永 久故障
正常01永 久故障*
*t -SD システム と t -OD システム
Preparata らは，最高 t 個までの多重永久故障を許すシステムの症候群から少なくとも一つの永久故障ユニットを検出可能な t 重故障逐次診断可能システム (t-fault sequentially diagnosable system ; 略
して t-SD システム)と，すべての故障ユニットを同時に検出可能な(t-fault one-step diagnosable system ;略して t-OD システム)とを提案した．
システム G = [V , E ] において，X を V の部分集合
2.3( X Ì V ) ，X を X の V に関する補集合（ X = V- X）とする．X ， X が各々故障，正常ユニットの集合である時の起こり得る症候群の一つを s(X)とし，その集合を S(X)とする．s(X)を症候群として持つ故障パターン（正常ユニットと故障ユニットとを区別したものであり，故障ユニット数は t 個以下である）は一般に複数個存在する．L1 ，L0 を各々故障，正常ユニットの集合とし，これらを用いて故障パターンを表現すると，当然のことながら症候群 s(X)に対して

定義 1 任意の症候群 s ( X ) Î S ( X )(1 £ X £ t ) に対して，これを症候群として持つ故障パターンが
L1 = X i , L0 = X i ( X i £ t ,1 £ i £ k )(2)のように k 個存在し，これ以外に存在しない時kxÎIX(3)ii =1なる x が存在し，さらに s (f ) に対する故障パターンが自明な故障パターン
L1 = f , L0 = V(4)以外に存在しない時及びその時に限りシステム Gは t-SD システムであるという．ただし X は X の要素の数であり， f は空集合である．

(1 £ X £ t )に対し自明な

定義 2 任意の症候群 s ( X )故障パターン以外の故障パターンが存在しない時
及びその時に限りシステム G は t-OD システムであるという．
ここで今後の議論において必要な集合を以下のように定義する．
定義 3 ユニット v によって検査を受けるユニットの集合 G(v )G(v ) = {u | (v, u )}(5)

ユニット v を検査するユニットの集合 G -1 (v )G(v ) 1 = {u | (u , v )}(6)
同様な集合が V の部分集合 X Ì V に関しても定義できる．
-G( X ) =U G(u ) - X

(7)

uÎ X

G -1 ( X ) =U G (u ) - X-1(8)uÎ X

Hakami and Amin はシステム G が t-OD システムであるための必要十分条件を以下のように与えた．
定理 1 総ユニット数 n のシステム G が t-OD システムであるための必要十分条件は(Ⅰ) n ³ 2t + 1(Ⅱ) 任意のユニット v Î V に対して G -1 (v ) ³ t(Ⅲ) 0 £ p £ t なる任意の整数 p 及び X = n - 2t + pを満足する V の任意の部分集合 X に対してG( X ) > p

である．なお，相互検査を有さないシステム G がt-OD システムであるための必要十分条件は(Ⅰ) ，(Ⅱ)のみで与えられる．
2.4 間欠 故障 を 含 む モ デ ル
間欠故障を加えたモデルにおける検査結果は表２のとおりである．正常ユニットによる検査結果
は被検査ユニットが正常あるいは永久故障である時のみ信頼でき，故障ユニット（永久故障，間欠故障）による検査結果は信頼できない．
表 2 間欠故障を含むモデルの検査結果 a(v, u )検 査ユニ ット
被 検 査ユニ ットuv
正常 永 久故障間欠 故障
正常01
*
永 久故障
*
*
*
間欠 故障
*
*
*
表２から明らかなように，間欠故障ユニットが正常ユニットから検査を受けている場合，その検査結果は検査のたびに変化し得る．さらに，間欠故障ユニットが複数の正常ユニットから検査を受けている場合，それらの検査結果は必ずしも一致しない．従って間欠故障ユニットは図２に示すように３種類の状態を取り得る．図２(a),(b)は，そのユニットを検査している全ての正常ユニットから０ ， １ が出力されている状態を表しており，図２(c)はそれ以外の状態を表している．間欠故障ユニットが図２(a)の状態を取った場合，このユニットは正常ユニットのように振る舞うことがあり（このユニットが検査する全ての正常ユニットに対して検査結果 ０ を，永久故障ユニットに対して検査結果 １ を出力する場合），このとき正常ユニットと区別することは原理的に不可能である．同様に間欠故障ユニットが図(b)の状態を取った場合，このユニットは永久故障ユニットと区別することは原理的に不可能である．

・・
*・・・・

*
*
0IF
00

*・・

*
*
1IF
1・・・・

1*・・

*
*0IF
1・・0

u ・・

u ・・u ・・

(a )

(b )

(c )

ka: F a u lt F ree u n it

ka・・

2.5 故障 状 態と症候 群
故障の種類と永久故障の他に間欠故障を加えたことにより，以下のような故障状態(fault situation)が考えられる．
・永久故障状態 (permanent fault situation)
故障ユニットが全て永久故障
・間欠故障状態 (intermittent fault situation)
故障ユニットが全て間欠故障・ハイブリッド故障状態 (hybrid fault situation)
故障ユニットが永久故障と間欠故障の両方
ハイブリッド故障状態は t/r 故障状態とも呼ばれる．t は故障ユニット数の最大値を表し，r は故障ユニットにおける間欠故障ユニット数の最大値を表す ．この表現を用いると永久故障状態間欠故障状態はそれぞれ t/0 故障状態，t/t 故障状態と表すことができる．
前述したように間欠故障ユニットは正常ユニッ
トのようにも，故障ユニットのようにも振る舞うため，正常ユニットによる検査から間欠故障ユニットを識別することはできない．よって間欠故障の存在は故障診断を不完全なものにし ，また，永久故障状態の場合と比較して故障診断の問題を複雑にする ．システム内における故障ユニットが 正常 と判定された場合その診断は 不完全 (incomplete)であるとみなされる．また ，システム内における正常ユニットが一つでも故障と識別された場合，その診断は 不正確 (incorrect)であるとみなされる．
2.6 ハイブリッド自己診 断 可能システム
故障ユニットの検出は不完全であるが，正常ユニットに対する診断は正確であるようなシステム
はハイブリッド自己診断可能システムと呼ば る ．
これまでに t/r-自己診断可能システム[2]，t/r/r-自己診断可能システム[3]，t/r/ t -自己診断可能システム[4]の３種類のシステムが提案されており，それぞれ以下のように特徴づけられる．
・t/r-自己診断可能システム
Mallera and Masson が紹介したシステム．症候群が永久故障状態から生じる症候群と一致する場合，すなわち hf(0)-compatible 症候群である場合，その診断は不完全であるが正確なものとなる．

ka: F a u lty u n it

図 2 間欠故障ユニットの取る 3 状態・t/r/r-自己診断可能システム
Yang and Masson が紹介したシステム．どんな症候群からも少なくとも永久故障ユニットは全て識別可能．
・t/r/ t -自己診断可能システム

Yang and Masson が紹介したシステム．ハイブリッ
ド自己診断可能システムの一般形あると位置付けられている．症候群が t/ t -故障状態より生じる症候群と一致する場合，すなわち hf( t )-compatible である場合，その診断は不完全であるが正確である．
以上のような研究を背景に，著者の一人 (T.K.)
は PMC モデルの特別なクラスの自己診断可能システムとして， highly structured システム を提案した[5]．次章ではこの highly structured システム及びその症候群解析法について概説する．
3 highly structured システム
システム G = [V , E ] の各ユニット v Î V が常に図３で表されるサブシステム H(v ;μ,ν)を持つ時,システム G は highly structured システムであるという[8]．また，この時 v をカーネルユニットと呼ぶ．

highly structured μ -OD シ ス テ ム や highly structured t0/r0/r0-自己診 断 可能システム（ただしt0,r0は t0+r0 =μ, t0 ³ r0 ³ 0を満足する整数）が構成可能[7] [8]であることが判る．
次に highly structured システムの症候群解析法を紹介する．定理２を満足する highly structured
t-OD システムに対して定理４ような症候群解析法が提案されている．
定理４ 定理２を満足するシステム G = [V , E ] の任意のユニット v Î V においてd (v, H (v; m ,n ) ) = p1 + [n / 2] - ( p 4 + p 6 ) ³ 0 (12)が成り立つ時 v は正常である．ただし， p k は図４に示すようなサブシステム H(v ;μ,ν)における検査結果パターン Pk の数とする．

P1

v0xi0yiP5

v0zj

P2v1xi1yiP6

v1zj

P3v0xi1yi

P4 v1xi0yi

図4

図3Subsystem H(v ;μ,ν)

ここで矢印は検査，μ は長さ２の検査本数，νは長さ 1 の検査本数を表す．この highly structured
システム[5][6] に対して，次の定理２，定理３が証明されている[8]．
定 理 ２ システム G = [V , E ] が任意のユニットv Î V に対し ，図３の部分システム H(v ;μ,ν)をもち, かつ
m + [n / 2] ³ t(9)ならば G は t-OD システム である.
定 理 ３ システム G = [V , E ] が任意のユニットv Î V に対し ，図３の部分システム H(v ;μ,ν)をもち, かつ
m + [(n - 1) / 2] ³ e(t , r , t )(10)e(t , r , t ) = t + Min (r , t + 1)(11)
ならば G は t/r/ t -自己診 断 可能システムである．
従って定理３より ， システム Gを構成する任意のユニットvがμ本の長さ２の検査を持てば，

1£ i £ m
1 £ j £nH(v ;μ,ν)における検査結果パターン Pk

また間欠故障まで考慮した場合 ， 定理３を満足する highly structured t/r/ t -自己診 断 可能システムに対して，カーネルユニット v の状態判定のために次の２つの関数 s 1 (v, H ,t ) ， s 2 (v, H , t ) が導入されている[8]．
s 1 (v, H , t ) = Min (r , t + 1) - [(n - 1) / 2]

+ Max ( p 4 - t ,0 ) + p 6 - p1 - 1s 2 (v, H , t ) = Min (r , t + 1) - [(n - 1) / 2]
+ Max ( p1 - t ,0 ) + p 5 - p 4

さらに上の２式から次式が成立する．
s 1 (v, H , t ) + s 2 (v, H , t ) = G (r , t ,n , p1 , p 4 )

(13)
(14)
(15)

ただし
G (r , t ,n , p1 , p 4 ) = F (r , t ,n ) - Min ( p1 - t ,0)(16)- Min ( p 4 - t ,0 )F (r , t ,n ) = 2 Min (r , t + 1) - 2t + n - 2[(n - 1) / 2] - 1 (17)この関数 s 1 (v, H ,t ) ， s 2 (v, H , t ) を用いて，定理５のような症候群解析法が提案されている．
定理５ サブシステム H(v ;μ,ν)の t/r 故障状態から生じるどのような hf( t )-compatible 症候群に対してもカーネルユニット v の状態は整数値ベ()

クトル s 1 (v, H , t ), s 2 (v, H , t ) が示す判定式上の領域（図５）によって唯一に判定できる ．すなわ
ち s 1 (v, H , t ), s 2 (v, H , t ) が○，△ ，×の領域にあ()るとき PF，IF，FF と判定される．
s1PFG
IF
s2

G0

GGFF

G >0

G =0
G = -1

図 5 s 1 (v, H ,t ), s 2 (v, H ,t ) 平面上における判定式

定理４，定理５の症候群解析法は１）診断能力に対する検査数を最小にできる，２）検査数に線形比例して症候群の解析が可能，３）各ユニットの検査順序を問わない，４）各ユニット毎にローカルな情報で検査が可能，の長所を持つ[6]．また，既存の highly structured システムの構成を変更することなくユニットを新たに追加したり，許し得る多重故障数を増やすといった拡張性を有する組織的構成法も提案されている[7]．
4 highly structured システムの マ ル チ エージェント
システムへの 応 用についての 検 討
一般にマルチエージェントシステムとは，複数個の人工知能（AI）が，何らかの手段を用いてコミニュケーションを保ちながら，外界からの情報（刺激）や自己の保持情報などを基に，互いに自律分散的に動作しながら全体としては協調して効率よく複雑な仕事を自動的に処理可能なシステムをいう．マルチエージェントシステムにおいては，各々のタスクには予め専用のエージェントが用意され，それらが互いに調停し合いながら知的に問題解決を行う．もし，誤った情報処理，発信を行うエージェント（故障エージェントと呼ぶ）がシステム内に存在するならば，少なくともその故障エージェントを同定，排除しない限り，システム全体の信頼性を維持することは困難となる．従ってマルチエージェントシステムの高信頼化を実現するには，中央集権的な制御機構なしに故障エージェントの同定，排除及びそれに伴う秩序の回復を行う仕組みが必要不可欠であると言える．
そのような仕組みの一つとして，各エージェントに self-checking 機構を設けることが考えられる．
各エージェントが自分自身の故障の有無を診断し，故障が生じていると診断される場合は，自動的に自己機能の縮小あるいは停止を行ない，必要ならばその旨を他のエージェントに伝達するという方式である．しかし，故障の有無が疑われている状
況下において，各エージェントの 自己申告 をそのまま何の保証もなく受け入れることは信頼性維持の面から難点がある．また複数個のエージェントに同時に故障が生じたような場合，それらが結果的に共謀して誤った情報処理，発信を行ってしまうことも十分考えられる．従って，通常のself-checking 機構ではマルチエージェントシステムの高信頼化の枠組みとして不十分である．
マルチエージェントシステムをコンピュータネットワークシステムの一種とみなせば，先に述べた故障診断理論の応用が可能である．ただし，実際のマルチエージェントシステムにおいては，各エージェントは他の全てのエージェントと直接係わりながら処理を行うのではなく，ある特定のエージェントとのみ協調して処理を行うことが一般的である．また，状況の変化や必要に応じて，新たなエージェントが追加されることも考えられる．
従って，あるエージェントの故障診断を行うために，システム全体の症候群を必要としたり，診断されるエージェントの順序が特定の順序に規定されていたり，新たなエージェントの追加を許さないような自己診断可能システムでは実用面から現実的ではない．これに対し，highly structured シス
テムには 前章で述べた１），２），３），４） の長所を持つ症候群解析法や，拡張性の高い組織的構成法も提案されている．
以上のことから我々は，マルチエージェントシステムの耐故障化の枠組みとして highly structuredシステムを適用することを提案する．次章では，自律分散的に円周を形成するアルゴリズムを題材に highly structured t-OD システムの理論を適用した例を紹介する．
5 highly structured t-OD システムの自律分散系への適用例
5.1 自律分散的に円周を形成するアルゴリズム
このアルゴリズムは，平面上の n 台のユニットにおいて２つの前提，[前提１] 各ユニットは何らかの手段により，他のn-1 台のユニットの位置情報を取得可能である，[前提２] 最終的に形成しなければならない円周の直径値は既知である，の下に構成されている．各ユニットは現在位置から最も遠い位置にあるユニットと最も近い位置にあるユニットとの距離を算出する．各ユニットはリアルタイムに変化する距離情報と最終的に形成しなければならない円周の直径値とをもとに，このアルゴリズムに従って自律的に行動する．その結果，中央集権的な制御機構なしに群れ全体で円周という秩序的な形を形成するものである[9]．

は円周を形成する際に，故障ユニットと診断されたユニットを除外して行動する．なお，ここでは永久故障（各ユニットが保持する直径値が突然大きな値に変化して元に戻らなくなる）のみが生じると仮定した．
シミュレーションを行った結果，中央集権的制御機構なしに，仮定した全ての故障ユニットの同定，排除及びそれに伴う秩序（円周維持）の回復が行えることを確認できた．

5.2 計算機シミュレーションの概要
次に実際に作成したシミュレータの概略について述べる．図６はシミュレータの実際の出力画面を用いた概念図である．番号付きの黒い矩形はユニットを，番号はそのユニットの ID 番号を表す．
矩形の尖った部分はそのユニットの正面を表す．

6 おわりに中央集権的な制御機構なしに自律分散的に円周を構成するロボット群に対して，highly structured t-OD システムの理論を応用し，n 台のうち t 台までの多重永久故障を許す機能を付加することを試みた．計算機シミュレーションを行った結果，自律分散系の耐故障化のために，highly structured t -ODシステムの理論が有用であることを確認した．間欠故障までも考慮したハイブリッド故障状態に対しても，定理５に従って永久故障状態の場合と同様に対応可能である．今後は，これらの理論[5][7][8]の創発的計算を行うシステムへの展開も図って行
きたい．

図 6 シミュレータの概念図
図６に示すように各ユニットとフィールドは各々，独立した計算機上でシミュレーション可能である．各ユニットは被検査ユニットを検査し検査結果を出力するわけだが，ここでは，各ユニットが保持する円周の直径情報についてのみ検査を行うことにした．具体的には以下のような流れとなる．
Step1:各ユニットは被検査ユニットの直径情報を取得，自己の直径情報との比較を行い，ある誤差内で等しいとみなせるならば正常を意味する 0 を，そうでなければ故障を意味する 1 を出力する（ただし，故障ユニットによる検査結果は信頼できない）．Step2:各ユニットは他のユニットの検査結果を収集し，検査結果の集合（症候群）を形成する．
この症候群をもとに定理４に従い，各ユニットの故障の有無を診断する．Step3:診断後，各ユニット

参考文献[1] P. Preparata, G.Metze, and R.T.Chien : On the connection assignment problem of diagnosable systems,
IEEE Trans. Electromag. and Comput., EC-16, 6, pp.
848--854 (1967).
[2] S. Mallela and G. M. Masson : Diagnosis without
repair for hybrid fault situations, IEEE Trans. Comput.,
C-29, 6, pp.461--470 (1980).
[3] C. L. Yang and G. M. Masson : A generalization of
hybrid fault diagnosability, in Proc.15th
Ann.Int.Symp.Fault-Tolerant comput., pp.36-41(1985).
[4] C. L. Yang and G. M. Masson : A new measure forhybrid fault diagnosability, IEEE Trans. Comput.,
C-36, 3, pp.378--383 (1987).
[5] 香田 徹：t 重故障同時診断可能システム,信学論(D), J61-D, 9, pp.680--687 (1978).
[6] 香田 徹：t 重故障逐次診断可能システム,信学論(D), J61-D, 9, pp.688--694 (1978).
[7] T. Kohda and K. Abiru : A recursive procedure for
optimally designing a hybrid fault diagnosable system
in Proc.18th Ann. Int. Symp. on Fault--Tolerant Computing, IEEE Computer Society, pp.272--277 (1988).
[8] T. Kohda : A simple discriminator for identifying
faults in highly structured diagnosable systems, Journalof Circuits, Systems, and Computers, 4, 3, pp.255--277(1994).
[9] 澤田正宏,田邊慎一,吉田紀彦：自律分散的に秩序形成を行うロボット群の並列計算機上でのシミュレーション,情報処理学会第 46 回全国大会 3A-1
(1993).