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

1

RoboCupRescue における最少通話による協調の実現
森本 武資 河野 健二 竹内 郁雄

ロジェクトである [1]．現在，シミュレータ上の仮想的1 はじめにな災害空間で活動するエージェントを研究するシミュ

マルチエージェントシステムの研究では，対象が非レーション・プロジェクトと，災害現場で実際に活動常に限定されたトイ的な問題をテストベッドとするするロボットなどを研究するロボティクス & インフ場合が多い．トイ的な問題における研究は，問題の本ラストラクチャ・プロジェクトが進められている．

質をとらえやすいが，成果を実際的な問題に適用しシミュレーション・プロジェクトが開発している大にいくいという欠点を併せ持つ．マルチエージェント

規模災害シミュレーションシステムは，マルチエーシステムに関する実際的な問題を研究するためには，ジェントシ ステム のテ ストベッドとして 利用可 能

様々な事象を対象とするオープンな問題を扱うことな段階に入った．2001 年 4 月に福岡で開催されたが重要である．筆者らは，大規模災害シミュレーショ

RoboCupRescue JapanOpen を皮切りに，2001 年 7ンを扱う RoboCupRescue シミュレーション・プロ

月の RoboFesta 関西，8 月の RoboCupRescue2001

ジェクトに参加し，多種類のエージェントが多数活動

in USA において，同システム上で活動するエージェするマルチエージェントシステムの開発に取り組んでントの救助能力を評価するための競技会が開催されいる．現在，シミュレーションシステムのプロトタイ

た．シミュレーション・プロジェクトは，同システム

プが開発され，この上で救助活動を行うエージェントを発展させることにより，防災情報インフラと結合さの研究が可能になった．しかし，同エージェントの研せ，実際の災害情報とシミュレーションを融合したシ究が進むにつれ，一見複雑な同システムが実はトイ的ステムにし，より有効な意思決定支援に役立てることな問題に帰着できることが分かり，オープンな問題がを目標としている．

本質的に抱える，問題設定と実装の難しさを改めて示す結果となった．本稿では，同システムの概要を示

3 エージェントの活動目的と災害空間し，筆者らのエージェントの協調を述べ，筆者らのこ大規模災害シミュレーションシステムで活動する

れまでの成果を紹介する．

エージェントには，市民，救急隊，消防隊，道路の寸断を修復する道路啓開隊，通信を行う救急，消防，啓2 RoboCupRescue プロジェクト

開各隊の司令所の 7 種類がある．エージェントの活動

RoboCupRescue プロジェクトは，大規模災害に対目的は死者数を最小にすることであり，同異種のエーしてロバストな社会を創ることを最終目標とするプ
Takeshi Morimoto, 電気通信大学 情報工学科
Kenji Kono, 電気通信大学 情報工学科
Ikuo Takeuchi, 電気通信大学 情報工学科

ジェントが協調することで負傷者を救助する．
同システムは災害発生直後の市街地をシミュレートする．この市街地を災害空間と呼ぶ．死傷の主な原因には埋没と火災が挙げられる．震災直後には家屋71

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

2が倒壊し多数の市民が閉じ込められ負傷する．更に，定し，それをシステムに伝える．行動は次のターンに家屋から逃げられず火に巻き込まれれば，致命的なダ反映される．具体的には，以下の繰り返しによって，メージを被る．救急隊は一刻も早く負傷者を見つけ出シミュレーションが進行する．

し救助しなければならないが，道路は瓦礫などで寸断

1. Kernel が個々のエージェントに視覚情報を送るされており，負傷者の所まで移動できない．負傷者の

2. エージェントが Kernel に行動内容を伝える

救出には，まず道路啓開隊が啓開活動により救急隊と

3. Kernel が行動内容を Sub-simulator に送る

消防隊の移動経路を確保し，消防隊が消火活動により4. Sub-simulator が更新結果を Kernel に伝える

負傷者が火に巻き込まれるのを防ぐ必要がある．

