6.2.1 ロボット偏りによるデッドロック問題
前節では，二体一組の主従関係交換手法が，故障が発生しない前提において，全頂点数の約 61%まで組立を保障出来ることを明らかにした．しかし，大規模構造物組立問題においてはパ ネル保管所の周囲から1枚ずつパネルを展開するため，組立初期段階の頂点数とロボット数の 割合はこれを上回る場合がある．また，十分な枚数のパネルが展開された状態であっても，パ ネルを保管しているドック周辺の頂点は，パネルを補充するロボットで混雑することがあり，
外周部でもロボットが一時的に偏る場合がある．これは特にボトルネックの存在する構造物で は問題である．しかし，二体一組の主従関係交換手法では，ロボットが三つのパネル上に5組
図6.10 ボトルネック構造物におけるロボット偏りにより発生するデッドロック状態
上記の問題に対して，本研究では，ロボットが故障しない前提で，構造物上のロボットに偏 りがありロボットが集中する場合でも，ある地点から任意の地点に100%移動出来る手法を提 案し，理論及び実機実験により検証する．
6.2.2 移動マップと主従関係分離に基づくロボット移動
6.2.2.1 ロボット偏り有りの場合の一方通行化
前述のロボットが偏る状態について，本研究の組立モデルの定義では，ロボットはロボット が居ない頂点への移動のみ可能であるため，頂点がロボットで全て埋まっている場合は完全に 移動不可能である．したがって，本研究では，頂点が全て埋まった状態から1 体だけロボッ トを取り除いた状態で移動可能な手法を提案する．図6.11が1体だけ頂点が空いている例で あり，図中の六角形がパネル，白丸がロボットを表し，赤丸で示した頂点が空いている状態で ある．
図6.11 頂点1箇所以外がロボットで埋まっている状態
このような頂点が 1つだけ空いている状態で，空いた頂点に移動したロボットが直前の位
90 第6章 理論：主従関係交換手法の有効範囲とロボットの偏りに基づくデッドロック回避 置に戻る行動を取ると，同じ状態が無限に繰り返され，デッドロックを抜け出すことが出来な い．これに対し，本研究では，各頂点におけるロボットの移動を一方通行化し，戻る行動を禁 止することで，同じ状態の繰り返しを防ぐ手法を提案する．各頂点における移動方向の向き付 けについては，各ロボットが予め所持する構造物の完成図において向き付け決めておくこと で，ある頂点において全てのロボットが同じ行動をとれるようにする．本研究では，この向き 付けされた完成マップを移動マップと呼び，ロボットは移動マップと需要度マップを利用し移 動する．
実際にパネルを向き付ける前に，次節において構造物上の全ての辺を一方通行化した際に，
到達不可能な頂点が存在するかどうか議論する．
6.2.2.2 構造物の向き付け可能性
上記の移動マップは，全ての頂点におけるロボットの移動方向を指定することが出来た場合 に，ロボットが直前の位置に戻らないように出来る．しかしロボットが任意の位置にパネルを 組立るためには，ある頂点にいるロボットが，任意の頂点に移動できることを満たす必要が ある．
各辺を一方通行化した場合に，ある位置から任意の場所に到達出来るかどうかは，グラフ理 論により示される．本研究で大規模構造物の一例として取り扱っているSSPSは，パネルの頂 点をノード，辺をエッジと見なした場合，1つの無向グラフであると言える．このグラフは，
六角形のパネルがどれも孤立せずに接続しているため，どのような接続形状であっても任意の 頂点間に道が存在する連結グラフであり，各頂点は少なくとも 1つの閉路に含まれる．した がって，グラフ理論におけるロビンスの定理により，このグラフはいかなる場合でも向き付け 可能であり，全てのエッジを方向付けた場合に強連結有効グラフが得られる．以上から，構成 しているパネルの全ての辺を一方通行化した場合に，ある頂点Aから任意の頂点Bに移動す ることが可能であり，その逆もまた可能である．
6.2.2.3 回転パネルと非回転パネル
前節から，構造物の全ての頂点が少なくとも1つの閉路に含まれるように向き付けをするこ とで，任意の頂点に移動可能な移動マップを作成可能である．構造物組立を有向グラフとみな した場合の閉路とは，パネルの外周を時計回り，もしくは反時計周りに回るように向き付けを した場合である．構造物の各頂点はそれぞれ3つの辺が接続しているため，全てのパネルに時 計回り，または反時計回りの向き付けをすることは出来ない．
したがって本研究では，ロボットが所持する完成マップ上の各パネルを，時計回り，または 反時計回りの向き付けをした回転パネルと，向き付けをしない非回転パネルという二種類のパ ネルに分け，全ての頂点が少なくとも1つの回転パネルに含まれるように予めマップに配置す る．図6.12は完成マップをこれら二種類のパネルで分け，向き付けをした移動マップの一例 である．この図では，円形の矢印が付いた六角形が回転パネル，何も矢印がついていない六角
図6.12 回転パネルと非移動パネルに向き付けられたSSPS完成図
• 正回転パネルと逆回転パネルは隣接できる
• 正回転パネル同士，または逆回転パネル同士では隣接できない
• 非回転パネルは回転パネルに隣接できる
• 非回転パネル同士は隣接できない
以上のルールを用いると，図6.12のように正回転と逆回転のパネルが交互に繋がり，その 間に非回転パネルが入る形状が出来る．
この図をグラフとして見ると，回転パネルは有向グラフにおける閉路として見ることができ るため，回転パネル上のどの地点からも任意の地点に移動する道が存在する．ただし，移動 マップの端に存在する非回転パネルの上は向き付けされていないため，その上は移動出来ない が，完成後のSSPSにおいて端の非回転パネルの外にはパネルが存在しないため，移動する必 要はない．もし，追加でパネルを組み立てる必要があっても，この非回転パネルの隣には回転 パネルが接続されることで，非回転パネル上への移動が可能になるため，非回転パネル上を通 る必要は無い．
92 第6章 理論：主従関係交換手法の有効範囲とロボットの偏りに基づくデッドロック回避
6.2.2.4 ロボットの移動と主従関係の分離・結合
移動マップを元にした各ロボットのルールについては，以下のように定義する．
移動マップに基づく移動
本研究では，出次数が2である頂点を分岐地点，入次数2の頂点を合流地点と呼ぶ．各 ロボットは，現在いる頂点において，移動マップに記された移動方向にロボットが居な い場合にのみ移動する．この時，ロボットのある頂点から隣の頂点への移動を1ステッ プとする．移動マップに記された移動方向にロボットが居る場合は，そのロボットが次 の頂点に移るまでは移動せずに静止する．このとき，あるロボットが1ステップ移動す る間に静止しているロボットは1ステップ静止したとみなす．したがって，全てのロ ボットの速度が同一である場合の各ロボットのステップ数は同期し，例えば，あるロ ボットが3回移動する間，静止するロボットの静止ステップ数は3となる．
ロボットが分岐地点に居る場合は，隣接しているロボットが居なければ，隣接する2つ の頂点それぞれから目的地への最短経路をダイクストラ法で計算し，近い方を選択す る．もし片方の頂点のみにロボットがいる場合は，もう片方の頂点に移動し，両方にロ ボットが居る場合は静止する．
また，ロボットが合流地点へ移動する場合，その地点に移動しようとしているロボット
（その頂点に入る辺を挟んで隣接する頂点にいるロボット）が他に居なければ，その頂 点に移動する．その頂点に隣接しているロボットが同じ頂点に移動を予定している場合 は，次項目の待機時間を利用してどちらが移動するか決定する．二台のロボットの待機 時間が同じであれば，固有番号が小さい方が移動する．
ロボットの待機時間
各ロボットは，移動出来ずその場で静止している状態では，自らが静止している間のス テップ数を待機時間として計測する．ある頂点で静止していたロボットは隣接する頂点 に移動するときに自らの待機時間を0にする．待機時間は周辺の2頂点先のロボット まで通信によってやりとり出来るものとし，待機時間の初期値は無限大（待機時間を保 存する変数の取り得る最大値）とする．
合流地点への移動優先権
合流地点では，2台のロボットが移動する可能性があるため，そのままでは衝突が発生 する．これを回避するため，待機時間が長い方が優先的に合流地点に移動するルールを 設定する．これは，合流地点での衝突を回避するとともに，合流地点に交互にロボット を入れることで，合流地点を含む2枚の回転パネル両方のロボットを移動させるためで ある．ただし，比較が出来ない初期状態や，待ち時間が全く同じ場合には，固有番号が 小さいほうが移動する．