如何避免機器人陷入局部最小？

Question

我有一段時間在機器人的運動規劃中佔有一席之地，並且有一段時間想探索通過「潛在領域」方法提供改善機會的可能性。我的挑戰是避免使用「勢場」方法時機器人陷入「局部最小」。爲了避免機器人陷入困境，我沒有使用「隨機遊走」方法，而是考慮是否可以實現A *的變體，這可以作爲一種準確的指導，以避免機器人陷入「當地最低限度「。

有沒有這種經驗，或者可以參考文獻，它比「隨機遊走」方法更有效地避免局部最小值。

Answer 1

A *和潛在字段都是搜索策略。你遇到的問題是，一些搜索策略比其他搜索策略更「貪婪」，而且更多的時候，過於貪婪的算法會陷入局部最小值。

還有一些替代方法，其中貪婪（陷入局部最小值的主要原因）和多樣性（嘗試新的替代方法在短期看來似乎不是一個好選擇）之間的緊張關係被參數化。

幾年前，我研究了一些關於螞蟻算法（搜索Marco Dorigo，ACS，ACO），他們有一個搜索算法家族，可以應用於任何東西，他們可以控制貪婪與探索您的搜索空間。在他們的一篇論文中，他們甚至比較了使用遺傳算法，模擬退火等解決TSP（規範旅行商問題）的搜索性能。螞蟻贏了。

我已經解決了過去使用遺傳算法的TSP，如果你喜歡，我仍然有delphi的源代碼。

Answer 2

使用諧波函數路徑規劃。諧波函數是描述流體流動和其他自然現象的潛在函數。如果他們使用邊界條件正確設置，那麼他們沒有局部最小值。這些自90年代初以來一直在使用Rod Grupen and Chris Connolly。已經表明這些功能是使碰撞概率最小化的最佳控制的特定形式。可以使用差分方程（即高斯塞德爾，連續過度鬆弛等）在低維空間中有效地計算它們。