0

フィールド内のオブジェクトを見つけるための速度の観点から、最良のアルゴリズムは何でしょうか？

フィールドは、一辺の長さが30.48cmの18x18の正方形で構成されています。ロボットは正方形（0,0）に配置され、途中の障害物を避けながら光源に到達することがその役割です。光源を見つけるために、ロボットは360度回転して、最も高い光の読み取り値を持つ角度を見つけてから、光源に向かって移動します。100cmからの光源を確実に検出できます。

現在これを実装している方法は、各タイルに関する情報を2x2配列に格納していることです。タイルの可能な値は、未探索（デフォルト）、ブロック（障害物がある）、空（そこには何もない）です。子が位置（i + 3、j）または（i、j + 3）にあるDFSアルゴリズムを使用することを考えています。ただし、各子の光の読み取り値が最も高い角度を特定するために回転を行うことを考えると、DFSよりも高速に光源を特定できるアルゴリズムがあるのではないかと思います。また、ロボットは床のグリッド線を使用してxとyの位置を修正するため、x方向とy方向にのみ移動します。

このタスクを実行するために、高速で信頼性の高いアルゴリズムを提案できれば幸いです。

4

2 に答える 2

0

これは非常に幅広い質問であり、私は専門家ではないため、私の答えは、現場での経験ではなく、「第一原理」の考え方に基づいています。

（ロボットの視線と動きは一般的に遮るものがないと想定しています。つまり、迷路ではなく、障害物が点在するオープンエリアです。）

問題は、360度スキャンから取得した情報を解釈することです。

  • ロボットが光源を見る場合、光源へのルートをたどるのは簡単であるか、「単純な」迷路歩行タスクです。

  • 難しいのは、ソースが表示されない場合です。ソースが可視範囲内にないことを意味している可能性があります。しかし、それはまた、光が障害物の後ろにあることを意味する可能性があります。残念ながら、あなたが説明しているような単純なセンサーでは、これら2つのケースを区別できません。

センサーシステムで障害物を確認できる場合は、「影」の領域（障害物の背後の領域）の位置をプロットし、それを使用して検索する場所を追跡できます。したがって、あなたの戦略は、少数の場所を訪問し、それぞれでスキャンを実行してから、影になっている少数の領域を系統的に「整理」することです。

ただし、シャドウ領域がどこにあるかを簡単に判断することはできないため、（最終的には）どこでも検索するアルゴリズムが必要です。DFSはあらゆる場所を検索する一般的な戦略ですが、（事実上）隅と隅を最初に調べることによってそれを実行します。より良い戦略は、幅優先探索を行い、大規模なスキャンで光源が見つからなかった場合にのみ、隅々までアクセスすることです。

このタスクを実行するために、高速で信頼性の高いアルゴリズムを提案できれば幸いです。

自分で開発する必要があると思います。（これが問題/タスク/競争のポイントではありませんか？）

于 2012-11-09T23:55:30.640 に答える
0

そうは見えないかもしれませんが、これは何よりも迷路をたどる問題のように見えます。これはある種のチャレンジまたはコンテストの状況だと思います。最初から目標への道は常に存在しますが、一瞬も道がないとします。障害物に完全に囲まれたビーコンをナビゲートするロボットの成功した結果の 1 つは、信号を取り囲む障害物の閉じた経路の説明を含むレポートです。そのような閉じた道がなければ、どこかに穴を見つけることができます。これが迷路のように見える理由です。

したがって、私が選択する基本的なアルゴリズムは、内向きのらせん状のトラバーサルから開始し、ビーコンが存在する場合にビーコンが確実に見えるように、十分に狭いパスを一掃することです。障害物がない場合 (縮退の場合)、最短時間でターゲットを見つけます。(ヒント: ターンごとに、センサーがステップごとに検出できるセルの数が減ります。)

らせん状のトラバーサルを反時計回りにします。あなたが持っているものは、右手を壁に置き、生成されたパスに従うことによって迷路を解決するためのルールに関連しています. この場合、迷路の開始点は境界上にあっても、終了点はそうでない可能性があるという複雑な問題があります。このような状況では、右手に触れるパスが失敗する可能性があります。この状況を検出するには、壁に隣接することによって一掃された領域で「空洞」を探す必要があります。

于 2012-11-10T00:25:02.463 に答える