5. Kernel が統合結果を Sub-simulator に送る
6. 災害空間の時間を 1 分進める

エージェントは同異種間で協調する必要があるが，個々のエージェントの視覚能力と通信能力は非常に制

エージェントは視覚情報を受けてから 1 〜 2 秒以内限されており，エージェントは限られた情報だけで協に行動を決定しなければならない．

調を実現しなければならない．加えて，災害空間はダイナミックに変化する．負傷者は徐々に消耗し，火4.2 災害空間のモデルと問題点

災は急激に広がり，他のエージェントは動きまわる．

災害空間は建物や道路，人間等のオブジェクトの集つまり，行動の対象自体が時々刻々と変化する．エー合として表現され，個々のオブジェクトは複数のプロ

ジェントは，行動対象の変化に応じて，活動と協調のパティを持つ．災害空間は 500 m 四方の市街地であプランを柔軟に変更できなければならない．

り，約 2500 個のオブジェクトによって構成される．
オブジェクトには，一般家屋，避難所，各隊の司令

4 大規模災害シミュレーションシステム

所といった建物オブジェクト，道路とその端点を表す

4.1 構成と処理

オブジェクト，川とその端点を表すオブジェクト，市シミュレーション・プロジェクトが開発している大規民，救急隊，消防隊，道路啓開隊，車といった移動物

模災害シミュレーションシステムは，複数のモジュー体オブジェクト，災害空間の場所や風向き等を表す世ルから構成される（図 1）．モジュールには，個々の界オブジェクトがある．しかし，全 15 種類のうち，災害をシミュレートする Sub-simulator，災害空間の世界，川，川の端点，車の 4 種類は実質的には使用さ地理情報を与える GIS （Geographical Information

れいない．災害空間上に存在するのは，建物と道路，System），災害空間の状況を視覚化する Viewer，こ人間だけである．

れらを統合する Kernel がある．個々のエージェント

建物には 13 個のプロパティがあり，道路には 15

も，システムを構成するモジュールの一つとして位置個，人間には 8 個あるが，システムにより実装され，づけられる．

かつエージェントの問題解決に必要なプロパティはわずかである（表 1）．

Agent

表1

Sub-simulator
KernelオブジェクトViewer

GIS
図1

シミュレーションシステムの構成問題解決に必要なプロパティ

プロパティ

建物

位置，燃焼度，面積

道路

位置，幅，閉塞幅，車線数

人間

現在地，生命力，負傷度，埋没度

災害空間のシミュレーションは 1 分刻みで進行す

災害空間の仕様は複雑だが，その複雑さには問題る．災害空間上の 1 分を 1 ターンと呼ぶ．エージェン

設定を豊かにするという点において有意味とはいえトは 1 ターン毎に，周囲の状況を知覚し，行動を決ない部分がある．加えて，複雑な仕様に開発が追いつ72

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
表2種類
市民救急隊
消防隊
道路啓開隊
救急隊司令所
消防隊司令所
道路啓開隊司令所

3

エージェントの能力

能力
Sense, Hear, Move(Route), Say(String)
Sense, Hear, Move(Route), Say(String), Tell(String), Rescue(Human), Load(Human), Unload
Sense, Hear, Move(Route), Say(String), Tell(String), Extinguish(Building)Sense, Hear, Move(Route), Say(String), Tell(String), Clear(Road)
Hear,Say(String), Tell(String)
Hear,Say(String), Tell(String)
Hear,Say(String), Tell(String)

かず，現在開発中のプロトタイプ・シミュレーション

エージェントが情報を獲得する手段には，視覚と通システムの実装は不安定である．不安定な実装の上信がある．個々のエージェントは，火災と半径 10m

では，協調以前に，単体で活動できるエージェントの以内の建物や道路，他のエージェントなどを視覚で実現すら難しく，実際，筆者らがエージェント開発にき，肉声と電気通信による通信ができる．肉声は話者要した労力の大半は，単体行動の実現のために費さから半径 30m 以内にいるエージェントに聞こえ，小れた．

