Robotic motion planning [lecture 1]

Key words:

  1. Basic assumptions about the robot.
  2. Configuration Space
  3. Degrade of Freedom, DoF
  4. Representation of the angle in 3d space
  5. Coalition detection

Part 1: Basic assumptions about the robot

机器人的种类多种多样,可以是机械手,可以是汽车,可以是无人机。但在路径规划中我们可以对它进行简化:首先我们认为这些都是刚体,(1) 对于汽车、无人机这样不会与自身发生干涉的,我们假设他为单刚体,这样我们在路径规划中就可以将它视为一个点,(2) 对于机械臂这种有多关节的,我们将它视为多个刚体的集合。在本节课里面大多数的时候讲的都是单刚体的内容。

Part 2: Configuration Space

如果不对他们进行简化,在实际的工作空间 (Workspace) 中规划一个无碰撞的路径,我们需要考虑非常多的限制,这样的计算要求是天量的。因此我们要将其投影到我们构造的 Configuration space 中,将机器人化为 Configuration space 中的一点(这也是为什么之前我们要将它假设为刚体)。与此同时我们可以在 configuration space 中将现实问题中的障碍物也投影进来,这样一个在现实中复杂的问题就变成了一个点在 Configuration space 中绕过障碍区域到达另一个点的画线问题。下图左边是真实世界中的机械臂和障碍物,右侧是其在configuration space 中的投影。

Part 3: Degrade of Freedom, DoF

Configuration space 需要自行构造,因此先要了解的是如何选择合适的参数,这个过程称之为 Parameterization。我们要选取最少的参数来描述机械臂的运动,而这个最小值也就是机械臂的自由度。在2D空间中这个值基础是3 (\mathbb{R}^2 \times S^1),对于3D空间这个值基础是6 (\mathbb{R}^3 \times SO(3))。

对于一个两侧被固定的 Close chains 系统, 自由度(Degree of Freedom, DoF)

DoF = N(k-1)- \sum_{i=1}^n(N-f_i) = N(k-n-1)+ \sum_{i=1}^nf_i

是基础自由度(3 in 2D, 6 in 3D),k是活动杆数,n是关节数 。f_i是某关节的自由度。

Part 4: Representation of the angle in 3d space

对于一个基础的没有受限制的3D空间物体,它的六个自由度分别是三个平移量和三个旋转角。在线性代数里面我们用下面的式子描述其运动

p_2 = R \cdot p_1 + T,\ where\ R\in \mathbb{R}^{3 \times 3}, T \in \mathbb{R}^3

将旋转矩阵转换为三个角度才能用来参数化,因此我们需要使用欧拉角,在二维空间中的欧拉角运算大

\begin{bmatrix}
cos(\alpha) & sin(\alpha) \\
-sin(\alpha) & cos(\alpha)
\end{bmatrix}

拓展这个式子可以推出三维空间中三个角度(\alpha,\beta,\gamma),由于较为复杂就不列了,直接查表即可。在几何中这三个角的意义分别是:\alpha是转换前的x坐标轴与N(x-y 与 X-Y的相交线)的夹角,\beta是z与Z轴的夹角,\gamma是转换后的X坐标轴与N的夹角。由于在转化回角度的过程使用的 \arctan ,因此欧拉角描述空间时会在某些地方没有定义(\beta=0时)。

代替的描述方式可以有四元数(Quaternion),入手的方式时找到这个旋转的向量 n=[n_x,n_y,n_z]^T以及沿着这个向量旋转的角度\theta。也许有人会问:这样的一个旋转向量一定存在么?答案是肯定的,因为旋转矩阵R属于SO(3),因此它的任何乘积都属于 SO(3),这使得任何旋转的叠加出来的依然都是旋转矩阵,也就必定存在一个可以描述这个旋转状态的向量。

\theta\textbf{n}描述的四元数如下:

u=[u_1,u_2,u_3,u_4]=[\cos{\theta/2},n_x\sin{\theta/2},n_y\sin{\theta/2},n_z\sin{\theta/2}]

四元数可以克服欧拉角的奇点问题

以上两种方式给我们了建立 configuration space的基础,但实际的建立过程还是很复杂。

Part 5: Coalition detection

在机器人的路径规划中,为了找到一个无碰撞的路径,通常我们需要将整个路径分解成一段段小的子路径,然后在每小段中检查机器人的任何一点是否与障碍物碰撞。由于需要大量的计算,我们可以通过给机器人套壳(hull)的方式来加速这个检查过程。

我们可以设计一个圆形的壳,这样每次只需要检查障碍物与圆心的距离是否小于半径即可,检查的次数就是一次;如果我们设置一个矩形的壳,那么每次就需要检查矩形的四条边是否比障碍物更近,那么检查次数就是四次。复杂的壳让你可以有更多的空间,但同时也增加了计算量。

Leave a Reply