0.motion_planning_overview

运动规划 §

问题的分类法 §

• 在世界坐标系下的移动规划 vs. 在自身坐标系下的任务规划
  • 以世界坐标系作为参照系，在世界环境下移动的运动规划
    • 自行车模型：自动驾驶车辆
    • 质点模型：swarm robots、无人机
  • 以自身作为参照系，进行移动或任务导向
    • 下肢：腿足/轮足机器人，通过步态控制对机器人移动或姿态进行控制
      • 轮足与腿足的取舍：相比腿足，轮足在突然的启动/停止的时候需要通过下半身的加速度实现，因此需要额外的距离，在上身负载较重的时候可能会产生意外的碰撞或者使机器人倾倒。腿足则可以通过移动腿部产生新的支撑点克服这一问题。
    • 上肢：机械臂、双臂、多臂，完成操控类任务
      • 非接触式任务：
        • 机器人的社会属性：肢体语言、跳舞等
        • 喷涂涂料：路径规划，覆盖全部面积又不产生重合
      • 接触式任务：
        • 拾取、放下
        • 安装
        • 打磨、旋转阀门等需要保持持续接触且维持受力

    • 连续机器人 §

参考书籍 §

• Dance Notations and Robot Motion, Jean-Paul Laumond, and Naoko Abe, 2016

基础概念 §

运动规划时的不同空间的定义 §

任务空间Task space/操作空间Operational space，笛卡尔空间Cartesian space §

• 任务空间Task space由机器人的任务性质决定。一般而言，若任务为控制位置和方向，任务空间则为六维空间。

  • Modern Robotics: Mechanics, Planning, and Control一书中定义为 > The task space is a space in which the robot’s task can be naturally expressed. For example, if the task is to control the position of the tip of a marker on a board, then task space is the Euclidean plane. If the task is to control the position and orientation of a rigid body, then the task space is the 6-dimensional space of rigid body configurations.

• 控制器末端与任务相关的动态特性，主要用于力控/柔顺控制/调节刚度/阻抗控制/力位混控等（force control/joint complaince/active stiffness/impedance control/hybrid position/force control）

• 出处：Oussama Khatib, A Unified Approach for Motion and Force Control of Robot Manipulators: The Operational Space Formulation, IJRA 1987

  The description, analysis and control of manipulator systems with respect to the dynamic characteristics of their end-effectors has been the basic motivation in the research and development of the operational space formulation.

• 在机器人学语境下，Cartesian space一般为或的欧氏空间，即二维或三维的直角坐标系，一般用来表示移动机器人质心位姿或者机械臂上某一点的位姿（如机械臂末端）。一般而言是任务空间的子集（不包含方向）。

工作空间Workspace §

• 机械臂末端能到达的位姿的集合（可能包含方向） - Modern Robotics: Mechanics, Planning, and Control (Kevin M. Lynch)一书中定义为： > The workspace is a specification of the configurations that the end-effector of the robot can reach, and has nothing to do with a particular task. … The workspace is often defined in terms of the Cartesian points that can be reached by the end-effector, but it is also possible to include the orientation. The set of positions that can be reached with all possible orientations is sometimes called the dexterous workspace.

构型空间Configuration space(C-space)/Joint space §

• 对于机器人而言也即是其状态空间State space（Planning Algorithms, LaValle）
• 对机械臂而言为其每个关节的配置。
  • 根据Robot Modeling and Control (Mark W. Spong)一书的定义，对于机械臂而言即为其所有关节的配置（通过已知每个关节当前的值和正向运动学模型即可求得机械臂每一个点在当前笛卡尔坐标系中的位置，即构型）

  In the path planning literature, a complete specification of the location of every point on the robot is referred to as a configuration, and the set of all possible configurations is referred to as the configuration space. For our purposes, the vector of joint variables, , provides a convenient representation of a configuration. We will denote the configuration space by .

  • Modern Robotics: Mechanics, Planning, and Control (Kevin M. Lynch)一书中定义为：

    The C-space is the space of all possible configurations of a robot.

