障害物を含む世界にあるフラグ (未知の場所に配置されている) を見つけようとするロボットのアルゴリズムを考案しようとしています。ロボットの使命は、フラグをキャプチャしてホームベース (開始位置を表す) に運ぶことです。ロボットは、各ステップで限られた近隣のみを認識します (世界がどのように見えるかを前もって知ることはできません) が、既に訪れたセルを保存するための無制限のメモリを持っています。
これを効率的に行う方法についての提案を探しています。特に最初の部分。つまり、フラグに到達します。
8675 次
8 に答える
5
単純な幅優先検索/深さ優先検索は、ゆっくりではありますが機能します。ボットが同じ正方形を持つパスを複数回チェックしないようにしてください。これにより、標準的なケースではこれらのアルゴリズムの実行時間が大幅に長くなり、フラグに到達できない場合は無期限に実行されます。
A* はよりエレガントなアプローチです。特に、自分自身に対するフラグの位置がわかっている場合はなおさらです。ウィキペディアは、いつものように、それを説明することでまともな仕事をしています. 使用する古典的なヒューリスティックは、目的地までのマニング距離 (障害物がないと仮定した場合の移動数) です。
これらのアルゴリズムは、「フラグを見つける」部分ではなく、帰りの旅行に役立ちます。
編集: これらのアプローチには、マップ上の正方形を表すオブジェクトの作成と、ヒットする「パス」または一連の正方形 (または実行する手順) の作成が含まれます。正方形を表すフレームワークを構築すると、どのような検索を使用するかという問題は、それほど困難な作業ではなくなります。
このクラスは、隣接する正方形のリストを取得し、それが通過可能かどうかを知る必要があります。
すべての情報を把握しているわけではないことを考慮して、未探索のタイルを通過可能として扱い、そうでない場合は再計算してみてください。
編集： 未知のオブジェクトの未知の領域を検索することについて...
空間の境界が見つかるまでPledge のアルゴリズムのようなものを使用して、移動しながらすべての情報を記録できます。次に、お気に入りのドリフト/パスファインディング アルゴリズムを使用して、目に見えないすべての正方形を調べます。途中でフラグが表示された場合は、作業を停止し、お気に入りの経路探索アルゴリズムを使用して家に帰ります。
于 2011-03-19T13:16:08.083 に答える
3
その一部は、たとえばA* アルゴリズムを使用した経路探索です。
その一部を探索します。未知の隣接セルを持つセルは、調査する価値があります。探索するのに最適なセルは、ロボットに最も近く、未探索の領域が最大のセルです。
ロボットが壁越しに見ている場合、一部の探索候補にアクセスできない可能性があり、フラグが既に表示されていても探索が必要になる場合があります。
新しいセルが明らかになるたびに、現在のターゲットを再評価する価値があるかもしれません。これが新しい細胞が明らかになったときにのみ行われる限り、進歩は常に行われます.
于 2011-03-19T12:34:20.667 に答える
1
これには 2 つの部分があります。1) 旗を探す 2) 家に帰る
検索部分では、完全なループを作成するたびに、ホームポイントを外側に移動して周回します. このようにして、すべての正方形を検索し、それが明確な場所、障害物、マップの境界、またはフラグであるかどうかを識別できます。このようにして、環境のマップを作成できます。
フラグが見つかったら、同じ方法で戻るか、より直接的なルートを見つけることができます。より直接的なルートである場合は、作成したマップを使用して直接的なルートを見つける必要があります。
于 2011-03-19T13:32:21.533 に答える
1
単純なDFS検索で、少なくともフラグが見つかります:)
于 2011-03-19T11:42:56.480 に答える
0
障害物に遭遇した場合は、正確な寸法を決定するために一周し、測定後に前のコースに戻ることができます。視界に障害物がなければ、最も近い未確認のエリアの方向に向かおうとすることができます。
最速の方法とは思えないかもしれませんが、始めるには良いポイントだと思います。
于 2011-03-19T11:58:37.190 に答える
0
あなたが望むのは、ロボットのビューポートですべての最小スパニングツリーを見つけて、ロボットが移動したいゲームをロボットにさせることです。
于 2011-03-19T11:43:15.717 に答える
0
アプローチは、ロボットが移動するときにグラフを作成することだと思います。グリッドの特定の状態をロボットに返す関数があります。ロボットは事前にグリッドの状態を認識しないため、これが必要です。
検索にヒューリスティックを適用して、フラグに到達する確率を高めることができます。
于 2011-03-19T12:36:41.317 に答える
0
多くの人が言及しているように、A* は、自分の現在地と目標がどこにあるかを知っている場合、グローバルな計画に適しています。しかし、このグローバルな知識がない場合は、調査すべき「バグ」アルゴリズムと呼ばれるアルゴリズムのクラスがあります。
探索に関しては、フラグを最速で見つけたい場合は、ボットが見ることができるローカルの近隣の範囲に応じて、この近隣が重複しないようにする必要があります。たとえば、ボットが周囲の 1 つのセルをあらゆる方向に見ることができる場合、3 列ごとに探索する必要があります。(列 1、4、7 など)。しかし、ボットが現在占有しているセルしか見ることができない場合、最も最適な方法は、既にアクセスしたセルに戻らないことです。
于 2012-09-16T22:14:09.733 に答える