隊による電気通信は同種の小隊と司令所に伝わる．司

このような問題設定の難しさや，それに付随するシ令所による電気通信では，他種の司令所にもメッセー

ステムの安定性の問題は，オープンな事象を扱うマジが伝達される（図 2）． 個々のエージェントの発話

ルチエージェントシステムが本質的に抱える問題である．RoboCup サッカー [2] でも，我々はこれと同じ救急隊司令所

消防隊司令所

道路啓開隊司令所

救急隊

消防隊

道路啓開隊

問題に直面したが，その際もやはり，協調の前に，まず単体の行動能力の向上が必要であるという認識に立ち，世界トップクラスのサッカー・エージェントを図2開発した [3]．複雑な問題設定の中では，マルチエー電気通信の流れ

ジェントの協調について，トイ的な問題をテストベッドとするのとはまったく別の苦労がある．と聞き取りはそれぞれ 1 ターンに 4 メッセージに限られている．聞き手は，届いたメッセージの中から 4

4.3 エージェントのモデル

つを話者によって選別し，内容を聞き取ることができ

個々のエージェントは，数人の人間の集まりを表しる．1 つのメッセージの情報量は，1 センテンス程度ている．市民は家族を，救急，消防，道路啓開隊は小に制限されている．小隊と司令所の通信回数の制限が隊を，司令所はそこで働く人達の集まりである．災害同じであるのは一見すると不自然だが，実際に東京消空間上では，72 家族の市民と，5 隊の救急隊，10 隊

防庁に置かれている通報用の電話の台数が 10〜20 台の消防隊，10 隊の道路啓開隊，そして司令所が各 1程度であることを考えれば，妥当な問題設定である．
しかしながら，エージェントの通信能力の制約は非棟活動する．
エージェントは，行為とその対象をシステムに伝え常に厳しい．メッセージの伝達には 1 ターンの遅延ることにより行動を起こす．ある経路 route に沿っがある上に，肉声は伝えられる対象が限られており，て移動するには，M ove(route) をシステムに伝える．

電気通信はメッセージの到達率が低いからである．

経路は道路や建物のリストで表現する．同様に，人間遅延は同種の小隊間ならば許容範囲だが，異種小隊

human の救助は Rescue(human) ，救急車への乗間の電気通信の伝達経路は，話者 → 同種司令所 →せ降ろしは Load(human) ，U nload，火災 building

異種司令所 → 異種小隊と長く，3 ターンもの遅延がへの放水は Extinguish(building) ，道路 road の啓生じる．

開は Clear(road) をシステムに伝える（表 2）．

肉声ならば，異種小隊間でも遅延を 1 ターンに抑73第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
えられるが，半径 10m の視野では他のエージェントの位置の把握が難しい上に，30m の肉声伝達範囲でcostF unc(Road) =は声が届く前に移動してしまっている場合が大半で

 1

通過可能
未確認
閉塞4(1)

ある．肉声による通信は，埋没した市民，や司令所のM
 2
Mような動かない聞き手に対してのみ有効であるといこうして得られた経路上の移動を繰り返すことで，える．

エージェントは閉塞状況をリアルタイムに学習しなが電気通信には，話すメッセージが多い程，聞き手がら，その時点で知り得る最良の経路を移動する．

メッセージを聞く確率が低くなるという，通信量と到達率のジレンマがある．例えば，消防隊 10 隊と消防

5.2 救急隊

隊司令所 1 棟がそれぞれ 4 回電気通信した場合，次死傷者に直接関わる救急隊の活動は非常に重要であのターンには，各消防隊に 40 ものメッセージが届く．

る．多数の市民が倒壊家屋に埋もれているのに対し，消防隊が内容を聞き取れるのは 4 メッセージだけで救急隊は 5 隊しかいない．救急隊は，救助活動の効果あるから，届いたメッセージの 10% しか聞き取れなを最大限に引き出すために，負傷の程度によって負傷いことになる．したがって，重要なメッセージを聞き者を選別し、生命の危機に瀕している負傷者を最優先逃さないためには，各エージェントが，最小限しか話に救助する “トリアージ” [4] に基づいて活動する．具さないようにする必要がある．