• 对于移动机器人而言，是排除障碍膨胀后的空间（相当于将机器人的体积纳入考虑，在障碍物外围设定安全范围）

零空间Null space §

• 当机器人构型存在冗余时（如七个自由度），会有多个解可以达成主要目的（primary goal），这些解即为null space

路径规划与轨迹规划的辨析 Path planning and trajectory planning §

• 路径Path和轨迹Trajectory的区别：Path为单纯的路径点，Trajectory在每个路径点的位置信息上加上了时间信息
• 举例：在规划了机械臂末端的路径后，求解得到每个状态得机械臂的关节构型，再通过多次曲线插值得到每个关节的轨迹

运动规划时不同空间的选取 §

• 在三维空间中确定关键点后，只对关键点求IK，将其转化到joint space。再在joint space对每个关节进行插值。
• 在三维空间中确定关键点后，根据实际问题的需求，在三维空间中对关键点插值形成运动曲线，然后逐点求IK。（计算量大）
• 直接在C-space中采用RRT等方式进行搜索，

求解路径规划问题 §

从末端位姿逐一求解IK： §

• 仅适用于不考虑避障与碰撞的情况
• 通过关键点求解IK，将工作空间中机械臂末端的目标位置逐一转换到关节空间对每个关节角度的配置
• 由关键点关节的位置生成一条平滑的位置曲线，关键点处曲线的斜率即为此处关节运动的速度
• 通过三次或五次多项式（cubic/quintic polynomial）对曲线进行插值，得出中间的关节位置
• 机器人执行插值后的结果
• 可能存在的问题：若机器人存在自由度冗余，一个机械臂末端位置可能对应多个IK解，尤其是在通过数值法求解时，两个关键点求解后机械臂可能会产生大幅的运动，使得中间插值得到的运动不连续（或者偏离预期的轨迹曲线较远）。

任务空间（task space）插值 §

旋转角的插值 §

• Slerp

构型空间（joint space）插值 §

搜索算法 §

• 参考：https://web.ics.purdue.edu/~rvoyles/Classes/ROSprogramming/Lectures/PathPlanning.pdf

Bug Algorithms §

Brushfire Algorithm §

Wavefront Planning §

• 算法步骤
  • 选择4连接或8连接
  • 初始化时将所有未搜索的格子置为0，障碍物的值可以设置为-1，终点设置为1 （或障碍物设置为1，终点设置为2）
  • 从终点出发开始搜索，搜索到的相邻格子+1，重复这一步骤
  • 停止条件：搜索直至抵达起点或者无法搜索到更多相邻的格子
  • 搜索结束后从终点开始，连接具有最小值的相邻格子直至达到起点。
• 路径规划必须从终点开始向起点规划，否则无法随梯度变化得到正确的方向。理论上Wavefront从终点或从起点出发均可，但是从终点出发能减少重新规划的可能。
• 本质是针对网格的广度优先搜索
• 缺陷
  • Not guaranteed to find a solution (depends on grid size)
  • Not optimal in terms of Euclidian distance (except for special cases)
  • Not incremental – must re-run the whole thing if the environment or goal change
  • Small grid size helps to find more optimal solutions, but leads to high memory and run time costs.

Visibility/Voronoi Graphs §

Quad-Trees §

Sampling-based Planning Algorithms，在关节空间c-space搜索（PRM，RRT等） §

势场法Potential field §

RPM - Probabilistic Roadmap §

RRT - Rapidly-exploring Random Tree §

Optimization-based algorithms（CHOMP，STOMP） §

RNN §

• 多用于冗余自由度机械臂的运动规划，将问题转化为QP后使用RNN进行求解，参考相关文献收集：冗余自由度机械臂的运动规划

运动规划求解器 §

轨迹规划 §