前節で分類したデッドロック問題は，前述の通り，大規模構造物組立において，ロボットが (i)パネルのフレーム上のみしか移動出来ない, (ii)荷物受け渡しは出来ない, (iii)局所通信の みを利用する, という三つの制限から発生している．このような問題に，これまでに提案され ている従来のロボットによるデッドロック回避手法を適用することは困難である．以下にそれ らの従来手法の詳細を述べる．
16 第2章 大規模構造物組立とデッドロック問題
2.4.1 ロボットにおけるデッドロック回避
大規模構造物組立においては，ロボットは(i)移動制限, (ii)機能制限, (iii)通信制限の3つ の制限があり，組立においてロボットを多数利用し，組立る地点の自然環境による影響を受け るため，個体差や故障が生じるという問題もある．従来のロボット間におけるデッドロック回 避手法については，様々なものが提案されているが，これら全てを考慮したものは現在の所例 を見ない．
具体的には，(i) の移動に制限がある環境でのデッドロック及び衝突回避については, [Duhant, 2007]の複数移動ロボットにおけるデッドロック回避手法や, [新井 ほか, 2001]の複 数自律ロボット協調などの先行研究があるが, これらはロボットが故障して停止しない環境を 前提としており，[Yuta, et al., 1991]ではロボット間で把持する物体のバケツリレーをする 手法を利用しているが，これは(ii)の制限に反する．また，[Gupta, et al., 1998]では予期し ない故障を含む不確定環境での衝突回避を扱っているが, これは移動に制限がなく, すれ違い が十分に出来る環境での検証であり，(i)を満たさない．また，予期しない故障を含む環境で
は, (iii)を満たし局所情報を利用するロボットは他のロボットの状況を知ることが出来ないた
め, 予め移動経路を決めておくことは出来ず, 広域な視点でデッドロックを回避することは出 来ない. この観点から, [Latombe, 1991] のような予め移動経路計画をする手法は利用できな い. また, 経路探索という観点からメタヒューリスティック手法の一つであるタブー探索法 [Glover, et al., 1997] の利用も考えられるが, 大規模構造物組立では, 組立や故障により常に ネットワークの形状は変化しているため，タブーとした道が次の瞬間には通れるようになる場 合もあり，適用は難しい. これら3つの制限を全て考慮した手法に我々が[Otani, et al., 2008]
において提案した二体一組のロボットの主従関係に基づく組立手法があるが，この手法はロ ボットの個体差や故障など動的環境下に対する解析が十分でない．
また，大規模構造物上で発生するデッドロックにおいては，ロボットが偏る場合に2.2.3.2 節で示した閉塞デッドロックが発生し，回避が非常に困難になる問題がある．我々の提案手法 もこの問題により組立出来なくなることが明らかとなっている．ロボットが偏る場合のデッド ロック回避手法としては，[星野 ほか，2011]で提案されている移動ロボットの適応的走行制 御が先行研究として挙げられる．この手法は移動経路の交差点にロボットが停滞するのを防ぐ 方法だが，故障などによるロボットの停止を考慮していないため，大規模構造物組立問題に適 用することは出来ない．
2.4.2 情報的なデッドロック回避
デッドロック回避においては，前項のように物理的なロボット以外にも，パケットルーティ ングのように情報的なデッドロックを扱う場合がある．
ケットとして送り出すため，送信元となるノードがパケットの送出を要求した際に経路を形成 する送信元始動型ルーティングプロトコルの一種でもある．
しかしながら，本研究で扱う大規模構造物組立問題は，通常のアドホックネットワーク問題 と異なり，送信するパケットが電子情報ではなく，物理的な筐体を持つロボットであることか ら，以下の相違点がある．まず，(i)ロボットはそれ自身がルータでありパケットとみなされ るため，一つのルータで複数のパケットを保持可能なDSRと違い，一つのルータにパケット は一つしか保持することが出来ず，(ii)ロボット自身がパケットであるため，パケットを分割 しての送出も出来ない．また，(ii)通常のネットワークではパケットが溢れた際に，パケット を破棄したのちタイムアウトを検知し，パケットを再送することが出来るが，ロボットを破棄 して再送することも出来ない．
上記の相違点により，パケットは一つしか保持出来ず，ロボット廃棄もできないため，すれ 違うためにはどちらかのノードを空ける必要があり，通常のルーティング問題では前提とされ ていないパケット(=ロボット) が移動できないデッドロック問題が発生し，本質的に大規模 構造物組立問題とネットワークルーティングは異なる問題であると言える．
2.4.3 本研究の位置付け
上記の通り，移動，機能，通信の3つの制限を全て考慮したデッドロック回避手法は，我々 が提案した二体一組の主従関係交換手法以外にはないが，この手法はロボットの個体差や故障 など動的環境下に対する解析が十分でなく，また，構造物上のロボットが偏る場合にデッド ロックが回避出来ない問題がある．更には，どの程度のロボット割合まで提案手法が有効であ るかという議論がなされていない．したがって，本研究では，[Otani, et al., 2008]で提案した 二体一組の主従関係交換手法の近実環境下への有効性を検証し，提案手法が有効となるロボッ ト割合を明らかにする．また，ロボットが偏る場合においても組立が可能な手法を提案し，検 証する．
第1章とこの章で紹介してきた従来手法を，ロボットの制限，実環境要素，及びロボットの 偏りという観点で分類したものを表 2.1に，その詳細についてまとめたものを表 2.2に示す．
表2.1のように，移動・機能・通信制限を満たし，かつ近実環境要素とロボットの偏りを両方
18 第2章 大規模構造物組立とデッドロック問題 検証した例はないため，本研究はこの部分に着目する．
表2.1 本研究の位置付け
理想環境 近実環境（個体差・故障）
移動・機能・通信制限無 ロボット偏り無し [Yamada, 2011]
[新井 ほか, 2001]
[山下 ほか，2002]
[Terada et al., 2008]
ロボット偏り有り [Duhant, 2007]
[Jian, et al, 2010]
[星野 ほか，2011]
[小泉 ほか，2010]
移動・機能・通信制限有 本研究
表2.2 従来手法と本研究の要素比較
手法 移動制限 機能制限 通信制限 故障・個体差 ロボット偏り考慮 [新井 ほか, 2001] X O X O X
[Yamada, 2011] X O O X X
[山下 ほか，2002] X X X O X
[Duhant, 2007] X O O X X
[Jian, et al, 2010] O O O O X
[小泉 ほか，2010] O O X O X
[星野 ほか，2011] O O O X O
本研究 O O O O O
2.4.4 本研究のアプローチ
本論文では，ロボットに移動・機能・通信制限がある環境下において，シミュレーション・
理論・実験という観点のもと，及び，理想環境と近実環境での比較という観点に着目し，表2.3 のように課題を分ける．具体的には，第5章では提案手法の大規模構造物組立における構造物 の形状や規模，個体差，故障といった，複雑化する現象を理論では取り扱うことが困難であり，
実際に実機のロボットを大量に用意し故障させることが不可能な問題に対して，シミュレー ションにより検証をする．そして，第6章前半では，提案手法の限界点や有効範囲を明らかに するため，理想的な環境下を前提として提案手法の理論化をする．最後に，第6章後半では，
最小限の実機のロボットを用いて，故障以外でロボット間に個体差があり，実際にロボット間
21
第 3 章
宇宙太陽発電衛星
この章では，本研究で取り扱う，宇宙太陽発電衛星の組み立てを説明する．この問題は，ロ ボットが(i)パネルのフレーム上のみしか移動出来ない, (ii)荷物受け渡しは出来ない, (iii)局 所通信のみを利用する, という大規模構造物組み立て問題における3つの制限を強いられる上 に，宇宙という過酷な環境下での組み立てであり，組み立てロボットには太陽の熱や宇宙線の 影響によって個体差の拡大や，故障が発生するなど，組み立てへの影響が懸念される．
本研究では，大規模構造物組み立てにおける最も困難な一例として宇宙太陽発電衛星を取り 扱い，その環境下で提案手法の有効性を示すことで，提案手法の大規模構造物組み立てへの適 用可能性を議論する．