体的には，負傷者を以下の 4 段階に分けて救助する．

1. 即救助 … 救助しないと助からない5 実現したエージェント

2. 救助 … 自力で避難はできないが当面生き残れる5.1 単体の行動能力の向上

3. 救助不要 … 自力で避難できる

複数のエージェントが協調的活動を行うためには，

4. 救助断念 … 救助しても助からない

個々のエージェントが基礎的な行動を確実に遂行でき救急隊は「即救助」「救助」の負傷者を発見した時のる能力を備える必要がある．RoboCupRescue におけみ救助を始め，「救助不要」「救助断念」の負傷者を発る基礎能力とは，迅速な移動能力である．筆者らは，見しても捜索を続ける．同じ場所に複数の負傷者がい通過可能性に基づいた経路探索により到達確率の高る場合には，まず「即救助」の救助を優先する．優先い経路を構成することで，迅速な移動を実現した．こ

度が同じ場合には，確実のため，埋没度の少い負傷者

れには災害空間の以下の性質を利用した．の救助を優先する．

• 一度通過した経路は渋滞を除き確実に通過できる

負傷者は時々刻々と消耗し傷も深くなるため，迅速• 閉塞は道路毎に判定されるため，未確認道路数な救出活動が必要である．救出にかかる時間を短縮すが少い程，閉塞遭遇率が低くなる• 車両は高速に移動できるため，移動距離を考慮しなくてよいるためには，救助能力を集中させなければならない．
救急隊は，「即救助」「救助」の優先度をもつ負傷者を発見した時に，電気通信によって他の救急隊に報告

経路構成の方針は，まず通過可能を確認した道路のみし，報告を受けた救急隊はその場所に駆けつける．複で構成を試み，次に未確認道路数最少の経路の構成数の報告が同時に届いた場合には，迅速に到達できるを目指す．それでも目的地までの経路が見つからなけ場所にいる負傷者の方に駆けつけ，別の負傷者の救助れば，閉塞も含む経路を構成する．このアルゴリズム

中に報告を受けた場合は，移動せず救助を続ける．こは，最良優先探索に，以下のコスト関数（式 1）を与の協調により，負傷者を救出できる確率が向上する．

えることで実現できる．ここで，M は最大経路長よ5.3 消防隊

り大きな値とする．

火災は状態が急激に変化するため，特に素早い対応が必要な災害である．ごく初期の火災は 1 隊の消防74

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

5隊でも消火可能だが，それ以降は多数の消防隊による協調機構はトリビアルである．消防隊は移動を極力集中放水が必要となる．消防隊には，目的の火災に即避け，放水に専念したい．上述の戦略に基づいた行動座に移動できる能力が強く求められる．また，災害空選択過程において，遠くの火災に移動する際に，移動間には同時に複数の火災が発生するため，火災の状態率（式 2）の確率で移動するかしないかを判断するこを見極め，放水を適切に振り分けなければならない．とにより，他の消防隊が該当火災に放水している可能

通信は遅延を伴うため，急変する火災への放水の分性が高いならば，移動せずにすぐに放水できる火災を散を，通信で実現することは難しい．各自の判断で迷優先する．

わず消火に取り組む方が効果的だと考えられる．火災

移動する確率 =は視界に関係なく見られるため，全ての消防隊は，火目的の火災数
消防隊数

(2)

災自体の状態とその周囲の火災状況の認識を共有している．個々の消防隊は，これらを基に打ち立てた消火5.4 道路啓開隊

戦略を軸に，通信を使わない暗黙の協調を実現する．
個々の消防隊は，火災の状態，火災周囲の状況，火救急隊と消防隊にとって，移動は救助・放水のた災と自分との距離から，火災の放水優先度を見積り，めの手段であり，移動に時間をとられたくない．道

優先度が高い火災に放水/移動する．図 3 の数字は優

路啓開隊は彼らの移動回数を減らすことを目的とす

