AIDANGYA | 安静写些东西
2019-02-28 | Motion Planning | UNLOCK

国内运动规划论文阅读笔记（1）

浙大李柏—-《复杂约束下自动驾驶车辆运动规划的计算最优控制方法研究》

基本知识点

求解单一车辆运动规划问题的方法

图搜索方法、随机采样方法、曲线插值方法、机器学习方法、最优控制方法

图搜索方法（参考54）

==基本思想==是利用栅格或晶格将自由空间转化为某种图，随后从图中搜索符合任务要求的路径。

主要步骤：1. 图的构造；2. 图中路径的搜索

构造方法：可是图法、Voronoi图法、栅格分解法

路径搜索：Dijkstra算法或 $A^*$ 算法

随机采样方法

==基本思想==是在构型空间（configuration space）中随机生成一系列样本点，并筛选满足任务需求的样本点序列作为规划结果。

优点 ：较之于图搜索方法，随机采样方法更适合求解高维度构型空间中的运动规划问题，并具有概率完备性。

缺点 ：无法精确处理复杂约束条件。

热门方法：概率路标算法（Probabilistic Roadmap Method, PRM），快速搜索随机树算法（Rapidly-exploring Random Tree， RRT）

PRM算法无法处理车辆运动中存在的微分方程等复杂约束条件，RRT算法适合解决具有微分方程约束限制的运动规划问题。

为了进一步提升RRT求解效率，人们提出了大量改进策略，例如基于双向搜索机制的RRT-connect、基于采样时效性管控的 $RRT^$ 、Anytime $RRT^$ 等。==RRT系列算法是当前最热门的路径规划方法之一==。

曲线插值方法

==基本思想== 通过预设的航路点（waypoint）拟合生成连续性、平滑性较好的路径。

常见方法：Dubins曲线法（非完整约束系统）、Reeds-Shepp曲线法、Clothoid曲线拟合法、多项式样条曲线拟合法（良好局部跟踪性质）。

优点：生成车辆运动路径一般具有可跟踪的性质，可配合其它方法进行路径/轨迹的平滑处理。

1551322017292

机器学习方法

增强学习[30,75,76]

动态优化方法（本文采样的方法）

车辆本质上属于动态系统，描述其动态特性的直接、准确方式是建立运动系统方程。在运动系统方程的基础上补充必要的约束条件及任务目标，即构成了最优控制问题（optimal control problem），有时也笼统将其称为动态优化（dynamic optimization）问题。

计算最优控制（computational optimal control）步骤：1. 利用配置点方法转化为时间离散的非线性规划；2. 采用梯度优化算法求解NLP问题；３.　将NLP求解得到的配置点还原为时间连续的车辆运动轨迹。

路径规划与轨迹规划的区别

路径规划 是指生成一条连接车辆行驶起点位置与终点位置，且不与环境中障碍物发生碰撞的几何路径。

轨迹规划 在路径规划的基础上添加了车辆沿路径行驶的时间相关约束条件（参考A Survey of Motion Planning and Control Techniques for Self-driving Urban Vehicles）。

运动规划环节的最终输出结果可以是路径或者轨迹，如果输出结果为路径，车辆的控制执行模块将跟踪这一几何路径；如果输出结果为轨迹，车辆将按照既定速度跟踪相应的几何路径。

多车协同运动规划方法（Multi-Vehicle Motion Planning，MVMP）

指在给定多辆汽车初始时刻运动状态、行驶目的以及约束条件的基础上，对各辆汽车的路径或轨迹进行求解的过
程[96]。

拟解决问题

  • 自动泊车
  • 多车协同变更车道
  • 无信号灯路口多车协同通行

工作内容

最优控制方法，具有准确、直接、客观、统一的优点。

本文采样计算最优控制方法，对精确建模、有效收敛、实时求解三大核心问题进行了研究

精确建模 ：如何选择模型描述车辆运动能力，如何筛选具有代表性的场景及任务，如何建立碰撞躲避约束条件，如何在建模过程中（从交通规则制定与场景布置等方面）体现无人驾驶与有人驾驶的区别。

有效收敛 ：在采用计算最优控制路线进行求解的前提下，如何选择离散化方式构造NLP（Nonlinear Programming）问题，选用何种优化算法求解NLP问题，如何保障NLP求解能够成功完成，如何提升NLP问题求解收敛效率。

