半順序計画

半順序計画は、アクション間の部分的な順序を維持し、強制された場合にのみアクション間の順序をコミットする、つまりアクションの順序が部分的である自動計画のアプローチです。また、この計画では、2 つのアクションが処理されるときにどのアクションが最初に実行されるかは指定されません。対照的に、全順序計画では、計画の各段階ですべてのアクション間の全順序が維持されます。目標を達成するために一連のアクションが必要な問題の場合、半順序計画では実行する必要があるすべてのアクションが指定されますが、必要な場合にのみアクション間の順序が指定されます。

次の状況を考えてみましょう。人は障害物コースのスタートからゴールまで移動する必要があります。コースは橋、シーソー、ブランコで構成されています。シーソーとブランコに到達するには、まず橋を渡らなければなりません。シーソーとブランコに到達したら、シーソーとブランコを任意の順序で渡ることができ、その後ゴールに到達できます。半順序計画では、これらの障害物間の順序は必要な場合にのみ指定されます。最初に橋を渡らなければなりません。次に、シーソーまたはブランコのいずれかを渡ることができます。3 番目に、残りの障害物を渡ることができます。その後、ゴールを渡れます。半順序計画は、その効率性のために最小コミットメントの原則に依存しています。

半順序計画または部分計画は、実行する必要があるすべてのアクションを指定しますが、必要な場合にのみアクション間の順序を指定します。これは半順序プランナーの結果です。半順序計画は、次の 4 つのコンポーネントで構成されます。

• アクションのセット(演算子とも呼ばれます)。
• アクションの部分的な順序。いくつかのアクションの順序に関する条件を指定します。
• 因果関係のリンクのセット。どのアクションが他のアクションのどの前提条件を満たすかを指定します。または、アクション内の変数間のバインディングのセット。
• オープン前提条件のセット。半順序プラン内のどのアクションでも満たされない前提条件を指定します。

アクションの可能な順序を可能な限りオープンに保つには、順序条件と因果関係のセットを可能な限り小さくする必要があります。

オープン前提条件のセットが空の場合、計画はソリューションです。

半順序プランの線形化は、特定の半順序プランから派生した全順序プランです。言い換えると、両方の順序プランは同じアクションで構成され、線形化の順序は元の半順序プランの部分順序の線形 拡張になります。

たとえば、ケーキを焼く計画は次のように始まります。

• 店に行く
• 卵を手に入れる; 小麦粉を手に入れる; 牛乳を手に入れる
• すべての商品の支払い
• 台所に行く

これは部分的な計画です。卵、小麦粉、牛乳を探す順序が指定されていないため、エージェントは店内を歩き回り、買い物リストが完成するまで、リストにあるすべてのアイテムを反応的に蓄積することができます。

半順序プランナーは、半順序プランを構築し、解決策を検索するアルゴリズムまたはプログラムです。入力は、初期状態、目標、および可能なアクションの説明で構成される問題の説明です。

この問題は、可能な半順序プランの集合が検索空間となる検索問題として解釈できます。初期状態は、目標条件と等しいオープン前提条件を持つプランです。最終状態は、オープン前提条件のないプラン、つまりソリューションです。

初期状態は開始条件であり、現在のタスクの前提条件と考えることができます。テーブルをセットするタスクの場合、初期状態はテーブルが片付いている状態です。目標は、テーブルをセットするなど、達成する必要のある最終的なアクションです。アルゴリズムの演算子は、タスクを達成するためのアクションです。この例では、lay (テーブルクロス) と place (グラス、皿、銀食器) の 2 つの演算子があります。

アルゴリズムの計画空間は、開始と終了の間で制約されます。アルゴリズムは開始して初期状態を生成し、目標のすべての部分が達成されたときに終了します。テーブルの設定の例では、対処する必要がある 2 種類のアクション、put-out 演算子と lay 演算子が存在します。未解決の演算子も 4 つ存在します。Action 1、lay-tablecloth、Action 2、Put-out (plates)、Action 3、Put-out (silverware)、および Action 4、Put-out (glasses) です。ただし、Action 2、3、または 4 が Action 1 の前に来ると、脅威が発生します。この脅威は、テーブルがクリアでなくなるため、アルゴリズムの開始の前提条件が満たされなくなることです。したがって、Action 2、3、および 4 が Action 1 の後に来るように強制する制約がアルゴリズムに追加されます。これらのステップが完了すると、アルゴリズムは終了し、目標は達成されます。