先度を表す．1 が最優先であり，これは放水範囲内にる．啓開隊は閉塞に遭遇しても自力で道を切り開けあって，消火価値が高く，ごく初期段階の火災を表るため，未確認道路の再探索に時間を費すよりも，最す．もしこの条件を満たす火災があれば，消防隊はそ少道路数の経路を突き進む方が効率が良い場合が多れに放水する．

い．また，最少道路数経路の確保は，他のエージェントの経路構成方針（式 1）とも合致しており，暗8Very Urgent Fire

1169414

図37Early Fire黙の協調（RoboCup サッカーにおける locker-room

Very Early Fireagreement [5]）を実現しているといえる．最良優先Fire within 30m

探索に与えるコスト関数は以下のようになる．

121013Urgent FireAll Fire5213

costF unc(Road) =火災の放水優先度

1M

通過可能
未確認 or 閉塞(3)

火災の消火価値は，その周囲 18m の火災状況からさらに，道路啓開隊は，他のエージェントからの啓決める．周囲に未着火の家屋が沢山ある場合，消火価開要請に対応する．救急隊と消防隊は，通りたいの値は高い．逆に火災が沢山ある場合や鎮火済みの家屋に通れない道路と，通りたかったのに通れなかった道しかない場合，その火災は焼け野原の中にあり消火価路を道路啓開隊に報告し，道路啓開隊は報告された値は低い．ただし，未着火と鎮火済みの両方がある場閉塞を優先的に切り開く．道路啓開隊は，道路を啓開合には，鎮火家屋は延焼防止線の役割を果たすため，するたびにそれを救急隊と消防隊に報告することで，その火災を消火すれば延焼防止線を結べるため，消火他のエージェントの道路状況に関するワールドモデル

価値が高い．消火価値は以下のプログラムから求めの精度を高める．

る．

6 実験消火価値 (F ire) = 未着火数-火災数 × 減少率

上述の 3 つの協調行動，救助能力の集中，閉塞とif 未着火数 > 0啓開の報告，放水能力の分散について，その有効性をthen 未着火数 += 鎮火数調べるために実験を行った．実験を行った災害空間では，震災直後に 4 棟が出火し 33%の道路が閉塞する．

75

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

協調の有無と活動結果

集中救助閉塞報告

放水分散

死者数

火災数

鎮火時間

救出人数

しない

しない

しない

25141

20332

する

する

しない

255316734

する

しない

する

2632

178

32

しない

する

する

24218129する

する

する

23104137

No Cooperate

No Report Block

515
Number of Move

1001050050100150200Time [min]25030050100150200Time [min]25030000250300150200Time [min]250300250300

Cooperate

50150200
Time [min]10010
Number of Extinguish

Number of Extinguish

510050No Distribute Extinguish
10505

協調の有無と移動回数

No Cooperate
1001000

図4

Number of Extinguish

Cooperate

15
Number of Move

Number of Move

156500図550100150200
Time [min]250300050100150200
Time [min]協調の有無と放水回数

実験結果を図 3 に示す．

ことを示している．啓開報告をしない場合（中央の救助能力を集中した方が，しない場合よりも多くの図）は，放水分散によって無駄な移動を控えているた負傷者を救出できている．閉塞と啓開を報告した場

め，移動するエージェントが少ない．全ての協調を行合と，放水能力を分散した場合も，しない場合より速う場合，消防隊は初期段階で鎮火を完了する．それ以く鎮火が完了している．また，3 つの協調行動を全て後の移動は，救急隊が次の負傷者の場所に向かうため行うことで，効果的な救助活動，消火活動を実現しての周期的なものがほとんどである．
図 5 は，協調しない場合，放水分散しない場合，全いる．
閉塞報告と放水分散の働きを詳しく見るために，協ての協調を行う場合の時間毎の放水回数を示してい調の有無による時間毎の移動回数（図 4）と放水回数る．協調しない場合は，初期段階に放水できず，火災（図 5）を示す．

