階層型タスクネットワーク

人工知能において、階層型タスク ネットワーク (HTN) 計画は、アクション間の依存関係を階層構造のネットワークの形式で指定できる 自動計画のアプローチです。

階層型タスク ネットワーク アプローチでは、次のような一連のタスクを提供することで、計画問題が指定されます。

1. プリミティブ（初期状態）タスク。これはSTRIPSのアクションにほぼ相当します。
2. 複合タスク（中間状態）。これは、一連のより単純なタスクで構成されていると考えられます。
3. 目標タスク（目標状態）は、 STRIPSの目標にほぼ対応しますが、より一般的です。

HTN 問題の解決策は、複合タスクをより単純なタスクのセットに分解し、順序付け制約を挿入することによって、初期タスク ネットワークから取得できる実行可能な基本タスクのシーケンスです。

プリミティブ タスクは、実行時の状態が前提条件をサポートしている場合、直接実行できるアクションです。複合タスクは、プリミティブまたは抽象のいずれかである、部分的に順序付けられた一連の追加タスクで構成される複雑なタスクです。目標タスクは、条件を満たすタスクです。プリミティブ タスクと他のタスクの違いは、プリミティブ アクションは直接実行できることです。複合タスクと目標タスクはどちらも、プリミティブ アクションのシーケンスを実行する必要があります。ただし、目標タスクは、真にする必要がある条件に関して指定されますが、複合タスクは、以下に概説するタスク ネットワークを介して他のタスクに関してのみ指定できます。

タスク間の制約は、(階層的) タスク ネットワークと呼ばれるネットワークの形式で表現されます。タスク ネットワークは、タスクとそれらの間の制約のセットです。このようなネットワークは、別の複合タスクまたは目標タスクが実行可能であるための前提条件として使用できます。このように、他のアクションのセット (ネットワークで指定されているもの) が実行され、それらのアクション間の制約 (ネットワークで指定) が満たされる方法で実行される場合にのみ、特定のタスクが実行可能であることを表現できます。階層的タスク ネットワークを表すための形式としてかなり広く使用されているのが、TAEMSです。

最もよく知られているドメインに依存しない HTN 計画システムには次のようなものがあります。

• NOAH、行動階層のネットワーク。^[1]
• Nonlinは最初のHTN計画システムの1つです。^[2]
• SIPE-2 ^[3]
• Oプラン、オープンプランニングアーキテクチャ^[4]
• UMCPは、おそらく最初の健全で完全なHTN計画システムです。^[5]
• IX/Iプラン^[6]
• SHOP2はメリーランド大学カレッジパーク校で開発されたHTNプランナーです。^[7]
• PANDAはドイツのウルム大学で開発されたHTN計画の拡張であるハイブリッド計画用に設計されたシステムである。^[8]
• HTNPlan-P、好みに基づいたHTN計画。^[9]

HTN プランニングはSTRIPSよりも表現力がはるかに豊かであり、一般的な場合には決定不可能である。^{[10]しかし、 HTN プランニングの多くの構文上の制約は決定可能であり、その複雑さは}NP 完全から2-EXPSPACE 完全までの 範囲であることが知られている。 ^[11]また、一部の HTN 問題はSTRIPS のような言語であるPDDLに効率的にコンパイルできる。 ^[12]

• ストリップ
• 階層制御システム- HTN計画に適したフィードバック制御システム