java - ロボットのパスの平滑化

Question

多角形の障害物がある平面上のロボットの最短経路を計算しています。すべてがうまく機能し、高速で、問題はありません。しかし、どうすればパスが曲がりくねるように滑らかになるのでしょうか? 以下は、頂点を直線で結ぶパスの図です。PS Robot はただの円です。

Answer 1

この紙は役に立つかもしれません。それは自明ではない問題のようです。概要：

自動グラフ ドローワーは、単純な多角形の頂点間のパスを計算する必要があります。これは、内部に留まることに加えて、特定の美的特性を示す必要があります。これらのいくつかは、実際の最短経路から離れすぎないように、多角形に関する何らかの情報を組み込む必要があります。単純な多角形の 2 つの頂点間の最短ユークリッド パスを「含む」局所的な凸領域を計算するアルゴリズムを提示します。領域には、最短パス形状に「追従する」境界形状があります。領域内部の 3 次ベジエ スプラインは、指定された 2 つの頂点間に「短く滑らかな」衝突のない曲線を提供します。得られた結果は審美的に心地よいようであり、使用される方法は独立した興味深いものになる可能性があります。それらは基本的で実装可能です。

Answer 2

Teragenでレンダリングされるリアルな飛行シーケンスを作成しようとするとき、私はパス計算手法をよく試していました。最初はベジェ曲線を使ってみました。

しかし、（少なくとも飛行するために）それらはそれほど有用ではないことを発見しました。その理由は、曲線間の曲率が不連続であるため、フライバイの連続的な正しいバンク角度を計算するために使用できないためです。また、カーブが山と交差していないことを確認するのは難しいです。

私は逸脱します。私が最終的に決めた方法は、単純なマススプリングベースのパスであり、それをリラックスして提出しました。

パスを多くの小さなセグメントに分割すると、より多くのメリットがあります。各ポイントについて、ポイントとその隣接ポイントとの間の角度が小さくなり、障害物から離れる方向に少し移動します。パスが落ち着くまで何度も繰り返します。

k = 0.01    // Adjust the values of k and j to your liking.
j = 0.01    // Small values take longer to settle. Larger values are unstable.
For each point P
    normal_vector     = vector_to_previous_point + vector_to_next_point
    obstacle_vector   = vector_to_nearest_obstacle
    obstacle_distance = magnitude(obstacle_vector)
    obstacle_vector  *= obstacle_distance^2
    P                += (normal_vector * k) - (obstacle_vector * j)

これらの種類の有限要素緩和法の利点は、あらゆる種類の制約をプログラムできることです。パスは、重み（この場合はjとk）に応じて、それらの間の妥協点に落ち着きます。

---

ロボット工学に興味があるなら、ロボット工学の提案に参加してみませんか？

Answer 3

ロボットの場合、未来はわかりません。ロボットの位置と障害物だけを知って、各点を描画する必要があります。最小の長さの曲線パスを作成する通常の方法は、ロボットを円でモデル化し、障害物との接触を維持するように円を移動することです。半径を1つ離すだけで、ターンはカーブになります。

最小距離ではなく曲線が必要な場合は、上記の半径をポリゴン頂点からの距離に比例させてみてください。

ベジエ曲線のアイデアは、振り返ってみるとパスを湾曲させるためにのみ機能します。ロボットがいた場所が変わります。通常、ロボットが過去を変えることは「不正行為」と呼ばれます。すでに歩んできた道を変える必要がないようにする 1 つの方法は、先を見据えることです。しかし、ロボットは隅々まで見ることができますか? ルールをより適切に指定する必要があります。