Distributed Algorithm for Cooperative Mobile Robots — [学士論文研究①]

“体系的な知識を身につけよ”

ということで学士論文研究のための知見をまとめていきたいと思います. 表題が僕の研究テーマです. 本日のアジェンダは次の通り.

  1. 分散システム (Distributed System) とは
  2. 自律分散ロボット (Autonomous Mobile Robots) とパターン形成問題 (Pattern Formation Problem) について
  3. 具体例: 円形成問題を解いてみる

キワード: Distributed Algorithms, Autonomous Mobile Robots, Multi-Agent Systems, Formation of Geometric Patterns

※ 内容に誤りなどがございましたらご指摘いただけると幸いです.


1. 分散システム (Distributed System) とは

まだ知識が浅いことを前提として受け止めて欲しいのですが, 分散システムの興味関心を僕自身の言葉で表すとするならば,

複数のコンピュータを協調させて大きなシステムを作るための研究

になります. 人の社会に置き換えると, 様々な人がある特定のルールのもと(法律など), コミュニケーションを取りながら大きなことを成し遂げる. このプロセスを計算機でやろうという情報工学の一分野です.

言葉の理解を深めるため, 幾つか他の方が分散システムについて書いている文章(日本語)を引用します.

計算機も, 単体で動作させるより, ネットワークで相互接続し, 複数の計算機を一つのシステムとして構築して協調処理を行った方が, 役割を分担できて効率がよい. このような, ネットワークで相互接続された複数の計算機から構成された, ある共通の目的を果たすシステムのことを分散システムという. — [2]
分散システムは自律的に動作する複数の(プロセスや計算機, ロボット, 人などを抽象化した)エージェントから構成されるシステムである. — [3]

分散コンピューティング (Distributed Computing) も同じような文脈で使われることが多いです. 僕の研究テーマにも関わってくる分散アルゴリズム (Distributed Algorithm) は, 分散システム上で, ある問題を効率的に解くための手続き, といったニュアンスでしょうか.

分散システムの代表例としては, 大規模データの分散処理を支える, オープンソースのソフトウェアフレームワークである Apache Hadoop をあげておきます. ただ誤解してはならない点として, 並列計算 (Parallel Computing) と分散システムが区別すべき概念だということを指摘しておかなければなりません. どちらも複数のプロセスを用いて特定のタスクをこなす点は共通していますが, 着眼点が異なります. 分散システムでは,

  • 各エージェントの自律性 (Autonomy)
  • 脱中心化 (Decentralization)

に目が向いているのが前提ですが, 並列計算では

  • 同時並行 (Concurrency)

に焦点を当てているからです.

分散システムの主要なチャレンジについては, この記事が非常によくまとまっていますので, 参考にしてみてください.


2. 自律分散ロボット (Autonomous Mobile Robots) とパターン形成問題 (Pattern Formation Problem) について

分散システムではエージェントが物理的に移動する可能性があるモデルも扱う必要があります. モバイル端末の通信ソフトウェアやモバイルセンサーネットワーク, 群ロボットなどはその一例です.

このようなモデルを扱うために発達しているのが, 自律分散ロボット (Autonomous Mobile Robots) に対する研究です. 複数の自律的なロボットがある程度のコミュニケーションを取りつつ, 分散システムの考えに則って特定のタスクをこなすということをやりたいのですが, 良いイメージ像の一つは, ベイマックスのマイクロマシンではないのでしょうか. 一つ一つのロボットを見ても大したことはできない. しかし集団となってロボット群を形成すると, とてつもないパワーを発揮する. そんなことが期待されている領域だと考えています.

http://sam000urai.hatenablog.com/

エージェント(Agent) のモデル

ゴールとしては, 分散処理で実装されたロボット群がどのようなタスクをこなすことができて, どのようなことができないのかということに対しての理解になるので, 弱いロボットを想定とした研究がされます. 自律分散ロボットのモデルの特徴は次の通りです.

  • 同じ機能をもつ
  • 脱中心化 (Decentralize)
  • 同じプロトコルで実行される
  • 明白な通信のメカニズムを持たない

自律分散ロボットの各エージェントは,

  1. Look: 状況を観察し, 可視範囲で他のロボットの位置を把握す
  2. Compute: 1 に基づいて行き先を計算する
  3. Move: 2 に基づいて移動する
  4. Sleep: 一時停止

の 4 状態のシーケンスをもとに動作しています. ロボットは直接的なコミュニケーション手段をもたないため, 他のロボットの位置を観察して適切に行動することが求められます. つまり, 空間内のロボットの位置が情報を伝達する唯一の手段であり, 計算のインプットとなっています.

以下にモデルを構築する時に考慮しなければならない点をまとめます.

# 観測 (Visibility)

ロボットが他のロボットを観測する時に, フィールドにある全てのロボットを観測可能か, もしくは視野に制限があるのかどうか.

# 記憶 (Memory)

過去の履歴に依存せず, 最新の観測結果に基づいて行動が決定されるのか (無記憶), 過去の履歴も参照するのか.

# 体積 (Volume, Collision)

