本論文では，確率的探索手法に基づいた，マルチエージェント環境のための経路プランニングアルゴリズムを提案する．近年，数多くのロボットが開発され，産業界や生活の場などに普及すると期待されている．その際，ロボットを複数台で協調動作させて，複雑なタスクを効率的に行うことが期待される．しかし複数のロボットをタスクに応じて適切に制御することは難しい問題である．この問題を解決するには，複数ロボットのための経路プランニングアルゴリズムが必要である．しかし複数ロボットを扱うには計算量が多く，協調作業を実現する実用的なアルゴリズムはほとんどなかった．提案アルゴリズムはマルチエージェント環境でも効率的にプランを探索することができる．そして，提案アルゴリズムは様々なタスクに応用可能であることを2つの実例を通じて示す．その1つ目は物体再配置問題である．この問題はこれまでいくつかのアルゴリズムが示されていたが，マルチエージェント環境では計算量が多く問題であった．提案手法を用いることで，マルチエージェント環境での物体再配置問題を解くことができる．2つ目の例は協調荷物搬送問題である．これはロボットが荷物を受け渡しながら作業を行うため，荷物を受け渡す場所(サブゴール)が必要となるが，提案手法を応用することで，サブゴールを自動的に探索することができる．その上，環境モデルだけを使って，どのような順序で受け渡しをすればよいかを探索できる．さらに，ヒューマノイドロボットを用いて実環境での適用可能性を確認する．単純に適用するだけではシミュレーション環境と実環境のずれが大きいため失敗することが多い．そのため，再プランニング手法を提案する．これを用いることで，実環境で生じたずれに応じてプランを修正できることを示す．

　第2章では，対象とする問題領域について述べ，提案アルゴリズムについて述べる．このアルゴリズムは，最終時刻を必要としない経路プランニングやロボット同士の衝突を回避する経路生成を実現するアルゴリズムである．提案アルゴリズムではロボットごとに経路プランニングを行なう．多数のロボットが存在する中での協調作業には，タスクを割り当てられたロボットとタスクを割り当てられていないロボットが存在しうる．タスクを割り当てられたロボットには目的位置までの経路をプランニングすればよいが，タスクを割り当てられておらず目的位置の定まっていないロボットにもほかのロボットを邪魔しないような経路を生成する必要がある．提案アルゴリズムはこのようなプランニングも扱う．

　第3章では，マルチエージェント環境における物体再配置問題への適用を示す．物体の再配置問題とは，1つ以上の物体を初期状態からそれぞれのゴール位置まで移動するためのロボットの行動系列を得る問題である．本研究では複数のロボットが存在しうる環境を考える．マルチエージェント物体再配置問題の例を図1に示した．提案アルゴリズムはロボットのゴール状態が指定されなくとも解くことができる．マルチエージェント環境では，複数のロボットが同時に行動するために問題の複雑さが増大する．この困難さを解決するには特にロボット1台あたりの行動プランニングの計算量が問題となる．提案手法を用いることで行動プランニングのための計算量を抑えられるため本タスクに有効である．シミュレーション実験を行い，マルチエージェント環境での物体再配置問題を効率的に解くことができた．本章で示したアルゴリズムによって，全体のタスク実行時間を減らすようにロボットの並行作業を実現した．また，ロボットを増やすことで再配置問題がより効率的に解けることを示した．比較実験を行い，従来手法であるダイナミックプログラミング手法(DP)と比較した．その結果，DP手法は提案手法より粗い精度でのプランニングでも，より長い計算時間がかかった．提案手法のほうがより短い時間で比較的短いプランが安定的に得られる点で有利な手法と言える．

