デュビンズパス

幾何学において、デュビンの経路とは、通常、二次元ユークリッド平面（すなわちxy平面）上の二点を結ぶ最短曲線のことを指す。この経路の曲率には制約があり、経路の始端接線と終端接線は規定されており、経路を走行する車両は前進のみ可能であるという仮定が置かれている。車両が後進も可能な場合、経路はリード・シェップ曲線に従う。^{[ 1 ]}

レスター・イーライ・デュビンズ（1920–2010）^{[ 2 ]は、解析学}^{[ 3 ]}のツールを用いて、そのような経路はいずれも最大曲率と直線部分、あるいはその両方で構成されることを証明した。言い換えれば、最短経路は最大曲率の円弧と直線を結んだものとなる。

議論

デュビンズは1957年にその結果を証明した。1974年、ハロルド・H・ジョンソンはポンチャギンの最大値原理を適用してデュビンズの結果を証明した。^{[ 4 ]}特に、ハロルド・H・ジョンソンは、区分連続曲率を有界とし、始点、終点、方向を規定した平面曲線が最小の長さを持つための必要十分条件を提示した。1992年には、同じ結果がポンチャギンの最大値原理を用いて再び示された。^{[ 5 ]}最近では、J・アヤラ、D・キルゼンブラット、J・ハイアム・ルビンスタインによって幾何学的曲線理論による証明が行われた。^{[ 6 ]}ホモトピー類におけるデュビンズのパスを特徴付ける証明は、J・アヤラによって与えられた。^{[ 7 ]}

アプリケーション

デュビンズ経路は、ロボット工学や制御理論の分野で、車輪付きロボット、飛行機、水中車両の経路計画に広く用いられています。最適経路を計算するための単純な幾何学的手法^{[ 8 ]}と解析的手法^{[ 9 ]があります。}

例えば、車輪付きロボットの場合、システムの単純な運動学的車両モデル（デュビンズ車両とも呼ばれる）は次のようになります。ここで、は車両の位置、は進行方向、車両は一定速度で移動しており、旋回速度制御は制限されています。この場合、最大旋回速度は最小旋回半径（および最大曲率）に対応します。規定された初期接線と終端接線は、初期進行方向と終端進行方向に対応します。デュビンズ経路は、車輪付きロボットモデルで実行可能な、2つの有向点を結ぶ最短経路を提供します。 ${\begin{aligned}{\dot {x}}&=V\cos(\theta )\\{\dot {y}}&=V\sin(\theta )\\{\dot {\theta }}&=u\end{aligned}}$ $(x,y)$ $\theta$ $V$ $u$

最適なパスの種類は、車で「右折 (R)」、「左折 (L)」、または「直進 (S)」するのと類似して説明できます。最適なパスは、RSR、RSL、LSR、LSL、RLR、LRL の 6 つのタイプのうち少なくとも 1 つになります。たとえば、いくつかの初期位置と最終位置および接線に対して、最適なパスが「RSR」タイプであると示されているとします。この場合、これは右折円弧 (R) の後に直線セグメント (S) が続き、さらに別の右折円弧 (R) が続くことになります。このシーケンスで各セグメントに沿って適切な長さ移動すると、開始点 A と終了点 B を各エンドポイントで目的の接線で結び、指定された曲率を超えない最短曲線が形成されます。

RSLデュビンズのパス
RSRデュビンズの道
LRLデュビンズの道

デュビンの間隔問題

デュビンの区間問題はデュビンの経路問題の主要な変種であり、始点と終点における進行方向の区間が指定される。始点と終点における経路の接線方向は、指定された区間内に収まるように制約される。この問題は、幾何学的解析^{[ 10 ]またはポンチャギンの最小原理}^[¹¹^]を用いて解くことができる。

参考文献

