2

私は現在、パス プランニング用の D* Lite アルゴリズムを実装して (こちらも参照)、それを把握しようとしています。どちらも C/C++ 用の 2 つの実装を Web で見つけましたが、ホワイトペーパーの疑似コードとは予想以上に異なっているように見えるため、アイデアを完全には追うことができませんでした。私は特に次の 2 つの論文を使用します: Koening, S.; Likhachev, M. - D* Lite、2002 年 Koenig & Likkachev、未知の地形でのナビゲーションのための高速再計画、ロボティクスに関する IEEE トランザクション、Vol. 21、No.3、2005 年 6 月

最初のホワイトペーパー (p.5、図 4) の最適化されたバージョンの D* Lite を実装してみました。「デバッグ」には、2 番目のホワイトペーパー (p.6、図 6、図 6) で示され説明されている例を使用します。 。7）。すべての作業は MatLab で行われます (他のユーザーとコードを交換するのが簡単です)。

これまでのところ、computeShortestPath() を 1 回実行することで、最初の最短パスを見つけるコードを実行しました。しかし今、私は疑似コードの {36''} 行目と {37''} 行目で立ち往生しています:

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

これらの変更を検出するにはどうすればよいですか? これがどのように検出されているのか、どういうわけか把握していないようですか？これまでの実装では、主に 3 つの行列を使用しました。すべての rhs 値を含むグリッド マップと同じサイズの 1 つのマトリックス。同様にすべての g 値を含む同じサイズの 1 つの行列。そして、最初の 2 列が優先キーで、3 番目と 4 番目の行が x 座標と y 座標である、優先キューの可変行数を持つ 1 つのマトリックス。

私の結果を比較すると、Step5 の computeShortestPath() の最初の実行で、2 番目のホワイトペーパーの p.6 図 6 に見られるのと同じ結果が得られます。ロボットを 1 歩動かすことも問題ありません。しかし、変更されたエッジ コストをスキャンする次のステップをどのように実装すればよいか、まったくわかりません。

ヒント、アドバイス、および/またはヘルプをありがとう!!!

4

1 に答える 1

1

次のことが他の誰かから私に指摘されました：

実際のコードでは、「グラフをスキャンして変更を確認する」必要はほとんどありません。グラフはコードで変更した場合にのみ変更されるため、いつどこで変更できるかはすでに正確にわかっています。

これを実装する一般的な方法の1つは、GraphクラスにOnGraphChangedコールバックを設定することです。これは、PathFinderクラスのOnGraphChangedメソッドを呼び出すように設定できます。次に、Graphクラスでグラフが変更された場合は、必ずOnGraphChangedコールバックが呼び出されます。

私は「真の地図」と「既知の地図」を使用して個人的に実装し、移動するたびに、ロボットに次のすべての可能な後継者をチェック/スキャンさせ、真の地図と既知の地図でそれらを比較しました。

于 2012-09-19T16:42:35.653 に答える