自律分散協調システム プロトコルと分散アルゴリズム 慶應義塾大学環境情報学部 徳田英幸 © H.Tokuda 2007.

Presentation on theme: "自律分散協調システム プロトコルと分散アルゴリズム 慶應義塾大学環境情報学部 徳田英幸 © H.Tokuda 2007."— Presentation transcript:

1 自律分散協調システム プロトコルと分散アルゴリズム 慶應義塾大学環境情報学部 徳田英幸 © H.Tokuda 2007

2 Mobile Ad hoc Networks ～ 事例1 ～

3 無線アドホックネットワーク アドホックネットワークとは？ ネットワーク･インフラが存在しない トポロジが人や物の動きと共に動的に変化する
peer-to-peerでの通信スタイル トポロジが人や物の動きと共に動的に変化する ノードの移動、無線電波品質の変化 Weak Connectivity 常時接続の保証ではない © H.Tokuda 2007

4 アドホックネットワーク：応用例 パーソナルエリアネットワーク 軍隊の (Military) 環境 一般市民の (Civilian) 環境
携帯電話、ラップトップ、時計 軍隊の (Military) 環境 兵士、戦車、戦闘機 一般市民の (Civilian) 環境 タクシーネットワーク、ミーティングルーム、スポーツスタジアム、ボート 緊急時の操作 地震、洪水、竜巻 捜索と救出、警察や消防士 © H.Tokuda 2007

5 Wireless Sensor Networks ～ 事例2 ～

6 センサネットワーク利用分野 （出展： ユビキタスセンサネットワーク技術に関する調査研究会）
© H.Tokuda 2007

7 日米欧におけるセンサネットワーク （出展： 野村総合研究所&ユビキタスセンサネットワーク技術に関する調査研究会）
© H.Tokuda 2007

8 Sensor Network Models Sink-node Model P2P Model Habitat sensing
Seismic monitoring Structuring instrumentation Soil conditioning P2P Model Smart Kindergarten Smart Objects, Smart Toys Smart Surroundings Lovegety Navigety Sink Node Smart Nodes © H.Tokuda 2007

9 Traditional Sensor Networks
© H.Tokuda 2007

10 P2p models: Lovegety & Navigety
The Original p2p goods: Lovegety Navigety © H.Tokuda 2007

11 What is a Smart Sensor? P2P model Smart Sensor =
Comp.+Comm.+Sensor+Actuator Why? Extending traditional sensor networks for Ubicomp applications P2P model No base stations Effective use of Context-information Ambient technology Smart Lamp © H.Tokuda 2007

12 A Group Tour Keeper Smart Sensor with LED lights + button １２ １３
© H.Tokuda 2007

13 U. of Karlsruhe: Smart-Its
Detection, processing and communication of sensor data in sticker-size to be embedded into everyday objects Generic Platform © H.Tokuda 2007

14 分散アルゴリズム

15 分散アルゴリズム Distributed Mutual Exclusion Election Algorithm
Distributed Deadlock Clock Synchronization Byzantine consensus problem 。。。 © H.Tokuda 2007

16 Logical Clock L. Lamport (1978) 分散システムでの事象(event)の順序関係
happens-before: a -> b If a and b are events in the same process and a occurs before b then a->b is true. If a is "send-event" of a message in Pi and b is "receive-event" of the message in Pj, then a->b is true. For any two events in different processes, x->y is not true and y->x is not true: x and y are concurrent events © H.Tokuda 2007

17 Lamport's Logical Clock
Ci : Logical Clock （局所論理時計） 規則１：受信事象以外の事象eがPiで起こった場合、その直後にCiに１を加える．事象eは、更新された時刻Ciに生起したとする． 規則２： Piがメッセージを送信するときには、時刻印ts=Ciをメッセージに付加して送信する． Piが時刻印tsを持つメッセージを受信したときには、Ciをmax{Ci, ts}+1まで進める．この受信事象は更新された時刻Ciに生起したとする． © H.Tokuda 2007

18 Lamport's Algorithm 基本的なアイデア ? ? Pi Pj Pk req-i req-j reply reply
© H.Tokuda 2007

