階層的タスクネットワークプランニング

階層的タスクネットワーク (HTN) プランニングは、目標状態に到達するためにプリミティブなアクションを直接探索するのではなく、メソッドのライブラリを使用して高レベルのタスクをサブタスクに再帰的に分解することで問題を解決します。

Definition

HTNプランニングは、実行すべきタスクの初期ネットワークと、複合タスクをサブタスクに分解するための一連のメソッドとして問題を表現します。解決策は、メソッドの制約を尊重するプリミティブで実行可能なアクションへの分解です。

Scope

このトピックでは、HTNプランニングパラダイムについて説明します。タスク（プリミティブおよび複合）、複合タスクをサブタスクに分解する方法を指定するメソッド、および実行可能なプリミティブアクションのみが残るまで初期タスクネットワークを洗練するプランニングプロセスです。古典的なプランニングと比較したHTNプランニングの表現力と複雑さ、および注目すべきHTNプランナーについても扱います。古典的な目標状態ベースのプランニングモデルは関連トピックで扱われており、HTNプランニングは代わりに手続き的なドメイン知識をエンコードします。

Core questions

• メソッドは、複合タスクを達成する方法に関するドメイン知識をどのようにエンコードしますか？
• タスク分解は、古典的なプランニングにおける目標状態への探索とどのように異なりますか？
• 古典的なプランニングと比較して、HTNプランニングの表現力と計算複雑性はどの程度ですか？
• サブタスク間の順序付けおよび事前条件制約は、分解中にどのように処理されますか？

Key concepts

• プリミティブタスクと複合タスク
• メソッドと分解
• タスクネットワーク
• 順序制約
• 手続き的ドメイン知識
• HTNの表現力
• 順序付きタスク分解
• SHOP2

Key theories

メソッドによるタスク分解

HTNプランニングは、目標指向探索を再帰的分解に置き換えます。複合タスクは、すべてのタスクがプリミティブになるまで、メソッドを介してサブタスクのネットワークに展開され、タスクを実行する方法に関する人間の専門知識を直接エンコードできます。

HTNプランニングの表現力と複雑性

HTNプランニングは、古典的なSTRIPSプランニングよりも厳密に表現力が高く、その一般形式では計画の存在が決定不能である可能性があり、制限された形式はより高い複雑性クラスを占めます。これは、メソッドベースの分解の力を反映しています。

順序付きタスク分解プランナー

SHOP2のような実用的なHTNプランナーは、タスクが実行される順序でタスクを分解することで計画を立てます。これにより、完全に決定された状態に対して事前条件を評価し、豊富なドメイン知識を効率的に組み込むことができます。

Clinical relevance

HTNプランニングは、製造プロセス計画、軍事およびロジスティクス運用、ウェブサービス合成、ゲームおよびストーリー生成など、専門家の手順が既知であり、それに従う必要がある場合に広く使用されています。これは、メソッドによってドメインエキスパートがタスクを達成するための標準的な方法をエンコードできるためです。

History

階層的プランニングは、1970年代のSacerdotiのNOAHと抽象化階層にその起源をたどることができます。Erol、Hendler、Nauは1990年代初頭にHTNプランニングを形式化し、その複雑さを分析しました。SHOPおよびSHOP2プランナー（2000年から2003年頃）は、順序付きHTNプランニングを実用的で広く使用される技術にしました。

Key figures

• Dana Nau
• Kutluhan Erol
• James Hendler
• Earl D. Sacerdoti
• Austin Tate

Seminal works

• erol1994
• nau2003

Frequently asked questions

HTNプランニングは古典的なプランニングとどう違うのですか？

古典的なプランニングは、アクションの事前条件と効果のみを使用して、目標状態に到達する任意のアクションシーケンスを探索します。一方、HTNプランニングは、達成すべきタスクから始まり、それらのタスクが通常どのように手続き的に行われるかをエンコードするメソッドを使用してタスクを分解するため、より豊富なドメイン知識に依存します。

HTNプランニングが決定不能であるのはなぜですか？

メソッドは複合タスクをさらに複合タスクを含むネットワークに分解できるため、分解プロセスは文法が任意の長さの派生を生成するのと非常によく似て、無限に再帰する可能性があります。したがって、その一般形式では、有効な分解が存在するかどうかを決定することは決定不能です。