A*探索アルゴリズムによる経路計画
背景 (Background)
カーナビゲーションシステムやGoogleマップで「目的地までの最短ルート」を瞬時に計算できるのはなぜでしょうか？あるいは、複雑な迷路を解くロボットや、ビデオゲームの中で自然に障害物を避けてプレイヤーを追いかけてくる敵キャラクターは、どのようにして「最も効率的な道」を見つけ出しているのでしょうか？これらの裏側で活躍しているのが、人工知能（AI）における古典的かつ強力な「経路探索アルゴリズム」です。中でも「A*（エースター）アルゴリズム」は、目的地までの直線距離（ヒューリスティック）を予測しながら賢く探索を進めることで、無駄な計算を劇的に減らす画期的な手法です。本プロジェクトでは、このA*アルゴリズムをゼロから実装し、その卓越した探索効率を検証します。
はじめに
本プロジェクトでは、「古典的な人工知能検索と推論」の文脈に基づき、A*探索アルゴリズムを実装して経路計画を行いました。 初期状態から目標状態に至る経路を以下の三種類の手法を用いてそれぞれ求め、探索状態数および探索結果の最適性という二つの観点から比較・評価しました。
- 最適探索
- 最良優先探索
- A*アルゴリズム
実装と考察
経路計画を解くために、Pythonを用いて実装を行いました。
まず、math および numpy ライブラリをインポートし、駅をノードとして緯経度情報を格納した辞書を定義しています。 次に、ノード間の接続関係と移動コストを表す隣接行列を設定し、接続が存在しない場合は無限大(inf)として表しています。
その後、ノード間の直線距離を計算するヒューリスティック関数 を定義し、A*探索などで用いる評価関数 の計算に利用しています。 コードの後半では、三種類の探索手法
をそれぞれ関数として実装しました。これらはいずれも未探索ノードと探索済みノードを管理し、ノードの評価関数の違いによって探索の挙動を比較できるようになっています。
また、経緯度と場所の情報により、三つの手法の経路図を作成し、以下の図に示します。
図1: 最適探索の経路
図2: 最良優先探索の経路
図3: A*アルゴリズムの経路（図2の最良優先探索と同じ可視化画像）
最適探索
最適経路: s0 → s2 → s4 → s6 → s7
総距離: 5.0
探索ノード数: 8本手法では、全てのノードをコストの昇順で展開し、最もコストが小さな経路を逐次的に探索します。その結果、最適経路として s0 → s2 → s4 → s6 → s7 が得られ、総距離は5.0でした。しかし、探索ノード数は8となり、最も多く計算コストが高いことが確認されました。 これは、最適解を探すために全探索を行なっており、探索効率は低下するという特徴を示しています。
最良優先探索
最適経路: s0 → s3 → s6 → s7
総距離: 6.0
探索ノード数: 4本手法では、評価関数としてヒューリスティック値 だけ使い、最も目的地に近いノードを優先的に探索します。その結果、経路 s0 → s3 → s6 → s7 が得られ、総距離は6.0でした。 探索ノード数は4と最も少なく、高速な探索が可能である一方で、必ずしも最短経路を保証しないことが分かります。そのため、探索範囲を大きく削減できますが、解の最適性は失われやすいことがわかります。
A*探索
最適経路: s0 → s2 → s4 → s6 → s7
総距離: 5.0
探索ノード数: 5A探索は、コストの評価関数 に基づき、実コストと目標までの距離の推定コストの両方を考えるノードを探索します。経路 s0 → s2 → s4 → s6 → s7 が得られましたが、総距離5.0と最適探索と同一の最短経路を探し出すことができました。さらに、探索ノード数は5であり、最適探索の8ノードよりも少ない探索で最適解に到達しています。 このことから、Aはヒューリスティックを適切に利用することで、探索効率と最適性を両立できることが確認できました。
三つの手法の比較
三手法を比較すると、以下の特徴が明確に表れました。
-
最適探索 常に最短経路を保証しますが、最も多くのノードを探索しています。探索の完全性と最適性が高い一方で、計算コストが大きいことが特徴です。
-
最良優先探索 最適解を保証しない方式として、探索ノード数が最も少なく、高速な探索が可能です。 しかし、ヒューリスティック値のみを基準とするため、最適解を得られない場合があります。
-
A*探索 最適探索と最良優先探索のそれぞれのメリットを融合して、できるだけ最短経路を導出しながら、探索ノード数を減らすことができます。 最適性と効率性の両立が可能であり、本プロジェクトにおいて最もバランスの取れた手法です。