19 Ricart-Agrawala's Algorithm
1)資源を使用したいプロセスPiはreq(TSi, Pi)を他のすべてのプロセスに送信する． 2)プロセスPiからreqメッセージを受信したプロセスはPjは以下のように行動する． Pjが今資源を要請していないならば、Pjの現時点での局所時刻印を持つreplyメッセージをPiに返す． もし要請中であれば、（TSi、Pi）をPjのreqの（TSj、Pj）と比較する． if (TSi, Pi) < (TSj, Pj)then replyメッセージをPiに返す． else req(TSi, Pi)へのreplyをPjが資源を使用し終わるまで保留する． © H.Tokuda 2007

20 Ricart-Agrawala's Algorithm (cont.)
3)他のすべてのプロセスから自分のreqメッセージに対するreplyメッセージを受信したときに限り、Piは、資源の使用を許可される． 4)Piが資源を解放したときは、replyを保留しているすべてのreqメッセージ（を送信したプロセス）に対して、replyメッセージを返す． © H.Tokuda 2007

21 直感的な例 Pi Pj Pk req reply reply reply reply © H.Tokuda 2007

22 分散アルゴリズム ～分散デッドロック問題～

23 デッドロック システムを構成しているすべてのプロセスが起きるはずのない事象を待ち続ける状態 WFG: Wait-For-Graph p1
Brec(p2,...) Brec(p3,...) Brec(p1,...) p2 p3 WFG:　Wait-For-Graph © H.Tokuda 2007

24 デッドロックの起きる必要条件(Coffman, 1971)
相互排除(Mutual Exclusion) 同時に資源を２つ以上のプロセスが使用できない． 保持＆待ち（Hold and wait） すくなくとも１つの資源を持っていて、かつ他の資源待ちになれる． 横取り不可（No preemption） 使用されている資源を横取りできない． 循環待ち（Circular Wait） WFG上でサイクルが生じている． © H.Tokuda 2007

25 デッドロックに対する対処 デッドロックの予防と回避 デッドロックの検出と回復
Deadlock Prevention： WFGにサイクルが生じないように規制する． Deadlock Avoidance：将来サイクルが生じるかどうかを確認しながら資源への要求を管理する． デッドロックの検出と回復 Deadlock Detection：デッドロックが起きた時点で、検出する Deadlock recovery (Roll Back)：犠牲となるプロセスの実行を中止して、ある時点からの実行を再開する． © H.Tokuda 2007

26 デッドロックの回復 どのようにしてプロセスの状態をroll backするか？ 回復の方法 Backward recovery
Forward recovery © H.Tokuda 2007

27 分散デッドロック システムを構成しているすべてのプロセスが起きるはずのない事象を待ち続ける状態 p1 Brec(p2,...)
© H.Tokuda 2007

28 WFG(Wait-for-Gragh) p1 Brec(p2,...) Brec(p3,...) Brec(p1,...) p2 p3
Host-B Host-A © H.Tokuda 2007

29 分散アルゴリズム ディペンダビリティ 耐故障アルゴリズム

30 ディペンダブルシステム 高信頼性（Dependability）とは、以下の要件を満たす 可用性（Availability）
システムを利用したいときに高い確率で利用可能 信頼性（Reliability） システムは、ある一定期間、正常に稼動可能 安全性（Safety） 障害時でも、システムに重大な問題が生じない 保守性（Maintainability） 故障したシステムを容易に回復可能 © H.Tokuda 2007

31 Dependability@cmu Prof. Dan Siewiorek C.mmp => Cm* => C.vmp
Issues in Testing and Reliability in Computer Systems 新しい概念？ Fault Tolerant Computing Systems Mission Critical Systems Dependable Computing Systems © H.Tokuda 2007

