はじめに
ロボティクスにおいて、グラフ探索は重要な技術です。
例えば、ある地点までのパスを生成するために、
グラフ情報で表された道路データベースから
最適な経路を探索したり、
グリッドマップで作成された地図に対して、
障害物を回避する経路を生成するときも、
グラフ探索が利用されます。
他にも、人間の言葉を認識するための自然言語処理においても、
文章を各単語で分けてそれらをグラフ情報とし、グラフ探索をすることで、
文章の意味を理解させるためにも使用されます。
今回はこのロボティクスでよく使用されるグラフ探索の基礎的な内容について
まとめておきたいと思います。
グラフ探索における基礎用語
まずはじめにグラフ理論では、
ノードとエッジという情報でデータを表します。
ロボティクスでは、交差点や各グリッドをノード、
道路やグリッド間の距離などをエッジとして表すことが多いようです。
また、このグラフデータにおいて、ループが無く、
すべてのノードがいずれかのノードに繋がっている構造を木構造といいます。
グラフ探索は、このようなグラフ形状のデータに対して、
あるノードからあるノードまでの経路(エッジ列)を取得することです。
ロボティクスでは大抵、エッジをノード間の距離などのコスト値とみたたて、
コストの総和が最小になるような経路を探索することを目的とします。
グラフ探索を実施する際には、スタート地点のノードから、
ゴールのノードまで、隣接するノードを一つ一つ探索していきます。
そこで利用するのが、オープンリストとクローズドリストという言葉です。
オープンリストは、現在探索中のノードに隣接するノードのリストで、
これから探索を実施するノードを格納するリストです。
一方、クローズドリストは探索を終えたノードを格納するリストです。
グラフ探索の進め方としては、
まずスタートノードをクローズドリストに格納し、
その隣接ノードをオープンリストに格納します。
そして、オープンリストの中から一つのノードを選び、
そのノードをクローズドリストに入れ、
そのノードの隣接ノードをオープンリストに入れながら、探索を進めます。
下記の通り、ノード探索には色々アルゴリズムがありますが、
それらは、
"次に探索するノードをどのようにオープンリストの中から選ぶのか？"
という部分で異なるもので、それ以外は同じ流れでグラフ探索を実施していきます。
幅優先探索と深さ優先探索
グラフ探索のアルゴリズムの中で最も基本的なアルゴリズムに、
幅優先探索と深さ優先探索があります。
幅優先探索は、
オープンリストに登録された古いノードから次のノードを選ぶ
ノード探索アルゴリズムです。
古いノードが順々にノードを探索するため、
スタートノードから徐々に幅を広げながら探索をします。
オープンリストのデータ構造をスタックとして実装すると、
この幅優先探索のアルゴリズムになります。
一方、深さ優先探索では、
オープンリストに登録された新しいノードから次のノードを選ぶ
ノード探索アルゴリズムです。
新しいノードから選んでいくため、スタートノードから
どんどん先に探索が進み、ゴールが無い場合には
元に戻りながら探索を進めていきます。
オープンリストのデータ構造をキューとして実装すると、
この深さ優先探索のアルゴリズムになります。
幅優先探索と深さ優先探索の違いに関しては、
下記の記事が非常にわかりやすいです。
通勤・通学中に理解する深さ優先探索と幅優先探索【アルゴリズム】 - おっ立ち野郎
ダイクストラ法とA*探索法
上記の幅優先探索と深さ優先探索の方法では、
ノードがオープンリストに登録された時間に応じて探索を実施するため、
エッジのコストに応じた探索には利用できません。
そこで使用されるのが、ダイクストラ法とA*アルゴリズムです。
ダイクストラ法は、オープンリストの中から
各ノードまでのコストの総和が
最も小さいノードから探索を進めるアルゴリズムです。
これにより、スタートノードとゴールノードまでの
最小コストの経路を計算をすることができます。
コストの総和を探索毎に更新しなくてはいけないため、
探索するごとに、各ノードのコストの総和を更新する必要があります。
また、幅優先探索や深さ優先探索では、
クローズドリストに登録されたノードはそのままですが、
ダイクストラ法の場合、新しい探索により最小コストが更新される可能性があるため、
クローズドリストからオープンリストにノードが戻る可能性があります。
ダイクストラ法の詳細な説明や、
このダイクストラ法を使ったグリッドマップにおける
最短経路探索に関しては下記の記事を参照下さい。
ダイクストラ法は、
エッジコストに基づいた最小コスト経路を計算することができますが、
ゴールの場所に関係なく、
最小コストノードをすべて更新しながらグラフ探索を行うため、
ノード探索の計算量が大きくなってしまうことがあります。
そこで、事前の情報(ヒューリスティック関数)を元に、
ノード探索を効率化してものがA*(エースター)アルゴリズムです。
A*による最短経路計算の場合、
ノードの最小コスト値だけでなく、ゴールまでの距離を足したものが、
最小になるノードから探索をすることにより、
ゴールに近いノードから探索でき、効率的な探索を実現できる可能性が高くなります。
詳しいA*アルゴリズムの説明と、
A*による最短経路計算のサンプルプログラムに関しては、下記の記事を参照下さい。
参考資料
最強最速アルゴリズマー養成講座：知れば天国、知らねば地獄――「探索」虎の巻 - ITmedia エンタープライズ
[algorithm]グラフ理論と幅優先探索＆深さ優先探索の入門の入門(夏休み企画4) | KentaKomai Blog
MyEnigma Supporters
もしこの記事が参考になり、
ブログをサポートしたいと思われた方は、
こちらからよろしくお願いします。
