Key words:
- Basic assumptions about the robot.
- Configuration Space
- Degrade of Freedom, DoF
- Representation of the angle in 3d space
- 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)的方式来加速这个检查过程。
我们可以设计一个圆形的壳，这样每次只需要检查障碍物与圆心的距离是否小于半径即可，检查的次数就是一次；如果我们设置一个矩形的壳，那么每次就需要检查矩形的四条边是否比障碍物更近，那么检查次数就是四次。复杂的壳让你可以有更多的空间，但同时也增加了计算量。