A*アルゴリズムは、現在のコストとヒューリスティックの和であるf値を用いて探索を行う。しかし、分岐数が多い問題では、最適解のコストを超えるf値を持つ「余剰ノード」を大量に生成してしまい、これがメモリ消費と計算時間の両面で大きな負荷となる。先行研究のPEA*は、f値が現在のノードの保存値と一致する子ノードのみをOPENリストに追加することでメモリ消費を抑えるが、一度すべての隣接ノードを生成してから不要なものを破棄するため、実行時間の面で大きなオーバーヘッドが生じる。
PEA*が全子ノードを生成した後に不要なものを破棄するのに対し、EPEA*はOperator Selection Function (OSF) を導入することで、現時点で必要とされる子ノードのみを直接生成する。これにより、PEA*における「余剰なノードの生成」と「再展開時の全子ノードの走査」という2つの実行時間オーバーヘッドを同時に回避している。また、PEA*においてメモリと時間のトレードオフを制御するために必要だったパラメータCを必要とせず、C=0の場合と同等のメモリ節約を実現する。
EPEA*は、ノードがOPENリストに登録されるまでのプロセスを「オペレータの発見と検証」「オペレータの適用（子ノードの生成）」「OPENリストへの挿入」の3段階に分離して扱う。中核となるOSFは、ドメインとヒューリスティックの知識に基づき、現在のノードの保存値と一致するf値を持つ子ノードの集合と、それを上回る最小のf値を持つ子ノードの情報を返す。具体的には、演算子を適用した際のヒューリスティック値の変化量に基づいて演算子をグループ化し、現在の保存値と一致する変化量を持つ演算子のみを選択的に実行することで、不要な子ノードの生成自体を回避する。
標準的なベンチマークを用いた実験により、EPEA*は実行時間とメモリ使用量の両面において、いくつかのアプリケーションで改善を示すことが確認された。また、IDA*への拡張であるEPEIDA*では、生成ノード数を従来のIDA*と比較して、平均分岐数bを用いて近似的にb分の1に削減できることが示されている。
EPEA*は、ドメインやヒューリスティックに関する事前知識をOSFとして定義する必要があり、常に適用可能または実用的とは限らないという限界がある。OSFの構成には、すべてのオペレータを検査するフルチェック型、直接計算を行う直接計算型、およびその両方を組み合わせたハイブリッド型の分類が存在する。また、不整合なヒューリスティックを使用する場合のトレードオフについても検討が必要である。
従来のA*アルゴリズムは展開するノード数の最小化に焦点を当ててきたが、分岐係数が非常に大きい問題領域では、最適解のコストを超える膨大な数のノード（余剰ノード）が生成され、それが計算時間とメモリ消費の両面で大きな負荷となる。これに対し、ノード展開時にf値が現在のノードのf値と等しい子ノードのみをOPENリストに追加し、それ以外のノードは破棄した上で親ノードを再挿入することでメモリ消費を抑えるPartial Expansion A* (PEA*) が提案されている。本論文では、このPEA*の概念を拡張し、計算時間の側面にも対処するEnhanced Partial Expansion A* (EPEA*) を提案する。EPEA*は、ドメインやヒューリスティックに関する事前知識を利用することで、f値が現在のノードのf値と一致するノードのみを生成する。EPEA*は常に適用可能または実用的とは限らないという限界があるものの、IDA*への適用やパターンデータベースを用いるドメインへの応用など、複数のバリエーションを通じて幅広い領域での利用を可能にしている。標準的なベンチマークを用いた実験の結果、EPEA*は実行時間とメモリ使用量の両面において、いくつかのアプリケーションで大幅な改善を示すことが確認された。
A*アルゴリズムは、現在のコストとヒューリスティックの和であるf(n)を用いて探索を行うが、分岐数が多い問題では、最適解のコストを超えるf(n)を持つ「余剰ノード」を大量に生成し、実行時間やメモリを浪費する課題がある。先行研究のPartial Expansion A* (PEA*) は、f(n)が現在のノードと同じ値を持つ子ノードのみをOPENリストに追加することでメモリ消費を抑えるが、子ノードを一度生成した後に再度生成し直す必要があるため、実行時間の面で不利であった。本論文が提案するEnhanced Partial Expansion A* (EPEA*) は、ドメインとヒューリスティックに特化した知識を用いるOperator Selection Function (OSF) を導入することで、f(n)が現在のノードと同じ値を持つ子ノードのみを、他の子ノードを実際に生成することなく特定する。OSFは、f(nc) = f(n)を満たす子ノードの集合と、f(nc) > f(n)を満たす最小のf値を持つ子ノードの情報を返す。これにより、EPEA*は余剰ノードの生成自体を回避できる。例えば、マンハッタン距離を用いるグリッド上の経路探索では、OSFを用いることで、特定の方向に移動した場合にf値が変化するかどうかを事前に判断し、必要な操作のみを選択的に実行することが可能となる。
本セクションでは、提案手法であるEnhanced Partial Expansion A* (EPEA*) の基礎となるPartial Expansion A* (PEA*) について述べる。PEA* は、Collapsing Frontier Nodes (CFN) と呼ばれる技術の一般的な文脈において説明される。
探索木の葉ノードの集合をフロンティアと呼び、最良優先探索アルゴリズムはフロンティアの中から最小コストのノードを選択して展開します。Collapsing Frontier Nodes (CFN) 手法は、あるノード n を共通の祖先として持つフロンティア内のノード集合 R を、ノード n 自体に置き換えることでフロンティアを縮小させる手法です。この際、ノード n のコストを集合 R に含まれるノードの最小コストへと更新しても、許容性の不変条件を維持したままコストを増大させることが可能です。この更新されたコストを格納値 F(n) と呼び、ノードの本来のコストである静的値 f(n) と区別します。格納値 F(n) が静的値 f(n) よりも大きい場合、そのノードは過去に展開済みであり、その時の最小コストのフロンティアノードの静的値が F(n) であったことを示します。なお、格納値はノードが折り畳まれるたびに更新されますが、その値が減少することはありません。
Partial Expansion A* (PEA*)は、探索中に生成される余剰なノードをOPENリストに追加しないことで、A*のメモリ使用量を削減する手法である。一貫性のあるヒューリスティックを前提とし、各ノードは静的なf値と、collapse（崩壊）操作によって得られる格納値（stored value）の2つを保持する。ノードの展開時にはすべての隣接ノードが生成されるが、OPENリストに挿入されるのは、現在のノードの格納値と等しいf値を持つ「現在必要（currently needed）」な子ノードのみである。f値が現在の格納値より大きい「余剰の可能性がある（possibly surplus）」子ノードは、親ノードへとcollapseされ、親ノードの格納値はこれら余剰ノードの中で最小の静的f値へと更新された上で、親ノード自身が再びOPENリストへ挿入される。一方で、f値が現在の格納値より小さい子ノードは破棄される。
PEA*は、余剰なノードをOPENリストに追加しないことでメモリを節約する手法ですが、ノードを再展開するたびに子ノードの生成とf値の計算を繰り返すため、子ノードが持つ静的な値の種類が多い領域では実行時間のオーバーヘッドが大きくなります。PEA*では、メモリ節約量と実行時間のトレードオフを制御するためにパラメータCを導入しており、ノードのf値と子ノードのf値の差がC以下である場合にのみ、その子ノードをOPENに追加します。Cが0の場合はメモリ節約が最大となり、Cが無限大の場合はA*と等価になりますが、最適なCの値はドメインやインスタンスに依存するため、選択指針は報告されていません。これに対し、提案手法であるEPEA*は、C=0のPEA*と同等のメモリ節約を実現しつつ、実行時間のオーバーヘッドも削減しており、メモリと時間のトレードオフを必要としません。実験においては、EPEA*の性能を評価するため、常にC=0のPEA*と比較を行います。
本セクションでは、A*アルゴリズムの新しい変種であるEnhanced Partial Expansion A* (EPEA*) を提案しています。提示された記述は手法の導入部分に留まっており、具体的なアルゴリズムの動作原理や詳細な定義については含まれていません。
EPEA*では、ノードが生成されてから探索候補集合であるOPENリストに登録されるまでに、3つの段階を経ることが重要な観測として示されています。第1段階はオペレータの発見と検証であり、適用可能なオペレータを特定した上で、そのオペレータを実際に適用すべきかどうかを判断するプロセスです。従来のA*やPEA*は、適用可能なすべてのオペレータに対して子ノードを生成しており、この「適用すべきかどうかの検証」というステップを区別していませんでしたが、これを独立した段階として扱うことがEPEA*の鍵となります。第2段階はオペレータの適用、すなわち子ノードの生成プロセスであり、A*においては親ノードのコピーを作成した後に実行されます。最終的な第3段階は、生成された新しいノードを探索の境界として管理するOPENリストへと挿入する工程です。
EPEA*における演算子選択関数（OSF）は、ノードの全子ノードを生成することなく、特定のf値を持つ子ノードの生成と、次に保存すべきf値の計算を同時に行うための仕組みである。OSFは、ドメインとヒューリスティックに依存する知識成分と、それを利用して目的を達成するアルゴリズム成分の2つで構成される。知識成分では、演算子を適用した際のヒューリスティック値の変化量であるデルタh(nc)や、f値の変化量であるデルタf(nc)に基づいて演算子をグループ化して管理する。具体的には、現在の保存値と静的なf値の差であるデルタF(n)に一致するデルタf(nc)を持つ演算子の行を特定することで、必要な子ノードのみを生成し、次の保存値であるFnext(n)を算出できる。既存のプランナで用いられる「優先演算子」の概念は、演算子を優先か否かの二値で分類するが、OSFはデルタfの値に基づいてより細粒度な分類を行う。これにより、EPEA*は不要な子ノードの生成を回避することが可能となる。
EPEA*は、ノードをOPENリストへ追加・展開する順序や、余剰な子ノードを統合するプロセスにおいてPEA*と同様のフローを持ちますが、ドメインとヒューリスティックに特化した演算子選択関数（OSF）を用いる点が異なります。PEA*が全子ノードを生成した後に不要なものを破棄するのに対し、EPEA*はOSFを用いて現時点で必要とされる子ノードのみを生成します。また、PEA*は全子ノードを走査して次の保存値を計算しますが、EPEA*はOSFから直接その値を取得します。具体的な動作として、あるノードの評価値がF(n)であるとき、OSFは評価値の増加量（delta f）が0となる子ノードを生成し、それ以外の評価値が高い子ノードは、OSFが保持する次の最小増加量に基づいた値を用いて親ノードへと統合されます。例えば、ある演算子の適用によって評価値の増加量が1となる場合、次に必要とされる評価値は現在の値に1を加えたものとなり、それ以外のノードは統合の対象となります。
A*、PEA*、EPEA*の3つのアルゴリズムをメモリ使用量と実行時間の観点から比較する。メモリ性能において、A*は生成したすべてのノードをOPENリストに保持するが、PEA*はパラメータCを用いて現在必要のないノードをOPENリストに含めないことでメモリを節約し、EPEA*はCが0の場合のPEA*と同等のメモリ節約を実現する。ノード展開数に関しては、A*は展開されるノード数において最適であるが、PEA*とEPEA*は一意なノード展開数において最適である。実行時間について、A*は余剰なノードの生成や、OPENリストの肥大化に伴う操作コストが課題となる。PEA*はA*よりメモリ使用量を抑えられる場合が多いが、同一ノードの再展開や、再展開のたびに全子ノードを生成するオーバーヘッドが生じる。EPEA*はPEA*と同様に再展開のコストはかかるものの、有用なノードの重複生成と余剰なノードの生成という2つのオーバーヘッドを回避できる。さらに、使用する演算子選択関数によっては、不要なノードに至る演算子のチェック自体を省略できる可能性がある。
EPEIDA*は、IDA*が持つ「現在の閾値以下のノードのみを探索し、閾値を超えるノードを破棄する」という部分的な展開の性質を効率化した手法である。従来のIDA*は、各ノードの全子ノードを生成した後に閾値と比較して探索を継続するか判断するが、EPEIDA*はOSF（Ordered Successor Function）を用いることで、閾値以下の「現在必要とされる子ノード」のみを直接取得し、同時に閾値を超える子ノードの中での最小コストを特定して次回の閾値を更新する。この仕組みにより、EPEIDA*は探索中に閾値条件を個別に判定する必要がなくなる。ノード生成数に関しては、IDA*が最終反復において展開ノード数の約b倍（bは平均分岐数）のノードを生成するのに対し、EPEIDA*は展開ノード数に深さに関連する項を加えた程度に抑えられるため、生成ノード数を約b分の1に削減できる。本手法は、実質的にPEA*（Partial Expansion A*）の反復深化版として機能する。
本セクションでは、現在必要とされるオペレータのリストを取得する手法であるOSF（Operator Selection Function）を分類している。OSFには、現在不要なものを含むすべてのオペレータを検査してリストを得る「フルチェック型」と、直接的な計算によってリストを得る「直接計算型」の2つの純粋なクラスが存在する。さらに、特定のコスト変化量に対しては直接計算を行い、それ以外の値に対してはフルチェックを行うといった、両者の性質を併せ持つ「ハイブリッド型」のOSFも存在する。EPEA*は、展開中のノードのすべての子供を生成するPEA*とは異なり、現在必要とされるオペレータのみを適用して必要な子供のみを生成するという点で区別される。これらの分類は、SAPFドメインを例として、後の節で具体的な構成方法とともに詳述される。
SAPFにおけるFull-Checking OSFの知識コンポーネントは、現在のノードがゴールに対して位置する8通りの相対的な方向に対応した8つのテーブルで構成される。アルゴリズム部分は、ノードの位置に基づいて適切なテーブルを選択し、適用可能な各オペレータによって生じるh値（ゴールまでの推定距離）とf値（推定コストの総和）の変化を記録する。このOSFは、各オペレータを検証して現在必要とされる子ノードのみを特定して生成する。また、次に保持すべき値であるFnext(n)を算出するため、値を無限大で初期化した後、生成された子ノードncが余剰である、すなわちncのf値が現在のノードnのf値よりも大きいと判断されるたびに、Fnext(n)をこれまでの値とncのf値の最小値として更新する。マンハッタン距離をヒューリスティックとして用いる場合、例えばゴールがノードの北西にある状況では、東や南への移動はh値とf値をそれぞれ1と2増加させ、西や北への移動はh値を1減少させ、f値に変化を与えないといった具体的な変化がテーブルに定義されている。