本論文は，自律システムを構成する核となるタスクプラニングを現実の問題に適用する際に最も重要となる課題の一つである「計算時間の扱い方」について，一つの統一的な方法論を提案するものである．

　与えられた目的を達成するための行動を計画するタスクプラニング技術について，現実に存在する問題を扱うことを目指して様々な研究が行われているが，大きく二つの方向性の研究に分類することができる．一つは，探索アルゴリズムのモデル化できる現象の範囲を拡大することによって，より現実的で複雑な問題を扱おうとする方向性の研究であり，不確定な状態遷移モデルの扱い方や可観測ではない問題への対応など，様々な研究がなされてきた．もう一つの方向性の研究が「プラニングに要する計算時間の扱い方」に関するものである．実環境ではプラニング中にも状況が時々刻々変化するため，オフラインで十分にプラニングしてから解を実行するということができず，計算時間の扱い方は実環境でプラニングする際に最も重要になってくる課題であると言える．しかし，時間が差し迫った状況でプラニングしなければならないような問題が現実には多数存在するにもかかわらず，そういった場合の計算時間の扱い方については，統一的に解決する方法が存在しないのが現状である．

　従来の研究における「プラニングに要する計算時間」の扱い方としては，「最適な解をなるべく速く計算するアルゴリズム」を開発し，十分無視できる程度に計算時間を短くしようとするものと，計算時間を無視できないことを前提として，プラニング中の状況の変化に対応するために解探索に割り当てる時間を制御するようなものがある．前者については，状況の変化に対応できるくらいの速さで計算ができれば実環境でのプラニングは確かに可能であるが，そのようなアプローチは計算時間の問題を根本的に解決するものではない．なぜなら，どれだけ速いアルゴリズムを開発しても，あるいは，どれだけ計算機の能力が将来的に向上したとしても，扱える問題の規模には必ず限界があり，計算時間の問題が完全に無視できるようになることは考えられないからである．その意味では後者のようなアプローチが有望だと考えられるが，探索時間の制御方法を恣意的に設計者が設定しているような研究や，個別の問題や個別の探索アルゴリズムについての探索時間制御方法を議論している研究が多い．計算時間の問題を適切に扱うためには，「置かれた状況がどのくらい時間が差し迫った状況なのかその場で判断し，あらかじめ決めておくのではない柔軟な方法で探索時間を制御する」という，人間が普段無意識に行っているような実時間問題解決方法を実現し，さらにその制御手法を問題依存ではなく広い範囲の問題に適用できる方法論として確立することが必要である．これが現実問題における実時間プラニングの本質であると考えられるが，このような計算時間の扱い方に関する統一的な方法論はこれまであまり研究されてこなかった．

　そこで本研究では，「状況に応じて柔軟に探索時間を制御することによって，なるべく良いプラニング結果を得ること」が実時間プラニングであると考え，そのために必要となる探索時間制御手法を，広範囲の問題に適用できる統一的な方法論として導出することを目的とする．

　本論文ではまず，探索に時間を費やすことのメリットとデメリットを定量的にトレードオフすることが探索時間制御に必要であるとして，効用関数という評価基準を定義した．ここで定義した効用関数は，「探索時間を費やして解を得て，その解をある状況ある時刻において実行した結果，どの程度プラニングの目標が達成されるか」というプラニングのサイクルのEnd-to-Endの評価基準であるが，このように定義することによって，任意の問題における探索時間のメリットとデメリットを汎用的かつ定量的に表現できる形式になっている．そして，置かれた状況に応じて常に効用という単一の評価基準を最大化する形で探索時間を制御するような汎用の枠組みを，探索後の効用関数の予測に基づいて探索を制御するメタ推論のアーキテクチャとして定式化した．ここで定式化したメタ推論アルゴリズムは，任意の問題での探索時間制御アルゴリズムについて常に成り立つ部分を汎用の枠組みとして定式化したものであり，その一部を個々の問題用にカスタマイズして実装することによって，任意の問題について同じ枠組みにのっとった実時間プラニングアルゴリズムが構築されることになる．

　本論文では次に，実際に個別の問題にこの汎用の枠組みを適用する際の方法論を導出した．個別の問題での実装の核となるのが，探索後に得られる効用を予測するモデルの構築であるが，予測モデル構築のためにはまず問題ごとに効用関数を分析し，いくつかの形式に分類することが必要であることを示した．そして，解の質という解自体の持つ静的な特徴を無次元量で表現した量がその問題において定義できるかどうかが効用の予測の仕方を大きく変える要因であることを示し，それぞれの分類ごとに効用予測モデル構築の手順を整理して示した．ここで示した手順は，実際に実時間プラニングアルゴリズムの設計者が行わなければならない手順であり，先に導出した汎用の枠組みと合せることにより，実時間プラニングシステムを構築するための統一的な方法論が与えられることになる．

　本論文の後半では，いくつかの具体的な問題に対して提案手法を適用することで，その有効性を確認した．最初に，列車選択という，人間が実生活で経験する実時間問題解決の例を取り上げ，提案手法を適用することで効用関数を最適化するように探索時間が制御されることを確認した．それと同時に，「これ以上探索することが有効かどうかを考えてその都度判断しながら探索する」という，人間が無意識に行っている思考の過程が提案手法によって上手く表現されることも示した．もう一つの具体的な問題として宇宙機の軌道計画問題を取り上げたが，これは，予定されている最適なタイミングでの軌道変更に失敗した後に早急に軌道を再計画しなければならないという状況を想定した問題であり，時間が差し迫った状況で的確に判断しなければならないプラニング問題の典型例である．この問題では，なるべく長時間の探索を行って最適に近い解を得たいという要求があるのに対して，軌道変更が最適なタイミングから遅れれば遅れるほど得られる軌道の最適性が悪化することも考慮に入れて上手く探索時間を制御しなければならず，さらに，状況の差し迫り方がプラナ側には読めないという難しい問題であるが，探索後に得られる効用をその時点までに見つかった解からオンラインで推定するという，人間のモデル化能力を模擬した統計的な手法によって効果的に探索時間を制御できることが確認された．