　第4章では提案手法の協調荷物搬送問題への適用を示す．複数ロボットによる協調作業のために，ロボットごとのゴールやサブゴールをあらかじめ決定することは難しい問題であり，ロボットの操作者にも負担である．本章では，最終的なゴールを達成するために必要となるサブゴールを比較的少ない情報から自動的に生成する手法を示す．それには，第2章で提案した経路プランニングアルゴリズムを適用する．本章で対象とした問題は，三体のヒューマノイドロボットが協力して荷物をスタート位置からゴール位置まで受け渡ししながら運搬するタスクである．本タスクでは同時に二体のロボットが協調して荷物を受渡しするものとする．荷物の受渡しのためには，二体のロボットが協調して，互いに荷物の受渡しが可能な位置まで近付く必要がある．本タスクでは以下のものが既知であるとした．(1)環境とロボットの3次元モデル，(2)荷物の最終ゴール位置，そして(3)荷物受け渡しの手順である．このタスクでは，ロボットはそれぞれ壁で区切られた別々の部屋にいる．環境は例えば図2のようなものである．ロボットは壁を越えられないが，壁が低くなっているところではロボット同士が荷物を受渡し可能である．荷物の最終的なゴール位置は与えられるが，各ロボットのゴール位置は与えられないものとした．従来の経路プランニングでは無駄な動きが生じるほか，環境が複雑になるほど計算時間が長くなる．提案手法では従来手法と異なりサブゴールを自動的に生成するため，必要とする情報が少なく扱いやすい．シミュレーション実験を行ない，提案手法は複雑な環境で従来手法よりも速く探索が行えることを示した．また，経路が複数ありうる環境では短い経路が生成されることが多く，プランニングアルゴリズムとして望ましい性質を持つことも確認した．

　第5章では協調荷物搬送問題での協調手順の探索を実現するアルゴリズムを示す．前章でのアルゴリズムでは，入力として協調手順(荷物の受け渡し順序)が与えられると仮定した．ロボットの操作者にとって，この受け渡し順序を指定することは煩雑である．そこで，本章では環境のモデルを用いて受け渡し順序を自動的に探索するアルゴリズムを実現する．さらにロボットが他のロボットに荷物を受け渡し可能かどうかを自動的に探索するアルゴリズムも示す．これらのアルゴリズムは提案する経路プランニングアルゴリズムと組み合わされているため，より少ない情報でロボットを操作できるようになる．シミュレーション実験を行い，作業にかかわるロボット数が最小となる経路を見つけることを確認した．

　第6章ではヒューマノイドロボットによる協調荷物搬送の実現を示す．本章では，前章までの提案アルゴリズムを用いてヒューマノイドロボットで協調荷物搬送作業を実現する．実環境ではロボットの足裏と床との摩擦やロボット動作のぶれなどによるずれが生じる．そのため単純な環境であってもプランニングされた経路をそのまま実行するだけではタスクが達成できないことが多い．この問題を克服するため，ロボットは環境を認識しながらずれに応じて経路を調整しつつタスクを実行しなければならない．これには現在の状態を認識して必要に応じて再プランニングを行う必要がある．本章で提案する再プランニング手法は以下の手順である．

　1. 初期位置からのプランニングを行い，経路を生成する．

　2. 経路のスムース化を行う．

　3. 経路に沿った行動を決定する．

　4. 行動を実行する．

　5. ロボットの位置が予定した経路から大きくずれた場合，現在位置をもとにプランニングをやり直す．

　6. ステップ2. から繰り返す．

　実験では障害物のある環境で2台のヒューマノイドロボットを用いて行った(図3)．それぞれサブゴールに向かって行動し，一方からもう一方へと荷物を受け渡すところまでを行った．この手法を実現する上で難しい点はステップ5.でロボットの現在位置を得ることである．このヒューマノイドロボットは頭部に回転可能なカメラを備えており，環境の情報を能動的に得られる．位置同定手法にはMonte Carlo Localizationを用い，環境中に配置した色つきマーカーをランドマークとして用いた．実験を行い，再プランニングにより環境との衝突を回避する適切な経路が生成でき，ロボットの荷物受け渡しが実現できることを確認した．

図1 マルチエージェント物体再配置問題の例

図2 協調荷物搬送問題で得られた経路の例

図3 ヒューマノイドロボットでの実験環境

