グラフの部分知識を持つパス探索アルゴリズム

Question

「迷路」（開始点、ゴール、空白、交差しないスペース、または「壁」を持つ長方形のグリッド）を使ってロボットをナビゲートするアルゴリズムをプログラミングする必要があります。移動ごとに一定のコストで任意の基本方針（N、NW、W、SW、S、SE、E、NE）に移動できます。

問題は、ロボットがマップのレイアウトを「認識」していないことです。それは8つの周囲の空間しか見ることができず、それらを格納する（それはそれが訪れるすべての空間の周囲のタイルを記憶する）。唯一の入力は、すべての移動に目標がある基本方向です。

この問題を解決するために実装できるアルゴリズムはありますか？ DijkstraやA *のような典型的なものは、グラフの以前のノードにコストをかけずに再訪することはできません（ロボットの歩みを見直してより良い道のりを歩くことは、もう一度）、A *のための合理的な発見的方法を作る方法を考えることはできません。

私はおそらく合理的な何かを思い付くことができますが、私は、これはすでに解決される問題だったかどうかを知りたかった、と私は車輪の再発明する必要はありません。任意のヒントのためのP

感謝を！

Answer 1

問題は解決されませんが、多くの計画上の問題と同様に、既に利用可能な多くの研究があります。

この領域のほとんどの作業は、R. E. Korfの原著「リアルタイムヒューリスティック検索」に基づいています。その論文は有料公開されているようだが、論文のpreliminary resultsとReal-Time A *アルゴリズムの議論は依然として利用可能である。

隠れた状態（グラフの部分的な知識を持つ経路探索）に関する離散計画に関する最新の出版物はSven Koenigです。これには、ラーニングリアルタイムA *アルゴリズムに関する重要な作業が含まれます。

Koenigの作品には、シミュレーションで発生する可能性のあるものがはるかに難しい理論的な実験のアルゴリズムの範囲がいくつか含まれています。 KoenigおよびSimmonsによる特に"Easy and Hard Testbeds for Real-Time Search Algorithms"を参照のこと。