　以上の成果は，プラニングを実時間で行う際の計算時間の扱いについての一般的な枠組みを与えるものである．本枠組みは，これまではToy Problemと呼ばれる簡単な問題しか扱えなかったタスクプラニングを現実問題に適用する際の最も重要な課題である「計算時間の問題」を統一的に扱うことを可能にするものであり，「現実問題に適用可能なAI」を実現することに大きく貢献するものと考えられる．

　修士(工学)船瀬龍提出の論文は，「解探索の時間管理手法を導入した実時間タスクプラニングに関する研究」と題し，8章と附録からなっている．

　与えられた目的を達成するために必要となる行動を計画する「タスクプラニング」は，ロボット等の自律システムの実現の核となる技術であり，特に近年では，現実の問題に適用できる方法論を目指した様々な研究が行われている．現実問題を扱う上で最も重要な課題の一つが「プラニングに要する計算時間」を扱うという問題である．計算機資源が有限である現実の世界では，プラニングに要する探索時間は無視できず，プラニング中にも状況が時々刻々変化するため，オフラインで十分に計算してから得られた解を実行するという理想論はなりたたない．このような状況におけるプラニングでは，探索に時間をかけることのメリットとデメリットを定量的にトレードオフし，「探索時間を適切な量に制御しつつ，なるべく良い解を得る」という人間が通常無意識に行っている方法論が必要になる．これが実時間プラニングの本質的な要件であるにも関わらず，従来の実時間プラニング研究では，それを様々な問題について統一的に扱える枠組みが存在してこなかった．

　本論文では，これらの背景を踏まえ，実時間プラニングにおける探索時間制御手法に関して，広範囲の問題に適用可能な統一的な方法論を確立することを目的としている．そのために，探索に時間をかけることのメリットとデメリットを時間軸上でモデル化して適切にトレードオフする汎用的アルゴリズムを導出し，それをいくつかの具体的な問題に対して適用することによって，提案手法の有効性を検証している．

　第1章は序論であり，タスクプラニングに関する研究の現状や傾向について概観し，本論文における問題意識と目的を明確にしている．

　第2章では，実時間プラニングに関する従来の研究について整理し，本論文で提案する実時間プラニング手法の方向性を明らかにしている．具体的には，一つの評価基準を最適化するよう，状況に応じて探索時間を柔軟に制御する必要があること，その探索時間制御手法を多様な問題に適用できる汎用的な形にすることが重要であることを述べている．

　第3章では，前章での考察を踏まえ，任意の問題に適用可能な探索時間制御の枠組みを定式化している．まず，探索時間を制御する際に用いる評価基準として「解の効用関数」を定義しているが，これは，探索を行うことによって得られる解を最終的に実行した結果の良さを探索の間の周辺状況の変化も含めて統合的に予測評価するものであり，探索時間を費やすことのメリットとデメリットを定量的に表現できる汎用的な形式になっている．さらに，多様な状況下においても常に効用関数という単一の評価基準を最大化する形で探索時間を制御できる汎用の枠組みとして，探索後の効用関数の予測に基づいて探索を制御するメタ推論のアーキテクチャを提案している．

　第4章では，第3章で提案した汎用の枠組みを個別の問題に適用する際の方法論を示している．具体的には，効用関数が問題によって複数の形式に分類されることを示し，それぞれの分類に関して，探索後の効用を予測するモデルを構築する手順を整理している．さらに，実際にプラニング・システムの設計者が行わなければならない作業とその手順が整理された形で提示されており，第3章で示した汎用の枠組みと合せて，実時間プラニング・システムを構築するための統一的な方法論を与えている．

　第5章と第6章では，提案手法を現実の実時間プラニング問題に適用することによって，その有効性を確認している．第5章では，人間が実生活で経験する列車選択という実時間意思決定問題の例を取り上げており，提案手法により最適に探索時間を制御できることを示すと同時に，時間が差し迫った状況において準最適な結果を得るために人間が無意識に行っているであろう思考過程が，本提案手法によって効果的に実現されていることも示されている．

　第6章は，宇宙機の軌道計画問題を取り上げている．予定されている最適なタイミングでの軌道変更に失敗した後，早急に軌道を再計画しなければならないという状況を想定した問題であり，状況の緊迫度がプラニング・システム側には読めないという難しい問題であるが，探索後に得られる効用をその時点までに見つかった解からオンラインで推定する手法でうまく探索時間を制御できることが示されている．両章ともに，従来研究の手法では扱うことのできない実時間プラニング問題を扱っており，本提案手法の有効性を示すものである．

　第7章では，第3章と第4章で提案した手法および第5章と第6章での具体的な問題への適用結果をもとに総合的に議論し，本研究の特徴や有効性について明らかにしている．

　第8章は結論であり，本論文で得られた知見をまとめ，今後の課題と展望を述べている．

　附録では，第6章で用いた，探索によって得られる効用の確率分布をオンライン推定する方法についてより詳細に説明している．

　以上要するに，本論文は，現実世界では無視できないプラニングのための探索時間を陽に扱い，それを適切な量に制御しつつなるべく良い解を得るという実時間プラニングを目指して統一的な枠組みを提案し，その有効性を複数の現実的問題への適用を通して検証したものであり，宇宙工学，知能工学上貢献するところが大きい．

　よって，本論文は博士(工学)の学位請求論文として合格と認められる．