探索算法

Question

大量編輯這個問題，使其更容易理解。

給定一個具有任意尺寸和任意數量障礙物的任意定位的環境，我有一個代理人以有限範圍的視線探測環境（障礙物不會阻擋視線）。它可以在NSEW的四個基本方向上移動，一次一個單元格，並且圖形未加權（每個步驟的成本爲1）。下面鏈接的是一張地圖，表示代理人（黃傢伙）在計劃時刻對環境的當前信念。在代理計劃時，時間不會通過模擬。

http://imagizer.imageshack.us/a/img913/9274/qRsazT.jpg

我可以使用哪些探索算法最大限度地考慮到重新審視細胞被允許公用事業的成本效益，？每個單元格都有一個實用值。理想情況下，我會試圖最大化SEEN（未訪問）的所有單元的效用總和除以路徑長度，但如果對於任何合適的算法來說這太複雜，那麼所看到的單元數就足夠了。有一個最大路徑長度，但它通常在數百或更高。 （我的代理上使用的實際測試環境至少大4倍，儘管理論上可以設置的尺寸沒有上限，並且最大路徑長度因此會相應增加）

我認爲BFS和DFS爲難以處理，由於缺乏合適的啓發式算法，A *是非最優的，而迪傑斯特拉不適合產生一條不間斷的路徑。有什麼算法可以想到嗎？此外，我需要幫助進行循環檢測，因爲我之前從未這樣做過，因爲允許重訪是我第一次。

我考慮過的一種方法是將映射減少爲生成樹，但不是將其定義爲連接所有單元的樹，而是將其定義爲可以查看所有單元的樹。我的做法會導致如下：

http://imagizer.imageshack.us/a/img910/3050/HGu40d.jpg

在結果樹，代理可以從一個節點到是0-1轉走在十字路口的任何相鄰節點。就我現在的想法而言，這就是我的想法。使用這棵樹生成的解決方案可能不是最優的，但它應該至少接近最優，而算法處理的細胞要少得多，所以如果這會使算法更容易處理，那麼我認爲這是可接受的交易。然而，我仍然想着如何爲此產生一條路徑。

Answer 1

您的問題與標準的強化學習（RL）問題非常相似，即網格世界。我將它定義爲一個標準的馬爾可夫決策過程（MDP）並使用任何RL算法來解決它。

的形式化是：

• 國s：你NxM離散網格。
• 操作a：UP, DOWN, LEFT, RIGHT。
• 獎勵r：代理可以從目的地小區s'看到的小區的值，即r(s,a,s') = sum(value(seen(s'))。
• 轉換函數：P(s' | s, a) = 1如果s'不是超出邊界或黑色單元，0否則。

既然您對平均回報感興趣，折扣係數爲1，您必須將累計回報按步數歸一化。你還說每一步都花費了一個，所以你可以在每個時間步驟減去1到立即獎勵r，但這不會增加任何東西，因爲你已經平均的步數。

由於問題是離散的策略可以是一個簡單的SOFTMAX（或吉布斯）分佈。

作爲解決算法可以使用Q學習，保證瞭解決方案的最優化提供足夠數量的樣本。然而，如果你的網格太大（並且你說沒有限制），我會建議策略搜索算法，比如策略梯度或相對熵（儘管它們只保證局部最優化）。你可以在互聯網上的任何地方找到關於Q-learning的東西。對於最近的政策搜索調查，我建議this。

這些方法很酷的一點是，它們將策略中的探索（例如softmax策略中的溫度，高斯分佈中的變化）編碼並嘗試最大化累積長期獎勵MDP。因此，通常你通過高度探索來初始化你的策略（例如，一個完整的隨機策略），並且通過反覆試驗，算法將使其確定並收斂到最優策略（然而，有時候隨機策略是最優的）。 所有RL算法之間的主要區別在於，他們如何在每次迭代中執行策略更新，並管理權衡探索和利用（我應該多少探索VS我應該利用已有信息多少）。

正如Demplo建議，你也可以使用遺傳算法（GA），但它們通常比較慢，需要更多的調整（精英，交叉，變異......）。

我自己也嘗試在你的問題的一些政策搜索算法和他們似乎運作良好，但我隨機初始化網格，不知道確切的最佳解決方案。如果您提供一些額外的細節（測試網格，最大步數以及初始位置是固定的還是隨機的），我可以更精確地測試它們。