多路径规划算法,路径规划算法仿真

　　参考：http://planning.cs.uiuc.edu/node821.html

　　常见的路径规划算法，如Dijkstra，A*，BFS算法，侧重于可及性，搜索速度和效率等。这些轨迹要么以网格的形式给出路径，要么以图形的形式给出路径，但实际上并没有考虑到实际机器人的运动特性。在这里，我们将介绍路径规划中常用的两条曲线，

。

　　杜宾斯曲线(Dubins curve)杜宾斯曲线通常用于机器人和控制理论领域，作为轮式机器人、飞机和水下机器人规划路径的一种方式。杜宾斯曲线给出了两个有向点之间的最短路径，实际上是可以遵循的。

　　简单的运动模型如下，

　　x=V c o s() dot { x }=V cos( theta)x =VCO()

　　y =V s I n() dot { y }=V sin( theta)y =Vsin()

　　= dot { theta }= mu=

　　其中(x，y)是车的位置， theta 是航向， mu 是转弯速度。在这种情况下，规划路径有几个限制。

　　最大速度V m a x V_{max} Vmax，最大转弯角度m a x phi _ {max} max，也对应于最小转弯半径。杜宾斯曲线可以用三种常见的运动来描述，S S S直，L L L L L左，R R R右。所以常见的集中动作可以总结如下：

　　{ LRL、R L R、L S L、L S R、塞尔维亚、RSR} LRL、RLR、LSL、塞尔维亚、塞尔维亚、塞尔维亚

　　这样的轨迹称为杜宾斯路径，两个有向点的最短路径可以如下：

　　看上图，rs d lr _ { alpha } s _ { d } l _ { gamma } rSD l由两个相切的圆和一条直线组成，而rlrr _ { alpha } l _ { beta } r _ { gamma } rlr，所以现在问题变成了

　　(RSL路径方程的例子：

　　最小转弯半径为r r r，q l (x l，y l， 1) q _ {l} (x l，y l， theta _ {1}) QL (XL，yl， 1)，q g (x g，y g， 2) q _ {g} (x

　　添加约束$y轴约束：y_G-y_l $$x轴约束：x_G-x_l $ 近似束： = 2 1 约束：-=_ 2-_ 1约束：=21总路径长度S=r s i n () d r s i n ()总路径长度S=r sin()d r sin()总路径长度S=rsin() d rsin()

　　我先不展示细节。方程式要列好。简而言之，最小转弯半径r r r确定后，就可以求解，，d d d，d，d。Reeds-Shepp曲线现在考虑Reeds-Shepp车。与Dubins的唯一区别是它可以倒退。

　　同理，Reeds-Shepp曲线增加了反向逻辑，可能的路径类型扩展了很多，可以规划成9类，共48种。

　　也要根据约束序列方程求解；我会在以后继续探索和完善…

　　Python有待完善

多路径规划算法,路径规划算法仿真

万老网