自律分散協調システムを 構築するには？ Network Robot ∼ 事例1

自律分散協調システムを
構築するには？
自律分散協調システム
∼システムについての議論∼
基礎的な(システム的な)概念
ドメインスペシフィックな知識
ドメインインディペンデントな知識
慶應義塾大学環境情報学部
徳田英幸
© H. Tokuda, Keio University
Network Robots?
Network Robot
∼ 事例1 ∼
© H. Tokuda, Keio University
Image of Network Robots
What is Network Robots?
Ubiquitous
Network
“Visible” type
Network Robots
“Virtual” type
“Unconscious” type
1
Navigation (Guide) Service
Co-operation
among three
different types of
robots
‘Unconscious-type’
Robot
Scenario of Advanced Network Robots
2005：Network robots in its infancy
Single function robots at home would
come to be connected to networks,
interactions between robots and consumer
electronics would be realized
2008：Phase of growth
Recognizing
people/environments
Network
Robot Platform
for sharing
robot contents
Robots will become diversified (virtual,
unconscious and visible types), mutually
interact and become available for multiple
purposes.
‘Visible-type’
robot
‘Virtual-type’
robot
2013：Mature phase
Context dependent
interaction between
human and robots
Robots can be used even outdoor via
ubiquitous networks; interact with two or
more robots; and free function expansion
will be realized
Centralized i-mode portal
NTT-Docomo
i-mode Gateway
∼ 事例２ ∼
© H. Tokuda, Keio University
集中型の問題点
„
単一故障
„
„
„
„
„
„
危機管理上の問題
顧客からのクレーム増
スケーラビリティ
„
集中型のメリット
„
„
ビジネスモデルの創出
回線使用料の独占
„
セキュリティの向上
„
アカウンティングの容易性
2,800万以上のclientに対応
応答性の低下
負荷分散の欠如
ビジネスの独占
„
専用回線の利用
2
Distributed i-mode Portal
分散型のメリット
„
新しいビジネスの導入
„
„
ビジネスモデルの創出
回線使用料の徴収モデル
• 個人から法人へ
„
スケーラビリティの向上
„
応答性・ユーザビリティの向上
多機能端末
„
„
„
i-mode portalの構造
Universal controller型が可能
分散型の問題点
„
アカウンティング問題
„
回線使用料の徴収へのオーバヘッド
自律分散協調システム
プロトコルと分散アルゴリズム
新しいドコモボックスの開発
„ セキュリティの確保
„ 多機能端末
„
„
端末コストの増大
慶應義塾大学環境情報学部
徳田英幸
自律分散協調システムとは？
自律分散協調システムとは？
新しいパワフルなパラダイム
創発システムのパラダイム
システム内にシステム全体を制御／統治す
るスパーバイザは存在しない。
„ 各サブシステムは、自律、分散した構成要素
からなる。
„ 全体のシステムの機能は、サブシステム間
の協調作業によって遂行される。
„
© H. Tokuda, Keio University
3
自律性について
„
社会システム
„
„
„
協調性について
„
„
自動整列問題
掃除ロボット問題
„
スマート交差点問題
協調プロトコル
• どのような協調パターンがあるのか？
• どのように記述するのか？
• なぜ協調するのか？
ネットワークロボットモデル
„
協調のメカニズム
„
発展途上国における地方自治体モデル
日本における地方自治体モデル
„
自然なプロトコル
„
人工的なプロトコル
• 生物システム
•
•
•
•
•
• どのようなアルゴリズムが良いか？
Client-Server
Ethernet’s MAC Layer
競売プロトコル
回覧板プロトコル
その他多種多様なプロトコル。。。
分散プログラムのモデル
„
並行プロセスモデル
„
分散プログラムのモデル化
。。。ちょっと復習。。。
„
並行オブジェクトモデル
„
„
„
Program = a set of cooperating (sequential)
processes
Program = a set of cooperating objects
対象としているシステムのモデル化に適している。
いくつかの分散・並行プログラミング言語も開発さ
れている。
© H. Tokuda, Keio University
並行プロセス: プロセス間通信(1)
並行プロセス: プロセス間通信(2)
Process Group G1
• Multicast
• Group Communication
• Unicast
Process C1
Process S1
GroupSend(G1, msg)
Process C1
Send(S1, msg)
Receive(C1, buf)
4
並行プロセス: プロセス間通信(3)
並行オブジェクト
• Broadcast
Object
All Processes
Object
methods
methods
SendAll(*, msg)
.
.
.
Process C1
プロセス間通信: Direct IPC
„
The communication is done between two processes
without using any communication entity.
Bsend(process_id, message, size)
Nsend(process_id, message, size)
Brec(process_id, buffer, size)
Nrec(process_id, buffer, size)
プロトコルとは？
∼協調動作の記述∼
process_id = Brecany(buffer, size)
process_id = Nrecany(buffer, size)
Request(process_id, message, sizeof(message),
buffer, sizeof(buf)
Reply(process_id, message, size)
© H. Tokuda, Keio University
プロトコルとは？
外交上の儀礼
„ 通信の送信側と受信側で取り決めた約束事
„ 通信手段
„
pro･to･col
1 Ｕ(外交上の)儀礼，典礼.
プロトコルの記述
„
„
„
„
2 Ｃ 条約原案; 議定書，プロトコル.
3 Ｃ (国家間の)協定.→＃
4 Ｃ 《米》 (実験･治療の)実施要綱[計画].
„
プロトコルの記述は、通信上の約束事すべてを
定義する。
通信メッセージのフォーマット（書式）の詳細
(format) -> (syntax)
メッセージを交換する際の手順 (procedure) > (grammer)
正しいメッセージが表わしている意味、語彙
(correctness) -> (semantics)
Completeな記述 vs. Incompleteな記述
5 Ｃ 【電算】 プロトコル 《データ通信の手順》.
[株式会社研究社 新英和・和英中辞典]
5
何のためにプロトコルが必要か？
データ転送に必要な初期化や終了
„ 送信者と受信者との同期（条件）
„ 転送エラーの検出や訂正
„ データの書式や符合化を行う
状態遷移図
„
Sender
Receiver
RTS
RTR
-msg
+msg
Wait
Wait
+ACK
Time-Space Chart
Sender
Receiver
msg
ACK
-ACK
Concurrent Programming Language
Process Sender( )
{
while(TRUE) {
prepare_message(buffer);
frame.data = buffer;
send_to_network(frame);
}
Process Receiver( )
{
while(TRUE) {
wait_for_frame(buffer);
receive_from_network( frame);
buffer = frame.data;
}
Stop-and-Wait Protocol
Process Sender( )
{
while(TRUE) {
prepare_message(buffer);
frame.data = buffer;
send_to_network(frame);
wait_for_frame(ack);
...
}
Process Receiver( )
{
while(TRUE) {
wait_for_frame(buffer);
receive_from_network( frame);
buffer = frame.data;
prepare_message(ack);
frame.data = ack;
send_to_network(frame);
}
分散システムの捕らえ方
© H. Tokuda, Keio University
6
システムの捕らえ方
„
構成論的手法
„
構成論的手法
„
Top-down, bottom-up手法
全体に対して個々のエージェントの役割が位置
づけられる。
„ コミュニケーションプロトコルの設計
„ マスタースレーブ的な協調、機能分割的な協調
„ 位置的、機能的分散処理の重視
„ 工学的な効率、システム動作解析可能性の重
視
„
• Client-server model
„
自己組織論的手法
„
„
自律的にシステムを構成
群知能、集団行動
• アリの巣
• 都市のかたち
„
自律型ロボットシステム
自己組織論的手法
„
協調的行動を発現するアーキテクチャの
構築
„
自律性とは？
„
システムダイナミクスの研究
„ 柔軟性、頑健性の重視
„ 自律性に基づく協調
„ 生物、社会現象の模倣
自律：
„
全体は、個々のエージェントのインタラクション
の結果として創出される。
„
協調方法を定義したアーキテクチャの構築
„
自分で自分の行為を規制すること
外部からの制御から脱して、自身の立てた規範に従って
行動すること
„
自立：
„
自律性をプログラムするとは？
„
„
他の援助や支配を受けず自分の力で身を立てること
エージェントを作るとは？
ロボット整列問題
„
一群のロボットを自律的に円に整列される
„
Alogrithm 1: Big brohter方式
„
Algorithm 2:先生ロボット＋生徒ロボット
„
Algorithm 3:先生ロボットを選出
„
Algorithm 4: 同一ロボット
• 各位置を明示
• 先生ロボットが計算し、支持
• 先生ロボットを動的に選出
7