「ヒューリスティック探索入門」のメモ

「ヒューリスティック探索入門」というPDFの1章、2章、4章の一部の学習メモです。
特に、「状態空間問題」といった問題設定や用語について認識できたこと、A*法の理論などについてとても勉強になりました。

(PDF) https://jinnaiyuu.github.io/pdf/textbook.pdf
(Github） https://github.com/jinnaiyuu/search-ja

できる限り元のテキストに沿っているつもりで、私の意見や考えは青字としています。誤りなどありましたら教えて下さい。

1章 イントロダクション

このPDFの主な対象は、状態空間問題 (state-space problem)。
特に、状態空間問題のうち完全情報かつ決定論的 モデル

• 状態空間問題とは、与えられたゴールに到達するための行動の列（＝プラン） を発見する問題
• 完全情報とは、エージェントが世界の状態を全て観察できるモデル
  不完全情報とは、エージェントは世界の状態を知ることはできないが、観察して世界の状態の一部を知ることができるモデル
• 決定論的とは、エージェントの行動によって世界の状態がどのように遷移するかが一意に定まること
  非決定論的とは、一意に定まらないこと
  （行動に応じて状態の候補のいずれかに確率的に遷移する場合や、別のエージェントがいてその意思決定が状態遷移に影響を与える場合など）

参考文献

Judea Pearl の Heuristic
https://www.amazon.com/exec/obidos/ASIN/0201055945/acmorg-20

Stefan Edelkamp and Stefan Schrodl の Heuristic Search Theory and Application
https://www.amazon.co.jp/dp/B0058NBJCW

Stuart Russell and Peter Norvig の Artificial Intelligence
https://www.amazon.co.jp/dp/B01HEY2P66

Malik Ghallab, Dana Nau, and Paolo TraversoのAutomated Planning and Acting https://www.amazon.co.jp/dp/B01JGMDWRA/

2章 状態空間問題

状態空間問題

状態空間問題とは、以下の問題である。

以下が与えられ、

• 状態の集合
• 初期状態
• ゴール状態の集合
• アクションの集合。アクションは、ある状態を別の状態に変換するもの
• コスト関数。コスト関数は、アクションごとのコストを表す関数で、コストは実数。
  （なお、コスト関数が定数である場合の問題は、ユニットコスト状態空間問題という。）

以下を解として返す。

• 初期状態からゴール状態へ遷移させるアクションの配列
  ここで、アクションの配列のコストは、各アクションのコストの和である

なお、状態空間問題は、グラフの形で考えることができる。（というか、解くにあたってはグラフで考えるしかないような気がする）

• 状態空間グラフ（＝状態空間問題を表すグラフ）は、各状態を頂点、アクションを辺、コスト関数を辺の重みとしたもの
• 状態空間グラフにおいて、アクションの配列は経路、アクションの配列のコストは経路の辺の重みの和となる。
• 探索する際に、状態空間グラフのノード・エッジ全てを保持する必要はなく、またメモリなどの制約から全てを保持できない場合もある。全てのノード・エッジを保持している場合を明示的状態空間グラフ、ルールなどの関数で表す場合を非明示的状態空間グラフという

状態空間問題の問題例

• グリッド経路探索
  Web上のデモ：http://qiao.github.io/PathFinding.js/visual/
• スライディングタイル
  15パズルなど
• 多重整列問題
• 倉庫番 
• 巡回セールスパーソン問題

問題の性質・難しさ

問題の難しさを左右する要素は以下のとおり：

• 状態空間の大きさ
• 分枝度
• デッドエンド
• 解の存在

関連する問題

以下のような関連する問題がある：

• マルコフ過程問題 (Markov Decision Process Problem) (MDP)

  • 状態遷移が決定論的ではなく確率的であると仮定したモデル
  • 動的計画法やモンテカルロ木探索が使われることが多い

• 部分観測マルコフ過程問題 (partially observable Markov decision process problem) (POMDP)

  • MDPからさらに不完全情報問題に拡張したもの
  • 多くの場合厳密計算は困難なので、モンテカルロ木探索などの近似手法が用いられる

• 敵対するエージェントがいる問題

  • 囲碁やチェスなど。特に二人零和ゲームでの研究が盛ん
  • MiniMax木、α-β木、モンテカルロ木探索などが用いられる
  • 近年では強化学習によってヒューリスティック関数を学習するアプローチの研究が盛ん

4章 ヒューリスティック探索

• ヒューリスティック探索
  問題の特徴を利用してノードの有望さをヒューリスティック関数 (heuristic function) として定量化し、それを探索に利用したアルゴリズムのこと

ヒューリスティック関数とその性質

• ヒューリスティック関数（h値）

  • ノードを状態の有望さに基づいて評価する関数
  • ヒューリスティック関数の値をそのノードのh値という
  • ヒューリスティック関数が定数の場合、何も情報がない状況で探索をしていることになる

• 完璧なヒューリスティック

  • ノードからゴールまでの正しい最短コストをh*とする
  • 全てのノードに対して、h値がh*と等しいとき、完璧なヒューリスティックという。
  • 完璧なヒューリスティック関数がもしあれば、ほぼ問題は一瞬で解ける

• 許容的なヒューリスティック

  • すべてのノードについて、h値が正しい最短コストh*以下である場合、許容的であるという
  • 緩和問題を解くことで許容的なヒューリスティックが得られる。 緩和問題とは、元の問題の解を含む問題をいう。（ 例えば、元の問題では存在しない辺を加えたものなど）

• 無矛盾なヒューリスティック

  • 全てのノードのペアについて、$h(u) <= h(v) + k(u, v) $ が成り立つ場合、無矛盾なヒューリスティックという
    ここで、$k$は$u$から$v$への最小コスト
  • つまり、出発するノード$u$のh値から経路$u \rightarrow v$のコストを引いたものより、到達するノード$v$のh値が同じか大きい場合無矛盾
  • 逆に、出発するノード$u$のh値から経路$u \rightarrow v$のコストを引いたものより、到達するノード$v$のh値が小さい場合、経路を進むとh値が消えてしまい矛盾しているような感じか
  • ゴールノードのh値が0である無矛盾なヒューリスティックは許容的なヒューリスティックである。（PDF内の定理2）

• 単調なヒューリスティック

  • 全ての辺に対して、$h(u) <= h(v) + w(u, v)$ である場合、単調なヒューリスティックという
    ここで、$w(u, v)$ は辺$u \rightarrow v$のコスト
  • 単調なヒューリスティックは、無矛盾なヒューリスティックの2つのノード間の経路を、直接繋がっている辺に置き換えたもの　
  • 単調性と無矛盾性は同値である（PDF内の定理3）

A*法

A*法のアルゴリズムは以下のとおり：

• g値は、初期状態からそのノードまでの既知の最短経路コスト
• h値は、何らかのヒューリスティック関数によるそのノードからゴール状態までの最短経路の見積もり
• f値は、g値とh値の和
• A*法は、f値が小さいノードから順に探索していくアルゴリズム

A*法には以下のような性質がある：

• グラフに経路コストが0以下のサイクルが存在しない場合、A*は完全である（PDF内の定理4）
  完全とは、解が存在するときに有限時間内に解を返すこと
• ヒューリスティックが許容的であるとき、A*は最適解を返す（PDF内の定理5）
  • 最短でない経路の解(コストをc'とする)が、最短経路の解（コストをcとする）より先にゴール状態に到達することは無いことを示す。 最短経路のコストをcとするとき、ヒューリスティックが許容的であるなら、最短経路の各ノードのf値はc以下となる。 一方で、最短でない経路のゴールノードにおいて、f値はc'となるため（g値はc'、h値は0であるので）、最短でない経路のゴールノードより先に最短経路の各ノードが展開される。

• 無矛盾なヒューリスティックを用いたA*探索はノードの再展開を生じない（PDF内の定理6）

  • 無矛盾なヒューリスティックの場合、全てのノードに最初に最短経路コストで到達することが証明できる。
  • あるノードをゴールノードととらえ、そのノードのh値を各ノードから引けば、「ゴールノードのh値が0である無矛盾なヒューリスティックは許容的なヒューリスティック」であるため、「ヒューリスティックが許容的であるとき、A*は最適解を返す」の証明と同様でよい（？）

• 許容的で無矛盾なヒューリスティックであるなら、解析的に良い性質を満たしているといえるが、経験的に速いと知られているヒューリスティック関数の中にはこれらの性質を満たしていないものも多い

A*法とヒューリスティックの情報

• ヒューリスティックの情報
  ヒューリスティック関数h1とh2が両方許容的であり、ゴールでない$s \in S$ に対してh2(s) > h1(s)であるとき、h2(s)はh1(s)よりも情報があるという
• ノード展開の必要条件（PDF内の定理7）
  A*探索で展開されるノードのf値はすべて最適解のコスト以下である
• ノード展開の十分条件（PDF内の定理8）
  f値が最適解のコスト未満であるノードは全てA*展開で探索される
• h1とh2の探索範囲（PDF内の定理9）
  h2はh1よりも情報がある場合、h2を使ったA*探索で展開されるノードはh1を使ったA* 探索でも展開される。つまり、h2の探索範囲はh1よりも小さくなる。
• ヒューリスティックの合成（PDF内の定理10）
  • ヒューリスティック $h_1, h_2 ... h_m $ が許容的であるとき、ヒューリスティック $h(s) = max(h_1(s), h_2(s) ... h_m(s))$ は許容的
  • ヒューリスティック $h_1, h_2 ... h_m $ が許容的で無矛盾であるとき、ヒューリスティック $max(h_1(s), h_2(s) ... h_m(s))$ は無矛盾で許容的

ヒューリスティック関数の例

• グリッド探索での、障害物を無視した最短距離（マンハッタン距離）
• スライディングタイルでの、現在の位置とゴール状態の位置の差の総和
• スライディングタイルでの、部分問題の最適解のコスト
• 巡回セールスパーソン問題での、最小全域木のコスト

非最適解の探索

最適解でなくて良いので、解を探索する方法には以下がある：

• 重み付きA*探索
  $f'(s) = g(s) + w h(s)$という形とし、h値に重み$w (\ge 1$)をつける
• 貪欲最良優先探索
  重み付きA*探索のh値の重みを無限大にしたもの
• 山登り法
  単純に最良のノードのみを記録し、最良のh値の状態を選び続ける。極小にはまったり、行き止まりに当たる可能性がある。
• 強制山登り法
  幅優先探索で現在のノードよりもh値が小さいノードを発見する。発見できれば幅優先探索を繰り返し、発見できなければ極小に陥ったということで失敗とする