アルゴリズムを探していますが、どこから始めればよいかわかりません。
デカルトグラフで点 A から点 B に到達しようとしています。動きは RC カーの動きに制限されます: 後方、前方、左前方、右前方 (一定の回転半径。車は完全に回転するか、まったく回転しません)。
次のようなアルゴリズムを構築するにはどうすればよいですか。
turningRadius, initialPosition, initialOrientation, finalPosition
そして、finalPosition に到達するための順序付けられた一連のステップを生成しますか?
最終的なオリエンテーションが何であるかは気にしないことに注意してください。
ありがとう！
編集: これは離散ノードを持つグラフではなく、連続座標系であることに注意してください
問題が説明されている方法では、アルゴリズムは簡単で、2 つの簡単な手順のみが必要です。1) 車が B を直接指すまで (左または右に) 曲がりながら前進し、2) B にぶつかるまで直進します。
比較的トリッキーな部分は最初のステップだけです。B が初期位置で車の縦軸から左側にある場合、自然なアプローチは左に曲がることから始めることです。これは、点 B がそのような (半径 の) 左折によって生成される円形軌道の内側にない限り、機能しturningRadiusます。後者の場合、車は円を描くように走りますが、B を直接狙うことはできません。このような場合、正しい戦略は、実際には右折から始めて、車を B に向けるまで曲がり続けることです。
したがって、軌道に最適性の要件がない場合、最初のステップの最も単純なアルゴリズムは、無条件にポイントから「離れる」ことです。Bが車の縦軸の左側にある場合は右に曲がり、 B が右に ある 場合 は左に 曲がります . 車が直接 B に向けられるまで回転を続けます。これは少し不自然に聞こえますが、常に機能します。つまり、いつでも最終的に車を向けることができます。
より最適な (より短い) 軌道が必要な場合は、車の初期位置/方向に対する B の位置を分析し (「B は旋回円の内側にあるか、外側にあるか?」)、次の方向を選択する必要があります。それに応じて最初のターン。
一般的に、これは簡単な問題ではありません。これは、「差分制約下での計画」のカテゴリに分類されます。LaValleの本（ここからオンラインで入手可能）の最後の3つの章は、これを扱っています。特に、後方に移動しないことを除けば、RCカーに似た「Dubinscar」を扱っているセクション14.4.2を見てください。
「Dubinscarpathplanning」も検索してください。あなたはたくさんの論文を見つけるでしょう。
面白くて楽しいプロジェクトのようですね！特定のアルゴリズムの推奨事項を得るには、おそらくより詳細な情報を提供する必要があります.RC カーに取り付けられたある種の組み込みコントローラーで文字通りこれを実行することを期待していますか? それとも、ワークステーションで実行し、リモートで車を制御するためのアルゴリズムですか? （または、これは純粋に抽象的な演習であり、車はありません… awwww。）
どこから始めればよいかを理解するための私の一般的な推奨事項は、Building Problem Solversです。これは、「AI」問題解決技術の世界への優れた入門書です。最近は少し時代遅れかもしれませんが…待ってください、私は何を言っているのでしょう! おそらくそうではありません。:-)
[オーケー、最後のコメントを説明する必要があります。私が実際に見たほとんどの「最新の」AI 技術は、実際には何年も前のアイデアにまでさかのぼります…ムーアの法則の絶え間ない進歩のおかげで、それらは現在実用化されています。そのため、1993 年に書かれた本では、私が個人的に見たものから、かなり最先端の技術が議論されています。反例を教えていただきたいです!]
a* (a-star) を試してみましたか? また、地形図を提供すると便利です。地形のさまざまな部分に重みを割り当てることができます。これにより、さまざまなパスが得られます。デフォルトでは、アルゴリズムは斜め方向を提供しないと思いますが、それを非常に簡単に追加できます。
また、デフォルトでは「回転」を処理しませんが、a-star は完全なパスを提供します。できることは、2 点に基づいて回転半径を計算することです。現在の位置と次の計算された位置、または最後の位置と現在の位置。次に、角度の変化に合わせて向きを足したり引いたりすることができます。これを微調整する必要があるかもしれません。