32 耐障害性（フォールトトレラント性） フォールトトレラント性 障害(fault)の種類
システムの一部に障害が発生しても、システム全体のサービスを提供を続けられる性質 障害(fault)の種類 過渡障害（transient fault） 一度だけ発生し、消滅する障害 ノイズによるビット損失など 間欠障害（intermittent fault） 一時的な障害が繰り返される障害 コネクタの接続不良など 永久障害（permanent fault） 修復されるまで存在し続ける障害 ディスククラッシュなど © H.Tokuda 2007

33 Dependabilityの議論 Dependability と IT assurance 運用・管理・保守している人、組織、社会制度
情報システム系 Reliability, Availability, Safety Confidentiality, Integrity, Maintenability ガバナンス系 運用・管理・保守している人、組織、社会制度 何がディペンドしているのか？ 人(命)、モノ、金 National Security . . . IT system Gov. © H.Tokuda 2007

34 障害の遮蔽 システムに冗長性を持たせることで障害を隠蔽 情報的冗長性 時間的冗長性 物理的冗長性 CRCチェック、エラー訂正符号など
動作のやり直しによる冗長性 トランザクション処理など 物理的冗長性 余分なデバイスやプロセスを持たせる冗長性 RAIDなど © H.Tokuda 2007

35 耐故障アルゴリズム 停止故障 仮定 t-回復力 (t-resilient) ビザンティン故障 故障したプロセスは永遠に停止する．
通信は、可能であるが、プロセスの挙動が保証されない t-回復力　(t-resilient) あるアルゴリズムが高々t個のプロセスの故障にも耐えるアルゴリズム． ビザンティン故障 故障したプロセスの動作に一切の仮定をおかない． 故障プロセスは、任意の動作しうる！ © H.Tokuda 2007

36 ビザンティン合意問題 正常なプロセスが同じ初期値を持っている場合、それらのプロセスは、ある値で合意形成することができる。
e.g. 3 processes -- 可能かどうか？ P1 値={0, 1} 合意の値は？ 故障プロセス P2 P3 © H.Tokuda 2007

37 ビザンティン合意問題：３ Processes
1 1 1 1 P3 P2 P3 P2 P3 P2 値={0, 1} 合意の値は? © H.Tokuda 2007

