障害物回避ロボットの自由空間に最短経路を見つけるアルゴリズムはありますか？

Question

ロボットは、グリッドのない平面上のある点から別の点に移動する必要があると考えてください。森などのようなものがあれば、最短経路をどうやって見つけるのですか？私はグリッドがA *アルゴリズムを使用できることを知っています。しかし、私が達成しようとしているもう一つの例は、それが人間への最短経路であることを見出そうとしているテレーンに関する優れた知識を持つゾンビです。

Answer 1

ロボット/ゾンビがポイントであるという単純な仮定をすると、これをより扱い易いものに減らすことができます。

これは、適合しているかどうかを確認するなどのことを避けるためです。ロボット/ゾンビが円の場合は、障害物のすべてのエッジを円の荒さによってオブジェクトの外側に移動させることで、他のすべてのオブジェクトを「太くする」ことができます。ロボット/ゾンビが矩形である場合、エッジを押し出すことはできますが、キューブのディメンションを使用して行いますが、矩形を回転させる必要はありません。

一度ポイントのパスを見つけようとすると、そのパスはより簡単になります。グラフのノードとして、「太い」ポリゴンの障害物の各頂点を変換し、それを直接目に見える（障害物を通らない）すべてのノードに接続します。あなたが3Dであれば、エッジを考慮する必要があり、問題はもう少し面倒になります。

グラフを作成したら、A */Dijkstra /何でも問題に対応できます。

本当に正確な結果が必要な場合は、コーナーを回ると円弧セグメント上を移動するため、ロボット/コンビが円の場合はコーナーを注意する必要があります。あなたがゲーム/シミュレーションを実行している場合、非常に薄い障害物や比較的大きな円/ロボット/ゾンビを除いて、その違いは目に見えません。

設定が静的な場合は、パフォーマンスを事前に計算できます。また、ノードの数は障害物の頂点の数に依存するため、経路探索のために低品質のオブジェクトで実行する価値があります。