实时求解 ：如何在线求解车辆运动轨迹；如何迅速对场景中的变化因素或不确定因素作出反应；当在线求解失败或未及时完成的情况发生后，如何进行应急处置。

如何验证

利用matlab进行仿真实验

对博士课题的启发

  1. 结合以模型为基础的计算科学及以数据样本为基础的人工智能—->概率机器人？
  2. 多车协同编队控制这一方向
  3. 单一车辆运动规划+强化学习

相关参考论文

增强学习

  • 刘春明．基于增强学习和车辆动力学的高速公路自主驾驶研究［博士学位论文］．长沙：国防科学技术大学
  • A deterministic improved Q-learning for path planning of a mobile robot.
  • 郑睿．基于增强学习的无人车辆智能决策方法研究［硕士学位论文］．长沙：国防科学技术大学

综述

  • 图搜索相关算法，刘华军，杨静宇，陆建峰，唐振民，赵春霞．移动机器人运动规划研究综述．中国工程科学
  • A Survey of Motion Planning and Control Techniques for Self-driving Urban Vehicles
  • Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions
  • Nonlinear programming for multi-vehicle motion planning with homotopy initialization strategies.

国防科大—-基于增强学习和车辆动力学的高速公路自主驾驶研究

控制与决策 是一个具有大规模连续空间以及多个优化目标的复杂序贯决策问题。

sequential decision—-序贯决策

generalization problem—-泛化问题

拟解决问题

  • 用于求解具有大规模连续空间以及多个优化目标的增强学习算法和理论
  • 高速公路环境中的车辆动力学仿真建模方法
  • 高速公路自主驾驶中的优化控制与决策方法

工作内容

算法研究

  • 研究了具有连续状态空间的增强学习问题，改进基于核的近似策略迭代方法（Kernel-based Least Squares Policy Iteration, KLSPI）
  • 研究了具有连续行为空间的增强学习问题，提出一个新的连续行为近似策略迭代（Continuous-action Approximate Policy Iteration, CAPI）算法
  • 结合结构化思想，提出基于二叉树空间分解的结构化近似策略迭代（Hierarchical Approximate Policy Iteration, HAPI）。针对多目标的增强学习问题，提出了求解MORL问题的基本框架以及基于序贯加权和MORL算法。

仿真实验

  • 高速公路中车流汇入的最短安全距离，基于增强学习的高速公路自主驾驶

国防科大—-基于增强学习的无人车辆智能决策方法研究

增强学习 （reinforcement learning）：一种不确定条件下的序贯决策机器学习框架，多用MDP模型

  • 离散表格型算法，Q-学习算法、Sarsa-学习算法，引起”维数灾难”和不适于连续状态空间
  • 提高泛化和逼近能力，提出函数值逼近方法。将最小二乘方法和策略迭代结合，得到最小二乘策略迭代算法（LSPI）

车道保持 ：指由于不存在超车条件使得车辆在行车道上行驶，车道保持又细分为==车速保持==和==车辆跟随== 。

车辆跟随中由两个重要概念：跟随距离和紧急制动距离

变道 ：指存在超车条件，车辆选择由行车道进入超车道或在超车完成后由超车道返回行车道的动作。虽然车辆的变道控制包含车辆的侧向控制和车辆的纵向控制 2部分，但是通过车辆的环境决定==是否变道只依赖于车辆的纵向速度==。需要对道路进行侧向跟踪

电子科大（硕士2018）——高动态环境下智能车局部路径规划研究

目标

提出一种有效的换道决策方法

论文内容

  • 参考速度和参考加速度规划
  • 换道可行性分析
  • 生成初始路径集合以及路径评价
  • 路径优化

方法

以车辆之间的安全距离和相对速度作为参考，动态调节智能车速度和加速度

基于多约束优化的局部路径规划方法

基于优化的路径规划算法，本文从==数值优化==的角度出发

1552355024710

文章具体内容

当前规划研究：障碍物轨迹、意图预测和车辆状态转移条件（换道条件，车道保持条件，速度和加速度调整，紧急制动）

