模型预测控制在运动规划中的应用 Introduction 线性MPC解决的优化问题一般是凸的 非线性MPC解决的优化问题一般是非凸的 模型 系统模型（描述系统自身） 问题模型（描述优化目标） 预测 状态空间 输入空间 参数空间 💡 示例 实际的输入F是连续，这会使得优化问题的维度是无限维，因此可以进行一些操作，把输入空间转化为参数空间，比如把力的优化看做多项式，进而将求最优的F转为求最优多项式参数。 控制（选择最优的输入或策略） x∉Obstaclex\notin Obstaclex∈/Obstacle也相当于不等式约束，但由于该约束一般为非凸
基于马尔科夫决策过程的运动规划 Planning with Uncertainties 在实际应用中，机器人的执行和状态估计都存在不确定性 不确定的分类：nondeterministic（不知道不确定性的来源）、probabilistic（机器人能够估计不确定性） 两种Game的方式： Independent Game——robot action space和nature action space相互独立（P(θ)P(\theta)P(θ)） Dependent Game——nature action space与robot action space有关（P(θ∣u)P(\thet
硬约束及软约束下的轨迹优化 概述 Minimum snap的优缺点： 优点 轨迹一定会经过中间路点 可以闭式的求解出轨迹上每一处的状态信息 构造了一个凸优化问题，可以闭式和数值求解 缺点 可以生成平滑的轨迹，但没有考虑避障 解决方法： Adding forces：添加推力或吸力，使轨迹往远离障碍物的地方拉——软约束 Adding bounds：添加区域约束，使轨迹必须处于区域当中——硬约束 硬约束——相当于给优化问题施加一些等式或不等式的约束，要求轨迹必须严格地满足约束 软约束——相当于给优化问题加上惩罚函数（比如靠近障碍物时，惩罚函数就会增大），不一定严格地满足
基于Minimumsnap的轨迹优化 概述以及基础 轨迹优化的作用：提高解的质量 Path quality Time efficiency 边界条件：起点、终点 中间条件：路点（前段路径规划生成的中间节点） 平滑准则 全维度的状态空间（XXX）里的路径规划问题可以转化为低维度的平坦的输出空间（σ\sigmaσ）里的路径规划问题（要求：全维度的状态空间（XXX）可以被平坦的输出空间（σ\sigmaσ）以代数组合的形式表示） 对于欠驱动的四旋翼来说，可以选择σ=[x,y,z,ψ]τ\sigma=[x,y,z,\psi]^{\tau}σ=[x,y,z,ψ]τ来作为平坦的输出空间（SE(3
满足动力学约束的路径规划 概述 满足运动学约束（Kinematic）和动力学约束（Dynamic） 约束一般要考虑到力的层级（加速度） 机器人有一定的动力学模型，不能当成质点来处理，考虑机器人高阶的约束 从粗到细的优化过程 轨迹只需要局部优化 该模型前轮负责转向，后轮负责驱动 上述公式角速度计算公式有误——应为vLtanϕ{v \over L}tan{\phi}Lvtanϕ 一些经典的动力学模型 状态栅格搜索算法（State Lattice Planning） 搜索算法的核心是如何根据使用场景来构建一颗搜索树： A*和PRM等算法就是先构建好搜索图，再构建搜索树 RRT是
基于采样的路径规划 采样基础： 不用显式的构造机器人的工作空间及其边界，只需要指出单个机器人是否发生了碰撞 完备的规划器、概率完备的规划器、解析完备的规划器（和概率完备的规划器类似，但采样是基于固定的栅格） Probabilistic Road Map（概率路图） PRM的两个阶段： 学习阶段：随机撒点，生成一个图结构 采样：基于一定的采样规则，随机采样；删除有障碍碰撞的点 连接（起点和终点要连接）：过远的点之间不用连接，删除掉连接有障碍物碰撞的线段 查询阶段：快速找到路径（利用A*和Dijkstra算法） 优点：概率完备、效率高 缺点：要求先学习再查询（在学习阶
基于图搜索的路径规划 图搜索基础： 机器人的配置、机器人的自由度、机器人的配置空间 把工作空间中的障碍物转化为配置空间中的障碍物——障碍物膨胀（在运动规划之前进行） 路径规划是在机器人的配置空间下进行的——机器人可以看做一个质点 对于任何一个搜索算法：构造搜索图 搜索图提供了搜索树，回溯节点得到路径 图搜索算法总体框架： 维护一个存储所有要访问的节点的容器 这个容器用起始节点初始化 循环 根据某些指标访问容器中的一个节点（Visit and Remove） 扩展节点：包含该节点的所有邻居 把邻居节点塞回容器 结束循环 访问过的节点不能再访问 BFS和DFS算法：
SUMMARY 学院派的规划流程 前端路径搜索（path finding） 寻找一个初始的、安全的路径 低维的、离散的空间 基于搜索（search-based）的路径规划 Dijkstra and A* Jump Point Search 基于随机采样（sampling-based）的路径规划 概率路线图（PRM） Rapidly-exploring Random Tree（RRT） and RRT* 满足动力学要求的路径规划 State Lattice Search Kinodynamic RRT*（基于随机采样） Hybrid A*（基于搜索） 后端