通常ロボットは単なる点として扱われるが, 衝突の可能性を考慮したり, あるロボットの影に隠れて観測できないロボットを許すかどうか.

# 移動 (Movement)

目的地に一度の移動で到達できるのか, 任意の地点で停止してしまうのか.

# 重複度検知 (Duplication Detection)

ロボットを点によってモデル化する時に, 同一地点に存在するロボット台数を計算する能力.

# アルゴリズム (Algorithm)

決定性アルゴリズムか, 確率的アルゴリズムか.

# スケジューリング (Operation Schedule)

FSYNC (すべてのロボットが完全に同期した時計を用いてアルゴリズムが実行できる), SSYNC (サイクルを実行しないロボットの存在を許す), ASYNC (ロボットの実行タイミングに制約がない)

[3] より, ロボットの実行モデル

パターン形成問題 (Pattern Formation Problem)

ロボティクスや制御, AIの分野における実験的かつヒューリスティックな観点から研究されているほとんどの基本的な問題は, 何らかの方法で特定のパターンを形成することです. 例えば主な問題として取り組まれているのが,

  • 一点集合問題 (Gathering, Rendezvous, Point Formation) : 一点に全てのロボットを移動させる
  • 円形成問題 (Circle) や直線整列 (Line): 全てのロボットで指定された半径の円や直線を形成する
  • Scattering, Covering : 密な構成にあるロボット群を, ある空間を占拠するようにばらまくこと
  • Flocking : 特定のパターンを維持したまま, ロボット群を継続させる

になります. 研究としてはどのような協調運動や制御プログラム, ロボット間のインタラクションが, 上述したような基本的な問題を解くことができるかに焦点を当てています.

無記憶 (Obliviousness) アルゴリズム

上述した問題を解くことができるようなロボットをモデル化しなければならないのですが, 考えられるパラメータは膨大です. ある特定の問題を解くためにも, 非常に多くのモデルが想定されます. その中でも重要な要素として触れておきたいのが, 記憶 / メモリをもつかどうかという点です. もちろん過去の状態を記憶していることは問題を解くために大変役立つものなのですが, ここで想定しているのは弱いロボットですので, 無記憶 (Obliviousness) アルゴリズムに言及しておこうと思います.

無記憶アルゴリズムのロボットモデルの関心は, ロボットが今現在の状況のみをリソースとして, 問題を解くことができるのかどうかであり, 自律分散ロボット研究においては基本的な問題の一つとなっています. 無記憶であることは次の 2 点と深く関連性があります.

  • 自己安定 (self-stabilisation) : アルゴリズムの実行中にプロセスが一時的な故障を起こしたとしても, そのあと十分長い時間の後には望む状態に収束されることが保証されるというもの. [2]
  • フォールトトレランス (fault-tolerance) : 構成要素の一部が故障しても, 全体としては正常に処理を続行する.

ある問題に対して, 無記憶的アプローチは有記憶と比べて好ましいものですが, 特定の状況では解くことのできない問題も存在しており, ある程度の記憶をもつロボットの研究も進んでいます. 現実のように連続空間ではなく, 離散的なフィールド(碁盤のようなイメージ)上においても, 無記憶アルゴリズムの影響と限界に関する研究がされています.

※ 本章を執筆するにあたって [1] の CHAPTER 1を参考にしました.


3. 具体例: 円形成問題を解いてみる

最後に具体例として, 自律分散ロボットで円形成問題を解いてみたいと思います. 今回使用するロボットモデルとアルゴリズムは [5] で触れられているものを参照しています.

A4: 半径 r の円に整列させる. 各ロボットは (自分から) 一番近いロボットと一番遠いロボットを見つけ, その中点 M からの距離が r になるような位置に移動する. 中点からの距離が合っていて移動する必要がない場合には, 左右の一番近いロボットを見つけ, その中点に移動する. [5]

モデル

上記の文章をもう少し詳しく解釈してみます.

  • 観測 : 他のロボットを観測する時に, フィールドにある全てのロボットを観測可能である.
  • 記憶 : 無記憶, 過去の履歴に依存しない.
  • 体積 : 考慮なし.
  • 移動 : 目的地にワンステップでは到達できず, 一定スピードで移動する.
  • 重複度検知 : なしと仮定する.
  • アルゴリズム : 決定的, 具体的な挙動のイメージを下に記す. 基本的には左下図の動作を繰り返すが, 目的地に十分近い場合には右下図の動作を行う.
  • スケジューリング : 言及なし, FYSYNC で実装する.

実装

scala で実装. GUI は Java の Swing を使用しました.

シミュレーション結果

赤点がロボット, 青点が中点M, 黄点が中点Mからロボットが距離 r となるような点を表しています. 50 台で実行しました.

あまり綺麗な円にならないのは計算を荒くしているためだと思われます.


本日は分散処理の一つの分野である, 自律分散ロボットのパターン形成について簡単にまとめてみました. 今後はパターン形成問題についての詳細や歴史, 群ロボットの扱いやシミュレーション, 合意形成やリーダー選出などの分散処理の基本的な問題, ブロックチェーンなどを扱っていこうと思います.