Pivtoraiko提出一种考虑移动平台差分约束的路径搜索算法，构建一种满足移动平台差分运动约束 的==高维状态点lattice state==来构造整个状态空间。

常用规划算法：

  • 基于图搜索的算法
  • 基于随机采样的算法
  • 基于数值优化的算法

智能车运动学模型

1552391468809

​ 单车模型

后轴中心点设为$p_r(x_r,y_r)$ ，前轴中心点设为$p_f(x_f,y_f)$ ，两轴垂直距离为$l$ ，车头朝向为$\theta$ ，前轮转角为$\delta$ 。

​ 为了满足车辆前后轮都无侧滑的假设，即在平行于两轴方向车速都为0，对后轮的约束条件为：

$$\left(\dot{p_re_y}\right)cos(\theta)-\left(\dot{p_re_x}\right)sin(\theta)=0$$

对前轮约束条件为：

$$\left(\dot{p_re_y}\right)cos(\theta+\delta)-\left(\dot{p_re_x}\right)sin(\theta+\delta)=0$$

实验手段

利用ROS系统的导航架构及Stage仿真平台，其中导航环境基于ROS CostMap插件，加载至Stage仿真平台可任意修改和扩展。

湖大——陈廖杰（2017）欠驱动机器人系统的运动规划方法及应用研究

知识点

机器人规划算法根据环境信息的分类

  1. 环境信息全部先验已知，则可以通过确定性的运动规划方法获得最优的解决方案
    • 前向图搜索
    • 人工智能（启发式搜索）
  2. 环境信息不完全已知或存在不确定因素的动态环境
    • 基于势场
    • 基于采样，快速计算能力实时重规划
    • 利用机器学习（强化学习），环境中强不确定性

研究现状

  1. [83] H.Kurniawati利用部分可观测马氏决策过程（Partially observable Markov decision process, POMDP）构建框架处理移动机器人不确定动态环境中的运动规划问题，提高学习规划的效率，并通过二维和三维场景中仿真验证其有效性。

  2. [84.85] H.Bai先后提出基于贝叶斯强化学习的连续状态空间离线POMDP框架和连续状态空间持续观测的POMDP框架，[86] 紧接着又提出一种目的预判的在线POMDP框架用于解决移动小车在复杂动态城市环境中的路径规划。

  3. [87] D.Liu EM-MDP不确定情况下的机器人系统运动规划问题

  4. [88] A.Konar 改进型Q学习方法处理移动机器人路径规划问题，有效减少移动机器人的转角次数。

  5. 强化学习用途，机器人导航避障[191-193]，无人机路径规划[194-195]

    [83] Motion planning under uncertainty for robotic tasks with long time horizons. IJRR,2011

    [84] Planning how to learn, ICRA,2013

    [85] Integrated perception and planning in the continuous space: A POMDP approach,IJRR,2014

    [86] Intention-aware online POMDP planning for autonomous driving in a crowd,ICRA,2015

    [87] Episodic memory-based robotic planning under uncertainty, IEEE Transactions on Industrial Electronics,2017，作者为大连理工刘冬，其博士论文为《基于情景记忆的机器人认知行为学习与控制方法》

    [88] A deterministic improved Q-learning for path planning of a mobile robot, IEEE Transactions on Systems,2013

    [191] 移动机器人路径规划强化学习的初始化，2012

    [192] 未知动态环境中基于分层强化学习的移动机器人路径规划,2006

    [193] 动态环境中服务机器人的改进型地图学习规划，2015

    [194] Cooperative and geometric learning algorithm for path planning of UAVs with limited information, Automatica,2014

    [195] Geometric reinforcement learning for path planning of UAVs, IROS,2015

    新加坡国立大学Haoyu Bai研究方向为强化学习跟运动规划结合

    值得借鉴之处

  • 环境信息建模，障碍物利用概率模型，由Kim等人2008年提出[197]

    [197] Kim, Real-time path planning with limited information for autonomous unmanned air vehicles,Automatica,2008

​

中科大——杜明博（2016）基于人类驾驶行为的无人驾驶车辆行为决策与运动规划方法研究

本文作者为中科大“智能先锋Ⅱ”无人车的参与者之一。

研究方法

