問題タブ [d-star]

私が扱いたい大規模なネットワーク（小さな世界のグラフタイプ）は本質的に動的であり、新しいノードが頻繁に追加および削除されます。おそらく、A*ではなくD*を使用する方が、この動的な環境でパスを検出するためのより良い方法でしょうか？

D *はどれくらいしっかりしていますか？実世界での経験はありますか？暗号化アルゴリズムのように-D*は多くのピアレビューとテストによって強化されていますか？この問題にD*を使用しますか？

ここに D* に関するいくつかの論文へのリンクがありますが、私には少し数学的すぎます。初心者向けの D*/D* Lite に関する情報はありますか?

私の A* 実装は、静的環境でうまく機能します。動的な環境で作業したい場合、つまり、最初から最後までトラバースする間にノード間の特定のコストが変化します。

これまでの読書から、LPA*、D*、および D* Lite アルゴリズムが役に立ちます。私の最悪のシナリオは、すべてを実装して、何が最適かを確認することです。

これらのアルゴリズムの機能を比較する研究はありますか? 私がこれまでに読んだ論文は、一度に 1 つのアルゴリズムに焦点を当てているだけであり、実験環境が異なるため、比較することは困難です。

**背景情報: 私は C++ を使用しており、私の環境は 3D シーンであり、私の検索グラフはナビメッシュを使用して表現されています。

パスファインディングが必要なシミュレーションを実装しています。
私の環境が変わらない場合、A *はうまく機能します。
LPA* と D* Lite は、元のマップにない静的な障害物に遭遇したときにうまく機能します。

しかし、これらの障害物が特定の速度で移動している状況をどのように処理すればよいでしょうか?
これを処理する LPA* または D* Lite アルゴリズムのバリアントはありますか?
または、何らかの形のステアリング動作をこれらのアルゴリズムと組み合わせる必要がありますか?

最終的に私のシミュレーションでは、移動する障害物がある環境で「エージェント」を開始点から終了点まで移動させたいと考えています。

Boost::Graph の Koenig と Likhachev による2002 年の記事で説明されているように、D*-Lite 経路探索アルゴリズムを実装しようとしています。基本的なアイデアとその背後にある理論については十分に理解できたと思いますが、PredとSuccセットがいつ更新されるかを理解するのに問題があります。

Move to sstartのステップで発生すると思いMainますが、最初の呼び出しComputeShortestPathはかなり無意味になりますか? そして、Succセットはオンリーと同時に挿入されることになっていPredますか? Predでは、Succ二重にリンクされたリストとして実装できますか?

以下にアルゴリズムの疑似コードを挿入しました。Predおよびセットは、Succそれぞれ先行および後続です。g、h、rhsおよびcは、異なるコストと重みです。U訪問する頂点の優先キューです。

D*-Lite アルゴリズムを実装しました (ここに説明があります。これは、エッジ コストが時間の経過とともに変化するときに経路探索を行うためのアルゴリズムです) が、エッジ コストの更新に問題があります。ほとんどの場合は機能しますが、2 つの頂点間を行ったり来たりしてループに陥ることがあります。この動作を示すテスト ケースを作成しようとしていますが、現時点では、大規模なアプリケーションで使用すると一部のケースで発生し、デバッグが困難になります。

できるだけ早くテスト ケースを作成しますが、疑似から C++ に移行したときに行ったエラーを誰かがすぐに見つけることができるかもしれません。(以下にテスト ケースが含まれています)この記事では、私が実装した最適化されたバージョン (図 4 ) を紹介しています。擬似コードを以下に貼り付けます。

私の実装のソースはこちらから入手できます。

それが役立つ場合は、コードでこれらの型を使用しています。

使用方法についてさらに情報が必要な場合は、質問してください。貼り付けるには多すぎます。

D*-Lite の疑似コード:

編集：

誤った動作を示すテストケースの作成に成功しました。これをペーストビンのコードと一緒に実行すると、最後のget_path呼び出しでハングアップし、ノード 1 と 2 の間を行ったり来たりします。無限のコスト。

編集 2:さらなる進歩。whileループ内のブレーク条件を( is not empty)ComputeShortestPathだけに置き換えると、パスが見つかります! ただし、必要ではないはずのグラフ内のすべてのノードを常に検査するため、非常に低速です。また、無向グラフを使用しているため、 と の両方を更新するコードを に追加しました。U != ØU{40"}uv

A は A* や D* などについて読んだことがありますが、どちらかを選択することができません。多くの検索 (ティックごとに 50 件の検索) があり、さまざまな可能性がある場合、最適な検索アルゴリズムは何ですか?

私は現在、SvenKoenigのD*Liteアルゴリズムの実装に取り​​組んでいます。 http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf。基本的に、実装を開始する前に、すべての詳細を理解しようとしています。アルゴリズムは有向グラフで機能するようです。これがPredとSucc関数を定義する方法です。

グラフの方向を定義するにはどうすればよいですか。また、どのパラメーターがグラフの方向を決定しますか。gコスト（アルゴリズムが更新gする値と一緒にコストがあるrhsため）や距離のヒューリスティック推定などのパラメータの値を使用する必要がありますか？

私はDLiteの最適化されたバージョンを見ています:

44 行目と 46 行目で同じ条件が評価される理由がわかりません (if u ~= s_goal)。43 行目と 45 行目にある if/if else に入る前に、これを評価することはできないでしょうか? それは可能性が ：

それは間違っているでしょうか？

よろしく

私は現在、パス プランニング用の 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''} 行目で立ち往生しています:

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

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

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