とロボットの偏りに基づくデッド ロック回避
この章では，二体一組の主従関係交換手法において，その有効性を保証出来るロボット割合 について明らかにすることで，提案手法の有効範囲を明らかにする．また，提案手法の有効範 囲を超えるロボット割合においてデッドロックに陥る問題に対して，有効性を保証するための 新たな手法を提案し，その有効性を理論的に証明し，実機上での動作を検証する．
表6.1は2章において提示した本論文のアプローチと各章の対応である．この表において灰 色の部分がこの章が対象とする部分である．
表6.1 本研究の課題
理想環境 近実環境(個体差・故障) シミュレーション 第5章・前半 第5章・後半
理論・実機 第6章・前半(理論) 第6章・後半(実機)
6.1 理想環境下での二体一組の主従関係交換協調手法の有効
82 第6章 理論：主従関係交換手法の有効範囲とロボットの偏りに基づくデッドロック回避 デッドロック回避可能なロボット割合について明らかにする．
6.1.1 最小パネル構成におけるデッドロック回避
二体一組の主従関係交換手法においては，構造物上のロボット何台までデッドロックを回避 し，組立可能であるかを調べる必要がある．本研究では，デッドロック回避可能な構造物上の ロボットの頂点数に対する割合を調査することで，提案手法の有効範囲を検証する．構造物組 立においては，構造物が小さければ小さいほどロボットが移動可能な地点が減少し，デッド ロック回避が困難である．この最小のパネル枚数は，全方向をパネルに囲まれた頂点が含まれ る場合と定義し，3枚パネルが隣接した状態を最小構成とする．
まず，この最小構成の3枚のパネル上において発生するデッドロックについて考える．構造 物組立においては，ロボットは需要度マップで最も近いパネルに移動し，所持するパネルを展 開し消費するとパネル保管所に戻り，パネルの補給をするという行動を繰り返す．図6.1は，
組立中のロボットの移動を表す．この図において，四角のロボットは中央のパネル保管所から 外周部に向かって移動し，丸のロボットは外周部から中央部に向かって移動し，黒の矢印で示 したような往復運動を繰り返す．したがって，赤枠で囲まれた3枚のパネル内の赤い四角と青 い丸のロボットに着目した場合，この赤枠で囲まれた3枚のパネルが繋がる頂点のうち，バツ 印で示した部分にロボットが居て通れない場合でも，赤い四角のロボットは右側の四角で囲っ た頂点に，青のロボットは左側の丸で囲った頂点に移動出来れば，デッドロックを回避出来る．
したがって，本研究では3枚のパネル内のロボットが反対側の頂点に移動出来れば，デッ ドロックを回避出来ると定義し，3枚パネル内のロボットの配置を列挙し，何台までのロボッ ト数においてデッドロック回避可能か示す．提案手法は二体一組に基づくため，最小のデッド ロック状態である2組(4台)から開始し，ロボットは1組(2台)ずつ追加する．
6.1.2 各ロボット数における検証
■検証における前提
3枚パネル上での検証においては，各ロボットの移動方向，及びデッドロック状態とその解 消について以下のように定義する．定義においては，図6.2に示す例を用いて説明する．
各ロボットチームの初期状態と移動方向
各ロボットチームの初期状態は，各チームのリーダー同士が隣接し，互いに反対側に 移動する状態と定義する．図6.2においては，色が塗られたロボットが各チームのリー ダーを表し，青丸のロボットチームは左側の円に，赤四角のロボットチームは右側の四 角に向かって移動する．
デッドロック状態解消の成功
全ての組のロボットが互いの目的地への移動が完了した時点で，デッドロック状態が解
図6.1 パネル保管所とパネル外周部の往復移動
図6.2 デッドロック状態の定義
消されたとみなす．図6.2においては，赤四角のロボットチームのフォロワが四角に移 動し，青丸のロボットチームのフォロワが円に移動した時点とする．但し，残り1組に なった場合も，移動を妨げるロボットが存在しないため成功とみなす．
デッドロック状態解消の失敗
ロボットが前述のデッドロック状態の解消状態にならず同じ状態に戻り，それを繰り返 す場合，デッドロック状態の解消が不可能であるとみなす．
以上の定義のもと，各ロボット数において 3 枚パネル上のデッドロック状態解消を検証 する．
84 第6章 理論：主従関係交換手法の有効範囲とロボットの偏りに基づくデッドロック回避
■2組(4台)の検証
2組のロボットを3枚のパネル上に展開した全てのケースを図6.3に示す．配置が鏡面形に なる場合と，ロボットチームの位置を交換したケースについては，同じとみなす．この7つの ケースをそれぞれ提案手法通りに移動させた結果，全てのケースでデッドロック状態を解消出 来た．付録に掲載する全ケースの遷移のうち，ケース1の遷移について，図6.4に示す．この 図は，時間tにおけるロボットの位置を表しており，t=0で互いの移動を妨げる状態から開始 している．t=0において，青ロボットは右に移動を予定していたが赤ロボットに阻まれ，t=1 では左方向に移動している．ロボットは右に移動しようとして左に移動した場合の直後は主従 関係交換をしないという前提であるため，t=2ではロボットがおらず，目的地から最も近い方 向に移動する．赤色ロボットは青ロボットとは異なり，主従を交換出来るため，t=2で主従交 換してデッドロックを回避する．t=4以降は互いの目的地に移動し，それぞれ3枚パネルを抜 ける．
図6.3 ロボットの初期配置：2組
図6.4 2組ケース1におけるロボットの移動
■3組(6台)の検証
2組のケースと同様に，3組のロボットを3枚のパネル上に展開した全てのケースを図6.5 に示す．図の見方は2組の時と同様だが，緑色のロボットが追加されたものである．この6つ のケースをそれぞれ提案手法通りに移動させると，2組の時と同様に，全てデッドロック回避 することが出来た．2組の場合と同様に，全ケースの移動過程については割愛し，ケース1に おける遷移について図6.6に表す．基本的には2組の場合と同じだが，t=0で赤の移動が緑及 び青に阻まれ，t=1で主従関係交換をしたため，その後のt=3までは主従関係を交換しない．
t=4では交換可能になるが，青に再び阻まれるため，t=5で再び主従関係を交換する．
■4組(8台)の検証
2，3組のケースと同様に，4組のロボットを3枚のパネル上に展開した全てのケースを図 6.7に示す．図の見方はこれまでと同様であり，紫色のロボットが追加されたものである．こ の4つのケースをそれぞれ提案手法通りに移動させると，2，3組の時と同様に，全てデッド ロック回避することが出来た．全ケースの移動過程については，遷移が長いためケースの例示 は割愛する．
86 第6章 理論：主従関係交換手法の有効範囲とロボットの偏りに基づくデッドロック回避
図6.5 ロボットの初期配置：3組
■5組(10台)の検証
これまでのロボット数同様，5組のロボットを3枚のパネル上に展開した全てのケースを図 6.8に示す．図の見方はこれまでと同様であり，黄色のロボットが追加されたものである．こ の2つのケースをそれぞれ提案手法通りに移動させると，2〜4組の場合とは異なり，ケース 1においてループに陥りデッドロックを回避出来ない状態が現れた．この出現したループ状態 を図6.9に示す．この図では，t=kからt=k+5までが一連のループとなっており，t=k+6は t=kの状態と全く同じである．したがって，二体一組の主従関係交換手法においては，3枚パ ネル上に 5組ロボットが居る場合に，デッドロック回避出来ない場合があることが明らかと なった．
6.1.3 二体一組の主従関係交換手法の有効範囲
以上の結果から，提案した二体一組による主従関係交換手法をロボットに適用した場合，3 枚13 頂点のパネル上において，4 組8体までのロボット，すなわち全頂点数の約 61% をロ ボットが占める場合でも，デッドロックを発生せずに目的地に二体一組で移動出来ることが明 らかとなった．シミュレーション結果と比較すると，シミュレーションで利用したロボット数 は37枚では30体，これは頂点数96の約31%を占め，同様に61枚では150頂点で50体で あり，約33%である．これらはいずれも，61%以下であるため，前章のシミュレーションで組 立成功率100%が達成可能であることと矛盾しない．
図6.6 3組ケース1におけるロボットの移動
図6.7 ロボットの初期配置：4組