38 ビザンティン合意問題 Lamportの解(1982)
障害プロセスがm個のとき、正常プロセスが2m+1個以上、全体で3m+1個以上のとき、正常プロセス同士で合意に至ることが可能 (例）m=1, n=4>=3m+1なのでＯＫ p１：(1,2,*,4)、p２：(1,2,*,4)、p４：(1,2,*,4) P1 P2 P4 P3 1 © H.Tokuda 2007

39 分散アルゴリズムの実践 ～頭の体操から創発システムへ～

40 (I) 分散ソート問題 １からＮまでの整数の分散ソート 問題 初期値 N = 100 Processes: P1- P10
Ｐ１からＰ１０までの各プロセスにランダムに選ばれた１０個の数が初期の値として与えられた時、どのようにしてソートすることができるか？ 各プロセスは、どのような条件で、ソートが終了したことを判定できるか？ © H.Tokuda 2007

41 (II) ロボット整列問題 ある部屋内において、与えられた半径ｄの円周上にほぼ等間隔で整列するプログラムを作成せよ。 仮定
ロボットが共有座標系を持つ 同期的な動作をする (c.f. life game) © H.Tokuda 2007

42 ロボット整列問題 一群のロボットを自律的に円に整列される Algorithm 1: Big brother方式
各位置を明示 Algorithm 2:先生ロボット＋生徒ロボット 先生ロボットが計算し、指示する Algorithm 3:先生ロボットを選出 先生ロボットを動的に選出 Algorithm 4: 同一ロボット 自律的に整列 © H.Tokuda 2007

43 hxt-課題：Robotroom.java どのように協調するのか？ 実行例… © H.Tokuda 2007

44 世代の概念: Life game (1) Life game Life gameのルール J. H. ConwayのLife Game
盤面上にいくつかの石（生命体）を置く．（初期集団） 盤面のある場所が空いていて、しかもその場所と隣り合うちょうど３個の場所に生命体が存在するならば、次の世代にはその空いた場所に新しい生命体が誕生する． また、すでに存在する生命体については、隣り合う場所に住む生命体が１個以下、または４個以上になると、過疎または過密のため、次の世代には、死んでしまう． © H.Tokuda 2007

45 世代の概念: Life game (2) 世代の概念 * * * … © H.Tokuda 2007

46 (III) Wave programの課題 配布されたwave2.cプログラムを改良して、
　競技場で起こるwave 現象をsimulateできるようにする。 　　＜初期状態＞＜次世代生成部分＞ ＊ソースコード ＊出力結果 ＊考察 　　これをもとに、創発を起こす上でもっとも重要な要因について議論せよ。 © H.Tokuda 2007

47 hxt-課題：wave2.c どのように協調するのか？ 実行例… © H.Tokuda 2007

48 創発システムについて 複数の要素が有機的に関係し合って、相互作用を通して全体としてまとまった機能を発現している要素の集まり 弱い創発システム
相互作用が変わればシステムの機能も変わる！ 弱い創発システム ミクロな要素の動きが集まって全体にわたるマクロなパターンが創発するシステム 強い創発システム 環境変化に適応できる創発するシステム © H.Tokuda 2007

49 共通する性質は？ 自分と同じ能力の要素が沢山存在する 沢山の要素が広い空間に分散している
すべての要素が共通の方法で（自分の近くの要素とだけ）情報の交換をする すべての要素が同時並列的にうごく すべての要素が同じ状況になるように動く(同じ評価関数をもっている） © H.Tokuda 2007

50 分散アルゴリズム ～分散デッドロック問題～

51 分散デッドロック システムを構成しているすべてのプロセスが起きるはずのない事象を待ち続ける状態 p1 Brec(p2,...)
© H.Tokuda 2007

52 WFG(Wait-for-Gragh) p1 Brec(p2,...) Brec(p3,...) Brec(p1,...) p2 p3
Host-B Host-A © H.Tokuda 2007

53 創発システムに向けて 慶應義塾大学環境情報学部 徳田英幸

54 情報システムにおける自律分散協調論 自律分散協調システムのねらい 自律分散協調コンピューティング 自己組織性 創発のメカニズム
アドホックネットワークプロトコル ソフトウェアエージェント 自律ロボット p2pアプリケーション © H.Tokuda 2007

55 自律性について 社会システム 自律分散協調モデル ガバナンスモデル 教育、交通、安全システム 創発とは？ ロボット自動整列問題
電子政府モデル 地方自治体モデル 教育、交通、安全システム スマート交差点問題 自律分散協調モデル 創発とは？ Waveは、どう起るか？ ロボット自動整列問題 ロボットよ、コンパスを持って協調せよ！ 掃除ロボット問題 どのようなアルゴリズムが良いか？ © H.Tokuda 2007

56 協調性について 協調メカニズム 協調プロトコル 自然なプロトコル 人工的なプロトコル どのような協調パターンがあるのか？
どのように記述するのか？ なぜ協調するのか？ 自然なプロトコル 生物システム 人工的なプロトコル Client-Server Ethernet’s MAC Layer 競売プロトコル 回覧板プロトコル その他多種多様なプロトコル。。。 © H.Tokuda 2007

57 創発のかたち 上位層でのかたち 水の対流 サッカー場のウェーブ 自律型ロボットの整列問題 グループ、群、コミュニティ
© H.Tokuda 2007

58 ロボット整列問題 ある部屋内において、与えられた半径ｄの円周上にほぼ等間隔で整列するプログラムを作成せよ。 仮定 ロボットが共有座標系を持つ
同期的な動作をする (c.f. life game) © H.Tokuda 2007

59 ロボット整列問題 一群のロボットを自律的に円に整列される Algorithm 1: Big brother方式
各位置を明示 Algorithm 2:先生ロボット＋生徒ロボット 先生ロボットが計算し、支持 Algorithm 3:先生ロボットを選出 先生ロボットを動的に選出 Algorithm 4: 同一ロボット 自律的に整列 © H.Tokuda 2007

60 課題：Robotroom.java どのように協調するのか？ 実行例… © H.Tokuda 2007

61 Wave programの作成 配布されたwave2.cプログラムを改良して、
　競技場で起こるwave 現象をsimulateできるようにする。 　　＜初期状態＞＜次世代生成部分＞ ＊ソースコード ＊出力結果 ＊考察 　　これをもとに、創発を起こす上でもっとも重要な要因について議論せよ。 © H.Tokuda 2007

62 演習：wave2.c どのように協調するのか？ 実行例… © H.Tokuda 2007

63 創発システムについて 複数の要素が有機的に関係し合って、相互作用を通して全体としてまとまった機能を発現している要素の集まり 弱い創発システム
相互作用が変わればシステムの機能も変わる！ 弱い創発システム ミクロな要素の動きが集まって全体にわたるマクロなパターンが創発するシステム 強い創発システム 環境変化に適応できる創発するシステム © H.Tokuda 2007

64 共通する性質は？ 自分と同じ能力の要素が沢山存在する 沢山の要素が広い空間に分散している
すべての要素が共通の方法で（自分の近くの要素とだけ）情報の交換をする すべての要素が並列的にうごく すべての要素が同じ状況になるように動く(同じ評価関数をもっている） © H.Tokuda 2007

65 創発のギャップ 人間 vs. 自律型ロボット 多様な個 同期性 個の密度 全体の規模 実空間上の行動 vs. ネットワーク上の行動
個の非プログラム性 個の学習・動的適応性 多様な個 多様な価値観 情動的な行動 同期性 個の密度 population density 全体の規模 Scalability 実空間上の行動　vs. ネットワーク上の行動 © H.Tokuda 2007

66 自律分散協調コンピューティング 分散アルゴリズム 複雑な問題に対する新しいアプローチ 協調作業支援システム
相互排除問題、デッドロック問題、etc 複雑な問題に対する新しいアプローチ エージェントシステム 遺伝的アルゴリズム(GA) 協調作業支援システム CSCWシステム グループウェア コミュニティウェア © H.Tokuda 2007

67 マルチエージェントシステム

68 マルチエージェント システム特定の目的をもって行動するエージェントが、他のエージェントと協調的に行動するための性質、条件やエージェントが複数存在するときに生じる現象、効果などについて研究することを目的としている。 特定の問題を部分問題に分割して解決していくことを主たる目的としていない。 © H.Tokuda 2007

69 マルチエージェントに関わる研究分野 分散人工知能： 知的エージェントの協調的な問題解決 分散協調ロボット：複数ロボットの協調作業
CSCW：人間を支援するプログラム間の協調方法 人工生命：生命的存在の集団行動、生態系 仮想現実：仮想現実空間中に可視化された複数エージェントおよび人間の相互作用 © H.Tokuda 2007

70 システムの捕らえ方 構成論的手法 自己組織論的手法 Top-down, bottom-up手法 自律的にシステムを構成 群知能、集団行動
Client-server model 自己組織論的手法 自律的にシステムを構成 群知能、集団行動 アリの巣 都市のかたち 自律型ロボットシステム © H.Tokuda 2007

71 構成論的手法 協調方法を定義したアーキテクチャの構築 全体に対して個々のエージェントの役割が位置づけられる。
コミュニケーションプロトコルの設計 マスタースレーブ的な協調、機能分割的な協調 位置的、機能的分散処理の重視 工学的な効率、システム動作解析可能性の重視 © H.Tokuda 2007

72 自己組織論的手法 協調的行動を発現するアーキテクチャの構築 システムダイナミクスの研究 柔軟性、頑健性の重視 自律性に基づく協調
全体は、個々のエージェントのインタラクションの結果として創出される。 システムダイナミクスの研究 柔軟性、頑健性の重視 自律性に基づく協調 生物、社会現象の模倣 © H.Tokuda 2007

73 マルチロボットシステム 基本アイデア：複数ロボットの協調作業 背景：分散環境の整備、集中的システムの限界
特徴：柔軟性、頑健性、並列性、拡張性 応用：清掃、点検、運搬作業、Flexible Manufacturing, 宇宙ロボット、エンターテイメント © H.Tokuda 2007

74 自律性とは？ 自律： 自立： 自律性をプログラムするとは？ エージェントを作るとは？ 自分で自分の行為を規制すること
外部からの制御から脱して、自身の立てた規範に従って行動すること 自立： 他の援助や支配を受けず自分の力で身を立てること 自律性をプログラムするとは？ エージェントを作るとは？ © H.Tokuda 2007

75 知的エージェントとは？ 知的エージェントは、ある環境をセンサで知覚し、ある環境にエフェクタを通して動作するものである。
自律ロボットエージェント センサ：カメラ、赤外線センサ エフェクタ：手、足などを制御するモータ © H.Tokuda 2007

76 環境の多様性 アクセス可能 vs アクセス不能 決定的 vs 非決定的 静的 vs 動的 離散的 vs 連続的
© H.Tokuda 2007

77 知的エージェントとは？（２） 環境 センサ群 知覚動作 ？ エージェント 動作 エフェクタ © H.Tokuda 2007

78 エージェント指向コンピューティング 新しい自律分散協調システム作りのパラダイムの１つ AI分野での知的エージェント
問題解決の質や性能の向上 コンピュータ・ヒューマンインタラクションの高度化 システムモデリングと設計支援 AI分野での知的エージェント エージェント指向プログラミング IT分野でのソフトウェアエージェント © H.Tokuda 2007

79 問題解決のパラダイム

80 自律分散コンピューティング 分散アルゴリズム 複雑な問題に対する新しいアプローチ CSCWシステム 遺伝的アルゴリズム(GA)
ニューラルコンピューティング 分散エージェント／マルチエージェント CSCWシステム © H.Tokuda 2007

81 遺伝的アルゴリズム(Genetic Algorithm: GA)
生物進化（選択淘汰・突然変異）の原理に着想したアルゴリズム 基本的には，Generate-and-Test型のアルゴリズム Holland, "Adaptation in Natural and Artificial Systems" (1975) 1985 1st Conf. on Genetic Algorithm at CMU © H.Tokuda 2007

82 問題空間と解空間の概念 © H.Tokuda 2007

83 世代の概念 Life game Life gameのルール J. H. ConwayのLife Game
盤面上にいくつかの石（生命体）を置く．（初期集団） 盤面のある場所が空いていて、しかもその場所と隣り合うちょうど３個の場所に生命体が存在するならば、次の世代にはその空いた場所に新しい生命体が誕生する． また、すでに存在する生命体については、隣り合う場所に住む生命体が１個以下、または４個以上になると、過疎または過密のため、次の世代には、死んでしまう． © H.Tokuda 2007

84 世代の概念 (2) 世代の概念 © H.Tokuda 2007

85 遺伝的アルゴリズム(Genetic Algorithm: GA)
生物における遺伝のメカニズムの応用 Generate-and-Test型のアルゴリズム 多点情報を利用した確率的な探索方法の一つ ３つの遺伝的オペレータ 選択 (selection) 交叉 (crossover) 突然変異 (mutation) © H.Tokuda 2007

86 基本的な処理手順 Step 1: 初期集団の生成 Step 2: 終了条件が満たされるまでループ 適応度の評価 選択 交叉 突然変異
© H.Tokuda 2007

87 選択と交叉 © H.Tokuda 2007

88 ３つの遺伝的オペレータ 選択 交叉 突然変異 染色体上のある遺伝子を確率的に起き換え、新しい個体を作り出す。
集団における適応度の分布に従って、次世代に生存する個体群を確率的に決定する。 交叉 二つの個体間で染色体を組み換えることによって新しい個体を生成するもので、両親の優れた部分形成を子に継承させる。 突然変異 染色体上のある遺伝子を確率的に起き換え、新しい個体を作り出す。 © H.Tokuda 2007

89 TSP (Travelling Salesman Problem)
巡回セールスマン問題 すべての都市を１度ずつ訪問する． 巡回コストを最小にする経路を見つける． © H.Tokuda 2007

90 GSによるTSPの解法 © H.Tokuda 2007

91