路径规划：基于kinodynamic的路径搜索

一、介绍

1、概念

kinodynamic规划问题是综合机器人的运动，同时受到运动学约束（如避开障碍物）和动力学约束（如速度、加速度和力的模量边界）。它的解是从时间到广义力或加速度的映射。传统的路径规划包括前端的路径搜索和后端的轨迹优化两部分。

**目的：**之所以要在前端考虑动力学约束，是为了减轻后端优化的负担，kinodynamic planning是从粗到精的过程；轨迹仅局部优化；不可行路径对非完整系统毫无意义；

2、车辆模型

（1）单车模型
（2）差速驱动模型

http://planning.cs.uiuc.edu/node659.html
（3）Simple car mode / Reeds & Shepp’s car / Dubin’s car

http://planning.cs.uiuc.edu/node658.html

二、 State Lattice Planner

状态栅格规划器(State Lattice Planner)是一种基于采样的满足动力学约束的路径规划算法。

1、基本思想

A*、RRT等算法可以建立一个用于路径搜索的图模型，得到搜索树用于解决路径规划问题。但得到的图模型对真实机器人系统未必可行。因此我们需要在图的节点之间建立可行的运动连接。s =f(s,u)，其中s为状态变量，u 为控制变量：

(1)两种方法：
正向：基于控制空间的采样；
前向模拟；固定控制量和一个时间间隔T；没有任务导向；容易实现；低规划效率；

反向：基于状态空间的采样。
给定了被控对象的初始状态和目标状态；反向计算u和T；好的任务导向，实现困难；规划效率高；需要对两点的边界值问题进行求解；

2、边界值问题(Boundary Value Problem, BVP)

参考：
https://blog.csdn.net/space_dandy/article/details/114396542

三、 Kinodynamic RRT*

参考：
https://blog.csdn.net/qq_37087723/article/details/113846316

四、 Hybrid A*

1、基本思想：

保证一个网格里只有一个节点。

2、启发函数设计：

（1）2维的欧式距离
（2）不考虑障碍物的非完整式（满足动力学约束）
（3）不考虑障碍物的非完整式（满足动力学约束）+ 忽略了汽车的非完整性，考虑障碍物。

3、Analytic Expansions

基于控制空间采样（离散化）效率较低，因为没有对目标偏差进行编码。我们手动添加（尝试）状态空间采样。

搜索树直接搜索出一条到终点状态的最优路径。（理论上最短，检查满足动力学约束等因素）如：设置概率N=20，扩展20个节点one shot一次。tirck: 距离越近，N越小。

参考链接：
与A*区别：https://blog.csdn.net/qq_31815513/article/details/88709640
论文解读：https://blog.csdn.net/qq_41871826/article/details/107431021
代码实现：https://github.com/teddyluo/hybrid-a-star-annotation
相关文献：https://blog.csdn.net/luohuiwu/article/details/103181609/
推荐课程：深蓝学院移动机器人运动规划学习课程

内容皆来源于网络和参考链接整理，侵权联系删。