問題タブ [motion-planning]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
grid - A* を使用したグリッド近似は、連続モーション プランニングの問題の解決に最適ですか?
A から B への衝突のないパスを見つけるという連続動作計画の問題を考えると、A* 検索は有限サイズのグリッド近似で最適であることが知られています。たとえば、各グリッド セルには 4 つまたは 8 つの隣接セルがあります。
ここで、A* パスは最適かもしれませんが、A* パスはグリッド セルと整数グリッド座標に限定されるため、連続空間内の最短パスとまったく同じである必要はありません。ここで、解像度を無限に上げれば、結果の A* パスは正確で、連続問題と等しくなるはずです。しかし、文献を見ると、セルベースの近似の「解像度の完全性」しか見つかりません。たとえば、C. Goerzen、Z. Kong、B. Mettler による「A Survey of Motion Planning Algorithms from the Perspective of Autonomous UAV Guidance」では、Rectanguloid 近似セル分解は最適ではありませんが、解像度は完全です。解像度が最適ではない、つまり解像度を無限大に上げた場合に最適であるという意味がよくわかりません。
私の質問は、私が実際にそれを間違って解釈しているのか、それともそのようなグリッド近似が無限の解像度に対しても正確に最適ではないのかということです.