　本論文はマルチエージェント協調作業のための経路プランニングに関する研究と題し，7章からなり，複数ロボットのための効率的な経路プランニングアルゴリズムを提案し，シミュレーション結果とヒューマノイドロボットによる実験結果に基づき提案手法の有用性を検証している．

　第1章は序論であり，主題と経路プランニングについて述べられている．また本論文に関係する従来手法の持つ問題点についても議論されている．

　第2章では，対象とする問題領域について述べられ，提案アルゴリズムが説明されている．提案アルゴリズムは，複数ロボット環境下での効率的な経路プランニングを中心とした複数のアルゴリズムからなる．多数のロボットが存在する中での協調作業には，タスクを割り当てられたロボットとタスクを割り当てられないロボットが存在しうる．このタスク割り当ての有無それぞれの場合に適した経路プランニングアルゴリズムを提案している．また，2台のロボットで協調するためのサブゴールを探索するアルゴリズムも示される．

　第3章では，マルチエージェント環境における物体再配置問題への適用が示される．物体の再配置問題とは，複数の物体をそれぞれのゴール位置まで移動するようなロボットの行動系列を得る問題である．この問題では複数のロボットが同時に行動するために計算量が非常に多い．シミュレーション実験が行われ，提案手法を用いることで経路プランニングの計算量を抑えられることが示されている．さらに，ロボットを増やすことで全体のタスク実行時間を短縮するようなロボットの平行作業が得られている．従来手法であるダイナミックプログラミング手法との比較も行われる．その結果，従来手法と同程度の経路が，提案手法ではより短時間で安定的に得られている．

　第4章では提案手法が協調荷物搬送問題へ適用される．対象とした問題は，複数のロボットが協力して，荷物を受け渡しながらゴール位置まで運搬するタスクである．従来の経路プランニングではサブゴールの情報を必要とする上に，ロボットに無駄な動きが生じる．提案手法では従来手法と異なりサブゴールを自動的に生成するため，必要とする情報が少なく扱いやすい．シミュレーション実験を行ない，複雑な環境では提案手法のほうが従来手法よりも探索が速いことが示されている．また，経路が複数ありうる環境では短い経路が生成されることが多く，プランニングアルゴリズムとして望ましい性質を持つことも確認されている．

　第5章では前章で扱ったタスクの荷物受け渡し手順を探索するアルゴリズムが示される．このアルゴリズムは，ロボットと環境のモデルを利用して受け渡し順序を探索する．また，本章のアルゴリズムには提案する経路プランニングが組み合わされているため，より少ない情報でロボットを操作できるようになる．シミュレーション実験を行い，提案手法で適切な受け渡し手順を得られることが確認されている．

　第6章では，提案アルゴリズムの実環境への応用として，ヒューマノイドロボットによる協調荷物搬送が示される．実環境ではロボットの足裏と床との摩擦やロボット動作のぶれなどによる「ずれ」が生じる．そのため単純な環境であってもプランニングされた経路をそのまま実行するだけではタスクが達成できないことが多い．この問題を克服するため，ロボットの位置が予定した経路から大きくずれた場合に経路を生成しなおすという再プランニング手法が述べられる．さらに，これを実現する制御システムが示される．実験では障害物のある環境で二台のヒューマノイドロボットを用いて荷物を運搬し受け渡す作業が扱われる．ヒューマノイドロボットは頭部の回転可能なカメラから環境の情報を能動的に得る．環境内に配置した色つきマーカーをランドマークとして用い，Monte Carlo Localization手法による位置同定が行われている．実験において，再プランニングにより環境との衝突を回避する適切な経路が生成でき，ロボットによる協調荷物搬送作業が実現されている．

　第7章においては，本論文のまとめと今後の展望が述べられている．

　以上これを要するに本論文は，複数ロボットによる協調作業のための経路プランニングを効率的に行うアルゴリズムを提案し，そのアルゴリズムを複数の問題に適用して有用性を実験的に実証するとともに，実環境における制御システムへの適用可能性を検証しており，情報学の基盤の発展に貢献するところが少なくない．

　したがって，博士(科学)の学位を授与できると認める．