^ Reeds, JA; Shepp, LA (1990). 「前進と後進の両方を行う車の最適経路」 . Pacific Journal of Mathematics . 145 (2): 367– 393. doi : 10.2140/pjm.1990.145.367 .
^ 「追悼レスター・イーライ・デュビンズ数学・統計学教授、カリフォルニア大学バークレー校名誉教授 1920–2010」カリフォルニア大学. 2011年9月15日時点のオリジナルよりアーカイブ。 2012年5月26日閲覧。
^ Dubins, LE (1957年7月). 「平均曲率の制約と、初期位置、終端位置、および接線が規定された最小長さの曲線について」. American Journal of Mathematics . 79 (3): 497– 516. doi : 10.2307/2372560 . JSTOR 2372560 .
^ジョンソン、ハロルド・H. (1974). 「平面曲線の幾何学への最大値原理の応用」 .アメリカ数学会報. 44 (2): 432– 435. doi : 10.1090/S0002-9939-1974-0348631-6 . MR 0348631 .
^ Boissonat, J.-D. ; Cerezo, A. ; Leblond, K. (1992年5月). 「平面における有界曲率の最短経路」(PDF) . IEEE国際ロボティクス・オートメーション会議論文集. 第3巻. ピスカタウェイ, ニュージャージー州. pp. 2315– 2320. doi : 10.1109/ROBOT.1992.220117 .
^ Ayala, José; Kirszenblat, David; Rubinstein, Hyam (2018). 「最短有界曲率路への幾何学的アプローチ」 . Communications in Analysis and Geometry . 26 (4): 679– 697. arXiv : 1403.4899 . doi : 10.4310/CAG.2018.v26.n4.a1 .
^ Ayala, José (2015). 「ホモトピー類における長さ最小化有界曲率路」 .トポロジーとその応用. 193 : 140–151 . arXiv : 1403.4930 . doi : 10.1016/j.topol.2015.06.008 .
^アニシ、デイヴィッド（2003年7月）「地上車両の最適運動制御」（PDF）（報告書）スウェーデン防衛研究庁。1650-1942年。
^ Bui, Xuan-Nam; Boissonnat, J.-D .; Soueres, P.; Laumond, J.-P. (1994年5月). 「Dubinsの非ホロノミックロボットのための最短経路合成」. IEEEロボティクス・オートメーション会議. 第1巻. サンディエゴ, カリフォルニア州. pp. 2– 7. doi : 10.1109/ROBOT.1994.351019 .
^ Manyam, Satyanarayana; Rathinam, Sivakumar (2016). 「Dubinの巡回セールスマン最適解の厳密な境界について」. Journal of Dynamic Systems, Measurement, and Control . 140 (7): 071013. arXiv : 1506.08752 . doi : 10.1115/1.4039099 . S2CID 16191780 .
^ Manyam, Satyanarayana G.; Rathinam, Sivakumar; Casbeer, David; Garcia, Eloy (2017). 「点列を通る最短Dubinsパスの厳密な境界設定」. Journal of Intelligent & Robotic Systems . 88 ( 2–4 ): 495–511 . doi : 10.1007/s10846-016-0459-4 . S2CID 30943273 .

外部リンク

Dubins Curves Archived 2016-03-22 at the Wayback Machine , from Planning Algorithms by Steven M. LaValle
Wolfram Demonstrations Projectのデモンストレーション、Dubins Car の等時線
Built Roboticsが作成したオープンソースの Python Reeds-Shepp 実装

[1] Reeds, JA; Shepp, LA (1990). 「前進と後進の両方を行う車の最適経路」 . Pacific Journal of Mathematics . 145 (2): 367– 393. doi : 10.2140/pjm.1990.145.367 .

[2] 「追悼レスター・イーライ・デュビンズ数学・統計学教授、カリフォルニア大学バークレー校名誉教授 1920–2010」カリフォルニア大学. 2011年9月15日時点のオリジナルよりアーカイブ。 2012年5月26日閲覧。

[3] Dubins, LE (1957年7月). 「平均曲率の制約と、初期位置、終端位置、および接線が規定された最小長さの曲線について」. American Journal of Mathematics . 79 (3): 497– 516. doi : 10.2307/2372560 . JSTOR 2372560 .

[4] ジョンソン、ハロルド・H. (1974). 「平面曲線の幾何学への最大値原理の応用」 .アメリカ数学会報. 44 (2): 432– 435. doi : 10.1090/S0002-9939-1974-0348631-6 . MR 0348631 .

[5] Boissonat, J.-D. ; Cerezo, A. ; Leblond, K. (1992年5月). 「平面における有界曲率の最短経路」(PDF) . IEEE国際ロボティクス・オートメーション会議論文集. 第3巻. ピスカタウェイ, ニュージャージー州. pp. 2315– 2320. doi : 10.1109/ROBOT.1992.220117 .

[6] Ayala, José; Kirszenblat, David; Rubinstein, Hyam (2018). 「最短有界曲率路への幾何学的アプローチ」 . Communications in Analysis and Geometry . 26 (4): 679– 697. arXiv : 1403.4899 . doi : 10.4310/CAG.2018.v26.n4.a1 .

[7] Ayala, José (2015). 「ホモトピー類における長さ最小化有界曲率路」 .トポロジーとその応用. 193 : 140–151 . arXiv : 1403.4930 . doi : 10.1016/j.topol.2015.06.008 .

[8] アニシ、デイヴィッド（2003年7月）「地上車両の最適運動制御」（PDF）（報告書）スウェーデン防衛研究庁。1650-1942年。

[9] Bui, Xuan-Nam; Boissonnat, J.-D .; Soueres, P.; Laumond, J.-P. (1994年5月). 「Dubinsの非ホロノミックロボットのための最短経路合成」. IEEEロボティクス・オートメーション会議. 第1巻. サンディエゴ, カリフォルニア州. pp. 2– 7. doi : 10.1109/ROBOT.1994.351019 .

[10] Manyam, Satyanarayana; Rathinam, Sivakumar (2016). 「Dubinの巡回セールスマン最適解の厳密な境界について」. Journal of Dynamic Systems, Measurement, and Control . 140 (7): 071013. arXiv : 1506.08752 . doi : 10.1115/1.4039099 . S2CID 16191780 .

[11] Manyam, Satyanarayana G.; Rathinam, Sivakumar; Casbeer, David; Garcia, Eloy (2017). 「点列を通る最短Dubinsパスの厳密な境界設定」. Journal of Intelligent & Robotic Systems . 88 ( 2–4 ): 495–511 . doi : 10.1007/s10846-016-0459-4 . S2CID 30943273 .

[ 1 ]

[ 2 ]は、解析学

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]があります。

[ 10 ]またはポンチャギンの最小原理

[