複数移動ロボットによる大規模構造物組み立てにおけるデッドロック回避手法として,
[Okawa et al., 2008]では単体ロボットでのデッドロック回避を提案しているが, この手法は
それぞれのロボットが独立して移動するため, パネルを展開したロボットが接続のために他の ロボットの隣接を待つ必要があり，組み立て効率が悪い. これに対し，我々は主従関係に基づ く二体一組のロボットによるデッドロック回避手法を提案し, その有効性をシミュレーション 上で検証してきた[Otani, et al., 2008]. 以下その手法について説明する.
4.1.1 提案手法におけるロボットの前提
まず，提案手法におけるロボットの前提について述べる．ロボットは完成済みのパネルの辺 上のみを移動可能であり，辺上で他のロボットと位置を交換することは出来ない．これは，フ レームではなくレール上を移動するロボットも想定してのことである．また，パネルの頂点同 士が接続することから，1つの頂点には1体のロボットのみが存在出来るものとする．また，
全てのロボットは固有の番号を持ち，2頂点先までのロボットとの通信可能であるとする．ロ ボットがある頂点に移動する際には，周囲2頂点先のロボットに自らの移動を周知し，衝突 の発生を防ぐ．同時に移動を開始した場合は，固有番号が小さいロボットが優先し，固有番号 の大きい方は移動を停止する．図4.1はロボットの通信可能範囲を表す．この図では，灰色の 丸，青丸，赤丸はそれぞれロボットを表しており，灰色のロボットの通信可能範囲が円で表さ れており，最大2頂点先のロボットと通信可能である．これは，文献[吉田 ほか，1998]に基 づいて，同時通信を維持可能なロボット数は約5〜10体であるという前提から，2頂点先まで の最大9体のロボットと通信出来る範囲を示している．灰色のロボットは赤色のロボットと
32 第4章 主従関係に基づく二体一組ロボットによる構造物組み立て手法
図4.1 ロボットの通信可能範囲
は通信出来ないが，青色のロボットとは通信可能であり，点線で囲った灰色ロボットと青色ロ ボットの間の頂点に移動する場合はこれら2体間で通信し，衝突を避ける．
ロボットは1 体につき1つのパネルを所持し，2台のロボットが隣接した 2頂点に居る場 合にその辺にパネルを展開し，接続する．パネルの展開と接続は別の行動であり，パネルを展 開した後に接続が可能である．パネルの展開が完了すると，所持するパネルがなくなり，パネ ル保管所の頂点上に移動するとパネルが補給される．パネル保管所にパネルが無くなると，ロ ボットはそのままパネル保管所内に戻る．各ロボットはパネルの展開場所を示した構造物の設 計図を持ち，保管所の全てのパネルがこの設計図通り展開され，全てのロボットが保管所に 戻った時点で組立が完了したとみなす．デッドロックの発生により，組立が一定時間内に完了 しなければ，組立失敗とみなす．
4.1.2 リーダーとフォロワ
単体行動するロボットを用いる場合，3.2.2章で述べたように，展開したパネルの二頂点は 同時に接続する必要性から，パネルを展開する地点において，(i)パネルを展開したロボット は二体目のロボットが隣接頂点に来るまで把持し続けるか，(ii)二体目のロボットが隣接頂点 に到達するまで待機する必要がある．ロボットは1つの頂点を専有するため，ロボット待機中 の頂点は移動不可能になり，効率の低下だけでなくデッドロック状態も発生する．
この問題に対する直接的な解決は，最低二台のロボットによるチームを形成し，常に一緒 に行動させることである．マルチロボットの自律分散制御においては，数台のロボットに チームを組ませ，チームの統括をリーダーとなるロボットを選出する例が多い．例えば，文
献[Smith, 2009] では，環複内に存在する複数の対象地点に複数のロボットを配置する問題
において，通信可能範囲内でロボットチームを形成し，その中で選出したリーダー同士が通
するまでにデッドロック状態に陥ると移動が出来ない．また，文献[Garrido, et al., 2013]の 手法では，他ロボットを移動障害物とみなしたとしても，全てのロボットの情報を即時に得ら れない上，ロボットは2頂点先までしか見れないため，ロボットを避けるように移動すること は困難である．
このように，大規模構造物組立において二台のチームに基づいてデッドロックを回避する場 合，デッドロック状態に陥る前に避けるという方法は適用困難であり，デッドロックに陥った 状況からの脱出が可能な手法が求められる．これに対し，我々は二体一組ロボットの主従関係 交換に基づくデッドロック回避手法を提案した[Otani, et al., 2008]．この手法では，ロボッ トが二体一組で行動することでパネル展開直後にロボットの待機無しでパネルの接続が出来る だけでなく，[谷口 ほか, 2007]に基づき，二台のロボットにそれぞれリーダとフォロワという 役割を持つ一組のチームとなって行動させ，その主従を交換することでデッドロック状態から の回避を実現する．更に，二体が常に一緒に行動するため，常時相互の状態を把握可能であり 故障の診断が出来るという利点もある．
ロボットはパネル保管庫の頂点に1 体ずつ出現し，隣接した頂点に単体のロボットがいる 場合は二体一組のチームとなる．この際，固有番号の小さい方がリーダーとなり，固有番号の 大きい方がフォロワとなる．このチームの意思決定は全てリーダーが統括し，フォロワはリー ダーの全ての指示に従う．但し，リーダーの移動速度がフォロワよりも速い場合，リーダーは フォロワが追従可能なように移動速度をフォロワに合わせて移動する．
4.1.3 ロボットの移動ルール
前章で定義した構造物組立モデルにおいて，ロボットは2頂点先までの情報しか利用できな いため，ロボットの移動を先読みすることが出来ず，2頂点先まで来てから回避行動を取らな ければならない．これに対し，提案手法においては，リーダーが後述する目的地設定方法に基 づいて1つのパネルを目的地として設定し，パネルを展開可能な状態になるまで，予めロボッ トに設定されたシンプルなルールにしたがって移動する．図4.2から図4.5はロボットの移動 ルールを表したものである．図中のそれぞれの二本線の付いた円形はロボットを，六角形はパ ネルを表し，同色のロボットが同じ組であり色が塗られたものがリーダーである．色の付いた
34 第4章 主従関係に基づく二体一組ロボットによる構造物組み立て手法 パネルは同色のロボットの目的地である．矢印はロボットの移動方向を示している．以下にそ れぞれの図に対応するルールを説明する．
ルール1：目的地との距離に基づく頂点選択
ロボットは目的地と直線距離で最も近い頂点を選択する．同一距離の場合はロボット から見て右側の頂点を選択する．図4.2左においては，青色ロボットチームの目的地は 右下にあるため，リーダーは目的地から最も近い頂点として破線で囲った頂点を選択 する．図4.2右では，リーダーの左右両方の頂点はどちらも目的地から等距離であるた め，右側の頂点を選択する．
ルール2：選択頂点にロボットが居る場合
ルール1で選択した頂点上に既にロボットが居る場合はロボットが居ない頂点を選択す る．図4.3に示すように，青色ロボットがルール1で選択した頂点に既に赤色のロボッ トがいる場合，青色ロボットは空いている頂点に移動する．
ルール3：同一頂点への移動の回避
ルール1で選択した頂点に移動しようとしているロボットがいる場合は固有番号の小さ い方が優先して移動する．図4.4は，青色ロボットと赤色ロボットの両方が同じ頂点を 移動場所として選択した場合である．この場合は，双方のロボット間の通信により固有 番号をやりとりし，番号が小さい方（この図では番号2のロボット）が移動する．
ルール4：目的地パネル上での移動
目的地パネルの上の頂点に到着している場合は，目的地パネル上を反時計回り方向に移 動する．図4.5は青色ロボットが既に目的地である青いパネルの頂点に到達した状態で ある．ロボットはルール4にしたがって，反時計回り方向に移動し，組立可能な地点を 探す．
4.1.4 需要度マップ
文献[Otani, et al., 2008]では，文献 [Terada et al., 2008]のポテンシャルマップを元にし た需要度マップを用いてロボットの目的地を設定する．ポテンシャルマップとは，隣接ノード 間の局所通信で作られたネットワーク全体を推定するマップであり，ネットワーク規模の増大 に対しスケーラビリティが高く，文献 [小南 ほか，2011][落合，2009][Sangsu, et al.，2009]
に代表されるようなネットワークルーティング問題で多く利用される概念である．
4.1.4.1 完成マップと需要度マップ
各ロボット及びパネルは図4.6左，及び図4.6右のような完成マップと，需要度マップを持 つ．前者は SSPSの完成図を表しており，後者はSSPSのどの部分が最も組み立てが必要か を表す．本研究では完成マップの全てのパネルが展開された時点で組立が完了する．需要度と