が燃え広がった頃になってようやく放水できるよう

図 4 は，左から順に，協調しない場合，啓開報告をなっている．放水分散しない場合も初期消火に失敗しない（他は行う）場合，3 つの協調を行う場合の，しているが，閉塞報告によって火災に近けるため 100

救急隊と消防隊の，時間毎の移動回数を示している．

ターンあたりから全ての消防隊が放水できている．全

協調しない場合は鎮火が完了するまで，多数のエーての協調を行う場合は，消防隊は初期消火に成功し，ジェントがほぼ絶え間なく移動し続けている．移動のわずかな放水で鎮火を完了している．これは放水分多さは，目的地に到達するまでに時間がかかっている散によって無駄な移動を抑えられているためである．

76

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

火災に移動する際も，他に移動するエージェントが少的に抱える，問題設定と実装の難しさを改めて示すいため，啓開隊によるサポートを受けやすくなる．

結果となった．協調について若干の知見が得られた

以上により，実装した協調の有効性が確かめられた．

が，今後は，問題自体，Sub-simulator 群のさらなる改善が必要である．しかしその分，問題自身がオープ7 競技会での評価ンであるといえる．このような問題はマルチエージェ

RoboCupRescue プロジェクトは，大規模災害シントの協調について，トイ的な問題をテストベッドとミュレーションシステム上で活動するエージェントのするのとはまったく別の苦労があることを報告した．

救助能力を評価するために，競技会を開催している．

RoboCup サッカーでもこのようなオープン性はあっ筆者らが開発したエージェント YabAI は，これまでにたが RoboCupRescue ではオープン性が桁違いに大開催された全ての大会，RoboCup JapanOpen（2001

きい．しかし，より現実に即した問題であり，このよ

年 4 月），RoboFesta（2001 年 7 月），RoboCup2001

うなある種，黎明期の混乱の中，このような複雑なin USA（2001 年 8 月）で優勝した．米国で開かれた(怪奇と付け加えてもよいくらいの) 問題設定の中で第一回世界大会（4ヶ国 7 チームが参加）ではイランも，エージェントの協調について，我々の RoboCupのチーム（Arian）と接戦を繰り広げたが，それを除

サッカーの研究と同様，問題が複雑であれば協調の前けば他を圧倒していたといえる．にまず個々のエージェントのスキルの向上が必要であYabAI の最大の勝因は，個々のエージェントの高い基礎行動能力にあり，本題となるべき個々のエーるという一般的な知見が得られたということは結論できるであろう．

ジェントの自律や複数エージェント間の協調というテーマにあまり触れていない．この結果は，現在の参考文献

大規模災害シミュレーションシステムが，エージェン[ 1 ] 田所，北野編: ロボカップレスキュー：大規模災害
救助への挑戦, 共立出版 (2000)[ 2 ] P. Stone, T. Balch, G Kraetzschmar (Eds.):
RoboCup 2000: Robot Soccer World Cup IV, lecture notes in Computer Science. Springer Verlag,
Berlin, 2000.
[ 3 ] 鈴木隆志，栗田英明，竹内郁雄: RoboCup シミュ
レーションエージェントの能力とワールドモデル, 情報処理学会研究報告, Vol. 2000 No. 27(GI-2) pp. 25-32,(2000)[ 4 ] 高橋友一他 : 大規模災害におけるマルチエージェン
トシステム, MACC2000 (2000)[ 5 ] Peter Stone and Mnuela Veloso: Task Decomposition, Dynamic Role Assignment, and LowBandwidth Communication for Real-Time Strategic
Teamwork, Artificial Intelligence (AIJ), 1999.

トの分散協調の研究以前の段階にあることを示している．

8 まとめ
様々な事象を対象とするオープンな問題を扱うた
めに，RoboCupRescue シミュレーションプロジェクトが開発中の大規模災害シミュレーションシステム上で活動する防災救助エージェントについて研究を行った．しかし，一見複雑な同システムが実はトイ的な問題に帰着できることが分かり，オープンな問題が本質

77