實現D * Lite路徑規劃 - 如何檢測邊緣成本變化？

我目前嘗試實施D * Lite算法進行路徑規劃（另請參閱here）以掌握它。我在網上發現了兩種C/C++實現，但不知怎的，它們不能完全遵循這些想法，因爲它們看起來與白皮書中的僞代碼相比差異超過預期。我特別使用以下兩篇論文： Koening,S.;Likhachev,M. - D* Lite, 2002 Koenig & Likkachev, Fast replanning for Navigation in Unknown Terrain, IEEE Transactions on Robotics, Vol. 21, No. 3, June 2005 實現D * Lite路徑規劃 - 如何檢測邊緣成本變化？

我試圖從第一白皮書（第5頁，圖4）和用於「調試」執行d *精簡版的優化版本我使用例如如圖並在第二份白皮書中解釋（第6頁，圖6和圖7）。所有工作都在MatLab中完成（更容易與其他人交換代碼）。

到目前爲止，我通過運行computeShortestPath（）來運行代碼以查找最初的最短路徑。但現在我停留在行{36「」}和{37「僞碼的」}：

{36」} Scan graph for changed edge costs; 
{37」} if any edge costs changed

如何檢測這些變化？我似乎沒有掌握如何檢測到這種情況？到目前爲止，我主要使用3個矩陣。與包含所有rhs值的網格地圖大小相同的一個矩陣。一個相同大小的矩陣包含類似的所有g值。並且對於優先級隊列具有可變行數的一個矩陣，前兩列是優先級鍵，第三和第四行是x和y座標。

比較我的結果，我得到了第5步中第一次運行computeShortestPath（）的結果，如第二篇白皮書p.6所示。將機器人移動一步也不是問題。但我真的不知道應該如何實施掃描邊緣成本變化的下一步。

感謝您的任何提示，建議和/或幫助！

來源

2012-09-19 EliteTUM

在尋找答案，對「終身規劃A *」（LPA *）同樣的問題，我在這裏發現了這個小程序： http://homepages.dcc.ufmg.br/~lhrios/applet_d_lite/index.html 玩弄它讓我產生了這樣的想法：'掃描改變的成本'是否意味着將可能的後繼節點與已知地圖中的可能後繼節點進行比較（如果我們發現了一個新的未知障礙，它可能會與實際地圖不同）？ – EliteTUM

請不要交叉發帖：http://cstheory.stackexchange.com/questions/12647/implementing-d-lite-for-path-planning-how-detect-edge-cost-change –

以下是向我指出別人：

在現實世界中的代碼，你幾乎從來沒有到「掃描圖進行的變化。」您的圖表只會在您更改代碼時發生變化，因此您已經確切知道何時何地可以更改！實現這個的

一種常見的方法是在你的圖表類OnGraphChanged 回調，它可以設置爲調用你的路徑查找器類的 OnGraphChanged方法。然後，在Graph類中的任何地方更改圖形，確保調用OnGraphChanged 回調。

我個人通過使用「真實地圖」和「已知地圖」來實現它，每次移動之後讓機器人檢查/掃描所有下一個可能的後繼者，並在真實地圖和已知地圖上進行比較。

來源

2012-09-19 16:42:35 EliteTUM

實現D * Lite路徑規劃 - 如何檢測邊緣成本變化？

回答

相關問題