僅具有部分圖形知識的尋路算法

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"。