連続スペース最短パス

Question

実生活ロボットを制御するための最短経路アルゴリズムが必要です。

私は、行列の形で環境のマップを持っていますが、1は障害物、0は空きスペースです。 A *のような従来の最短経路アルゴリズムを使用すると、マンハッタン距離の最短経路が得られます。したがって、実際の最短経路にはどこもありません。この問題は、対角線が2つの直線よりも優れているように動きをペナルティする方法を考えることができないために発生します。私は、A *が最初に2点間の最短経路を試すようなヒューリスティックを作ることができますが、実際にはユークリッド最短経路をより良い経路にしません。

連続スペース最短パスを取得する方法を知っている人はいますか？それは実際の最適経路である必要はありませんが、直線と90度の角度よりも優れています。

私は一つのアイデアを持っています： 出発点から丸を作ってください。 円の1点が壁の横にあるか、目標になるまで円の半径を大きくします。円の端にあるすべての点は、円の半径のペナルティを持つ子ノードとして設定されます。サークル内のすべての点（開いていない点）は、テストする理由がないため閉じられます。目標状態に達するまでヒューリスティックなユークリッド最短経路を持つA *の方法でこれを繰り返します。ロボットをある点から次の点にまっすぐに移動させます。

これは、私が探しているものに近いものを与えるはずです。さまざまな角度の直線のセット。もちろん、連続した曲線の線でもっと良いでしょう...

Answer 1

私は連続した空間パス計画アルゴリズムを実装し、それについてはhereをブログに書きました。単純なgradient descentアルゴリズムを使用することで、A *を使用して最初の見積もりを取得し、それを確定します（また、目的地での鋭い回転とロボットの方向付けをペナルティ化します）。

のは、*から離散パスはn「ウェイポイント」（グリッド上の座標を）持っているとしましょう。最初と最後のものは移動できませんが、パスがブロックされたグリッドセルを通過しない限り、他のものはできます。最小化される関数は、現在の方向に垂直なウェイポイントを移動するパラメータn - 2によってパラメータ化されます。