非グリッド マップを使用する場合、経路探索で問題のある領域 (沼地、行き止まり)を見つけて回避するための既存のアルゴリズムはありますか? これらの領域を回避したり、ジャンプ ポイントの再帰などによってこれらの領域を擬似的に回避したりするグリッドに利用できるものはたくさんありますが、四分木、ナビゲーション メッシュ、またはその他の不均一なマップに役立つものはまだ見つかっていません。
2 に答える
1
行き止まりの検出と沼地はグリッド固有ではありません。それらはグリッドマップで評価されるだけです。
于 2012-03-30T04:50:59.147 に答える
0
そのようなことはおそらく存在します-毎年何百ものパスファインディングとモーションプランニングの論文が発行されていますが、もっと大きな質問をする必要があると思います-なぜこれをしたいのですか？
ナビメッシュまたはスパースグリッド表現を使用するという考え方は、グラフ内のノードの数を減らすことにより、解決策を見つけるために必要な時間を短縮することです。検索が遅すぎる場合は、グラフ内のノードとエッジの数を削除するだけです。開始する前にオフラインで検索から行き止まりを手動で削除することにより、すべての検索のオーバーヘッドを削減できます。
グラフを整理した後でも検索が遅くなり、検索問題の近似解を許容できる場合は、最適なコストが得られるまでインフレ率を下げることを再計画する加重A*の使用を検討してください。
計画アルゴリズムには妥協点がたくさんあります。選択したことの長所と短所を理解してください。
最後の提案として、使用しているプランナーにプリミティブが正しく実装されていることを確認してください。A*のようなアルゴリズムは、優先キューが正しく実装されているかどうかに依存します。特に、decrease-keyがO（log n）以上であることを確認してください。
于 2012-03-14T01:05:33.190 に答える