通过研究人类在综合交通场景下的驾驶行为决策过程，构建一种基于决策树的驾驶行为决策模型，并在此基础上通过深入研巧人类在驾驶过程中的视觉行为注意机制，提出一种基于驾驶员视觉行为的RRT运动规划方法。

行为决策理论

  • 理性决策理论
    • 所谓理性决策理论，就是认为决策者从完全理性的角度，根据其能巧获得的所有准确的、完全的决策信息，得出一个最优的或者具有最大效用的决策方案。
  • 行为决策理论
    • 强调从人类实际决策行为着手研究决策行为规律及其影响的行为决策理论。

运动规划方法概述

  1. 基于自由空间集合构造的规划方法

    • 可视图法（上世纪80年代广泛使用）
    • Voronoi图法（构建图时间复杂度低，实时性、平滑性好，但不能保证路径最优）
    • 栅格分解法（实时性更高，受限于搜索图的分辨率，CMU曾将其应用于越野环境下）

    三种方法先将起始位置、障碍物顶点及目标位置连接起来，构成一张可视图 ，然后利用图搜索算法得到最优路径。区别在于搜索图的构建方法。

  2. 前向图搜索方法

    • Dijkstra算法（经典最短路径搜索算法，1959年提出）
    • $A^$ 算法（栅格结构地图表现不错，受限于地图分辨率。Stanford在2008年DARPA比赛中采样混合$A^$ ）
    • $D^*$ 算法（适应动态搜索环境）
    • 人工势场法（基于势场的梯度变化得到最短距离路径，极易陷入局部极小值）

  3. 基于随机采样的规划方法

    具有一定的不确定性，即概率完备性

    • 概率路线图算法PRM（1994年提出，属于多查询搜索算法）
    • 快速搜索随机树算法RRT（1998年，单一查询的快速搜索随机数算法）
      • 该算法具有增量式生长特性，被广泛应用于动态环境、高维状态空间及存在运动动力学约束的环境中，2008年DARPA比赛MIT

  4. 智能化规划方法

    • 基于遗传算法的运动规划方法（可获得全局最优路径，但是无法满足实时性的要求）
    • 基于神经网络的运动规划方法（具体比较强的学习能力，但是网络的权值难以设定）

决策方法

有限状态机

Finite State Machine (FSM)，用来研巧有限个状态的计算及这些状态之间的转移和动作等行为的离散数学模型。

  • 有限状态集合，表示对象的不同状态
  • 输入集合，引起对象状态转换的触发事件集合
  • 状态转移规则集合，代表对象在接收到不同输入信息时从一个状态转移到另一个状态的规则

ID3决策树

车辆运动规划方法

本文整个规划过程中，分别引入了基于视觉行为的混合采样策略，基于车辆运动约束的度量函数以及基于Ｂ样条曲线的轨迹优化算法。

环境感知地图的表示方法

  • 拓扑地图表示法，又称路网地图
  • 度量地图表示法
    • 几何表示法
    • 空间分解法

非完整性约束

非完整性约束就是指含有系统广义坐标导数且不可积分的约束。由于无人车系统的速度项无法通过积分变换转化为系统对应的空间位置，使得系统控制变量个数少于系统位姿自由度，因此无人车就是一个典型的非完整性约束系统。

1552572694009

RRT轨迹优化方法

最大曲率约束 + B样条曲线相结合的连续曲率轨迹优化方法

新颖点

  1. 驾驶员视觉注意力机制

1552571949149

​ 2. 车辆转向约束加入RRT算法的度量函数，提高平滑度。连续曲率RRT算法

疑惑及未来可研究内容

  1. 速度控制中油门跟刹车是如何配合工作的？
  2. 局部目标生成器 ，清扫车里面$A^*$ 规划时如何实现的？
  3. 车辆编队的运动规划问题

中文运动规划综述阅读笔记

移动机器人运动规划研究综述—-刘华军

构型空间（C——空间），每一个位姿代表着机器人在物理空间中的位置和方位,机器人被当作一个点,运动规划问题就变成在位姿空间中寻找一条从起始位姿点到目标位姿点的连续路径。

基于随机采样的运动规划方法联合其他运动规划方法的智能化规划方法将是研究的重点和热点。

硕士答辩

夏浪，Hybrid $A^*$ ，数值优化

Op, $Op^*$ 对比

dissertation

评论加载中