上記のアルゴリズムに見られるように、半順序計画では特定の脅威、つまり連結されたアクションを中断する恐れのある順序付けに遭遇し、その結果、計画全体が破壊される可能性があります。脅威を解決するには 2 つの方法があります。

• プロモーション
• 降格

昇格は、脅威となる可能性のある接続を、脅威となる可能性のある接続の後に順序付けます。降格は、脅威となる可能性のある接続を、脅威となる可能性のある接続の前に順序付けます。

半順序計画アルゴリズムは健全かつ完全であることで知られています。健全とはアルゴリズムの完全な順序付けとして定義され、完全とは実際に解決策が存在する場合に解決策を見つける能力として定義されます。

半順序プランニングは全順序プランニングの逆で、全順序プランニングでは、すべてのアクションが一度に順序付けられ、手元のタスク全体にわたって実行されます。2 つの競合するプロセスがある場合、どちらが優れているかという疑問が生じます。Anthony Barret と Daniel Weld は 1993 年の著書で、半順序プランニングの方が高速で効率的であるため、全順序プランニングよりも優れていると主張しました。彼らはこの理論を Korf のサブゴール コレクションの分類法を使用してテストし、全順序プランニングよりも自明な直列化可能性を生み出すため、半順序プランニングの方がパフォーマンスが優れていることを発見しました。自明な直列化可能性により、サブゴールを含むゴールを処理する際にプランナーが迅速に実行できるようになります。面倒な直列化が可能なサブゴールや直列化が不可能なサブゴールを処理する場合、プランナーのパフォーマンスは低下します。サブゴールを自明な直列化可能または面倒な直列化可能にする決定要因は、さまざまなプランの検索空間です。彼らは、部分順序計画の方が最速の経路を見つけるのに優れており、したがってこれら 2 つの主な計画タイプのうちより効率的であることを発見しました。

半順序計画は、サスマン異常を簡単かつ最適に解決することが知られています。このタイプの増分計画システムを使用すると、この問題が迅速かつ効率的に解決されます。これは、半順序計画が効率的な計画システムとしての地位を固めた結果です。

このタイプの計画システムの欠点の 1 つは、各ノードに非常に多くの計算能力が必要になることです。ノードあたりのコストが高くなるのは、半順序計画のアルゴリズムが他のアルゴリズムよりも複雑であるためです。これは、人工知能に重要な影響を及ぼします。ロボットを特定のタスクを実行するようにコーディングする場合、作成者は必要なエネルギー量を考慮する必要があります。半順序計画はより高速かもしれませんが、ロボットのエネルギー コストに見合わない可能性があります。作成者は、効率的なロボットを作成するために、これら 2 つのオプションを認識し、比較検討する必要があります。

• 人工知能：現代的アプローチスチュアート・ラッセル、ピーター・ノーヴィグ著
• ダニエル・ウェルドによる「最小コミットメント計画入門」
• Kambhampati, S.、Knoblock, CA、Yang, Q. (1994)。「改良探索としての計画: 部分順序計画における設計トレードオフを評価するための統一フレームワーク」Elsevier Science。
• Poole, D., Mackworth, A. (2010)。人工知能における部分順序計画：計算エージェントの基礎。ケンブリッジ大学出版局。
• Dyer, CR「部分順序計画（第 11 章）」（2003）CS 540。ウィスコンシン大学マディソン校。ウィスコンシン州マディソン。
• Barrett, A.、および Weld, D. (1993)。部分順序計画: 可能な効率向上の評価。ワシントン大学: コンピュータサイエンスおよびエンジニアリング学部。注。
• Simmons, Reid. (2001)。「計画、実行、学習 1. 部分順序計画」カーネギーメロン大学。ピッツバーグ。メモ。
• http://pdf.miner.org/000/744/302/partial_order_planning_evaluating_possible_efficiency_gains.pdf
• http://pdf.miner.org/000/037/660/decomposition_and_causality_in_partial_order_planning.pdf
• http://dl.acm.org/quote.cfm?id=1867345
• http://arxiv.org/pdf/1106.0249.pdf
• http://www.grastien.net/ban/teaching/06-planning4.pdf