円形障害物における経路探索 (2017)

2017年3月森の中をナビゲートするA*経路探索アルゴリズムは、最適なパスを迅速に生成するための強力な手法です。通常、A*はグリッドベースのマップをナビゲートするデモンストレーションに使われますが、A*は単なるグリッドアルゴリズムではありません！ あらゆるグラフで機能します。このアルゴリズムを使って、円形の障害物がある世界を通過するパスを見つけることができます。同じアルゴリズムが両方の問題をどのように解決するのでしょうか？ まずA*の仕組みのレビューから始めましょう。A*アルゴリズムA*アルゴリズムは、開始点から終了点までの最適なパスを見つけ、その途中で障害物を回避します。これは、部分的なパスのセットを徐々に拡張することによって行われます。各部分パスは、開始点からゴールまでの途中にある中間点までのステップのシリーズです。A*が進むにつれて、部分パスはゴールポイントにますます近づいていきます。アルゴリズムは、残りの可能性よりも優れていると証明できる完全なパスを見つけたときに終了します。アルゴリズムの各ステップで、A*は部分パスのセットを評価し、セットの中で最も有望なパスを拡張することによっていくつかの新しいパスを生成します。これを行うために、A*は部分パスを優先度付きキューに保持し、推定長（これまでのパスの実際の測定長に、ゴールまでの残りの距離の推測を加えたもの）でソートします。この推測は過小評価でなければなりません。つまり、推測は実際の距離よりも短くすることはできますが、長くすることはできません。ほとんどの経路探索問題では、良い過小評価は、部分パスの終点からゴールまでの幾何学的な直線距離です。部分パスの終点からゴールまでの実際の最良のパスは、この直線距離よりも長くなる可能性がありますが、短くなることはありません。A*が開始するとき、優先度付きキューには1つの部分パスしか含まれていません。開始点です。アルゴリズムは、優先度付きキューから最も有望なパス（つまり、推定長が最小のパス）を繰り返し削除することによって機能します。このパスがゴールポイントで終わる場合、アルゴリズムは完了です。優先度付きキューは、他のどのパスもそれより良くならないことを保証します。そうでない場合、キューから削除した部分パスの終点を開始点として、A*はすべての可能な方向に1ステップずつ進むことによっていくつかの新しいパスを生成します。これらの新しいパスを優先度付きキューに戻し、プロセスを再度開始します。グラフA*はグラフ上で機能します。グラフは、エッジで接続されたノードのコレクションです。グリッドベースの世界では、各ノードは個々のグリッド位置を表し、各エッジは北、南、東、西の隣接位置への接続を表します。A*を円形障害物の森で実行する前に、それをグラフに変換する必要があります。森を通過するすべてのパスは、線分と円弧セクションが交互に繰り返されます。これらはパスグラフのエッジです。これらのエッジの終点がノードになります。グラフ上のパスは、エッジで接続されたノードのシリーズです。セグメントとアークの両方がグラフのエッジとして機能します。セグメントをサーフィンエッジと呼びます。パスが障害物をサーフィンするためにそれらを使用するためです。アークをハギングエッジと呼びます。パスでの目的は障害物の側面に沿って進むためです。次に、障害物の森をグラフに変換する簡単な方法を探ります。可能なすべてのサーフィンエッジとハギングエッジを生成します。これは接線可視性グラフと呼ばれます。サーフィンエッジの生成2つの円の間のサーフィンエッジは、両方の円をわずかにかすめる線分です。これらの線分はビットージェントとして知られており、各円のペアに対して4つあります。円の間を横切るビットージェントは内部ビットージェントであり、外側を沿って進むものは外部ビットージェントです。内部ビットージェント歴史的に、内部ビットージェントは、異なるサイズの2つのプーリーを横切るベルトの長さを計算するために重要でした。そのため、内部ビットージェントを構築する問題はベルト問題として知られています。内部ビットージェントを見つけるには、以下の図の角度 hetaを計算します。重なり合う円にはビットージェントがありません。中心が点AとB、半径がrAとrB、中心間距離がdの円が与えられた場合、 heta = arccos((rA+rB)/d)となります。 hetaがわかると、点C、D、E、Fを見つけるのは簡単です。外部ビットージェント外部ビットージェント（プーリー問題）の構築は、同様の技術を使用します。小さい円がより大きい円に完全に含まれている場合、外部ビットージェントのために hetaを次のように見つけることができます。 heta = arccos(|rA - rB| / d)。円AまたはBのどちらが大きいかは関係ありませんが、図に示すように、 hetaはAからBへの側に出現しますが、Bから離れる側に出現します。視線取って、2つの円間の内部ビットージェントと外部ビットージェントは、円間のサーフィンエッジを構成します。しかし、3番目の円が1つ以上のサーフィンエッジをブロックしている場合はどうでしょうか？円が視線を遮るAとBはお互いから見える場合、サーフィンエッジが別の円によってブロックされている場合は、そのエッジを破棄する必要があります。このケースを検出するために、単純な点線距離計算を使用します。サーフィンエッジから障害物の中心までの距離が障害物の半径より小さい場合、障害物はサーフィンエッジをブロックしているため、エッジを破棄する必要があります。点Cから線分ABまでの距離を計算するには、次の方法を使用します。まず、垂直な昇順子が点Cに当たる線分AB上の距離の割合であるuを計算します。u = ((C - A)・(B-A)) / ((B-A)・(B-A))次に、AB上の位置Eを計算します。E = A + clamp(u, 0, 1) * (B - A)0 1 u={{Math.round(100*(C.x-A.x)/(B.x-A.x))/100}} d rCから線分ABまでの距離dは、CからEまでの距離です。d = ||E - C||d < rの場合、円はAからBへの視線をブロックしているため、エッジを破棄する必要があります。d >= rの場合、AからBへの視線があり、エッジを保持する必要があります。d >= rのケースを見るために円を移動してみてくださいd < r。ハギングエッジの生成グラフノードは、サーフィンエッジをハギングエッジに接続します。前のセクションでサーフィンエッジを生成しました。ハギングエッジを生成するには、サーフィンエッジの終点から開始し、円の周りを移動し、別のサーフィンエッジの終点で終了します。円のハギングエッジのセットを見つけるには、まず円に接触するすべてのサーフィンエッジを見つけます。次に、円上のすべてのサーフィンエッジの終点間にハギングエッジを作成します。すべてをまとめるサーフィンエッジ、ハギングエッジ、ノードの生成、およびブロックされたサーフィンエッジの除外により、グラフを生成し、A*アルゴリズムを使用して経路探索を実行できます。拡張議論したグラフ生成手順は、アルゴリズムを説明するには十分ですが、改善できる点はたくさんあります。これらの拡張により、アルゴリズムはCPUとメモリの使用量を減らし、より多くのケースを処理できるようになります。いくつか見てみましょう。接触する障害物おそらくお気づきかもしれませんが、これまでの例の円形障害物は重なったり接触したりしていませんでした。円が接触することを許可すると、経路探索問題は少しだけ難しくなりますが、それほど大きくはありません。ビットージェント内部ビットージェントのこの式でビットージェントを見つけることができることを思い出してください。 heta = arccos((rA+rB)/d)外部ビットージェントのこの式: heta = arccos(|rA - rB| / d)2つの円が接触または重なっている場合、それらの間に内部ビットージェントはありません。この場合、(rA+rB)/dは1より大きくなります。arccosはドメイン[-1, 1]外の入力に対して未定義であるため、arccosを実行する前に円の重なりを確認することが重要です。同様に、一方の円がもう一方の円を完全に囲んでいる場合、それらの間に外部ビットージェントはありません。この場合、(rA - rB) / dは範囲[-1, 1]外であり、arccosを持ちません。円は重なりません：外部と両方